10412 - Big Big Trees
Moderator: Board moderators
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;
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;
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.
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.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
-
- 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
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
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.
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.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
-
- New poster
- Posts: 10
- Joined: Tue Nov 26, 2002 4:19 pm
-
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
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...
![:-)](./images/smilies/icon_smile.gif)
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...
-
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
-
- New poster
- Posts: 28
- Joined: Wed Jul 31, 2002 10:33 am
- Location: Ukraine
- Contact:
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??
Thanks in advance
( Found my mistake ( in my implementation) , thanks for reading![;-)](./images/smilies/icon_wink.gif)
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
![:wink:](./images/smilies/icon_wink.gif)
( Found my mistake ( in my implementation) , thanks for reading
![;-)](./images/smilies/icon_wink.gif)
-
- New poster
- Posts: 13
- Joined: Tue Jul 22, 2003 1:57 pm
- Location: Kavadarci, Macedonia
- 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
?
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
?
Re: 10412 - Big Big Trees
I keep getting WA. What's the output for the input:
Thanks in advance.
Code: Select all
1
3 5 100
3 0 0 1
2 0 0
3 0 0 1
Re: 10412 - Big Big Trees
Finally, I got AC.
Input:
AC output:
To bobi1978.
Input:
Code: Select all
1
3 5 100
3 0 0 1
2 0 0
3 0 0 1
Code: Select all
0
My output is 6.Example:
1
2 7 5
1 3
4 3 3 2 1
is the output
6
or
4