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[i]=in.nextDouble();
y[i]=in.nextDouble();
}
int m=in.nextInt();
int val[]=new int[m];
int wt[]=new int[m];
for(i=0;i<m;i++)
{
wt[i]=in.nextInt();
val[i]=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[i],y[i]),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[i][w] =0;
else if (wt[i-1] <w)
{
if(K[i-1][w]==0)
K[i][w]= K[i-1][w-wt[i-1]];
else
K[i][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[i][w]=val[i-1];
else
K[i][w] =(int)Math.min(val[i-1],K[i-1][w]);
}
// System.out.println(i+" “+w+” “+K[i][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
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.
@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.