SRM 534: Notes that contradict the problem statement

I had class till 9:00 (TC time), so I wouldn't be able to start the match till 9:35.

I opened the medium problem, I think I could have used those extra 30 minutes to solve it. I got to the point I can get a list of all the relevant divisors of n quite quickly. (Relevant divisors would be those that can be made after multiplying the special integers together). After that though there are some doubts. According to the internet, the bound on the number of divisors is math.exp( math.log(10**18) / math.log( math.log(10**18) ) ) = 68075. There are probably a lot of things to consider. And the relevant divisors might as well be much less. But the last test case already has 4000+.

The div1 250 was lame. And I mean it, lame. It is becoming quite common to do bitmask dp problems in div1 250 that can also be solved quickly by guessing a solution that is not easy to prove. I guess the point is to give time advantage to people who don't prove solutions before submitting. I decided to play safe and just do bitmask dp. (By the time I opened 250 I already knew there were a lot of solutions for 500, and that I didn't have time to think of something for it, I also knew that I needed a fast submission in order to save the match.) So I coded the bitmask dp. I am confident at bitmask dp, I got a 238 score, which would of have been really fine.

Unfortunately, the problem included a very stupid corner case. The problem statement says that checkers that reach the right most cell are removed. keyword is "reach". As I was coding my heavy dp solution and busy doing bit operations I coded explicitly the story in the problem statement. So I made checkers go away whenever they reach the last cell. A checker that is initially in the right most cell does not really "reach" it. It turns out a note saying the opposite was hidden in the notes section. But I don't usually expect notes to contradict the statement. It would have been much, much better problem design to make the constraints unable to have a checker initially in the right most cell. A good compromise would be to include "oo" in the examples. Or if Fake difficulty is really such a priority, at least make the statement say explicitly that checker on the rightmost cell are removed before any turn, instead of unnecessarily adding ambiguities by using the word 'reach'.

Update: Contradict is a heavy word. But notes should be there to clarify ambiguity. Not to add new things to the statement. The idea of (You must remove the checker on top of the rightmost cell at the beginning of the game) is a complete new step to do. There's also the fact of how this corner case was not necessary at all - Instead of asking coders to always ignore part of the input, just make it so that part of the input is impossible to happen.

I figured this out just as intermission started, so I couldn't fix it. My only hope was challenges, and maybe other people made the same mistake in my room. Seems not. I initially thought someone in my room made the mistake, it turns out that I am just blind as usual. It is always better not to challenge.

Anyway, the -25 is likely to cause me to lose all rating gained in the last three months. The unsuccessful challenge is entirely my fault. But the 0.00 score in the 250, I will blame 80% on the urge to add useless corner cases to problems. 10% is my responsibility for not reading notes, I was actually in such a rush that I didn't notice the problem had notes, and 10% because I knew that the problem likely had an easy to do reduction that didn't need bitmasks, and it turns out it did. But I preferred to play safe and do bitmasks.


Explanation: Div1 250: The one with the checkers and the board

You have a row of cells. Some cells contain one checker. Two players play the following game: In each turn, you can move a checker one step to the right, if that cell is empty. OR, if there are two checkers in the two cells next to it, you can also make the checker jump three spaces to an empty cell. If at any point of the game (including the start) there is a checker in the last position of the board, it will get removed.


Yes, sure, you can do bitmask dp. But there is also an easy solution that involves this:

- For each checker that is not in the right-most cell, get the distance between this checker and that cell. If the sum of these distances is even, the first player loses. Else she wins.

The trick to this finding and proving this solution is to notice that moving a cell from its position i to position i+1, or to position i+3 (a jump) will do exactly the same thing to the parity of the sum of the distances - It will toggle the parity. Thus no matter what move you do in a turn, the parity of the sum of distances will always change.

The obvious losing position (An empty board) has a the sum of distances equal to 0, which is even. Consider all positions in which the sum of distances is 1. You can always make at least one move that reduces this sum to 0, and causes next player to be in a losing position. When the sum is 2, you can only reduce by 1, and take the next player to a winning position. When the sum is 3, you can only reduce by 1 and maybe by 3 by jumping something (This is only the case for higher sum values, but as you'll see this does not matter) - Whatever you do, the parity of the new sum will be even, and thus 3 is also a winning position.

From there, you can conclude that all cases in which the sum of distances is odd are winning positions. Else all cases in which the sum of the distances is even is a losing position.