- Practice
- Algorithms
- Game Theory
- Game of Stones
- Discussions

# Game of Stones

# Game of Stones

kevindu + 8 comments This is the O(1) solution based on the pattern.

`for _ in xrange(input()): print ["First","Second"][input()%7 in [0,1]]`

aaoferreira + 3 comments @kevindu do you mind to explain how did you get to that conclusion? thanks!

NikhilPathania + 2 comments input%7 defines the choice that first player can have after a series of steps. if value is 0 or 1

then player 1 loses as he has no choice, else if it is

`2 then he will give 2, 3 then he will give 3, 4 then he will give 3, 5 then he will give 5, 6 then he will give 5.`

Clearly mod 7 is between 0-7, mod 7 is taken because max is 5 and min is 2, so at the climax of game atmost 7 cards are left

aaoferreira + 0 comments Thanks @Nikhil_Pathania !

dguai + 1 comment Isn't mod 7 between 0-6?

leom_hardt + 1 comment Yes, but

if( (x mod 7 == 1) OR (x mod 7 == 0))PRINT "Second" else PRINT "First"

lincolndu + 1 comment if( x mod 7 < 2 )PRINT "Second" else PRINT "First"

godaddy671 + 0 comments Is it right? I want to know more about this . I also take a help of Apple Support Canada to know this things. At the same time this site also helps me my Apple related issue. if anyone inteerested take a help of this site.

dorna_hassani + 2 comments I had the same question and still don't get the answer.

My solution was (dynamic programming approach):

`private static String winner(int n) { String[] memory = new String[101]; Arrays.fill(memory, ""); return winner(n, memory); } private static String winner(int n, String[] memory){ if(n == 1){ return "Second"; } if(2 <= n && n <= 5){ return "First"; } if(memory[n] == ""){ if(winner(n - 5, memory) == "First" && winner(n - 3, memory) == "First" && winner(n - 2, memory) == "First"){ memory[n] = "Second"; } else{ memory[n] = "First"; } } return memory[n]; }`

which is longer than this solution and recursive but makes sense to myself. I'd like to understand the reasoning of the other solution, more specifically this sentence:

mod 7 is taken because max is 5 and min is 2, so at the climax of game atmost 7 cards are left.

ende76 + 2 comments It's proof by induction.

**The hypothesis:**

For**n**% 7 in [0, 1], the first player loses, otherwise the first player wins.**The anchor:**Clearly, for 0 or 1 stones, the first player has no move, so he loses.

For any of 2, 3, 4, 5, or 6 stones, the first player can make a move that leaves 0 or 1 stones for the second player, so the first player wins.**Induction step:**

Now, for a given starting position**n**we assume that our hypothesis is true for all**m < n**.If

**n**% 7 in [0, 1], we can only leave the second player with positions**(n - 2)**% 7 in [5, 6],**(n - 3)**% 7 in [4, 5], or**(n - 5)**% 7 = [2, 3], all of which mean – by induction – that the second player will be in a winning position. Thus, for**n**% 7 in [0, 1], the first player loses.If

**n**% 7 in [2, 3, 4, 5, 6], there's always a move to leave the second player with an**m**% 7 in [0, 1], thus – again by induction – forcing a loss on the second player, leaving the first player to win.That concludes the proof.

The invariant is, that once a player A can force [0, 1] on player B, A can keep forcing that position, while B cannot force it on A.

dorna_hassani + 1 comment Thank you for the great response! Now I get the reason but don't think it's a solution I would think of intuitively. Hopefully after a while I'll get there.

ben_epstein + 0 comments I didn't think about it inductively (formally), although that is definitely a great way to think about it.

Another way is to test it out yourself until you see a pattern. You know that 2-6 will leave P1 as the winner, and you know that 7 will leave P1 as the loser. With this in mind:

Begin walking up one by one, deciding who would win given an input. 8 would leave P2 as the winner because P1 would subtract [2,3,5], leaving P2 with [3,5,6], all in the winning section.

Knowing that being at 7 or 8 cause that player to loose, figure out how the other player (P1) can 'force' P2 to get to 7 or 8 (Since P1 starts, she has the upper hand). You'll get to the point where you see that the next loosing numbers to be at are [14,15] which happen to be n%7[0,1] (As seen by the induction above). Hopefully then you will catch the pattern :)

salman_farsi + 0 comments Mind blown

a7n007 + 0 comments [deleted]

mohitgupta943 + 0 comments [deleted]

c650Alpha + 0 comments This is crazy clever.

pariharyash6 + 0 comments smart solution

sttony + 0 comments 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

P2 P1 P1 p1 P1 P1 p2 p2 p1 p1 p1 p1 p1 p2 p2 p1 ...This will help understand. If n-5, n-3, n-2 can reach a P2 node, then n =P1, if not n=p2.

rochelly_fernan1 + 0 comments public static boolean isMultiple(int number){

`double result = number % 7; double result2 = (number -1) % 7; if (result == 0 || result2 == 0) return true; else return false; }`

MobilityWins + 1 comment When 0(1) solution and 0("other solutions) I have no idea what that means, in my entire college degree (2 months from finishing) this has not been taught, what is the best source i can find teaching about runtime complexity solutions.

the_piranha + 0 comments Hi @MobilityWins , please refer to the link below. The first 6 videos in the playlist explain time complexity very beautifully.

https://www.youtube.com/playlist?list=PLEbnTDJUr_IeHYw_sfBOJ6gk5pie0yP-0

lincolndu + 0 comments PHP solution

fscanf($_fp,"%d",$t); for($i=0;$i<$t;$i++){ fscanf($_fp,"%d",$n); echo ($n%7 <2 ) ? "Second\n" :"First\n"; }

wasuaje + 0 comments Python Version

n = int(input().strip()) for i in range(n): option = int(input().strip()) print("Second" if option % 7 in [0, 1] else "First")

NAklecha + 0 comments Guys try it yourself for like 20 cases, on a paper! You will find out :P

jpritcha3_14 + 0 comments The pattern emerges pretty quickly if you start from 1 stone and look at if the first player will win or lose with each stone you add.

# SPOILER

You'll find that the first player will lose when the starting number of stones s is: 1,7,8,14,15,21,22... (i.e. when s % 7 < 2). With this knowledge in hand the code is trivial:

t = int(raw_input()) for _ in xrange(t): s = int(raw_input()) if s % 7 < 2: print 'Second' else: print 'First'

shivnshus + 2 comments My solution

int player2(int n){

`if(n<2) return 1; return (player1(n-5)&&player1(n-3)&&player1(n-2));`

}

int player1(int n){

`if(n<2) return 0; return (player2(n-5)||player2(n-3)||player2(n-2));`

}

int main() {

`int n,t,i,j; scanf("%d",&t); for(int a0=0;a0<t;++a0){ scanf("%d",&n); i = player1(n); if(i==1) printf("First\n"); else printf("Second\n"); } return 0;`

}

cantfind + 1 comment Did it pass? I mean, it gives the correct output, but is very inefficient.

For a large n, you'd end up with a stack overflow, and the computational complexity is exponential.

fyras1 + 0 comments Yes that's why you need to add some DP so you don't go through the same "n" and "player" over and over again

noob_akshay + 0 comments `//eliminate repeated calls with dp int gos(int n, int cur) { if(n less than 2) return cur; if(cur==0) return (gos(n-2,1) || gos(n-3,1) || gos(n-5,1) ); else return (gos(n-2,0) && gos(n-3,0) && gos(n-5,0) ); } Such a good problem :)`

tao_zhang + 1 comment This game is composed of the repeating group of

`LWWWWWL`

Therefore the solution in Java is like this --> System.out.println(scanner.nextInt()%7<2?"Second":"First");Source: https://www.cs.umd.edu/~gasarch/COURSES/250/S15/nimnotes.pdf

pgmreddy + 0 comments True for repetition

sidpat + 3 comments Is there any actual theory behind this game?

Any other way to deduce the logic instead of just putting the numbers in and seeing the pattern?

Thanks, Sidpat

Pankaj_546Asked to answer + 0 comments Ya, there's a theory called- "Impartial Games" which deals with the cases when there are only two player and they either win or lose.

In face the problem is easy and can be coded with DP [O(n) solution], without finding the exact relationship (until the test cases are too large, you dont need the O(1) solution;IN CASE YOU NEED- still you can use the DP sol to get the table, and find the relation without hand coding every case ).

I first suggest you to Understand THIS problem. (as the same theory will be required many times). and then see the Impartial Games, as they can have many Extra Material you don't want.

ShafaetChallenge Author + 0 comments See the editorial to learn about winning-losing positions. If you don't understand how to deduce the logic, you won't be able to solve most game problems.

dmlerner + 0 comments Grundy numbers.

clivic + 0 comments The key to solve this problm is enumerate it out on a paper.

At first I thought wow when the n is big there were a lot of possibilities so how could it possible to have a fated loss or win. I was wrong.

reinaldo_rafael1 + 1 comment C++ Solution and Explaination:

At first I had tried to modulos N by 10 (n = n%10) and set the number of if statements for each possibility from 1 to 10 to determine the winner, I was completely wrong. So I purchased the Test Cases for TC #0 and noticed that the pattern repeated itself after the 7th entry, it would go "Second First First First First First Second" and after that the pattern was the same. So I realized the best answer was to check if n was equal or greater than 7 and if so modulus n by 7 (n = n % 7). If the remainder was 0, it meant n was equal to the 7th case of the pattern (7 or 14 for example) and Player 2 Wins or if the reminder was 1, it meant n was equal to the 1st case of the pattern (8 or 15 for example) and Player 2 wins, any other remainder meant Player 1 wins.

int main() { int t; cin >> t; for(int i = 0; i < t; i++){ int n; cin >> n; if(n >= 7) n %= 7; if(n == 0 || n == 1) cout << "Second" << endl; else cout << "First" << endl; } return 0; }

itbalachander + 1 comment Can you help me why if(n >=7) is used... I understood your code. But didnt get this condition statement .. Without that code work should fine ??

reinaldo_rafael1 + 0 comments Yes without it, it should work fine. It was there mainly so that I myself could understand it more clearly (Know why I used n%7 if I ever come back to the code and forget, although in retrospective I could've just written a comment.

yogeesh_pandey + 0 comments Tyipical case of dynamic programing.

This problem is biased to player one. if Any of the move chain exists which lead to player one to win player one to win.

ygongdev + 1 comment Surprised to see this marked as easy when a similar problem was marked as hard in another contest.

ParaLogia + 0 comments This problem is much more lenient, allowing for various naive implementations. The recent problem was more general, and the test cases/constraints were a lot wider, which prevented such solutions from passing. But I also think that was the easiest "hard" problem I ever saw.

Sort 88 Discussions, By:

Please Login in order to post a comment