Unofficial Editorials January Cook Off

cook90
editorial
multhree
survive

#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} = { extstyle \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:


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


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

Link to my solution.


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


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


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