RNR's blog

How to solve this? [Game theory]
By RNR, history, 6 years ago, In English

Hello,

Can someone explain the logic [and formal proof why this logic works] to solve this problem?

https://csacademy.com/contest/round-64/task/limited-moves/

Consider a heap of N objects. Two players take turns playing the following game:

At his very first move, the first player removes from the heap between 1 and N-1 objects After that, at each step the player to move can remove any number of objects between 1 and the number of objects removed by the other player at the previous move When the heap becomes empty, the player to move loses the game.

[UPD.]

I know that removing the number of objects from Last on bit works. The Last on-bit, I mean the below.

int k=0;
while( n % (1<<(k+1)) == 0)
            k++;
printf("%d",(1<<k));
fflush(stdout);
n -= (1<<k);

I need a formal proof/Argument that why is this working. Or why this is guaranteed to work?

Thank you.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

include <bits/stdc++.h>

using namespace std;

void make(int n,int k,int moves){ for(int i=moves;i<500 && n > 0;i++){ printf("%d\n",k); fflush(stdout); if(n == 1) return; int a; scanf("%d",&a); n -= a; n-=a; n-=k; k = min(k,a); } }

int main() { int n; scanf("%d",&n); int moves= 0; int mn = 0; for(int i=0;i<500;i++){ if(n == 1){ puts("1"); fflush(stdout); return 0; } else if(n == 2){ puts("2"); fflush(stdout); return 0; } for(int j=29;j>=0;j--){

}
}
for(int i=29;i>=0;i--){
    if(n == 1){
        puts("1");
        fflush(stdout);
        return 0;
    }
    else if(n == 2){
        puts("2");
        fflush(stdout);
        return 0;
    }
     if((1 << i) <= n){
           int k = n - (1 << i);
           printf("%d\n",k);
           n-=k;
            fflush(stdout);
            scanf("%d",&k);
            moves++;
            n -=k;
            if(n == 0){
                return 0;
            }
           make(n,k,moves);
            if(moves == 500) return 0;
    }
}

return 0;

}

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I asked the logic and not the solution.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      Go find the logic from my code then

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually, I have seen the solutions after the round but I need a formal proof of the logic used. Thanks.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think this code is simple and better than yours.

        #include <iostream>

using namespace std;

int main() {
    int n,a,k;scanf("%d",&n);
    for(int i=0; i<500; i++)
    {
        if(n==1)
        {printf("1\n"); return 0;}
        
        k = 0;
        while( n % (1<<k+1) == 0)
            k++;
        cout << (1<<k) << endl;
        n -= (1<<k);

        if(n==0) 
            break;
        
        scanf("%d",&a); n-=a;
        
    }
    return 0;
}
        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RNR (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If n is odd then we win by removing 1. So no one will move to odd n and the game will be always on even numbers. But now we can divide all numbers by 2 and repeat our argument. It is easy to see that this strategy is exactly 'remove last 1-bit'.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you... I got it when n is odd, the strategy will be 1,1,1,1,..... it can be easily be seen. And if n we are removing the last 1-bit such that when the opponent removes some number of objects it leads to the above strategy... Cool. Thanks a lot.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I came up with this, it passes, but is it really correct? It just mirrors the interactor output after the first number.

    int N;
    cin >> N;
    
    int num = 1;
    for (int i = 1; i <= N - 1; ++i) {
        if (N % i == 0 && (N / i) % 2 == 1) {
            num = i;
            break;
        }
    }
    for (int i = 0; i < 500; ++i) {
        cout << num << "\n";
        cout.flush();
        cin >> num;
    }
→ Reply