PROBLEM LINK:
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.