SEALUP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Kamil Debowski
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic programming, knapsack problem, geometry

PROBLEM:

For a given convex polygon with N vertices, and M types strips, each defined by its length and cost, the goal is to cover all edges of the polygon with the strips minimizing the total cost of used strips. Strips cannot be bend nor cut. There is no limit on the number of used strips.

QUICK EXPLANATION:

Cover each edge independently in the best way. The minimum cost of covering a single edge can be computed used dynamic programming dp[d][i] capturing the information about the minimum cost of covering distance d using first i types of strips.

EXPLANATION:

First of all, let’s observe a few things. Since the polygon is convex, one strip can cover only one edge (of course we place strips alongside the edges, strictly on them, because otherwise no edge can be covered). Thus, we can compute the minimum cost of covering each edge independently of the other edges, and get the final result by summing these costs. Now the problem is reduced to covering a single segment of length let’s say Z with the given strips. Next observation is that there is no point of covering an edge with overlapping strips because any such solution can be transformed to a solution using the same strips without overlaps. The final fact is that the order of strips covering a single edge does not matter. Approaches for a given subtasks can be based on the above observations. For the first subtasks, one can take a strong advantage of the additional constraints on the input.

Subtask 1

In the first subtask the polygon has at most 10 vertices, but more importantly, there is just one type of strips. Thus in order to get the result for a single edge of length Z, one can just compute the minimum number of strips required to cover edge of length Z, and since there is just one type of strips, let’s say that they are all of a length L, then \lceil Z/L \rceil strips are needed to cover such an edge and this is the best we can do.

Subtask 2

In the second subtask the polygon has at most 42 vertices and there are at most 2 types of strips. Let’s call these types A and B. Then any edge of the polygon will be covered by x strips of type A and y strips of type B. Thus the problem of covering an edge of length Z is reduced to finding the best values for x and y, such that x \cdot length_A + y \cdot length_B \geq Z and x \cdot cost_A + y \cdot cost_B is minimal possible. Since this cost function is unimodal, one can use ternary search over x and for a fixed x pick the smallest y sufficient to fulfill the requirement of the length function.

Subtask 3

In the last subtask the polygon has at most 2000 vertices and there are at most 10 types of strips. One approach here is to precompute results for a more general problem first and then get the answer for each edge using these precomputed results.

Let dp[d][i] be the minimum cost of covering distance of length \textbf{exactly} d using the first i types of strips. Since the maximum length of polygon’s edge is around \sqrt {2 \cdot 10^{12}} < 1.5 \cdot 10^6, the maximum d for which table dp will be computed can be set to for example 2 \cdot 10^6. Just be aware, there are tricky cases where is the best solution the edge of length Z is covered in such a way that its beginning of length Z-1 is covered by some segments and the last part of length 1 is covered by a single strip of length 10^6. Now, having dp dynamic programming table defined, we can fill it using a similar approach as in the well-known knapsack problem. However, one very important thing to notice is that for two distances d_1 < d_2, the minimum cost of covering d_2 can be smaller than the minimum cost of covering d_1 if we place the strips without overlaps. So keeping it in mind, we can compute the dp table using the below two-phase approach:

for i = 1 to M:
   for d = 0 to maximum_distance:
      dp[d][i] = INFINITY

dp[0][0]
for i = 1 to M:
   for d = length[i] to maximum_distance:
      dp[d][i] = min(dp[d][i], dp[d-length[i]][i-1] + cost[i])

for d = maximum_distance-1 down to 1:
   dp[d][M] = min(dp[d][M], dp[d+1][M])

Obviously, dp[d][M] is now the minimum cost of covering distance of length exactly d.

Having dp table computed, we can iterate over all edges of the polygon, and for each one get the minimum cost to cover it from the dp table. Just be careful here, because since the length of an edge is a real number Z, we want to get the minimum cost of covering distance \lceil Z \rceil. Binary search is a decent approach to avoid computing square root of squared distance, but one can try also some variations of square root implementation to find this value. For implementation details please refer to author’s and tester’s solutions below. The total time complexity of this method is dominated by the cost of precomputation which is O(\text{MAX\_DISTANCE} \cdot M). Also, one can reduce memory complexity while computing dp table, because when computing dp[d][i] only values for i-1 first types of strips are needed.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.

Can anyone tell me mistake in this code.

http://ideone.com/yLOLip

Thanks in advance.

Contest link is not working! Please sort out this issue!

Can anyone tell me mistake in this code?

http://ideone.com/yLOLip

Thanks in Advance.

Please add problem to practise section

Correction: The pseudo-code given has some error on the 8th line as min function takes 2 parameters but here only one is given.

The statement should be
dp[d][i] = min(dp[d][i] , dp[d-length[i]][i-1] + cost[i])

2 Likes

@naman_1 thanks a lot, there was ‘+’ instead of a comma there

This problem did not require dynamic programming,it can be solved greedily.
my code :https://www.codechef.com/viewsolution/12662159

“dp[d][i] = min(dp[d][i] + dp[d-length[i]][i-1] + cost[i])”

I think it should be dp[d][i] = min(dp[d][i-1], dp[d-length[i]][i] + cost[i])

To include the case when a same item is bought multiple times

1 Like

Can u explain your approach please

1.overflow in the distance calculation , keep x ,y long long ints .
2.array size is small . Should be greater than root(2)*10^6 .

1 Like

(sqrt(2) * 10^12) < (1.5 * 10^6)

How can you write this one? It’s mathematically incorrect… Or you should change less than sign to greater than sign

2 * 10^12 is the argument of sqrt function, I improved formatting, now it should be clear.

Without doing such complicated mathematical calculation in tester solution you can also perform like this in that line.

int d = sqrt(sq - 0.5) + 1;

Mine method int d=ceil ( sqrt(sq) );

Can anyone explain the choice of the value of MAX in tester’s solution.

Changing it from 2.5 * 10^6 to 2 * 10^6 gives WA.

But according to editorial, this should also work.

Can anyone tell how to apply ternary search on Subtask 2 as given in editorial?

See this

I am facing a strange situation that when I take dp table as dp[12][1000005] I am getting a correct answer, even though the maximum length is of order 1.5 * 10^6.

However if I revert this dp table to dp[1000005][12], this gives a Runtime Error (which should come anyway).

Moreover, if I simply take 1d array as dp[2500009] then I am getting 2 WA in subtask 3

I tried to think every possibility for the issues but couldn’t find a proper reason for why is this happening ?

Can anyone please provide some help.
Thanks in advance.

Solution giving Correct answer for dp 12 1000005

Solution giving WA

Consider an item having length (10^6 - 1) and cost c. Now if you required to form a stick with length 10^6, then the cost will be same as for length 2*(10^6 - 1) which is greater then 1.5 * 10^6 hence you should iterate to atleast 2 * 1.5 * 10^6 to cover all possible values.

@vsp4 your assertion is very correct, it may be the case when an item and a stick have the lengths you mentioned, but my solution implicitly manage such a case as i am doing this using top-down approach rather than bottom-up . You might want to look at my solution i have linked to.
Moreover my main problem that why taking dp[12][1000005] is getting an Accepted is still a mystery to me. Can you throw some light on the same? Thank you.