Fair Share

Subtask 1

Alice can force the final array to have only one element if the number of rounds, $K$ is at least $\left \lceil{log_2 N}\right \rceil$. At every round, Alice divides the array in equal (or almost equal for odd size array array) two parts.

Bob’s strategy in this case is to keep the part that have the maximum element in it.

Hence, for $K$ $\geq$ $\left \lceil{log_2 N}\right \rceil$, the answer is equal to the maximum element of the array.

Time Complexity: $O(N)$

Subtask 2

For $K$ $\geq$ $\left \lceil{log_2 N}\right \rceil$, the answer is equal to the maximum element of the array.
Hence we can assume, $K < \left \lceil{log_2 N}\right \rceil$

Let’s define, $dp[i][j][k]$ = the sum of the elements of the final array if the game is played on $a[i], a[i+1], …, a[j]$ for $k$ rounds.

Base Case: $dp[i][j][0] = a[i]+a[i+1]+…+a[j]$, for $i \leq j$

Transition: $dp[i][j][k]$ $=$ $min(max(dp[i][m][k-1], dp[m+1][j][k-1]))$for $i \leq m \leq j$

But this is too slow with time complexity: $O(N^3*\log_2 N)$

We can notice that, for a fixed $i$ and $k$, $dp[i][j][k]$ is non-decreasing for increasing $j$.
So, we can binary search for the largest such index $m$ that,
$dp[i][m][k-1]$ $\leq$ $dp[m+1][j][k-1]$.

Then to find $dp[i][j][k]$, we only have to consider these two values:

$max(dp[i][m][k-1], dp[m+1][j][k-1])$ and
$max(dp[i][m+1][k-1], dp[m+2][j][k-1])$.

This speeds up the solution to: $O(N^2*(\log_2 N)^2)$

Exploiting the monotonicity, it is also possible to get a solution with $O(N^2*\log_2 N)$.

Subtask 3

Let's binary search on the answer. Let's fix $X$ and check if Alice can force the final array to have sum at most $X$.

If $K = 1$, then Alice must split the array into two parts such that each part has sum $\leq X$

If $K = 2$, then Alice must split the array into two parts such that each part can be further split into two parts with sum $\leq X$.

So, Alice must split the whole array into $4$ parts where each part has sum $\leq X$.

Similarly, if the game is played for $K$ rounds, Alice must be able to split the whole array into $2^K$ parts where each part has sum $\leq X$.

To find if the whole array can be split into $2^K$ parts each having sum $\leq X$.

we can iterate from left to right and split the array into parts with sum $\leq X$ greedily and check if the number of parts is at most $2^K$.

Time Complexity: $O(N*\log_2 (Sum\ of\ the\ Elements\ of\ the\ Array))$