SEALUP - Editorial

dynamic-programming
easy
editorial
geometry
ltime44
sealup

#1

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]* 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]* be the minimum cost of covering distance of length extbf{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]* = INFINITY

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

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( ext{MAX\_DISTANCE} \cdot M). Also, one can reduce memory complexity while computing dp table, because when computing dp[d]* only values for i-1 first types of strips are needed.

AUTHOR’S AND TESTER’S SOLUTIONS:


Setter's solution can be found [here][333]. Tester's solution can be found [here][444].

#2

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


#3

Can anyone tell me mistake in this code.


http://ideone.com/yLOLip

Thanks in advance.


#4

Please add problem to practise section


#5

Can anyone tell me mistake in this code?

http://ideone.com/yLOLip

Thanks in Advance.


#6

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]* = min(dp[d]* , dp[d-length*][i-1] + cost*)


#7

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


#8

(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


#9

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) );


#10

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.


#11

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


#12

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


#13

import java.io.;
import java.util.
;
class sealing
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
//System.out.println(“Enter”);
int t=in.nextInt();
int i,j,k,p;
for(p=0;p<t;p++)
{
int n=in.nextInt();
double x[]=new double[n];
double y[]=new double[n];
for(i=0;i<n;i++)
{
x*=in.nextDouble();
y*=in.nextDouble();
}
int m=in.nextInt();
int val[]=new int[m];
int wt[]=new int[m];
for(i=0;i<m;i++)
{
wt*=in.nextInt();
val*=in.nextInt();
}
long s=0;
for(i=0;i<n;i++)
{
if(i==n-1)
s=s+calc((int)dis(x[n-1],y[n-1],x[0],y[0]),wt,val,m);
else
s=s+calc((int)dis(x[i+1],y[i+1],x*,y*),wt,val,m);
}
System.out.println(s);
}
}
static int calc(int W, int wt[], int val[], int n)
{
int i, w;
int K[][] = new int[n+1][W+1];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K*[w] =0;
else if (wt[i-1] <w)
{
if(K[i-1][w]==0)
K*[w]= K[i-1][w-wt[i-1]];
else
K*[w] = (int)Math.min(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
}
else
{
if(K[i-1][w]==0) K*[w]=val[i-1];
else
K*[w] =(int)Math.min(val[i-1],K[i-1][w]);
}
// System.out.println(i+" “+w+” “+K*[w]);
}
}
//System.out.println(n+” “+W+” "+K[n][W]);
return K[n][W];
}
static double dis(double x1,double y1,double x2,double y2)
{
double ans=(x1-x2)(x1-x2)+(y1-y2)(y1-y2);
ans=Math.sqrt(ans);
return ans;
}
}

Used knapsack approach with some modifications…Whats the point am i missing in my code?
Thanks in advance


#14

Just be aware, there are tricky cases
where is the best solution the edge of
length ZZ is covered in such a way
that its beginning of length Z−1Z−1 is
covered by some segments and the last
part of length 11 is covered by a
single strip of length 10 ^ 6.

Could someone please explain what that statement means??

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

Also, as a consequence of not understanding that statement above, I don’t understand why the code above is being used.

Given that I am kind of a newbie, I found the above editorial, a little too concise for case 3. Would anyone mind elaborating for improved clarity?? Thanks.


#15

@hpclearn, I feel if the constraints are generalized, the solution provided by the editorialist will fail. It just happens that his particular choice of MAX isn’t failing for the test cases provided for this question by Codechef. To ensure that the code solution does not fail for any of the test cases provided with the constraints described, he must choose a MAX value that is greater than 3 * 10^6. i.e ( 2 * 10 ^ 6 + 10^6)

Let me explain why with an example…

Consider the following test case:

1
2
0 0 
0 5
1
3 7

If you set MAX = 6 , then the answer that the tester’s solution will output will be INF (if you check dp[5] ), which is clearly wrong. The answer is clearly 14. Because to cover a distance of 5, all we need is 2 strips of length 3, each of which cost 7 rubles. This is because dp[5] will only be set to it’s correct value if dp[6] is set to it’s correct value. And that correct value is reverse propagated to dp[5]. Setting MAX = 6, will only result in values upto dp[5] being set to their correct values. Hence the incorrect answer.

In fact, the correctness of the entire algorithm entirely depends on the value of MAX used. And the value of MAX used by the tester is in fact wrong because it is less than 3 * 10 ^ 6.


#16

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


#17

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

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

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


#18

Can u explain your approach please


#19

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 .


#20

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