Unofficial Editorials January Cook Off

editorial
, , ,
1

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.

Difficulty:Cakewalk

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).

Link to Solution here.

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:
\begin{equation}
D_{i} = {\textstyle \sum^{j-1}{0}} D{j} (mod 10)
\end{equation}

Difficulty: Easy

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.

Link to Solution here.

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

11 Likes
2

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

3

Please help me in finding the error in the first question
https://www.codechef.com/viewsolution/17115932

4

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
5

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
6

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.

Link to my solution.

1 Like
7

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
8

May I know where the announcement thread is located @vijju123 ?

10

I think the 3rd problem can be solved using dp.

We’ll take the two cases(a1a3… and a1>a2<a3…) separately.

Let dp[i][j] denotes the minimum swap needed to make array great for indices 1 to i and N-i+1 to N with j denoting if this element is swapped or not.

We start from left and move to center.

We have following recurrence:
Val1=dp[i-1][0],val2=dp[i-1][1]
dp[i][0]=min(val1,val2) here first u should check if these satisfy the relations(i mean lets say if i-1 is not swapped then check a[i-1],a[i] and a[N-(i-1)+1],a[N-i+1]) if they dont accordingly set val1 Or val2 to inf.

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

My ac solution(though implemented now and not in contest):

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

Edit:This solution should fail since i didnt consider the case for -1 when n>=4 and n is even and middle 2 elements are same

(Lucky)

2 Likes
11

My both Solutions got AC in one go.

Problem: SURVIVE

My short solution in PYTHON-3.5:Mine is O(n) could be done in O(1) also.

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.*

Problem: MULTHREE

My Short solution in PYTHON 3.5:-Time Complexity O(1)

test=int(input())
for y in range(test):
     k,dig0,dig1=input().split()
     k,dig0,dig1=int(k),int(dig0),int(dig1)
     sum1=dig0+dig1
     for i in range(3,k+2):
          y=sum1%10
          sum1+=y
          if(y==2):
            ter1=((k-i)//4)
            ter1*=20
            sum1+=ter1
            ter=k-i
            if(ter%4==3):
               sum1+=18
            elif(ter%4==2):
               sum1+=12
            elif(ter%4==1):
               sum1+=4
            break
          if(y==0):
            break
    if(sum1%3==0):
      print("YES")
    else:
      print("NO")

LOGIC:-

For a number to be divisible by Three sum should be divisisble by 3.Keep on adding sum and finding digits(sum%10); if digit is 0 then break as sum will remain same even after u do any operation so break.
Else break when u find a two as 2,4,8,6 block will keep on repeating. therefore add ((k-i)//4)(2+4+6+8)
to sum ((k-i)//4) is floor division plus remaining 4 12 or 18 depending on whether 4 or 4,8 or 4,8,6 is remaining. This block’s size is got by (k-i)%4.Then at last check whether sum is divisible by 3.

Essentially almost same as solution of @taran_1407

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:-
THIS PAGE

3 Likes
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!!