Day 2

Problems
https://www.spoj.pl/problems/ALL/
https://www.spoj.pl/problems/PQUEUE/
https://www.spoj.pl/problems/PPATH/
https://www.spoj.pl/problems/LINELAND/

Notes

• Three easy problems and one pretty hard problem. The three easy ones were all pretty much simulation or simple BFS.
• One thing I realized was that I've been implementing queues (e.g. when doing a BFS) as vectors, and just traversing the whole thing. It's much more efficient to just use the STL queue, so there isn't as much wasted space. I'm too used to using vectors...
• The tough problem was LINELAND (there wasn't even a solution on the NWERC '06 site, which was the source of the problem). My solution was basically just to try placing the segment of lenght L starting at all the x values of the given points, then do a ternary search between every consecutive pair of x values. Here, I augmented the list of possible x values by adding x[i] - L to take into accounting the segment of length L ending at x[i]. It's not too hard to show that the area is piece-wise quadratic, so this works.
• An interesting note is that while I could've just solved all those quadratics (would've made the solution faster? too many cases, though) it was much easier to just implement the ternary search. The hard part was dealing with double precision when you're at the corners.
• I noticed I'm getting into the habit of optimizing problems I've solved, coming up with heuristics to speed them up, etc. It means I won't be able to work on as many problems as would otherwise, but I'm learning more this way :)

More Notes

• So, I made a few more optimizations to LINELAND. For finding the left and right boundary points for the segment of length L at a given position, I just binary searched. Learned something subtle about the difference between finding a lower/upper bound (a +1 index difference). More importantly, I got to implement the sqrt(N) solution to range min queries. Got this about 7x faster.

References
http://www.csc.kth.se/contest/nwerc/2006/
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Day 1

Problems
http://www.spoj.pl/problems/MBEEWALK/
http://www.spoj.pl/problems/PARTIT/
http://www.spoj.pl/problems/EMPTY/
http://www.spoj.pl/problems/GARDENAR/
http://www.spoj.pl/problems/MDOLLS/

Notes

• C++'s STL pair (in the utility header) is generally faster than manual encoding for integers, e.g. using a pair<pair<int, int>, int> to represent a triple vs. using a long long to encode 3 integers in [1..10^6]. Using pairs makes it easier to implement too... tried this on EMPTY.
• The minimum number of chains needed to cover a poset is equal to the maximum size of an antichain in a poset (Dilworth's theorem). This came up in MDOLLS surprisingly. More generally, you can find a minimum path cover in a directed, acyclic graph by reducing it to bipartite matching. This approach was probably too slow for the problem though, even with something fancy like Hopcroft-Karp. I should learn to implement that regardless.
• Using heuristics can make asymptotically slower algorithms (compared to the intended solution) run in time. This didn't actually come up, but I got a 50x speedup on EMPTY just from removing the points that obviously can't be on the edge of the cuboid.
• A quick way to work out the details in a DP is to check edge cases and extrapolate the indices. Makes coding up problems like PARTIT faster.
• The other two problems were relatively straightforward -- MBEEWALK was a simple DP and GARDENAR just involved finding a closed form expression for the answer.
  

References
http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
http://www2.cs.science.cmu.ac.th/person/rogaway/ps3-solns.pdf

The Plan

So, I've decided to start this blog (mainly) in preparation for the ACM ICPC World Finals in Harbin, China this February. I haven't really done any serious contest coding since senior year of high school, so this should be fun.

My training philosophy at this point is basically to just do as many problems as I can. My primary source of problems will be SPOJ, though I'll probably write a blog entry about other sources of problems at some point. I'll remember the problems I do, so there's not much benefit in taking a more organized approach to choosing problems to work on. Time spent on easy problems won't be wasted, since they won't take long and will help with speed/accuracy. Moreover, time spent on hard problems is always good, even if I don't come up with a solution right away.

That being said, I doubt I'll be choosing problems completely at random. The goal is to look at a few non-trivial problems (number of accepted users helps) and work on whatever seems interesting. Once in a while, I'll reflect on what topics need more work and adjust myself accordingly.

Feel free to chat with me if you want to discuss or compare solutions, etc. :)