Editorial for JAGAM

general
1

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

3 Likes
2

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: CodeChef: Practical coding for everyone

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

3 Likes
3

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
4

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
5

thank you it really helps me