Morphy's blog

CodeChef January Cook-Off 2019
By Morphy, 6 years ago, In English

CodeChef January Cook-Off starts in ~72h (Sunday, 20th January, 2019 at 21:30 IST). As ussual you will have 5 puzzles to solve in 150 minutes.

The character of the contest is Ada — the most intuitive girl I have ever met.

I challenge top coders to get full score in topcoder time.

By the way, the contest clash with the north regional junior chess championship of my country, so to me seems like a notorious coincidence.

good fun and have luck!

Contest log:

  • -24:00:00. Pran found a corner case on ADAROKS that I didn't contemplate, We fixed our solutions ad added more data.
  • 00:05:45. 28 acs for ADASCOOL in div1 and 14 in div2, Atreus is leading in div1.
  • 00:15:00. Div2 users found the cakewalk problem, stefdasca is leading in div2. In div1 LHiC solved ADAMTR, his solution is similar to tester, I used 2-SAT as a blackbox.
  • 00:40:00. Internal Server Error :( now we know they upgraded their nginx to 1.4.7.
  • 00:43:00. CodeChef is up again, moreover Saiphani724 solved ADAMTR and is leading in div2. Pran predicts 4 perfect scores in div1, I predict 10.
  • 01:00:00. KrK solved ADAPWNS, now he is first and LHiC is second.
  • 01:12:00. LHiC aced ADAFUN, but he is still second because he didn't solved ADAPWNS, the problem is a trie dp, so its kind of standard.
  • 01:20:00. I noticed that my countrymate The_Blitz is participating in div2. It seems that having a chess handle is not helping him in the contest.
  • 01:32:00. uwi only solved 2 problems, did he gave up the contest after the server down?
  • 01:40:00. yashChandnani solved ADAFUN, now he is first!
  • 01:44:00. RAVEman solved ADAROKS, the top of the scoreboard in div1 is changing a lot!
  • 01:54:00. KrK solved ADAFUN and took the lead again, however I think RAVEman will winn, because he already solved ADAROKS which is harder.
  • 02:10:00. uwi is still on board it seems he had a hard time with ADAROKS, his solution fails on a case added by the tester (uwi, complain with pran), also I noticed that the educational hero awoo is taking part in the contest, he managed to solve ADAPWNS, and is in the top 20.
  • 02:21:00. I bet RAVEman will winn, Pran bets on LHiC.
  • 02:30:00. No participant got perfect score. Congrats to the winners!

Div 1:

KrK

LHiC

RAVEman

Div 2:

Saiphani724

andrew_ucla

stefdasca

I'll add some hints for solutions in my blog: https://aleigorithms.wordpress.com/2019/01/17/codechef-january-cook-off-2019/

  • Vote: I like it
  • +135
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bengali translations? woah.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Is there any proof for the solution of ADASCHOOL?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Hint: if you go to the right to return you have to go to the left.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Consider it as a chessboard. We can move student on white cell to black cell and vice versa.

    If M and N, both are odd, we'll have unequal number of white and black cells. So the answer is "No".

    If any of them is even, say N is even, we can swap rows 1 and 2, then swap rows 3 and 4 and so on. Same for even M.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

If ever there will be elections for the "most unbalanced contest ever".

COOK102B would surely win

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve ADAPWNS ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Instead of looking at pawns let's look at blocks of dots. For exmaple ,,,P..P...P.PP..P transforms to (3,2,3,1,0,2) blocks of dots. Now you can either

    1) move 1 or 2 dots from i-th block to (i+1)-th block

    2) remove 1 or 2 dots from the last block.

    Now the key observation is the following:

    1) The game described in the task with (a_1,a_2,...,a_n) blocks of dots is equivalent to another game

    2) We have indpendent sets of dots (a_n,a_(n-2),a_(n-4),...,a_(n%2)). And the move is to remove 1 or 2 dots from chosen set. If you can not move you lose.

    Now calculating the nimber of the second game is easy by standard SG and the result is (a_n%3)^(a_(n-2)%3)^...^(a_(n%2)%3).

    Why the 1st game is equivalent to the second game? The intuition is that whenever a player make a move from (k-th) block to (k+1)th block where k % 2 != n % 2 then the other player can move the same amount of dots from (k+1)-th to (k+2)-th. So the number of dots in every other block doesn't matter and only moves from piles such that k % 2 = n % 2 matters.

    You can be more formal, but that is the idea.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Internal Server Down !! In the middle of the contest :(

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I wasted much time on infering a law of ADAPWNS and thinking about ADAROKS. I solved ADAFUN a short time after the contest.

Problems seems harder this time, but good.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I was afraid that problems were too easy, now I'm glad top coders found the puzzles challenging :)

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I think once you know Silver Dollar Nim, adapawns will be easy. I estimate atleast half those who solved to know it. Sad that my memory is weak.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yes, I know. But the law is different a bit.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I spent most of my time during the contest trying to understand ADAFUN, but I still do not get how to calculate W(S) if |S| >=3. By this I mean that I read and reread the question but I still do not get what to do. The test case did not help that much since it was not really explained. So I would really appreciate any help with it.

Ps: I saw the hints, I checked them. However, I do not get the question, and there was no explanation, so I did not help.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    What specifically did you not understand? The definition requires some knowledge of mathematical formulations, maybe that's the problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      The statement is clear, but he has a point, maybe we should have added explanation so that the problem would be accessible to anyone regardless their math background.

      e.g:

      note that 5%4 = 9%4

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the answer. You know, my confusion was not exactly related with my math background. I am not sure maybe it was due to english or me being kind of tired and sleepy, anyway I was confused with just this part. "the highest power for which such a pair exists" I was not really that sure how to understand that part. For example In the case W{5,9} I was thinking about 16,4 or even 8 instead of just 4. But looking at it now it was really simple. It is just logical and both numbers and take the most significant bit. I do not know it was just me I guess.

        Anyway thanks for your answer, it really helped.

        → Reply
»
6 years ago, # |
← Rev. 13   Vote: I like it 0 Vote: I do not like it

why is my code for ADAMATR giving wa ? link to code — https://www.codechef.com/viewsolution/22575614

my approach —

notations — cc[i] is 1 if number of i swaps needed is odd else cc[i] is 0 dp[i][j] is 1 if total swaps required are odd else 0

so there are three cases possible for any pair i,j 1. if a[i][j]==b[i][j] and a[j][i]==b[j][i] so even swaps needed dp[i][j]=0 2. else if a[i][j]==b[j][i] and a[j][i]==b[i][j] so odd swaps needed dp[i][j]=1 3. else solution is not possible

now i calculate the value of cc[i] for all i by fixing cc[0]=0 and then i check whether these values are satisfying dp[i][j] similarly i fix cc[0]=1 and solve;

if dp is satisfied for all i,j in any of the two cases then there exists a solution.

→ Reply