Topcoder SRM 726 - DIV2 500

general
,
1

I couldn’t come up an efficient solution for the problem, as there were no editorials available for it I had a look at other submitted solutions, but couldn’t understand the approach. It would be cool if some one can give me an analysis for the same.

2

A few hints:

  • Find any valid path in the grid. Let’s say the length of the path is X. Every valid path in the grid is of length X.
  • The winner will be decided on the basis of who starts removing nodes when only 1 path (the last path of length X as discussed above) is left in the grid. If there are even nodes in that final path, who will win?
  • The parity of total no. of present nodes in the graph is important too - can you think why?

Let me know if you need more help to understand this fully.

1 Like
3

A turtle can move only down or right. The start and end positions are fixed. This means every valid walk from start to finish is of the same length.

Given height h of the board and width w, the turtle has to move downwards (h - 1) times and to the right (w - 1) times. So every valid walk is (h - 1) + (w - 1) steps long and consists of (h - 1) + (w - 1) + 1 tiles.

As both players play perfectly and the starting board always has a valid path from start to finish, there’s always a valid path on the board as long as there are at least (h - 1) + (w - 1) + 1 walkable tiles.

Now just count the number of walkable tiles and substract (h - 1) + (w - 1) + 1 and you get the number of turns players can take until there are only (h - 1) + (w - 1) + 1 tiles on the board left. When this player takes one more tile away, there can’t be a valid path from start to finish and this player loses the game.

So the solution is to check whether the difference of walkable tiles on the board and path length from start to finish is divisible by 2.

1 Like
4

Thanks, I got the approach. It would be really helpful if you can share your thought process,like how you came up with the above approach in the first place. For me, whenever I see a game theory problem I think along the line as hemanth_1 suggested above.

5

You can start thinking from the base case - consider a graph with 2 nodes and 1 edge between them - who would win?

Now, add another node to the graph - try various edges that it can have to the remaining nodes, determine how the game will work in each scenario.

6

Thank you.