Unofficial Editorials January Cook Off

editorial
, , ,
12

The first problem can be solved in O(1) time complexity per test case,
here is my code in cpp


#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while(t--){
        int n,k,s;
        cin>>n>>k>>s;
        int sundays = s/7;
        int TOTAL = k*s;
        int buy = n*(s-sundays);
        if(buy < TOTAL){
            cout << "-1" << endl;
        }else{
            cout << ceil(float(TOTAL)/n) << endl;
        }
    }
    return 0;
}

The logic: If total number of chocolates needed for S days is MORE that the number of chocolates possible to buy in that (S-number of Sundays) days then it isn’t possible to survive, else it is just ceil(float(TOTAL Needed chocolates)/(maximum number of chocolates possible to buy per day i.e. N )) … ceil() function is used as integer division will exclude some days at the end. i.e. a box of chocolates should be bought at the day number of chocolates left is less than K.

1 Like
13

When will the editorial for problem MAGA be up ?

14

Do they plan to release the official editorial for the MAGA problem? -_-

15

I followed a bit general approach for the second problem as I didn’t have enough time to actually think of all the edge cases. So I saw in the test cases that after the 3rd element there is a pattern. So I stored that pattern in a vector and checked how many times it will get repeated in the final number.

And then I just added first three numbers+(sum of vector)*(number of times it is repeated in the final number) + remaining numbers.If this sum is divisible by 3, then the answer is YES otherwise,NO.

Here is the solution
Solution

16

Doesn’t change the solution though!!

17

Yupp.The solution remains same.

18

Buy everyday, because if you don’t buy everyday, it may cause problem on coming Sunday. Take care to exclude X boxed later only if you can survive.

Second thing, why diff is initialized to N?? It should be 0.

19

for e.g if i take the test case 13 10 8
then on the first coming sunday the chocolates we would be having are less than k. So the answer should be -1. But the correct answer is 7. What am i missing? coz for this test case my code is giving output as -1

20

Please post it at the announcement thread- which is the official thread for feedback. It will be seen by problem setting panel there.

21

I wasted two hours on third problem messing with if else blocks. and yes, if i manage to solve it soon (by tomorrow i mean) i will write editorial.

Glad you liked it!!

22

Same here buddy. My entire time whooshed away in those if else. BTW, check out this solution, you might like it-

23

Here’s the simulation of first 7 days for your TC. Set dif = 0, count = 0,

Day 1:
diff = diff+10-8 = 2, count = 1

Day 2:
diff = 2+10-8 = 4, count = 2

Day 3:
diff = 4+10-8 = 6, count = 3

Day 4: diff = 6+10-8 = 8, count = 4

Day 5: diff = 8-8 = 0, count = 4 Your mistake, as you didn’t buy this day and later on concluded insufficiency of sweets.

Day 5: diff= 8+10-8 = 10, count = 5

Day 6: diff = 10+10-8 = 12, count = 6

Day 7: diff = 12-8 = 4, count = 6.

Hope this makes clear.

And to all who read this comment, if stuck in a simulation, use print statements to do all this. :wink:

2 Likes
24

Very much liked it @vijjju123 !! Just loving it…

A 200-line solution shoved under the nose of an innocent boy. :stuck_out_tongue:

25

Though your solution is nice one, it have a worse Time complexity of O(Slog(7*S)) while above mentioned solution has time complexity of O(S).

You can improve your check function to work in O(1) by a simple change, and even shorter code.

2 Likes
26

I think binary search is an overkill here. But well, Binary search is <3 .

1 Like
27

thanks alot @taran_1407

1 Like
28

Initially I waited for few mins before coding and then I saw multiple WAs,so I thought O(S) might be missing some corner cases. I was sure about BS solution,so implemented it :stuck_out_tongue:

29

Lol, I was hunting for cakewalk problem in first few min my order was-

>Opened p4. ".....He asked to find the matrix? DEFINITELY NOT CAKEWALK"
>p5  has "graph" in it. Lol graph no cakewalk.
>Great array...hmmm. Might be. (2 min after reading the statement and thinking "Noo....please this be p4.....XD
>Multhree "YEAH This can be cakewalk!!" (Submitted a soln- got WA- "Hmm...Not cakewalk I guess lol")
>And finally chocoland lol.
1 Like
30 
#DP_Intensifies
31

Happened with me too.