10412 - Big Big Trees

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10412 - Big Big Trees

Post by 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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan »

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
Location: Canada
Contact:

Post by 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
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

I dont understand...

Post by 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
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by 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
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

Post by jaivasanth »

Thanx......... i will try it ........... :)

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

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:

Post by 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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

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

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

Post by 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. 8)

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by 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 :wink:


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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by 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
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

WA

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

Re: 10412 - Big Big Trees

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

Re: 10412 - Big Big Trees

Post by 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.

Post Reply

Return to “Volume 104 (10400-10499)”