Member Count: 484,755 - May 25, 2013  [Get Time]
 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=4089I 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/#ioEDIT3: 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=3512BTW 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

 Home  |   About TopCoder  |   Press Room  |   Contact Us  |   Careers  |   Privacy  |   Terms Competitions  |   Cockpit Copyright TopCoder, Inc. 2001-