I tried the 2.5-hour Round 1A Friday night and just missed the cut-off for advancing. The round started a few minutes late as the problems site was overloaded at first. When it did respond, I got the problems in a different order, with the last problem listed first. Thinking it was the first (and therefore easiest) problem, I started on it without noticing the difficulty scores. That “Alien Rhyme” involved finding pairs of words with common suffixes. There were a few gotchas to the greedy approaches, so I was lucky to work out a correct algorithm, but it took me a few tries to get a decent data structure for organizing the words by common suffixes. I ended up with a vector of maps, one per suffix length with each map itself mapping a suffix to a set of words. Amazingly, it worked.

Next I tried the Pylons problem which boiled down to finding a complete path through a graph. I couldn’t think of a good approach for the large 20×20 constraint, so I went for partial credit with a brute force solution which would work for the small 5×5 constraint. After that was submitted I noticed that the large graphs were dense enough to have many complete paths, so maybe a randomized brute force approach would work. I added a little randomization and resubmitted. It turned out I had the right idea, but I didn’t randomize it enough (only the starting points and not the node visitation order). So I still only got partial credit, but with a penalty for making a second submission.

The remaining problem was an interactive one and I had too little time left for the overhead of testing it locally, so I didn’t attempt it. I could see that the solution may require solving a Chinese Remainder problem, and I did solve it the next day. It’s nice that the site enters practice mode when the competition is over, so we can test out ideas later.

The good news is that I get to compete in Round 1B!