1. https://codeforces.com/blog/entry/49691?locale=en (Magical Idea, with no convincing proof as of now, of why is f(x) convex)
Even if you can somehow show that f(x) is indeed convex, what is the intutive explanation of the newly formed dp[i][x] ?
2. Intro: I saw this question recently in a workshop. As far as I know there exists 2 solutions to this question. One of them being the official solution with a good proof the other one, that my team tried in the contest and got AC with it. However my solution has some portions which I cannot prove should work. I wish to discuss that portion.
Problem: There are 2 players Alice and Bob. Each of them has a constraint A and B respectively given in input. They are given an array of N non negative integers. Now Alice has 1st turn and then the move alternates between the two. In a single turn of Alice, Alice must eat a non-empty prefix of elements of the array. The sum of all these elements gets added to his total. Now turn changes to Bob. And from that point onwards he also must eat a non-empty prefix of the remaining array. This keeps on happening in each turn. Wherever a person eats gets added to their total. If Alice's total exceeds A, before Bob's total exceeds B, then Alice looses and Bob wins and vice-versa. If both of them don't exceed their totals and end up consuming the entire array. Then the person whose turn starts after the Nth element, i.e the person who is unable to eat something looses .
Print the winner of the game if both play optimally.
1<=N<=1e5
1<=A,B<=1e9
0<=array(i)<=1e9
Example
N=3, A=3, B=3
Array = [1,2,1]
Then Bob wins. Alice takes first element or first two, either way Bob consumes all remaining.
If B=2 in above case,
Then Alice wins.
Spoiler:
.
.
.
.
.
Relabel A as A_0 and B as A_1.
Let sum = A_0 + A_1 be the initial sum.
For 0<= x, y <= 1, 1 <= i <= n
Let dp[x][y][i] be the minimum A_x at position i such that player x wins with player y starting at i. Then dp can be found in linear time.
My solution: (Way uglier than the previous one)
Let us define C as the entire array and preC[i] as the the prefix array of C uptill the i_th element.
Firstly pad a +infinity at the end of C array, to incentive both players to NOT pick that element in case of draws.
Let us define a method
pair f(i) which takes in an index i and solves the following problem on the array preC[i]:
Both players play optimally for the array defined by preC[i] (they completely forget about the future elements of C array) so as to minimize their scores given THEY BOTH HAVE TO CONSUME THIS ENTIRE ARRAY. (Note: They have completely forgotten about A and B here). So this can be done by a standard game theory dp
like dp[i][0] = min(dp[i + 1][0], dp[i + 1][1]) + array[i], if it is 0th players turn at i_th position and dp[i][1] = max(dp[i + 1][1], dp[i + 1][0]);
So eventually dp[1][0] will store the value player 0 will get if they both play optimally on this preC(i) array and TOTAL - dp[1][0] will be what player 1 gets.
Now what we return from the f(i) method is {dp[1][0] > A, TOTAL - dp[1][0] > B}, i.e the boolean pair of which of the two players exceeded their threshold while consuming this entire array.
Now notice that that f(i) will look like this for the first i's
f(1) = {0, 0}
f(2) = {0, 0}
...
f(k - 1) = {0, 0}
f(k) != {0, 0}
f(k + 1) != {0, 0}
...
f(n) != {0, 0}
So this is a monotonic function in terms of being {0, 0} or not {0, 0}.
Now binary search for the k by calling this function again and again.
Now at f(k), if it is {1, 0} or {0, 1} then we are done, the guy with 1 is loosing and the guy with 0 is winning, right?
But it is possible that f(k - 1) was {0, 0} but f(k) is {1, 1}, i.e by the presence of the k_th element both the players lost.
Ex. N = 3, A = 3, B = 3, array = [1, 2, 1, 100]
Now when k = 3 (1-based indexing), Alice takes 1st and 3rd element and Bob takes second element.
But when k = 4, Alice will take the first three elements making a sum of 4 (so as to avoid taking the 100), and then Bob will HAVE to take the last element making his sum as 100.
So, to handle this case, when f(k) = {1, 1}.
I take the C[k] and change its value.
More precisely I binary search on the value of C[k] from the range [0, C(k)] to find the smallest value x + 1, such that the array [C(1), C(2), ..., C(k - 1), x] gives f(k) != {0, 0}.
Let me explain by example
N = 3, A = 3, B = 3, array = [1, 2, 1, 100], we found k = 4.
Now if array = [1, 2, 1, 100], f(4) returns {1, 1}
But if array = [1, 2, 1, 0], f(4) returns {0, 0}
What about [1, 2, 1, 50], then also f(4) returns {1, 1}
So we binary search on the value of the right most guy here.
Eventually you will find out that [1, 2, 1, 2], gives f(4) = {0, 0} (Alice takes 1st element, Bob takes next two elements and then Alice takes last element, both sum to 3)
Whereas the immediate next state, i.e [1, 2, 1, 3] gives f(4) = {1, 0} (Alice takes first element, Bob takes next two and alice takes last element OR Alice takes first three elements and Bob takes last, either way Alice exceeds).
So ta da, we found our solution that Alice looses and Bob wins.
Basically two binary searches + dp call inside each binary search. So O(N*logN)
The portions with which I had doubt was:
1. Will the binary search on the last value ensure the requirement that there must exist an x, such that [1, 2, 1, .., x] gives f() = {0, 0} whereas [1, 2, 1, ..., x + 1] gives f() = {1, 0} or {0, 1} (i.e not both {1, 1}).
2. Also is the solution path (i.e how to pick the elements) found by this dp usable for the original question.
3. Lastly, what is the intuition of having x = 50 or anything not equal 100 in the last cell. We know that in reality it is 100, but making it smaller kind of changes the incentive structure in our dp, so both players change their strategy before that element, because they now don't think of it as a BIG NEGATIVE.
Interesting follow up question that arises is, is this kind of game theoretic dp's where speed of killing opponent matters have this generic method of binary searching on a certain prefix of the array?