PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This problem can be solved by using DP (Dynamic Programming). Basically, the relationship dp**[VA][VB][MA]** = max(dp[ceil**(VA**/2)][ceil(VB/2)][MA-1], sum of dp[VA-i][VB-j][MA] / ((SA+1)*(SB+1)), for 0 ≤ i ≤ SA, 0 ≤ j ≤ SB) is hold, where dp[VA][VB][MA] is the answer for the input VA, SA, VB, SB, MA. However there are some troubles.
First, dp[VA][VB][MA] is appeared both of the left hand side and the right hand side. So, dp[VA][VB][MA] cannot be calculated directly by using above expression. But this is not a hard problem. Transpose that term, then we obtain dp[VA][VB][MA] = max(dp[ceil(VA/2)][ceil(VB/2)][MA-1], sum of dp[VA-i] [VB-j] [MA] / ((SA+1)*(SB+1)-1), for 0 ≤ i ≤ SA, 0 ≤ j ≤ SB, i+j > 0).
Second, dp[a][b][c] is unknown for a ≤ 0, b ≤ 0. We can use binary search for solving this issue. Let the correct answer be P. If we set dp[a][b][c] = X for a ≤ 0, b ≤ 0, then X ≤ dp[VA][VB][MA] ≤ P or P ≤ dP[VA][VB][MA] ≤ X is hold. Therefore, we can calculate the correct answer by using binary search. Note that, if VA ≤ 0 and VB > 0, dp[VA][VB][MA] = 0, and if VA > 0 and VB ≤ 1, dp[VA][VB][MA] = 1.
Third, if dp[a][b][c] is calculated naively with O(SA*SB) time, we will get TimeLimitExceeded. To avoid this, a cumulative sum can be used. Let sm[a][b][c] be sum of dp[x][y][c] for M ≤ x ≤ a, M ≤ y ≤ b, where M is a small integer such as -101. Then, sum of dp[a-i][b-j][c] for 0 ≤ i ≤ SA, 0 ≤ j ≤ SB = sm[a][b][c] - sm[a-SA-1][b][c] - sm[a][b-SB-1][c] + sm[a-SA-1][b-SB-1][c], and sm[a][b][c] = sm[a-1][b][c] + sm[a][b-1][c] - sm[a-1][b-1][c] + dp[a][b][c]. By using this relationship, dp[a][b][c] can be calculated with O(1).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.