Codechef Why u not give editorial of DIVGAME( Game Of Divisors ).
@bugkiller sorry if u not like the way I questioned. It is not easy to understand other code until it is properly commented. So if u have no problem then upload your answer with proper comment.
Let me share the way I approached this problem !
Actually in these problems when you have no clue for the solution, You can always code a brute force solution for the first (letβs say 1000000 values) and then uβll notice some pattern.
Although that pattern doesnβt have to be 100% correct for all values larger than the limit we chose, but it gives you an overview of the solution for the problem, and sometimes it turns out to be a correct pattern for all values.
To make a brute force efficient solution that can calculate up to 1000000 values, we can use simple memoization.
And here is the recursive function that can tell if the first player can win the game if the input number is n.
bool CanWin(int n)
{
if(n==1){return false;}// If n==1, The current player loses the game.
if(CanWin(n1)==false){return true;} // If the current player decreased the number by 1, the other player can't win the game.
for divisor in Divisors(n)
{
if(Solve(n/divisor)==false){return true;}
}
return false; // None of the available moves can make the other player lose the game.
}
Applying this code for the first 10^6 values, You will find that the first player can always win the game, unless the input number is prime.
We also have some special cases β¦ If the input number is 2 or 17 β¦ The first player can still win the game.
Also if the input number is 16 or 34 or 289 (these are not primes), he canβt win the game.
In the contest time,I had no guarantee that this assumption is correct for values larger than 10^6 β¦ but I submitted it and got AC β¦ However after the contest, I analyzed that assumption and got to a pretty convincing proof, which is hard for me to type in an easy readable way
I will try to write my proof in a compact way
Letβs collect some observations about this game

Number β2β is considered a winning situation. And number β3β is considered a losing situation.

For any prime number, the only possible move is to decrease it by one.

For any composite number, I can reduce it to a prime number in only one move.

For reducing the composite number, A player should reduce it for an odd prime number. (Reducing to β2β gives the other player the winning situation)

If the two players are playing optimally well, All the games will end up with these two moves, β3β> β2β > β1β
Now, letβs sum up these observations.
For any composite number (except for powers of 2), It is possible to reduce it to an odd prime number, which in turn will shrink to a smaller composite number and these goes on till one of these two events happen (and It is pretty obvious that one of these scenarios will happen eventually).
The second player finds the number β3β (In this case, the first player wins the game).
Or, the first player finds a power of β2β. Let me remind you what is the problem with the powers of 2.
I canβt reduce these numbers to an odd prime number. The possible moves is to decrease it by one, or to reduce it to another power of β2β.
Letβs manually investigate the scenarios when the first player runs into a power of 2.
 β2β > the first player will win the game
 β4β > reduce it to β3β then the first player again wins.
 β8β > reduce it to β7β > β6β > β3β > β2β > then the first player wins again.
 β16β > Letβs discuss the possible moves
 Reduce to β15β > β3β > β2β > the second player will win
 Reduce to β8β,β4β,β2β > the second player will win in all these cases.
 Any power of β2β larger than β16β > It is possible to reduce it to 16, which will always be a losing situation for the second player, hence the first player wins.
So we can come to a proof that, for any power of β2β (except for 16), the first player can win.
Back to out scenario, We said that the two players will continue these moves (composite > prime > composite > prime > β¦) till running into a β3β or a power of β2β.
So we proved that in all cases (except for running into a 16) the first player will win.
Now comes the question, What are the cases where the first player can run into a β16β, keeping in mind that the second player always produces a new number by decreasing a prime number by 1.
Easy right? , Of course It is the β17β.
When the second player runs into a β17β , It is a winning situation for him β¦ He will reduce it to β16β and the first player loses.
Now coming to the last question β¦ What are the cases that will oblige the first player to turn his number into β17β β¦
It is one of these two numbers β17.2β or β17.17β, which are β34β and β289β.
I think it is pretty obvious why he has to change these two numbers into β17β.
And hence, I think we came to a proof that all starting numbers except for primes(except for β17β and β2β) and β34β and β289β will make the first player win.
It was just fun intended. Nothing like I disliked it. Donβt worry.
Can you share how you analyzed the assumption and found a pretty convincing proof?
It is posted now
Hi Krish, hereβs the editorial you were looking for: http://discuss.codechef.com/questions/40480/divgameeditorial