Register Now
Member Count: 484,755 - May 25, 2013  [Get Time]
Login
forums   
Round Tables
News Discussions
Algorithm Matches
Marathon Matches
NASA Tournament Lab
Software Forums
TopCoder Cookbook
High School Matches
Sponsor Discussions
Search Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Forums Round Tables Educational Discussion Africa -Middle East 2007/2008 - Incidental points (4089)
Africa -Middle East 2007/2008 - Incidental points (4089) | Reply
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4089
I just spent the whole morning trying to find out why my code gives WA, I even tried comparing the results from the bruteforce algorithm (which times out) with the one I am using right now on random input.

To explain what I am doing:
- I group all pairs of points by their slope.
- I count the pairs of a certain slope that contain each point.
- The result is max(count) + 1.
- I am using a fraction to store the slope to prevent precision errors.

(code in edit)
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by vexorian) | Reply
I passed it with the same approach. But i am getting TLE on PKU-OJ.
Can anyone describe faster algorithm, i think mine is O(N^2lg N).

Code in edit.

EDIT2: You can find the test cases here.

http://www.icpc-anarc.org/yr/2007/#io

EDIT3: Your code gives MLE not WA.
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by kemo) | Reply
Well, tested against that input and the output is identical, but the online judge in which I've been testing my solution (the one I linked to) was giving me WA , well, it would be a little lame if it always said wrong answer when it was actually a MLE.

Edit: Doh, the first time it gave me a WA because I didn't consider negative input correctly, the next few times it was MLE or time out, but I wasn't checking at the status area but at my email and it it was saying Wrong Answer even while in the status area it was really a MLE...
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by kemo) | Reply
It can be faster if you implement it with array, and each time you sort the angle of the point from specific point, but I got wa, with that implementation.
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by Arsalan) | Reply
You can find the judge's test cases here
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by vexorian) | Reply
After some WA, I passed after I handled overflow.
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by mostafa_saad) | Reply
I had to do a lot of stuff, after I changed it to just store slope and lower point and just do counts there, that fixed the MLE but it was TLE, I had to find my hash class in my personal library, forgot how bad STL is for uva... TC spoils us too much...
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by vexorian) | Reply
I feel you did many staff, although it do not need.
Here is a simple code that passes this problem & (270 at UVA)

For a better time, you just implement the same idea in a better way.

code in edit.
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by Arsalan) | Reply
Thanks a lot that was faster.
AC on TJU-OJ but still TLE on PKU-OJ.
My AC code in the edit.
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by kemo) | Reply
Can you give me this problem URL at PKU to try with it?
Re: Africa -Middle East 2007/2008 - Incidental points (4089) (response to post by mostafa_saad) | Reply
http://acm.pku.edu.cn/JudgeOnline/problem?id=3512

BTW there is a search option on PKU OJ.

Thanks.
Forums Round Tables Educational Discussion Africa -Middle East 2007/2008 - Incidental points (4089)
Previous Thread  |  Next Thread
RSS