Posted:

**Wed Mar 08, 2006 9:03 am**...deleted by author

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=33&t=10093

Page **2** of **6**

Posted: **Wed Mar 08, 2006 9:03 am**

...deleted by author

Posted: **Wed Mar 08, 2006 9:04 am**

deleted by author

Posted: **Wed Mar 08, 2006 3:11 pm**

- Please please please don't post 58 kbs posts because they will surely slow the forums a lot and its a nightmare to see what the post is abut. You can use sites, where you can upload small files for free. Just now i can't find one, although i have used them

- When doing test cases be sure they are good. I run yours and there are almost all 1s so i really doubt you will find something there. Try to upload new testcases where the points lie close together (so the probability that two are collinear is much bigger) and i will run them

- When doing test cases be sure they are good. I run yours and there are almost all 1s so i really doubt you will find something there. Try to upload new testcases where the points lie close together (so the probability that two are collinear is much bigger) and i will run them

Posted: **Wed Mar 08, 2006 7:51 pm**

can some body give me a hint about solving this problem with DP ?

thanx

thanx

Posted: **Wed Mar 08, 2006 8:24 pm**

but if i upload test cases to other sites it will be deleted after some time and other users will not be able to use them.- Please please please don't post 58 kbs posts because they will surely slow the forums a lot and its a nightmare to see what the post is abut. You can use sites, where you can upload small files for free. Just now i can't find one, although i have used them

Each of test cases contains 16 trees, but only 8 various trees, that is each tree is included in test case twice. I want to check up working of my program when test cases contains each tree twice.- When doing test cases be sure they are good. I run yours and there are almost all 1s so i really doubt you will find something there. Try to upload new testcases where the points lie close together (so the probability that two are collinear is much bigger) and i will run them

16

12

540 958

901 979

540 958

901 979

758 725

664 899

758 725

664 899

848 602

636 114

848 602

636 114

284 491

829 764

284 491

829 764

Posted: **Wed Mar 08, 2006 9:28 pm**

I kinda agree with you there, but you might try using tiny font or something, these test cases are great thread-killers.StatujaLeha wrote:but if i upload test cases to other sites it will be deleted after some time and other users will not be able to use them.- Please please please don't post 58 kbs posts because they will surely slow the forums a lot and its a nightmare to see what the post is abut. You can use sites, where you can upload small files for free. Just now i can't find one, although i have used them

Darko

16

12

540 958

901 979

540 958

901 979

758 725

664 899

758 725

664 899

848 602

636 114

848 602

636 114

284 491

829 764

284 491

829 764

Posted: **Thu Mar 09, 2006 9:30 am**

The answer for the last input posted by Statuja Leha should be

Case #1:

1

(from an AC code).

Hope this helps.

PS I don't know if such an input is valid...

Case #1:

1

(from an AC code).

Hope this helps.

PS I don't know if such an input is valid...

Posted: **Thu Mar 09, 2006 12:33 pm**

for this input?Ivan wrote:The answer for the last input posted by Statuja Leha should be

16

12

540 958

901 979

540 958

901 979

758 725

664 899

758 725

664 899

848 602

636 114

848 602

636 114

284 491

829 764

284 491

829 764

Posted: **Thu Mar 09, 2006 3:33 pm**

Yes, my accepted code outputs 1, but the reason is that the above input

is not valid.

Maybe it's a better idea to discuss your algorithm ?

is not valid.

Maybe it's a better idea to discuss your algorithm ?

Posted: **Thu Mar 09, 2006 5:45 pm**

I use greedy algorithm: i cut the most possible quantity of trees at each step.Ivan wrote:Maybe it's a better idea to discuss your algorithm ?

Posted: **Thu Mar 09, 2006 6:11 pm**

Your algorithm is wrong.

Posted: **Thu Mar 09, 2006 6:47 pm**

Greedy?

Did you expect such a piece of cake? Just looking at the name of the

problemsetter you should rule out such a possibility. Additional hint -

there are only 16 trees (a problem intended to be solved greedily

would have at least a few hundred trees).

Actually the problem involves:

1. Geometry

2. DP approach (memorization).

3. Use of a binary mask (as a boolean array - each line defined as an

16-bit integer - either contains a given point or not).

Hope this helps.

Did you expect such a piece of cake? Just looking at the name of the

problemsetter you should rule out such a possibility. Additional hint -

there are only 16 trees (a problem intended to be solved greedily

would have at least a few hundred trees).

Actually the problem involves:

1. Geometry

2. DP approach (memorization).

3. Use of a binary mask (as a boolean array - each line defined as an

16-bit integer - either contains a given point or not).

Hope this helps.

Posted: **Thu Mar 09, 2006 6:54 pm**

:-) Thanks, Ivan.Just looking at the name of the

problemsetter you should rule out such a possibility.

Posted: **Thu Mar 09, 2006 7:18 pm**

I believe that algorithm is O(n^2 * 2^n) but it can be improved to O(n * 2^n) with bitmasks. (actually it just replaced the constant with a smaller constant).

Posted: **Sun Mar 12, 2006 3:25 pm**

I got AC, but took over 6 seconds..

I basically use O(n^3) to find out all the sets of colinear points, none of which is a subset of any other colinear points. ie if i have trees(1 3 5), then i don't consider trees(1 3).

Then I run a O(n^2*2^n) dp.

Is there any better solution than this..

.. obviously there is !!

Some got AC, taking less than 0.010 secs of time.

Some help would be appreciated.

I basically use O(n^3) to find out all the sets of colinear points, none of which is a subset of any other colinear points. ie if i have trees(1 3 5), then i don't consider trees(1 3).

Then I run a O(n^2*2^n) dp.

Is there any better solution than this..

.. obviously there is !!

Some got AC, taking less than 0.010 secs of time.

Some help would be appreciated.