A fixed-parameter-tractable week

This week had quite a few competitions, culminating in the ultimate TCO elimination round where one had to place in top 4. But before we come to that, let's start with TopCoder SRM 695 on Tuesday (problems, results, top 5 on the left, my screencast).

The medium problem was from a relatively new but growing family of problems inspired by the theoretical concept of fixed-parameter tractability: you are given an undirected graph with at most 1000 vertices and at most 1000 edges, such that each vertex has at most three adjacent edges. Each vertex also has a weight, and you need to pick at most K edges maximizing the total weight of vertices covered by (adjacent to at least one of) the picked edges. The interesting aspect is that K is really small: at most 7. So you're allowed algorithms exponential in K, but polynomial in the size of the graph. Can you come up with one?

After a 30-minute break, Codeforces Round 363 followed (problems, results, top 5 on the left, my screencast, analysis). Some of the problems in this round were from the VK Cup onsite finals, but I've not yet seen the mapping between this round's problems and the onsite final round problems. Does anybody have it?

The hardest problem in this round was an great example of slowly and gradually (one might even say tediously :)) unwinding a problem, combining ideas from combinatorics and arithmetic - as opposed to problems that require just one, if brilliant, idea to be solved. The problem statement was relatively simple: we define a permutation of integers between 1 and n to be coprime, when a pair of its elements is coprime if and only if their 1-based indices are coprime. Given a partially filled permutation (some numbers known, some arbitrary), how many ways are there to complete it as a coprime permutation?

Codeforces Round 364 on Friday was also based on VK Cup onsite finals problems (problems, results, top 5 on the left). Ainta has solved the very difficult problem D in just under 40 minutes, and was able to cruise to an easy victory afterwards. Congratulations!

I'm still curious how to solve even more difficult problem E, as string problems were always my weak spot and I'd love to learn more about them. You are given a string with 200000 characters. You need to form the longest possible sequence of strings starting with the given string, and such that each following string appears as a substring at least twice in the preceding string (those two occurrences may partially overlap).

And finally, we come to TopCoder Open 2016 Round 3A, where only top 4 participants would earn a spot in the onsite competition (problems, results, top 5 on the left, my screencast). In the aftermath of this round, an interesting discussion about appropriate problems for high-level tournament round ensued. What's your view?

I've enjoyed all three problems in this round, but the 250 seems to be the most well-received by everybody. You are given a permutation of integers between 0 and 2n-1. You need to come up with any balanced parenthesis sequence that stays balanced when we apply the given permutation to it (i.e., if the 5-th element of the permutation is 9, then the parenthesis on position 5 of the first sequence moves to position 9 in the second sequence). n is up to 25.

Thanks for reading, and check back next week!

Tweet