MIXGA - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Aleksa Plavsic
Tester: Hussain
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Game Theory, Strategies

PROBLEM:

Given K and an array A consisting of N integers, 0 \leq A[i] \leq 1. Vanja wants the absolute value of expression \geq K, while Miksi wants to avoid that. They perform moves, in turns, assign a sign to ith element. Vanja moves first.

SUPER QUICK EXPLANATION

  •   Find the final value of expression, when both play optimally, and compare it with k.
    

EXPLANATION

Once you get the optimal strategy for this problem, implementation is very simple. Let us denote X as the value of expression before ith turn.

If A[i] == 0, then we can skip this turn, since the sign would not matter anyway.

Strategy of Vanja

Vanja’s strategy would be simple, since Vanja wants to maximize absolute value of expression, he will always add 1 to X if X>0 and subtract 1 if X<0. If X == 0, Vasya can do either.

Strategy of Miksi

If |X| \neq 0, then his strategy is obvious, since he wants to minimize absolute value of expression, he will add 1 to X if X<0 and subtract 1 from X if X>0, so that absolute value of expression is minimized.

But what if X == 0? This is the special case, since Miksi has to either add 1 or subtract 1 from X, which would increase the absolute value of X. (Side fact: In chess, such positions are called Zugzwang, Compulsion to make a turn which ruin your position.)

Consider this case

3 2       
0 1 1

On turn 2, Miksi has to make a move, since sum of expression upto (i-1) turn is 0, increasing absolute value of expression by 1. On turn 3, Vanja will assign same sign as Miksi assigned to 2nd element, thus getting absoluet value 2 and winning game.

Consider test case

3 1
1 1 0

Now, Vanja will add 1 to sum on 1st turn, Miksi will reduce the absolute vakue of sum by assign opposite sign to 2nd element as Vanja assigned to 1st element, getting absolte value 0. This, Miksi wins the game.

Now the intuition is clear, you can simply implement this with much ease.

Complexity:
Time complexity of this solution is O(T*N).

A General Technique

We can use dp to choose whether to assign positive sign or negative, but time complexity of such solutions is of order O(N^2) or higher (Usually), which will get TLE for this particular problem, though otherwise useful technique. The general idea of this can be found here.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

https://www.codechef.com/viewsolution/19790534
Why is this code not working??
Approach - adding all the 1’s for even and odd indexes in beginning and then checking different conditions.

Hi,
https://www.codechef.com/viewsolution/19800896 why is this approach wrong?

My solution assumes that both the players know all N numbers at the beginning as given in the question. But, the given solution considers sum till ith point(kind of greedy solution).
Please check my code and clarify on this.

1 Like

Order matters. Example-

N=5, K=2

0 1 0 0 1.
Ans- Yes, ans Vanja can modify his sign to match the other guy's

Kudos to setter for this problem.

2 Likes

Even if both players know all N numbers, we know that odd positions will be filled by Vanja, and even positions will be filled by Miksi. So, their choices do not affect each other. Both independently aim for their goals.

The condition for processing left to right is, that when we are filling signs of ith position, signs of all previous elements have been decided for sure. So, we only rely on sum upto i-1 th element only.

Hope that’s clear.

https://www.codechef.com/viewsolution/19805134

Why does this not work?

My approach is exactly the same as described in the editorial

Instead of checking the index type(odd||even) I use a flag variable to determine who’s turn is it

And I do not let my sum to go below 0 so that case is avoided since if it is Miskis turn and the sum is 0 then miski can either subtract one or add one so I make it mandatory to add one since in the end the absolute value is being checked so it doesn’t matter I believe

Can someone help?

Thanks a lot, bro :slight_smile:
Can you also tell how do you think of test cases, like I find it a bit hard to come up with test cases!

I have over 2 year experience of finding bug in other people’s code and understanding their code XD. I will say it comes with practice. :slight_smile:

The use of flag is fine, but you forgot to reset the flag for each test case.

Here is corrected submission. https://www.codechef.com/viewsolution/19809235

https://www.codechef.com/viewsolution/19799743

Can someone find the case my code is failing ?

My logic:

  1. Count no of 1’s in Vanja’s postion (x) and 1’s in Miskis position (y).

  2. if(x>y) then vanja will win if(x-y>=k) as vanja will put all + and Miskis all -

  3. else if(x<=y) then

{

if(x>=k) miskis will bring x to k-2 (not k-1 because if remaining y is odd he will give 1 contribution to the sum) by putting that many y’s with - sign and for all remaining y’s he will alternate between + and - for their sum to be 0.

else if(x < k) then Miskis will win always ( due to above argument)

}

@vijju123 seems like your second submission for this problem has same logic as this . Can you tell where this approach is wrong ?

1 Like

https://www.codechef.com/viewsolution/19802017

Can anyone tell me whats wrong with my approach??

@tanweer919 

I don’t know your logic but one thing that is certainly wrong with your solution is you are printing expression in loop unnecessarily.

if(i%2==0)
sum+=a[i];
else
{
if(sum>0)
sum-=a[i];
else
sum+=a[i];
}
This is the core code. I think no additional lines for else should be written for Vanja as that work is optimally done by Miksi.

Your third case seems faulty.

Yes. This what you have to do.

@taran_1407 Even I suspect that but not able to find a counter-case, can you provide one ?