Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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
RSS