11008 - Antimatter Ray Clearcutting

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

Moderator: Board moderators

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Wed Mar 08, 2006 9:03 am

...deleted by author
Last edited by StatujaLeha on Wed Mar 08, 2006 9:06 am, edited 1 time in total.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Wed Mar 08, 2006 9:04 am

deleted by author
Last edited by StatujaLeha on Mon Mar 13, 2006 3:18 pm, edited 5 times in total.

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » 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
Impossible is nothing

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Wed Mar 08, 2006 7:51 pm

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

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Wed Mar 08, 2006 8:24 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
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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Mar 08, 2006 9:28 pm

StatujaLeha wrote:
- 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
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

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

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Thu Mar 09, 2006 12:33 pm

Ivan wrote: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
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » 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 ?

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Thu Mar 09, 2006 5:45 pm

Ivan wrote: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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Mar 09, 2006 6:11 pm

Your algorithm is wrong.
If only I had as much free time as I did in college...

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Mar 09, 2006 6:54 pm

Just looking at the name of the
problemsetter you should rule out such a possibility.
:-) Thanks, Ivan.
If only I had as much free time as I did in college...

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

taking too long..

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

Post Reply

Return to “Volume 110 (11000-11099)”