A week with 4x4

TopCoder Open 2015 Round 3A took place on Saturday (problems, results, top 6 on the left). First 6 places in the onsite competition in Indianapolis were handed out to those who could solve either the medium or the hard problem, with another 6 selected in Round 3B that will take place in two weeks. According to the official website, we will have a semifinal round and a final round onsite, but the number of advancers from the semifinal isn't known yet. A similar structure was used in 2009, with 18 onsite participants competing in a single semifinal and 8 qualifying to the final. Scaling that down to 12 onsite participants means we'd have 5 contestants in the final, but of course only TopCoder knows for sure.

The hard problem has left me stunned: how come such simple question has never been studied before, and yet requires a complex but doable solution? The problem simply asked about the number of AxB rectangles of 0s and 1s such that each CxD subrectangle contains the same number of 1s. C and D are up to 4, so the subrectangle is very small, but A and B are up to a billion.

Coming back to a problem I mentioned last week: given a tree and a vertex selected in it, what's the maximum number of different vertices a walk of a given length L starting from the given vertex can visit?

The main idea of the solution is that walks in a tree do not have a lot of freedom. More specifically, if a walk in a tree starts and ends in the same vertex, then it traverses each edge an even number of times - for each step "down" there's a corresponding step "up", which in turn means we traverse each edge either 0 times or at least twice. Because of this, a cyclic walk of length L visits at most L/2 different vertices in addition to the starting/ending vertex. Suppose now that the walk is not cyclic, going from some vertex A to another vertex B. Again, since walks in a tree do not have a lot of freedom, it's not hard to see that this walk can be represented as the direct walk from A to B along the tree, plus some cyclic walks inserted into it, so we get 1 new vertex per edge when walking from A to B, and 0.5 new vertices per edge when walking along the cycles, and the maximum number of different visited vertices is 1+d+(L-d)/2, where d is the distance between A and B. Now it's clear that we should simply pick B to be as far from A as possible, but at most L edges far.

Thanks for reading, and check back next week!