|Felix Halim .NET|
University Experience IOI 2002 Yong In, Korea ACM ICPC Regional Manila 2003 ACM ICPC Regional Manila 2004 ACM ICPC Regional Manila 2005 ACM ICPC Regional Kaohsiung 2006 ACM ICPC Regional Singapore 2007 ACM ICPC Regional Jakarta 2008 (ext) ACM ICPC Regional Jakarta 2009 (ext) ACM ICPC Regional Jakarta 2010 ACM ICPC Regional Jakarta 2012 - Problem H ACM ICPC Regional Jakarta 2013 - Problem J (new!) ACM ICPC World Final Tokyo 2007 Google India Code Jam 2005 Google India Code Jam 2006 Indonesia National Contest 2007 Indonesia National Contest 2008 Indonesia National Contest 2010 Facebook Hacker Cup 2011
Problem H - Alien Abduction
During the interview with the champion team (+1 ironwood branch), Pi-Hsun (Peter) Shih said that his favorite problem is problem H (this problem). I should've asked why did he like it? is it because of the problem statement? or because he had fun in writing the solution :). Anyway, this problem is set by me and I would like to tell you how this problem was created / prepared.
Initially, this problem was set to be "easier", that a simple K-d Tree or Quadtree solution will work fine. However, since Problem D is already using K-d Tree for finding the nearest neighbors, to give good variations to the problemset, I rewrote this problem so that it is NOT solvable using (static) K-d Tree nor Quadtree (unless you are able to code "dynamic" K-d Tree / Quadtree in contest time :P).
This problem is solvable using Range Tree. I taught Range Tree during Pelatnas (training camp) 3 TOKI 2012 to 8 of Indonesian students to prepare them for IOI 2012. There are several other students from University of Indonesia were present during the training camp and those same students were participating in ICPC Jakarta 2012. I was surprised that they didn't get this problem accepted in contest time!
I think Range Tree is a rare problem in programming contest. I won't discuss it in detail here, since it is a classic algorithm in computational geometry, you can search for it to learn more. Perhaps it will be included in the next version of the Competitive Programming Book. Rare problems like this usually become the "decider problems" that set apart teams at the top.
Many (inexperienced) teams were submitting naive (not even clever) brute-force solutions O(N*Q). Of course they will get "No - Time Limit Exceeded" reply. Then, they tried optimizing on reading the input more efficiently, optimize the loop, etc, but the complexity is still the same O(N*Q). This problem can be a time-waster for inexperienced teams. As the problem setter, I feel sorry for them.
I'd like to talk about how this problem was prepared, to give you an idea what is it like to be a problem setter. It took me a lot of time to prepare, especially for the test data since I have to kill off simple/clever brute-force solutions. Moreover, I have to kill off solutions using (static) K-d Tree and Quadtree :)
For the test cases, I prepared 4 types of tests:
There is one team I know (Azureus_HKU) using a clever brute-force that I didn't anticipate. They create a multimap for each x-coordinate, so for each x-coordinate they can know wheater there are people abducted in log(N), by binary searching the y-coordinate. But fortunately, the 3rd kind of testcase above also kills of this solution :). This clever brute-force algorithm can still run in O(1000*Q*log(N)) if the input is like this: all people are at coordinate between (0 <= Xi,Yi < 1000) and the alien abduction operations are at Xk = 5000, Yk = 0, Ek = 4000. What will happen is that each query, you need to scan/iterate all 1000 distinct X coordinate (and immediately find that the Y coordinate is not qualified). Thus it will need to iterate Q*1000*log(N) = 50000 * 1000 * 10 = TLE. It took 15+ seconds, while the Range Tree solution is around 5 seconds. BTW, the time limit for the problem is 10 seconds, which is quite generous :)
This is the input generator for problem H. You can try to test whether your bruteforce solution will pass the 10 second time limit. Remember to compile your C++ program WITHOUT using any optimizations.
So how does this Range Tree solution works? you asked. Well, we have to wait for our beloved chief of judge, Suhendry Effendy, to write a blog post about it. Please kindly remind him every now and then, because he often forgot to blog >:D.comments powered by Disqus