11008 - Antimatter Ray Clearcutting
Moderator: Board moderators
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
...deleted by author
Last edited by StatujaLeha on Wed Mar 08, 2006 9:06 am, edited 1 time in total.
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
- 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
Impossible is nothing
- arsalan_mousavian
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
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
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
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
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.
taking too long..
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.