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 AbductionDuring the interview with the champion team (+1 ironwood branch), PiHsun (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 Kd Tree or Quadtree solution will work fine. However, since Problem D is already using Kd 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) Kd Tree nor Quadtree (unless you are able to code "dynamic" Kd 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) bruteforce 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 timewaster 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 bruteforce solutions. Moreover, I have to kill off solutions using (static) Kd Tree and Quadtree :) For the test cases, I prepared 4 types of tests:
There is one team I know (Azureus_HKU) using a clever bruteforce that I didn't anticipate. They create a multimap for each xcoordinate, so for each xcoordinate they can know wheater there are people abducted in log(N), by binary searching the ycoordinate. But fortunately, the 3rd kind of testcase above also kills of this solution :). This clever bruteforce 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 