JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm NICEDAY @ SPOJ
 Re: NICEDAY @ SPOJ (response to post by innocentboy) | Reply Imagine the contestants as points in 3D space.B is worse than A iff all three his coordinates are greater than A's iff point B is in the correct octant centered at A.Sort the points according to Z coordinate (the third contest).Now we will do some sweeping according to the Z axis, starting at 0.Whenever you encounter a contestant during the sweep, you have already seen all contestants that can possibly be better than him. (The other ones have a larger Z coordinate.) Thus at this point you can decide whether this contestant is excellent.To do this efficiently we need to realize the following fact:Fix the Z coordinate. For a single contestant that we already processed, the set of coordinates of worse contestants looks as follows:```| | worse | | contestants | A------------- | | | 0----------------- ```For more contestants the set is the union of these sets:```| | | B-- | | worse | | contestants | A------| D | | | C------ | 0----------------- ```Once we encounter a new contestant during the sweep, there are two possibilities: Either he lies inside the set, or not. In the first case the contestant is eliminated immediately as he is not excellent and can not influence anything in the future. In the second case we will update the coastline. This includes adding the new point, and possibly removing some points that don't lie on the coastline any more:```| | | B- | | worse | | contestants | |A D | | | | C | E-------------- 0----------------- ```To do both operations efficiently, keep the coastline as its vertices stored in an STL set. To process a new point you first search for it in the set to find the corresponding part of the coastline, check whether it is eliminated, and if not, erase the points it covers and add it to the set.This is an O(N log N) solution and the set is the only non-trivial data structure in the program.See http://www.algorithmist.com/index.php/LA_3525 for a similar task.
 Subject Author Date NICEDAY @ SPOJ innocentboy May 9, 2007 at 2:31 AM EDT Re: NICEDAY @ SPOJ misof May 9, 2007 at 2:56 AM EDT Re: NICEDAY @ SPOJ innocentboy May 9, 2007 at 4:12 AM EDT Re: NICEDAY @ SPOJ nikhil-garg Dec 26, 2009 at 5:18 PM EST Re: NICEDAY @ SPOJ misof Dec 26, 2009 at 7:34 PM EST Re: NICEDAY @ SPOJ nikhil-garg Dec 26, 2009 at 8:09 PM EST Re: NICEDAY @ SPOJ pagal_123 Jun 26, 2013 at 11:04 AM EDT Re: NICEDAY @ SPOJ fushar Dec 27, 2009 at 5:14 AM EST Re: NICEDAY @ SPOJ nikhil-garg Dec 27, 2009 at 10:45 AM EST Re: NICEDAY @ SPOJ fushar Dec 27, 2009 at 6:14 PM EST Re: NICEDAY @ SPOJ nikhil-garg Dec 27, 2009 at 6:22 PM EST Re: NICEDAY @ SPOJ fushar Dec 27, 2009 at 6:46 PM EST Re: NICEDAY @ SPOJ fushar Apr 12, 2010 at 8:43 PM EDT Re: NICEDAY @ SPOJ ikatanic Apr 13, 2010 at 10:31 AM EDT Re: NICEDAY @ SPOJ fushar Apr 13, 2010 at 10:45 AM EDT Re: NICEDAY @ SPOJ ikatanic Apr 13, 2010 at 12:08 PM EDT
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm NICEDAY @ SPOJ Previous Thread  |  Next Thread