Editorial for JAGAM

Can anyone post unofficial editorial for MIX MIX GAME asked in LTIME63 ?

3 Likes

In fact, we only need to know the results within two steps.

If there is no win or loss within two steps, then it must be a draw.

Why, we can assume that the first person will win after two steps, but the second person can always return the first person to his previous step. For example, the first person is facing X, he makes X - a[i], then the second person can make X - a[i] + a[i]. So the first person can’t win after two steps, the second person is the same, so we need to consider the situation within two steps, and this is very simple.

And this is my solution: https://www.codechef.com/viewsolution/19859614

I am very happy if it helps you.:slight_smile:

3 Likes

The solution was easy if you had observed making your own test cases.

I’ll point out the important observations below :

  • The game ends in two moves, else it will be a draw. Can be verified on any test case . This is because , if 1 can’t win , it will make any move randomly, then if 2 will make a move , 2 will either win or move closer to win. To counter this losing effect, 1 will come BACK to where it started. Take example : 3 20 10 2 3 4, as you can see, the game won’t end.

  • THE ONLY WAY 1(first one to move) can win , is ONLY if z1 or z2 already in list. ex. z1= 4 z2 = 6 A = 2,3,-4. using -4 and subtracting from 0, you get 0- (-4) = 1 WINS.

           `if(lsearch(z1))  flag = 1;
            else if(lsearch(z2))  flag = 1;`
    
  • If 1 can’t win , only possibility is 2 winning or TIE.

  • 2 can win IF AND ONLY IF whatever move 1 makes , puts it in a losing position. or if z1 or z2 == 0.

    else if(z1 == 0 or z2 == 0) flag = 2;

  • NEXT STEP : find all the moving positions : Take example z1 = 5 , z2 = -5 , A = 1 , 4

  • To find losing position,

  • List item
    j = 0;

FOR(i,n)
            {
                LOSE[j++] = z1 + A[i];
                LOSE[j++] = z1 - A[i];
                LOSE[j++] = z2 + A[i];
                LOSE[j++] = z2 - A[i];
            }
           
  • Now if any move is possible that won’t end up in losing position , player 1 will be saved. So the only thing needed is to find if there is a move that won’t end up in LOSE[0…4n - 1].
  • FOR(i,n) { FOR(k,j) { if( !searchlose(A[i])) { flag = 3; } if(!searchlose(-A[i])) { flag = 3; } } } if(flag == 0) flag = 2; }

We just searched if using A[i] or -A[i] would leave in NOT-A-LOSING position. If found , 1 won’t lose and draw results. If no position is losing , then ultimately 2 wins .

CONTENTS OF lsearch

bool lsearch(int x) { bool found = 0; //cout<<"1 "; FOR(i,n) { if(abs(A[i]) == abs(x)) { found = 1; break; } } return found; }

SOLUTION LINK:
https://www.codechef.com/viewsolution/19869248

1 Like

The question may seem tricky at first sight, but just requires observation.
I have put detailed explanation in solution itself, though the comments are slightly shifted, its easily understandable.
My solution- https://www.codechef.com/viewsolution/19884936

1 Like

thank you it really helps me

//