SURVIVE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sidhant Bansal
Testers: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY:

easy

PREREQUISITES:

basic math

PROBLEM:

In this problem, the greedy approach of buying the box of chocolate for some consecutive early days is the right direction.

Let A = K * S and B = N * (S - S/7), here A denotes the total number of chocolates we need to eat and B denotes the maximum no. of chocolates we can buy. Here S - S/7 denotes the number of days the shop is open.

So if A > B or ((N - K) * 6 < K and S \geq 7), then the answer is -1.
otherwise the answer is ceil(\frac{A}{N}), where ceil(x) denotes ceiling function on x.

The first condition i.e A > B, for -1 is fairly obvious that if the total no. of chocolates we need to eat is more than we can buy at max then it is invalid.

The second condition i.e (N - K) * 6 < K and S \geq 7 is a bit tricky, it is basically the contrapositive of the statement, “if you can survive the first 7 days, then you can survive any given number of days”. So the contrapositive (i.e same statement in different words) is "if you cannot survive the first 7 days then you won’t be able to survive for S \geq 7". The condition for being able to survive on the 7^{th} day is basically if we add our remaining chocolates from the first 6 days, i.e (N - K) * 6 and it is still smaller than K, i.e the chocolates we need for the 7^{th} day, then we don’t survive. But we only need to test this when S \geq 7.

Incase, we are able to survive, then the answer is ceil(\frac{A}{N}), which is basically total number of chocolates we need to eat divided by the number of chocolates we can buy in a single day (and if a remainder exists, then we need to buy one more day). This portion is pretty straightforward.

The above reasoning to check for -1 is obviously tricky and a simpler approach exists which is to just simulate the days once we know the value of ceil(\frac{A}{N}).

SOLUTIONS

Setter’s solution.
Tester’s solution.

1 Like

@admin Weak test cases for this question:
1
9 8 10

Submissions giving wrong answer
S1
S2

I request you to add this test case in practice question. Please make sure such things not happen in future as it brings down the moral of participants.

5 Likes

For the first condition we could just use N < K (we must buy at least a day supply of chocolate on the first day), and the second condition can be written as 6N < 7K (we must buy at least a week supply of chocolate during the first week).

Solution.

@admin
The test cases are very week

1

8 7 8.

The output should be -1. But many accepted solutions of this problem are producing output 7 for this case which is quite obvious wrong. Please make sure such kind of things not occur in future and the test cases for questions in the contest should have appropriate corner cases.

1 Like

Problem: SURVIVE

My short solution in PYTHON-3.5:My solution in O(n) easy to understand. O(1) is more efficient

te=int(input())
for _ in range(te):
     n,k,s=input().split()
     n,k,s=int(n),int(k),int(s)
     capacity=k*s
     availablity=n*s
     availablity-=n*(s//7)
     maans=0
     if(capacity<=availablity):
          answer=0
          counter=0
          for i in range(s):
             counter+=1
             counter%=7
             if(counter!=0):
                maans+=1
                answer+=n
             if(answer>=capacity):
                break
          print(maans)
     else:
          print("-1")

LOGIC:-
Maxmimum choclates he needs is ks which is capacity. And the availablity of chocolates is ns-(n(s//7)) as on Sunday shop is closed and he can’t buy any chocolates. So if capacity > availablity print("-1") as it is not possible to purchase. Else Run a loop to find the number of days and dont forget not to calculate sundays and add n chocolates only on non sundays.

Like,Comment, Follow and award reputation points if u like. For any other queries or doubts contact me.

For Codes as files to download visit:- DOWNLOAD CODE

I am guilty of this

Please add this at least to practice test cases

Another Weak Testcase

1 
8 7 8

for t in xrange(int(raw_input())):
n,k,s=map(int,raw_input().split())
b=1
F=True

d=[]
for i in xrange(1,(s/7)+2):
	d.append((7*i)-1)

for i in xrange(1,s+1):
	if k>n:
		F=False
		break
	elif i in d and (n*b)-(k*i)<k and s!=i:
		F=False
		break
	elif (n*b)-(k*i)==0 and s==i:
		pass
	elif (n*b)-(k*i)<k and (n*b)-(k*i)!=0 and i!=1:
		b+=1
if F==True:
	print b
elif F==False:
	print -1

What seems wrong with my code?

#include
using namespace std;

int main() {

int t;
cin>>t;
while(t--)
{
       int n,k,s,tot,box=1,flag=0,set=0;
       cin>>n>>k>>s;
       tot=n;
       for(int i=1;i<=s;i++)
       {
            //  cout<<"before tot="<<tot<<" day="<<i<<" set="<<set<<endl;
              
               if(tot>=k)
              {tot=tot-k;
              set=0;
              }
              else if(i%7!=0)
              {      
                    
                     tot=tot+n-k;
                     box++;
                    if(i%7==6)
                    set=1;
                     
              }
              else if(i%7==0&&set==0)
              {i--;
              tot=tot+n;
                     box++;
                     
              }
              else
              { flag=1;
                     cout<<"-1"<<endl;
              }
              
       }
       if(flag==0)
       cout<<box<<endl;
       
}


return 0;

}


t = int(input())
while t:
    cnt=0
    n,k,s = (int(n) for n in input().split())
    chocs=n
    days=1
    while chocs>=0:
        if cnt==s:
            print(days)
            break
        cnt+=1
        if chocs<k and cnt%7!=0:
            days+=1
            chocs+=n
        chocs-=k
    else:
        print(-1)
    t-=1


my code gives correct answer for the weak cases mentioned but is not being accepted can anyone help what should i modify or where am i incorrect
ps: it is in python 3

1

30 6 30

check this one correct answer should be -1 but many accepted solutions are showing it to be 6.please anyone help!!

1

30 6 30

check this one correct answer should be -1 but many accepted solutions are showing it to be 6.please anyone help!!

30 6 30 is not coming -1,
it should be 6 itself