September 15, 2017 TCO17 Algorithm Round 3B Recap

OVERVIEW

TCO Round 3B was last regular online round of TCO 2017 Algorithm Competition. qwerty787788, Um_nik, ikatanic, rng_58 and RRx qualified to the onsite competition, congratulations!

250 pts – ChromosomalCrossover

Here you are given 2 strings, A and B, and can do following operation unlimited number of times: select prefixes of A and B of the same length and exchange them. What if the maximal achievable length of common substring of A and B? Note that using this operations we can just for any position exchange corresponding letters in A and B. Let us find for all possible pairs of starting positions (i, j) what is the maximal achievable common substring starting in this positions. There are 2 cases:

• i = j. In this case any exchanges would be pointless and we can just check answer for original A and B.
• i ≠ j. We can assume i < j as we can easily exchange whole strings. Now let’s go from left to right. For each position k we will store set S[k] of values A[k] (after exchanges) can be. Initially S[k] = {A[k], B[k]}. Now for each x starting from 0 we would look at S[i + x] and {A[j + x], B[j + x]}. If intersection of this sets is empty then x is length of the longest common string possible for starting positions (i, j). Otherwise if set {A[j + x], B[j + x]} has 2 elements and its intersection with S[i + x] is one element we should update S[j + x] to {A[j + x], B[j + x]} \ S[i + x].

You can look up my solution for details.

500 pts – FoxAndNecklace

Here we have N marbles each with different color and associated values and we want to construct at least d different necklaces of size k with total value of at least minimalSum. Is it possible?
Now every set of k marbles would produce (k – 1)! / 2 different necklaces, so we would divide d by this number (rounding up) and now have to answer if we can find that many sets with at least minimalSum value.
One way to do this is notice that if k relatively big d will be relatively small, and we can just backtrack with early exit if minimalSum is already not achievable. This works for k >= 8.
If k <= 7 we can use different “meet in the middle” techniques to calculate number of good subsets. For example we can generate all sets of size up to k – 1 from first half of marbles, likewise for the second half and then match them, applying the same algorithm for each part afterwards.
ikatanic’s solution provide implementation of this approach.

900 pts – Permatch

Suppose we have several rooks on chess board. If we divide them into pairs such that rooks in each pair are either in same row or column we call this a match. We call match perfect if there is exactly one way to do it. Can we add some rooks so there is a perfect match? And if we can what is the minimal number of rooks to add?
Let’s have a bipartite graph with vertices of left part corresponding to rows and vertices of right – to columns. We will connect row and column by edge if there is a rook on their intersection. Which graphs produce perfect match? There are 3 conditions:

• Graph is a forest (i. e. each component is a tree), otherwise of there is a match it is not unique.
• Each component has odd number of vertices.
• If we root a tree in arbitrarily for each vertex there are at most 2 children vertices whose subtree size is odd.

We need to add some edges to our graph so all conditions are met. for this we would use dynamic programming on subsets of components. See rng_58’s solution for details.