Editorial for Fair Share

Subtask 1

Alice can force the final array to have only one element if the number of rounds, KK is at least log2N\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 KK \geq log2N\left \lceil{log_2 N}\right \rceil, the answer is equal to the maximum element of the array.

Time Complexity: O(N)O(N)

Subtask 2

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

Let’s define, dp[i][j][k]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]a[i], a[i+1], …, a[j] for kk rounds.

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

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

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

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

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

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

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

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

Subtask 3

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

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

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

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

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

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

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

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

    Statistics


    59% Solution Ratio

    user.964301Earliest, 3M ago

    Deshi_TouristFastest, 0.1s

    Deshi_TouristLightest, 393 kB

    sakib.17442Shortest, 744B

    Toph uses cookies. By continuing you agree to our Cookie Policy.