# Unofficial Editorials January Cook Off

Hello Guys, The editorials for January Cook of are cooked (first two only).

### Problem: SURVIVE

#### Problem Statement:

Given a shop opening from Monday to Saturday, you are allowed to buy N sweets everyday the shop is open and you eat K sweets everyday, determine if you can survive for next S days.

#### Solution:

The constraints of problem are small enough to check for everyday.

For every ith day (1<=i<=S) not being divisible by 7, buy N sweets. Eat K sweets everyday. If at any day you have less than K sweets to eat, answer is impossible.

If you survive S days, and supposing C is the number of remaining sweets and A being number of days you bought sweets, just subtract C/N from A. (The number of sweet boxes untouched).

### Problem: MULTHREE

#### Problem Statement:

Given K, d0 (first digit) and d1 (second digit), we care to check that K-digit number is divisible by 3. if K> 2, Remaining digits of our Number are given by:

D_{i} = {\textstyle \sum^{j-1}{0}} D{j} (mod 10)

#### Solution:

First thing to note is that if sum of digits of a number is divisible by 3, number if divisible by 3.

Another thing, (I would recommend running a brute force for all possible values of d0 and d1 to observe this pattern, do give a try before reading).

After first three digits, only the pattern â€ś2486â€ť repeats till end of the number. This means that we can split our number into 4 parts.

1. First 3 digits, manually take sum.
2. Next 0 to 3 digits (pattern may start at 4, 8 or 6, Taking care of that).
3. â€ś2486â€ť X number of times. ** Add X*20 to sum**.
4. Last 0 to 3 digits (pattern may end at 2, 4 or 8).

Finding X: Check for start point of pattern (will be from p = 3 to 6 in 0-based indexing), X = floor((K-p)/4).

Edge case: If fourth digit is 0, we take sum of first three digits and check its divisibility by 3.

PS: I have intentionally kept the length of editorials short. If you donâ€™t get it, feel free to post a comment.

11 Likes

Same kind of observation for 2nd question. Instead of 2486, I took 8624. Link to solution :
Solution .

Doesnâ€™t change the solution though!!

Yupp.The solution remains same.

https://www.codechef.com/viewsolution/17115932

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.

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

For the problem code SURVIVE 8 out of 10 randomly selected accepted ACâ€™s gave an output of 9 while the correct output should be -1:

1
9 8 10


yet again,shows negligence in making the testcases!

11 Likes

Lovely editorial for 2nd problem. Even I followed the same idea- the solution was easy (had I just been more careful and not done silly errors).

While implementing p2 tho, I did quite LOTS of silly errors-

1. Not updating K while calculating third digit. (i.e. After we check for first 2 digits, we should do K-2 as 2 digits are attached to the K digit num- I missed that).

2. In data type. At some point I used int (I think for sum)- should had avoided that since K is out of its range, so generated sum will also be.

3. Be careful of any case when sum of digits becomes 5 ,which can lead to situation where 0 is appended. Got TLE cause of this T_T.

When will the editorial for 3rd problem be there @taran_1407? That was some hell of casing (if-else, case checks etc.)

1 Like

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

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.

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

http://codeforces.com/blog/entry/57259?#comment-409134

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.

2 Likes

Very much liked it @vijjju123 !! Just loving itâ€¦

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

For the first problem, I used binary search on answer and for k no of days, we can use initial k days for buying one box of chocolates.

1 Like

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

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

1 Like

thanks alot @taran_1407

1 Like

Here is the worst solution for 1st sum which i did.

Dp[i][j][k] denotes the minimum number of boxes taken upto ith day such that u have a balance of j,and k denotes if on that day a box is taken.

Dp[i][j][0]=min(dp[i-1][j+k][0],dp[i-1][j+k][1])

Dp[i][j][1]=min(dp[i-1][j-(n-k)][0],dp[i-1][j-(n-k)][1]) + 1

Dp[i][j][1]=inf for i%7==0

Really good solution @taran_1407.

3 Likes

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