2018 ICPC World Finals

May 2, 2018, 12:40 pm

The ICPC World Finals in Beijing just wrapped up, and I had the great privilege of representing the University of Texas with my teammates, Arnav Sastry and Daniel Talamas. This was the first time any of us competed at the World Finals, and it was an amazing experience.

My team didn't perform as well as we'd hoped, but we didn't do embarrassingly poorly either. We ended up solving four problems (out of eleven) and placing 65th (of 140). Here, I'll write a brief summary of our experience in the competition.

Getting started

When the countdown finished, Arnav logged into the computer and handed me the problem packet. While Arnav was writing our .vimrc, .bashrc, and template, I started reading the problems front-to-back while Daniel read back-to-front. I told Arnav that B looked like an implementation problem, and, being the fastest typist on our team, he took a look and started coding.

While Daniel and I continued reading problems, other teams got accepted verdicts on three problems: F, B, and K. I diverted my attention to K.

First AC

While Arnav coded B, I came up with a greedy constructive algorithm for K. Soon I convinced myself of its correctness, and as soon as Arnav submitted B I took the keyboard to code K. Arnav's solution to B got accepted, and we celebrated our quick AC. The solution to K was relatively simple to implement, and it was finished in just a few minutes. Passing samples, I asked Daniel for a sanity check on my idea and submitted K.

Seventh place

Arnav got back in the hot seat and began coding a solution to G using Java's AWT library. Geometry has historically been our weak point, but we know how to do basic things like polygon union and intersection using this library. In the past we have gotten some tricky geometry problems with this trick, so with nothing else to code we decided it was worth a shot. We didn't have high hopes, because at this point no other team had gotten G.

In the meantime, our K solution got accepted, and we rose to 7th place on the leaderboard.

Arnav finished our solution to G, and running on samples it was nowhere near accurate enough. The sample output was 50, and our code gave 49.997. With no ideas for a real solution, we gave up on G for the time being.

DP on edges

At this point, Daniel figured out the solution to A: a DP on edges. He explained it to me, and I started to code, but he preempted me and coded it himself. Unfortuately, the code failed samples, and it took us a very long time to find the bug: in our DFS, we forgot to update the memoization table.

While Daniel tried to find his bug, Arnav worked on F (the apparent next easiest problem) and I worked on C. I mistakenly thought that some team had already gotten AC on C, and I had an idea that I thought could work. As I wrote pseudocode, it became clear that my idea had a big flaw, and Daniel pointed out that no one else had C, so I abandoned it.

Arnav was unsure if his solution to F would run in time. He coded it anyway, and it gave wrong answer. Daniel found his bug in A and submitted, getting accepted.

Time limit squeezing

We knew that if we could get F, H and I were our next best bets. Unfortunately, even after finding an edge case and fixing a bug in F, we got TLE. After some more optimizations, we got another TLE; after one more, WA. Finally, we fixed that bug and got AC, but with a massive penalty for wrong submissions. We found out after the contest that some teams wrote a solution without the optimizations we included, but broke early when nearing the time limit, and these solutions got AC as well. I'm very impressed by the teams that got F on their first attempt!

H is for hard

H was another geometry problem: find the minimum number of line segments you need to use to cut every wire going across a rectangular door (also given as line segments). Arnav and I realized quickly that you can always do it in two cuts, so all that is needed is to check if it is possible in one. Thinking what remained would be easy, we focused our attention on H rather than I, the other problem that may have been within reach.

This turned out to be a mistake. We spent the last two hours trying to get H, with only a few wrong attempts and wrong conjectures. In hindsight, our strengths were much more in favor of I. Nonetheless, while Arnav and I coded H, Daniel thought about I.

The hard part of H (like many geometry problems) is finding the right WLOGs: there were up to \(10^6\) line segments, so the obvious \(O(N^2)\) sweep line approach doesn't work. We needed some way to reduce the runtime.

We guessed that our cut should always link two opposing sides, and we tried an approach that produced four candidate line segments and then checked all of them. Although it passed every case we could think of, it gave WA when we submitted.

The worst part: we still don't know how to solve it. We figured out I on the plane ride back to the States, but H still eludes us. I fear that I will be haunted by this problem forever.

Wrapping up

We spent the last 10 minutes speed-coding a solution for H based on another (incorrect) conjecture, but we couldn't finish in time and so we didn't get to submit it.

We were disappointed to have only solved four problems, but we had a great time at the contest. The problems were generally interesting, and I hope to return next year, wherever it ends up being!

K revisited

My favorite problem of the set was K (probably because I solved it). You are given a graph with \(N\) vertices and \(M\) edges, and you want to construct a tree with \(N\) vertices that minimizes the number of nodes whose degrees differ from their respective degrees in the original graph.

The obvious greedy thing to do is write down the degrees of each node, and, while the sum of the degrees is greater than \(2N - 2\), cut the largest degree down to \(1\) (or to some other value if changing it to \(1\) would remove too many edges).

The question is: given our new degree sequence, can we construct a tree with these degrees?

My approach was to sort the nodes again by their new degrees, and build a rooted tree. We keep a stack of nodes who don't have parents, and for a node \(u\) with degree \(d\) we pop \(d - 1\) nodes from the stack and assign them parent \(u\). We must special case the root.

It was not immediately obvious that this process never gets stuck (tries to pop from an empty stack). While Arnav coded B, I came up with a nifty proof. Let \(D\) be the degree sequence. If we are trying to add node \(k + 1\), the number of nodes currently in our active stack is \(k - \sum_{i=1}^{k} (D[i] - 1)\). Simplifying, this is \(2k - \sum_{i=1}^{k} D[i]\).

We want to show that this is always at least \(D[k + 1] - 1\). Rearranging, we want

\[\sum_{i=1}^{k+1} D[i] \leq 2k + 1\]

for all \(k\).

We can't prove this using standard induction, because when we are partway through the process we don't know anything about the future degrees. In fact, the only restriction on the future degrees is that the sum of all degrees is \(2N - 2\).

But then the claim is obvious for \(k = N - 1\): \(\sum_{i=1}^{N} D[i] = 2N - 2 \leq 2N - 1\). The off-by-one here is because we want a slightly stronger claim for the last node (because the root does not get a parent). But we satisfy this stronger claim too.

For \(k = 0\), the claim is obvious as well: the first degree must be \(1\), since the degrees are sorted and if all degrees are at least \(2\) the sum of degrees must be at least \(2N > 2N - 2\).

So the partial sum of degrees is under the linear function at the beginning and at the end. How can we show that it is under the linear function along its entire domain?

Since we ordered the degrees in increasing order, the partial sum of degrees as a function of \(k\) is convex! A convex function always stays under the line connecting two points on its graph. This completes the proof that the construction works for any degree sequence with the right sum, including the greedy sequence we found earlier.

The other problems of the set were also interesting, but this was the one from which I learned the most.

It's been a while since I posted on this blog, so hopefully I start doing that more in the coming months. I probably won't, but I will try. Thank you for reading!