Silence_for_Melody's blog

By Silence_for_Melody, history, 3 months ago, ,

Hi Codeforces.

On friday I participated in the round 1A of the GCJ but I could not pass the third problem. Even the easy set test. Here are my two codes.

PROBLEM

In the easy one, I just did what the editorial said. However, I got WA repeatedly (15 submissions).

For the full set, my idea is the following. First rest from P the perimeter of all the rectangles and now I have P'. Now, each rectangle i add to the answer 0 if it is not cut, or a number in range [ L[i], R[i] ] where L[i] = 2 * min (W[i], H[i]) and R[i] = 2 * hypot (W[i], H[i]) if is cut. The idea is to choose a subset of the rectangles whom will be cut and the sum of additional perimeters must not exceed P'.

Now, each subset j generates an interval [ L_subset[j], R_subset[j] ]. However, these intervals will always start (left side value) with at most 250 * 100 (maximum side length and maximum quantity of rectangles). Therefore, I did a DP where DP[i] is the maximum right side of an interval for the left side be exactly i.

Start DP[i] = -INF
DP[0] = 0
FOR i in range(0, N):
FOR leftside in range(0,25001)
DP[leftside] = max (DP[leftside] , DP[leftside – L[i] ] + R[i] )


Now, for each DP[i] for i <= P' I checked if DP[i] >= P', then the answer is P as this could be reached. Otherwise, the answer is max DP[i] for i <= P' plus the sum of perimeters of all rectangles.

The complexity of this idea is 100 * 100 * 250. Could give TLE, I don't know because the system always gave me WA.

I spend all the weekend tring to find out why my codes gave me WA, now I need your help. Many thanks

 » 3 months ago, # |   +3 Check on these cases: 2 1 100 1 1 1 100000000 1 1 Correct o/p: Case #1: 6.828427125 Case #2: 6.828427125 Your output seems wrong.
•  » » 3 months ago, # ^ |   0 you are awesome. My mistake was in the second loop. I shold do it in reverse order to avoid using incorrect subproblems states in DP Many thanks