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

×

RKABOL01 - Editorial

PROBLEM LINK:

Practice
Contest

Author: ravikiran0606
Editorialist: ravikiran0606

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

COMBINATORIAL GAMES,DP

PROBLEM:

Initially there are K coins in the pile. There is an array of N integers a1, a2,...aN. The game is played in turns.In each turn, the player can take away ai coins (1<=i<=N) from the pile. The player who cannot make any turn loses the game. It is assumed that both the players play optimally. We need to find the winner of the game.

EXPLANATION:

In this question, we can find who will win the game using the rules of the combinatorial games. We can consider the game as the set of positions where the first player will win or lose. Let's represent this information in an array dp[maxi]. Let dp[i] = 1 denote that with i coins in the pile, first player will win and dp[i] = 0 denote that with i coins in the pile, first player will lose in that position.

Positions have the following properties:

1)All terminal positions are losing.
2)If a player is able to move to a losing position then he is in a winning position.
3)If a player is able to move only to the winning positions then he is in a losing position.


The base case is that dp[0] = 0, since with 0 coins, first player cannot make a move and he will lose. We need to fill the array by using the above properties. Losing positions are those indices i such that dp[i] = 0 and winning positions are those indices i such that dp[i] = 1. In this question, from the position i, the player can move to positions i-a[p] ( for all 1<=p<=N such that i-a[p]>=0 ). From position i, if a player can move to at least one position j such that dp[j] = 0, then dp[i] = 1. (rule 2) Otherwise dp[i] = 0 (rule 2). In that way, if we fill the array dp upto kth position. If dp[k] = 1, then the answer is "Yes" else "No".

AUTHOR'S SOLUTION:

Author's solution can be found here

This question is marked "community wiki".

asked 13 Mar, 21:38

ravikiran0606's gravatar image

4★ravikiran0606
41
accept rate: 0%

edited 15 Mar, 13:37

admin's gravatar image

0★admin ♦♦
19.6k349497539

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:

×15,182
×1,617
×19
×19
×19

question asked: 13 Mar, 21:38

question was seen: 123 times

last updated: 15 Mar, 13:37