Coding Practice: Day 1

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.

Coding Practice