Codeforces Educational Round 169 Discussion stream (with hints)

Can the answer be YES if $N \ge 3$?

In one of the optimal answer all the removed edges will be in some continuous range.

Let $S = A+B$.

Then $A - B = 2 \cdot A - S = S - 2 \cdot B$

So Alice should try to make her sum as large as possible, and Bob should try to make his sum as large as possible.

If we sort $A$ in descending order. $A_1 \ge A_2 \ge \ldots \ge A_{N-1} \ge A_N$

Now, alice will take $A_1, A_3, \ldots$, and bob will take $A_2, A_4, \ldots$

Bob should only increase the piles which increases his score.

$A_2$ can be increased by $A_1 - A_2$ after which sorted order will change and Bob will not be able to increase score further.

For each color $c$ and each node $u$ we can find the nearest nodes $i_u$ and $j_u$ such that $i_u \le u \le j_u$, $i_u,j_u$ are reachable from $u$ and $i_u,j_u$ have color $c$.

In shortest path, we will go through $x \to i_x | j_x \to i_y | j_y \to y$.

Try out this for all 4 colors.

It’s a practice problem on how to solve Nim game problems. Checkout Game Theory

We do not need both the types of operations, we can either always merge or split, both of these are equivalent. Look at both the sides of middle in palindrome.

If we are merging 2 elements on left side in optimal answer, we can replace this operations with splitting the mirror element on right side.

I will always merge now. My goal is to count the maximum no of elements I can get such that the final array is palindrome.

Let the final length be $f$, and initial length be $L$.

No of operations will be $L - f$

Let’s say we want to find no of operations for subarray $L,R$.

First element will be obtained by merging some prefix, and last element will be obtained by merging some suffix. Let the first element of final array be $S$, ie last element of final array will also be $S$. Let the $i,j$ be the subarray for remaining elements.

First element is subarray $L,i-1$ and last element is subarray $j+1,R$.

Let $P$ be the prefix sum for $A$.

Notice that $P_{i-1} - P_{L-1} = P_{R} - P_{j} = S$, shuffling around we can get.

$P_{i-1} + P_{j} = P_{R} + P_{L-1}$,

So we can group subarray based on $P_{R} + P_{L-1}$, and try to calculate answers for all subarrays with same value.

Let $dp_{L,R}$ be the maximum no of final elements we can get for subarray $L,R$.

$dp_{L,R} = 2 + \max dp_{i,j}$, among all $L \le i \le j \le R$ with condition on prefix sum mentioned above.

After grouping subarray with equal value of $P_{R} + P_{L-1}$, for processing a particular group, we can do sweep line algorithm with range max segment tree.

276641649

276649508

276663241

276664313

276668954