×

# SPOJ problem MATGAME (Game theory)

 0 I was trying to solve the spoj problem MATGAME. I have read topcoder tutorial on game theory and this discussion on topcoder forums and this discussion. All i understand is that each row can be treated as a subgame. I cannot figure out how to assign grundy numbers to sub games. Can someone help me? Thanks in advance. P.S. I am a novice in game theory problems. asked 29 Oct '13, 10:04 160●1●1●10 accept rate: 0%

 1 Its a nice modification of Sprague-Grundy Theory. For this problem you need to find the Grundy number of each and every row the given matrix. To calculate the Grundy number of each row you need to know the Grundy number of each and every cell of the row. Now if you are on a cell of a row you have 2 possible moves -> either finish the current cell and move to next or move to a lower number in the current cell. An edge case comes when the number in the cell is equal to 1. Here you have just one move that is to move to next cell. Now you may calculate Grundy numbers in this manner -> grundy[i][j] = grundy[i][j+1] >= grundy[i][j] ? grundy[i][j] - 1 : grundy[i][j]; Now just find the NIM sum of 1st elements in each row. answered 31 Dec '13, 16:26 2★hellgeek 16●2 accept rate: 0%
 1 Can you please explain how the following formula is derived: grundy[i][j] = grundy[i][j+1] >= grundy[i][j] ? grundy[i][j] - 1 : grundy[i][j]; thanks in advance, answered 14 Sep '14, 10:58 91●3 accept rate: 0%
 0 This blog will definitely help. answered 10 Aug '17, 02:10 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×1,071
×124
×51

question asked: 29 Oct '13, 10:04

question was seen: 8,249 times

last updated: 10 Aug '17, 02:10