You are not logged in. Please login at www.codechef.com to post your questions!

×

CIELBTL - Editorial

PROBLEM LINKS

Practice
Contest

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 ≤ 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".

asked 22 Nov '12, 16:32

admin's gravatar image

0★admin ♦♦
14.9k347484503
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×10,491
×1,684
×6
×1

Asked: 22 Nov '12, 16:32

Seen: 1,077 times

Last updated: 22 Nov '12, 16:32