Page 2 of 6

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

Posted: Wed Mar 08, 2006 9:04 am
by StatujaLeha
deleted by author

Posted: Wed Mar 08, 2006 3:11 pm
by 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

Posted: Wed Mar 08, 2006 7:51 pm
by arsalan_mousavian
can some body give me a hint about solving this problem with DP ?
thanx

Posted: Wed Mar 08, 2006 8:24 pm
by 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

Posted: Wed Mar 08, 2006 9:28 pm
by Darko
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

Posted: Thu Mar 09, 2006 9:30 am
by 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...

Posted: Thu Mar 09, 2006 12:33 pm
by StatujaLeha
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

Posted: Thu Mar 09, 2006 3:33 pm
by 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 ?

Posted: Thu Mar 09, 2006 5:45 pm
by StatujaLeha
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.

Posted: Thu Mar 09, 2006 6:11 pm
by Abednego
Your algorithm is wrong.

Posted: Thu Mar 09, 2006 6:47 pm
by 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.

Posted: Thu Mar 09, 2006 6:54 pm
by Abednego
Just looking at the name of the
problemsetter you should rule out such a possibility.
:-) Thanks, Ivan.

Posted: Thu Mar 09, 2006 7:18 pm
by 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).

taking too long..

Posted: Sun Mar 12, 2006 3:25 pm
by 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.