where the editorial of DIVGAME(Game Of Divisors) cook 44

general
1

Codechef Why u not give editorial of DIVGAME( Game Of Divisors ).

4 Likes
2

@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.

3

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(n-1)==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 :smiley: … 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 :smiley:

I will try to write my proof in a compact way :smiley:

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? :smiley: , 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.

4 Likes
4

It was just fun intended. Nothing like I disliked it. Don’t worry.

1 Like
5

Can you share how you analyzed the assumption and found a pretty convincing proof?

6

@tacoder I added the proof to my comment, please take a look at it.

1 Like
7

It is posted now

8

Hi Krish, here’s the editorial you were looking for: http://discuss.codechef.com/questions/40480/divgame-editorial