11008 - Antimatter Ray Clearcutting

[StatujaLeha]

...deleted by author

[StatujaLeha]

deleted by author

[tywok]

- 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

[arsalan_mousavian]

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

[StatujaLeha]

- 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

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.

- 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

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.

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

[Darko]

- 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

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.

I kinda agree with you there, but you might try using tiny font or something, these test cases are great thread-killers.

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

[Ivan]

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

[StatujaLeha]

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

for this input?

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

[Ivan]

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 ?

[StatujaLeha]

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

I use greedy algorithm: i cut the most possible quantity of trees at each step.

[Abednego]

Your algorithm is wrong.

[Ivan]

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.

[Abednego]

Just looking at the name of the
problemsetter you should rule out such a possibility.

:-) Thanks, Ivan.

[sclo]

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).

[sohel]

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.