shelob's blog

ASTRGAME (codechef) — Application of Sprague-Grundy Theorem
By shelob, history, 9 years ago, In English

Hello Everyone,

Recently after learning game theory, I tried my hand at the this problem. My doubt is the following :-

How would you precisely define the game, position of game (or the state of the game), and sub-games (if any) in this problem.

I don't need the code, just the definitions.

Thanks!

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The state of a game is (L, R) which means that we have the substring from position L to position R. Say you will make a move which erases a substring from i to j, then you'll split the game into two impartial games with states (L, i — 1) and (j + 1, R).

→ Reply