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

×

SPOJ problem MATGAME (Game theory)

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

charizard's gravatar image

4★charizard
1601110
accept rate: 0%


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.

link

answered 31 Dec '13, 16:26

hellgeek's gravatar image

2★hellgeek
162
accept rate: 0%

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,

link

answered 14 Sep '14, 10:58

shubhamsingh's gravatar image

3★shubhamsingh
913
accept rate: 0%

edited 14 Sep '14, 10:59

This blog will definitely help.

link

answered 10 Aug, 02:10

fane_faiz's gravatar image

2★fane_faiz
1
accept rate: 0%

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:

×866
×83
×50

question asked: 29 Oct '13, 10:04

question was seen: 7,545 times

last updated: 10 Aug, 02:10