## 10412 - Big Big Trees

Moderator: Board moderators

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

### 10412 - Big Big Trees

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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions
I found out the problem it was with setting the limit for the line segment intersection check.

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

### I dont understand...

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
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm
Thanx......... i will try it ...........

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
I solved this problem in the contest, but failed after rejudgement.
Could somebody provide some I/O? Really appreciate your help!

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Thank you, Yarin.
I have made the same mistake as what you say. I never thought about it. Thanks again!!

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi!

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??

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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
I try to solve the question recently.
But I don't know what's wrong.
Could someone give some input/output?
Thank you

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Contact:

### WA

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
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

### Re: 10412 - Big Big Trees

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
``````

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

### Re: 10412 - Big Big Trees

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.