10412 - Big Big Trees

[likhan]

I'm using DP to calculate the cost.
cost[0] = 0
cost = cost[i-1] + min(len[j]+len[k]) [j,k are tree's leaves length of i-1th and ith tree. and also no line segments between the j and k intersects and the straight line distance is less then the specified.]
and then again minimized cost = min(cost, cost[i-1]+m )

where m is the length between two successive trees

i'm checking the line segments by calculating
for ith tree's kth leaf
x1 = i * m;
y1 = k;
x2 = x1 - len[k];
y2 = k;
for i-1th tree's jth leaf
x1 = (i-1) * m;
y1 = j;
x2 = x1 + len[j];
y2 = j;
what is the problem;

[likhan]

I found out the problem it was with setting the limit for the line segment intersection check.

[kmhasan]

Why do you need DP for this problem?

For two consecutive trees you only need to find the minimum walking distance between them. The answer is the summation of all such minimum walking distances.

Yes, you need line intersection check. Try to avoid floating point calculations, my solution didn't use any.

[jaivasanth]

I am not able to understand.....
How can it be a linear time algo.....?
Does that make it a greedy solution? Can you explain your algo.. i am not able to get a proper soln

[kmhasan]

I didn't say mine was a linear solution. Neither is it a greedy one.

To get the minimum walking distance between 2 trees you need to check all the possible walking distance between them. Mine would be a O(N*H*H) impelementation where N is the number of trees and H is the tree height. Let me elaborate:

Let i and i+1 be two consecutive trees that have height H(i) and H(i+1) respectively. Now for each leaf in tree i you can get the rightmost coordinate of that leaf, for this leaf you have H(i+1) leaves to jump to. You can now compute the leftmost coordinate of those H(i+1) leaves of tree i+1. Now for all the leaves of tree i except for the leaf you choose at tree i, you have to check if they intersect with the linesegment that can be drawn joining the two coordinates i mentioned. Similarly, you have to check this line intersection for all the leaves of tree i+1. You can only jump when the line segment doesn't intersect with any leaf and the jumping distance <= given max jump length. The walking distance for a jump would be the summation of the length of the two leaves. In the worst case you wouldn't be able to make a jump for tree i and i+1. In that case, the walking distance would be the given tree distance. So you have your minimum walking distance for tree i, i+1. Do a simple iteration on i, to find the sum of the minimum walking distances. That's the answer.

[jaivasanth]

Thanx......... i will try it ...........

[LittleJohn]

I solved this problem in the contest, but failed after rejudgement.
Could somebody provide some I/O? Really appreciate your help!

[Yarin]

During the first half or so in the contest the test data was wrong, or rather the output was wrong. If you got it accepted then, most likely you did the exact same mistake as the problem setter (I know I did too ).

The mistake was that when comparing if you can jump from height h1 to height h2 from a tree t1 to t2, it checked all leafs between h1 and h2 on BOTH trees even though one of the trees maybe wasn't high enough and thus had no leaf all heights between h1 and h2...

[LittleJohn]

Thank you, Yarin.
I have made the same mistake as what you say. I never thought about it. Thanks again!!

[Alexander Grushetsky]

It's very strange mistake. I (and I know at least one person more) did it too.
Maybe there is hypnotic text in the problem description that says to do this mistake.

[cyfra]

Hi!

I have a problem with this task... I checked it many times and I can't find out what is wrong....

Could anyone tell me what is wrong in my program??

Thanks in advance


( Found my mistake ( in my implementation) , thanks for reading

[windows2k]

I try to solve the question recently.
But I don't know what's wrong.
Could someone give some input/output?
Thank you

[bobi1978]

I have two questions for this problem:

1. Can I jump from/to a leaves of length 0 (zero)?

2. When jumping along a straight line, can this line touch the end of another leave or not?

Example:
1
2 7 5
1 3
4 3 3 2 1

is the output
6
or
4
?

[coze]

I keep getting WA. What's the output for the input:

Code: Select all

1
3 5 100
3 0 0 1
2 0 0
3 0 0 1

Thanks in advance.

[coze]

Finally, I got AC.
Input:

Code: Select all

1
3 5 100
3 0 0 1
2 0 0
3 0 0 1

AC output:

Code: Select all

0

To bobi1978.

Example:
1
2 7 5
1 3
4 3 3 2 1

is the output
6
or
4

My output is 6.