Topcoder SRM 534; The one I didn’t participate in

UPDATE 3: Made change to the explanation of why the DP recurrence works.

UPDATE 2: Even though the DP recurrence for medium problem works flawlessly, I am now in doubt about the chain of reasonings I followed to prove it. If you can see the missing links, please comment. Until then, expect a 3rd update.

UPDATE 1 : Added a single dimension DP solution to medium problem.

Each month there is always one SRM whose timing just doesn’t suit me at all. The early morning SRM! And this SRM was one of those, a 7AM one for me. I either end up not performing well in such an SRM, or not participating at all. And this time it was the latter case. But I just tried it in practice room, and proves I would have done pretty well, as I was able to get both the easy and medium without much hassle. I didn’t bother with the hard problem yet.

DIV-2 Medium; EllysCheckers:

A dynamic programming problem. I think I am getting better at DP, as due to the bad experience with it in last SRM, I was able to get a correct recurrence for this one quite fast. Let dp[i][j] be our result for the subproblem given board from position i, to j. Our final answer will be dp[0][board.size()-1]. Base case is when board has only one cell, i.e. j-i == 0. In this case, the answer is straight away “NO”, because the first player can’t win. If there is a checker in the single cell, it will be removed at the start of the game, and if there isn’t, there isn’t anything to do. In both cases, the first player can’t move at all. Now for the recursive case, lets first go through some theory…

The game’s rules make sure that at the end of the game, board will be completely empty. We are allowed to move a checker one position to right, and the right most cell will always be empty. So we can always move the rightmost checker at least one more position to the right, until it is removed from the board. Also, a move by one position, or by three positions, are equivalent. In both cases, the same player moves the checker to the target cell. Say a checker exists at position i, the next player to move can either directly move it to position i+3, or he can move it to i+1, and when the other player moves it to i+2, the first player can take another turn and move it to i+3. So from this, we deduce that at the start of the game, we know exactly how many checkers will be moved by both the players to the last cell on the board. The player who can move the most checkers to the final cell, wins. Or if they can both move the same number of checkers to the last position, the player who goes second, wins. Now from this discussion, we deduce the following recursion:

dp[i][j] = dp[i][j-1], if count(i, j-1)==even

dp[i][j] = !dp[i][j-1], if count(i, j-1)==odd

Where count gives us the number of checkers that exist on the board between the given positions. Think about it, whenever we add one more cell to the board, the status of each checker changes. If it was previously moved by the first player to the last cell, now it will be moved by the second player because there is one more cell to go to the right. The same is the case for checkers that were being moved by the second player to the right most cell, will now be moved by the first player to the right most cell. So if there were even number of checkers that existed between position i and j-1, they will be equally divided between the two players as winning/losing checkers. And if the number is odd, one player will get more winning checkers then the other. In both cases, adding another cell to the board switches the number of winning/losing checkers for each player. In the first case, the switch won’t have any effect, as the total number is even and both players get the same winning/losing checkers. In the second case, the switch makes the loser a winner, and the winner a loser.

UPDATE 3: The ability of any player to win the game depends on the parity of the board. That is, the total number of steps that can be taken to make all the checkers reach the final cell. If the parity is odd, the first player wins, because he will make the final move. If the parity is even, the second player wins for the same reason. When we add another cell to the board, if the total number of checkers on the previous board was even, its parity won’t change, because an even number of extra steps are going to get added to it, and when we add even number to either an odd or even parity, the parity doesn’t change. In contrast, if the number of checkers was odd previously, the parity would change. Because we are adding an odd number to the total previous parity, and when we add an odd number to either an even or odd parity , it is switched.

UPDATE 1:
A bit of rethinking about the problem took me to a single dimension DP, instead of two dimensional. Check and see that each subproblem depends on all the board cells from position 0 upto the last position, and not on any of the intermediate ones. Thus we can skip calculating results for positions between first and last, and just calculate the result for subproblem from first cell till the last. The rest of the theory remains pretty much the same.

DIV-2 Easy; EllysDirectoryListing:

The problem is easy, with one tricky case. All you need to do is to iterate over the listing from position 0 to two places before the last position (because we do not need to check for “.” or “..” on the last two positions) and whenever you encounter a “.” or “..”, swap it with the last position. After the first swap, the second swap is to be performed with the last-1 position. There is one catch though, if on the first swap, the last position either has a “.” or “..”, you will swap it out to the current position under observation, in such a case, we do not want to move ahead, rather perform another swap over the current position with the last-1 position. With this check in place, we are ready to go.

Conclusion: 

I think I would have done well, may be a +60 to +70 gain in ratings. Oh well, the feeling that I am getting good at DPs is good enough for now. Adios!

Be Sociable, Share!

Leave a Reply