wrong approach

http://www.codechef.com/problems/NUMGAME in this problem if n is even then alice will win and else bob,this is the correct ans for it, but according to me it should not be the answer, example if n=5 then if played optimally then Alice should win(but according to solutions Bob should win) WHY SO and which answer is correct?

1 Like

Initial value : 5

  • Alice’s turn: 5 is a prime number so it can only divide 1, therefore Alice can only subtract 1. 5-1=4
  • Bob’s turn: 4 can divide by 2 and by 1. Since they are playing optimally Bob subtracts 1 from 4, leaving Alice with an odd number again. 4-1=3.
  • Alice’s turn: 3 can only divide by 1 so once more Alice is left with no choice but to subtract 1. 3-1=2.
  • Bob’s turn: 2 can only divide 1 but this is good because 2-1=1, and we know that after this turn Alice can no longer play.

Bob wins.

So yes, the answer is: when n is even Alice wins, otherwise Bob wins. The best way to look at this problem is to build a table and simulate plays with the first 10 numbers starting with one. That will help you understand the problem.

Something that could help the answer look more accurate:

An odd number can only divide another odd number. So every time a player has to play with an odd number he or she can only subtract by another odd number leaving the next player with an even number. An even number can always subtract by another even number or an odd number (remember that all numbers can divide 1) but, since both players are playing optimally they will never do that because subtraction of two even numbers leaves the next player with an even number. Instead the player can choose any odd number that the current number can divide and then subtract it. This also implies that if a player starts with an even number he or she will always win the game because the only thing they have to do is making sure the next player plays with an odd number. At some point the next player will be left with 1 and as you know whoever is left with 1 loses the game.

You already solved this problem but I think this explanation might be helpful. If I thought this way the first time I solved this problem I would have saved some time. There are of course problems that in order to understand and solve you’ll have to try some values of your own to see the outcome but whenever you can, avoid this approach. This is extremely helpful in short contests because you’ll solve the problem faster and perhaps have enough time to solve the other ones.

7 Likes

@junior94, thanks , i thought for playing optimally we have to divide with the greatest divisor,but thats now clear.

@aasthi >> Remember: Never think that an assumption for a problem is right until you have considered fair amount of tests on that assumption. :slight_smile: Good Luck ahead.

1 Like

Could anyone point me why am i getting WA.
It works fine with sample cases on mys machine.

#include<iostream>
#include"stdio.h"
using namespace std;

int main()
    {
     int tc,k ,n;
     cin>>tc;
     if(tc>10000)
        return 0;
     while(tc--)
     {
        cin>>n;
        if(n>1000000000)
            return 0;
        if(n%2)
            cout<<"Bob"<<endl;
        else
            cout<<"Alice"<<endl;

     }
    return 0;
    }

You have to print “ALICE” and “BOB”. Not “Alice” and “Bob”

2 Likes