# Unofficial Editorials January Cook Off

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

### 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} = { extstyle \sum^{j-1}{0}} D{j} (mod 10)

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

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

#2

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

#3

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!

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

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

#7

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

Dp*[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*[j][0]=min(dp[i-1][j+k][0],dp[i-1][j+k][1])

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

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

Really good solution @taran_1407.

#8

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

#9

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
long long k;
int x,y,p=0;
int b[]={2,4,8,6};
int c[4];
cin>>k>>x>>y;
int z=2*(x+y);
int s=z%10;
if(k>2){
if(s==0){cout<<"NO


“;}
else{
int a=(((k-3)/4)%3)2;
//cout<<“a=”<<a;
for(int i=0;i<4;i++){c
=b*;}
int r=1;
while(s!=c[0]){
for(int j=0;j<4;j++){
c[(j+r)%4]=b[j];
}
r++;
//for(int i=0;i<4;i++){cout<<c*<<” “;} cout<<”
";
}
for(int i=1;i<=(k-3)%4;i++){
p=p+c[i-1];
}
//cout<<“p=”<<p;
z=z+a+p;
//cout<<“z=”<<z;
if(z%3==0){cout<<"YES
";}
else{cout<<"NO
";}
}
}
else{
if((x+y)%3==0){cout<<"YES
";}
else{cout<<"NO
";}
}
}
return 0;
}
what’s wrong in my code to show a WA??

#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*[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*[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* and a[N-(i-1)+1],a[N-i+1]) if they dont accordingly set val1 Or val2 to inf.

Similarly,
Dp*[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)

#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):
counter=0
for i in range(s):
counter+=1
counter%=7
if(counter!=0):
maans+=1
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.

#12

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


#include
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;
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.

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