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. 