You are not logged in. Please login at www.codechef.com to post your questions!

×

Topcoder SRM 726 - DIV2 500

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.

asked 21 Dec '17, 21:21

randaam_oozham's gravatar image

3★randaam_oozham
51
accept rate: 0%


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.

link

answered 21 Dec '17, 22:12

schleppel's gravatar image

4★schleppel
1264
accept rate: 23%

edited 21 Dec '17, 22:33

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.

link

answered 21 Dec '17, 21:57

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

edited 22 Dec '17, 11:52

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.

(21 Dec '17, 23:31) randaam_oozham3★

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.

(22 Dec '17, 11:59) wittyceaser2★

Thank you.

(22 Dec '17, 14:57) randaam_oozham3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×195
×30

question asked: 21 Dec '17, 21:21

question was seen: 429 times

last updated: 22 Dec '17, 14:57