×

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 ≤ jSB) 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 ≤ jSB, 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 ≤ iSA, 0 ≤ jSB = 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.

This question is marked "community wiki".

16.9k347485513
accept rate: 36%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×11,984
×1,879
×6
×1

question asked: 22 Nov '12, 16:32

question was seen: 1,136 times

last updated: 22 Nov '12, 16:32