After the recently concluded January Long Challenge, I would like to invite you for some more interesting challenges to keep your coding schedule always packed!
Participate in the January Cook-Off 2018 and enjoy Chef’s tricky tests. Joining me on the panel are:
Problem Setter and Editorialist: sidhant (Sidhant Bansal), arjunarul (Arjun Arul)
Problem Tester and Admin: kingofnumbers (Hasan Jaddouh), mgch (Misha Chorniy)
Russian Translator: CherryTree (Sergey Kulik)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team
I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.
Contest Details:
Time: 21st January 2018 (2130 hrs — 0000 hrs Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/COOK90
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes:
- Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])
According to me, the problems are very interesting and I am sure that you will have fun while solving these problems :)
Good Luck! Hope to see you participating!!
PS — In this cook off, we have changed the penalty from 20 minutes to 10 minutes. Enjoy!!
Gentle Reminder: Contest starts under 5 minutes !!
I just loved your problems! Hope you set more contests in the future! :D
How to solve far graphs when there are odd cycles. Also will the vertices always get -L/2,0,L/2 even in odd cycled graphs ??
There is at most one cycle of length 3. After removing them and all edges which have an end point in that cycle, the resulting graph is bipartite. (Assume answer is "Yes")
Disclaimer : I have coded this up but could not get accepted. Submission
How to solve MAGA?
Simple dp, with extreme amount of case handling. Consider cases where the size of the array is even/ odd, the current index in dp you are at is even/odd and wether you performed swap in the previous step or not.
States will be dp[last][idx], last indicating wether swap was performed for last index, and idx needs to move only until mid of the array.
Yeah same here. My code exceeded 200 lines. I was wondering how people solved so fast.
You just need to write a neat code :) Here's mine:
I did something similar. got WA . I don't know why. Here's my code
For Problem B, "Multiple of 3", can it be solved using CRT?
It is possible to solve because gcd(10,3)=1.
I calculated 2 values, one for mod 10(a1) and other for mod 3(a2), eqn was n=(d0+d1)+(d0+d1)*(2^(k-2)-1).
Combined them using this eqn from wikipedia, n3=a1m2n2+a2m1n1 where n1=10, n2=3 and m1=1,m2=-3 which is derived from extended euclid gcd.
Now I just checked n3%3 and printed, but this gave a WA. Can someone please help me(show me de way)?
You can calculate n3 mod 30 then check (n3 mod 30) mod 3 == 0
I tried it but getting WA. Link
Sorry, this idea is wrong. the correct one is notice that digit[i] = digit[i-4] for all i except first few ones.
Can you please tell me why this idea won't work?
because ( digit[0] % 10 + digit[1] % 10 + digit[2] % 10 ... ) % 3 is not equal to ( (digit[0] + digit[1] + digit[2] ...) % 10 ) % 3
Okay! Got it, thanks!
We can go further than this. I noticed that the repeating digits are always on the lines "2,4,8 6". The only corner case is when d0+d1=5, for which only 0 is appended always.
first calculate (d0+d1)%10 and then divide into group of 4s . the pattern will repeat like ; 2,4,8,6 and lastly add those. for ex. d3 = 2*(d0+d1)%10 , d4 = 4*(d0+d1)%10 , d5 = 8*(d0+d1)%10, d6 = 6*(d0+d1)%10 , like this the pattern will repeat for K/4 groups , you have to add the remaining . here is the code:
Thanks sir, I implemented this during contest but pretty late because my first approach gave a WA.
Hints for MAGA?
It's a straightforward DP problem :D DP1[i]=min swaps if not swapping [i, n-i+1] in interval [i, n-i+1] DP2[i]=min swaps if swapping [i, n-i+1] in interval [i, n-i+1] You can be a little clever and just count the numbers if a1>a2<a3... and then multiply every number by -1 and do it one more time :)
Can you elaborate a bit more on the dp states?
okk got it just to check for the other case ??
Yeah :D It doesn't make sense to code the same thing again :D
How to solve FINDA?
Editorial for MAGA has still not been released.