Random problems

As discussed in the previous post, my latest Code Jam problem pointed at approximate algorithms right from the statement: you are given a rooted forest with at most 100 vertices, and consider all valid permutations of its vertices. A permutation of vertices is valid if every non-root vertex comes after its parent. Additionally, each vertex is assigned a letter, so each permutation induces a string when we write all those letters in the order of the permutation. Which fraction of valid permutations induce a string that contains the given substring? Your answer doesn't need to be very precise: an error of 0.03 is allowed.

We need to estimate a fraction that's between 0.0 and 1.0 with an error of 0.03 allowed - that doesn't sound very precise. In fact, that's just 17 times more precise than simply always answering 0.5 :) That allows us to use the Monte-Carlo approach: pick k independently and uniformly sampled valid permutations, find out the number m of them that contain the given substring, and output m/k as the answer.

There are two things still unclear about this solution: how large does k need to be to make the error small enough, and how to uniformly sample valid permutations.

k independent samples from a Bernoulli distribution is called a binomial distribution, and we can use its cumulative distribution function to estimate the required k. However, there's a simpler approach that works for virtually any distribution: the Central Limit Theorem. It says that for moderately large values of k the mean of k random values sampled independently from the same distributions is almost like a normal distribution with mean equal to the mean of each random value, and standard deviation equal to the standard deviation of each random value divided by the square root of k.

Each random value in our case is equal to 1 with some unknown probability p, and to 0 with probability 1-p. Its mean is thus p, and its standard deviation is sqrt(p*(1-p)), which is at most sqrt(0.5*0.5)=0.5. The standard deviation of the mean of k such values is thus 0.5/sqrt(k), and by the theorem it's distributed almost normally. For the normal distribution we know the probability that it will be off its mean by the given number of standard deviations. For example, it's within 6 standard deviations of its mean with probability roughly 1 in 500 million. 6 standard deviations is at most 3/sqrt(k), and thus picking k=10000 makes 6 standard deviations lie within the allowed 0.03 error.

Of course, the Central Limit Theorem can't always be blindly applied - one must understand what's going on. For example, note that the error probability of 1 in 500 million is for one number. Since the problem has actually asked you to compute 500 such numbers, the probability of going outside the allowed 0.03 error in at least one of them could only be bounded by 1 in a million, which is still a pretty remote chance - but one has to keep this point in mind when using the theorem. For example, picking k=1000 in our problem means that 0.03 would correspond to roughly 2 standard deviations, so we'd give an answer within allowed error with probability at least 95%, which sounds good enough to submit. However, since we need to compute 500 numbers and not just one, the probability that all of them will stay within 2 standard deviations is much, much lower: 0.95⁵⁰⁰ is about 7*10^-12, so one is very likely to fail when using k=1000.

Another issue is that "moderately large" and "almost" terms are of course not formal. The real theorem gives those terms a precise meaning, and it turns out that in our case they work as expected if p and 1-p are both significantly greater than 1/k. To see the opposite situation, consider a value of p that's less than 1/k. It's not hard to see that the mean of k values will now be almost always 0, sometimes 1/k, and much more rarely anything else - clearly not very close to being distributed normally. This issue doesn't hurt in our problem since for the values of p that are so close to 0 and 1 we'll clearly give a good answer.

The most difficult part of this problem was not the Monte-Carlo idea - it was figuring out how to sample valid permutations uniformly. I won't go into details on this part, though, as it's explained very well in the contest analysis.

What I wanted to bring up instead is the philosophical question of how should problems with approximate solutions be properly stated and checked. As an example, the solution described above can give a wrong answer once in a million attempts. Is that good enough? Would it be unfair if some contestant was so unlucky that he got a wrong answer that way and had to submit again? What if this problem allowed only one submission attempt, and thus getting a wrong answer would have a much steeper penalty - which probability of mistake is acceptable then?

This problem had another peculiar property: the reference solution used Monte-Carlo approach as well, so we could only be sure that the reference answers are correct up to some probability. In other words, one could say that with some very remote probability submitting an exact answer could give a wrong answer verdict! We have made sure that chance is really remote by using MapReduce before the contest to run a lot more attempts for each testcase, and thus we were extremely confident that our answers are precise. What do you think is an acceptable probability of mistake in this case?

Finally, some of my past Code Jam problems (Proper Shuffle, Good Luck) went even further: the inputs themselves were randomly generated, and one had to estimate the hidden variables used for this random generation. In that case the input file by itself does not completely formally determine which output files are correct and which are not! With some probability many different sets of hidden variables could be used to generate the input, and while the actual variables used for generation are known to the judges and will be compared against when checking your solution, you don't have a way to be 100% certain your output is correct even given infinite computational resources. You can, of course, be 99,9999999999999999% certain. How many nines is acceptable here?

I'm looking forward to hearing your opinions on this subject! I'll share my own boundaries in a following post.

An asymmetric week

The June 6 - June 12 week started with Codeforces Round 356 on Wednesday evening (problems, results, top 5 on the left, my screencast, analysis). It turned out to be impossible to solve all five problems in time, and thus the winning strategy involved skipping one of the easier problems to spare time for the hardest one.

Here is the problem I skipped: you are given a 500x500 grid where each cell is either black or white. You're given a number k, and are allowed to paint any kxk subgrid black (but only do that once). What's the size of the largest 4-connected black area you can get?

TopCoder SRM 692 took place very early on Friday (problems, results, top 5 on the left). In line with the current TopCoder tradition, just two people have managed to solve all three problems - congratulations Kriii and rng_58! Amusingly, all 3 top finishers were in one room, setting the stage for some challenge phase racing, but it didn't happen as the gaps were probably too big.

Yandex.Algorithm 2016 Round 2 on Friday was the second chance to score points towards qualifying for the top 25, which for most practical purposes is achieved by placing in the top 8 in one of the three rounds (problems requiring Yandex login, results, top 5 on the left, my screencast, analysis). Just like last week, the winning strategy turned out to be submitting everything in the open and racing to solve all problems, although one could place in the top 8 with any strategy. Congratulations to apiad on the victory!

The hardest problem in this round was quite beautiful geometry: you are given a convex polygon with 100000 sides. For each point strictly within the polygon we can define its asymmetry value: the maximum ratio of the two segments between this point and the boundary of the polygon along any line. For example, if that point is the center of symmetry of the polygon, its asymmetry value is 1. What is the smallest asymmetry value over all points inside the given polygon?

On Saturday Google Code Jam 2016 Online Round 3 started another big Code Jam weekend (problems, results, top 5 on the left, analysis). The competition was tough as only the top 25 would qualify for the onside round in New York. The right strategy turned out to involve skipping the large input of problem C, which was a tricky graph problem, and solving the purely mathematical problem D instead. Congratulations to xyz111 for the convincing victory that put all strategy considerations aside!

I was the author of problem B in this round, which went like this: you are given a rooted forest with at most 100 vertices, and consider all valid permutations of its vertices. A permutation of vertices is valid if every non-root vertex comes after its parent. Additionally, each vertex is assigned a letter, so each permutation induces a string when we write all those letters in the order of the permutation. Which fraction of valid permutations induce a string that contains the given substring? Your answer doesn't need to be very precise: an error of 0.03 is allowed.

Finally, Google Distributed Code Jam 2016 Online Round 2 wrapped up this busy week on Sunday (problems, results, top 5 on the left, analysis). The results were once again much more optimistic than last year's, suggesting that the contestants have mastered the new format. Congratulations to eatmore on the victory, and to everybody who qualified for the onsite round - looking forward to seeing you all in New York!

In the last week's summary I've described a hard TopCoder problem: you're given a 50x50 integer matrix with all values between 1 and 61. We pick two (possibly intersecting or even coinciding) submatrices uniformly at random. We find X - the least common multiple of all numbers in those two submatrices combined. Now we find the number Y - the smallest possible integer that does not divide X. What's the expected value of Y?

Since the matrix is just 50x50, we can solve the problem quite easily if only one submatrix is considered: we can just iterate over all possible submatrices and find the value of X and then Y for each of them. We can also notice that the answer is always a power of a prime, and can't exceed 64 (since 64 does not divide the least common multiple of all numbers between 1 and 61).

How do we go from one submatrix to two submatrices? This is where some advanced algorithms come into play. First, instead of finding the Y for each submatrix, let's find the number of submatrices which have each value of X. The number of possible lcms of some subset of values between 1 and 61 isn't very big. Using that information we can "sum over all divisors": find the number of submatrices with the value of X dividing each interesting value. Having done that, making a jump from one submatrix to two submatrices is super easy: the number of ways to pick two submatrices such that their values of X both divide the given value is just the square of such number for one submatrix. And finally, we need to undo the sum over all divisors step: knowing the number of pairs of submatrices with lcm that divides the given value, we compute the number of pairs with lcm that's equal to the given value. Now we just need to find the value of Y corresponding to each possible value of X.

How do we transition to sum over all divisors and back? This is done via dynamic programming, similar to the approaches described in my April post and in this recent Codeforces discussion. The tricky part here is that we don't operate on bitmasks, but rather on sequences of prime powers, which have more than two possible values for smaller primes. But the logic stays exactly the same: iterate over the prime first, and then over the number.

Thanks for reading, and check back soon for more!

A non-blind week

TopCoder SRM 691 wrapped up May's contests (problems, results, top 5 on the left, my screencast). rng_58 applied his usual start-from-hardest strategy which almost gave him the win this time - if not for xudyh's amazing performance. It didn't seem likely that all three problems can be solved in time, but xudyh has managed to do just that with only a few minutes to spare. Congratulations!

The hardest problem required both knowing an advanced algorithm, and being careful while reducing the problem to the said algorithm to stay within the time limit. You're given a 50x50 integer matrix with all values between 1 and 61. We pick two (possibly intersecting or even coinciding) submatrices uniformly at random. We find X - the least common multiple of all numbers in those two submatrices combined. Now we find the number Y - the smallest possible integer that does not divide X. What's the expected value of Y?

Yandex.Algorithm 2016 Round 1 on the first weekend of June has once again tempted contestants with submitting blindly for smaller penalty time (problems requiring Yandex login, results, top 5 on the left, analysis). Tourist has convincingly demonstrated that blind submissions are not essential to winning the round, as having instant feedback allows one to take more risks and thus proceed quicker. Congratulations!

Russian Code Cup 2016 Qualification Round 3 has finalized the list of 600 Elimination Round participants (problems, results, top 5 on the left, analysis). YakutovDmitriy has claimed the first place with a large margin, despite finishing more than 20 minutes later than second-placed jiry_2, all thanks to being careful and not submitting incorrect solutions. Great job!

I've mentioned a nice Code Jam problem last week: consider a RxC grid such that every cell has exactly one of its two diagonals drawn. Those diagonals separate the grid into pathways which connect 2*(R+C) unit segments on the sides of the grid to each other. Given a matching telling to which other unit segment should each unit segment be connected, construct any grid that results in such connectivity. R times C is at most 100.

It turns out that the relatively small constraints are a red herring: this problem has a O(R*C) solution. We can build it as follows: start by finding two adjacent unit segments that need to be connected. If they're on one side, they can be connected by placing exactly two diagonals next to them, and if they're in a corner, then just one diagonal will do. Moreover, it doesn't make sense to connect them in any other way, as then their pathway will just occupy more space while not bringing any benefit, and any "holes" surrounded by the pathway will be completely wasted as two pathways can't intersect.

Having connected those two, we pick another two unit segments that are adjacent in the remaining list - note that we also take those that might've been originally separated by the two segments we've already connected. Again, we will connect them while occupying the least possible space, and not leaving any holes between the new pathway and the wall. More formally, we'll start from the left segment, and go along the side of the already placed pathways while "keeping our right hand" on the already placed diagonals. You can see a couple of examples on the right.

We continue like this while there are still segments left to connect. If at some point there are no two adjacent segments to connect, it means that the original list requires two intersecting pathways, which is impossible to achieve. Another possible roadblock is that we don't reach the right segment from the left segment while keeping the right hand on the wall. That means that the grid has already became disconnected, and since we occupied the least possible space with each move, there's no solution at all.

Thanks for reading, and check back next week!

A diagonal week

The May 23 - May 29 week was full with various tournament rounds. TopCoder Open 2016 Round 2B took place on Thursday (problems, results, top 5 on the left). Top 40 have qualified for the Round 3s which was of course the main point, but W4yneb0t wasn't content with just that as he found 100 points in the challenge phase to snatch the first place from Egor – congratulations!

Google Code Jam 2016 Online Round 2 was the main event on Saturday (problems, results, top 5 on the left, analysis). Just four contestants have managed to solve all four problems in full, and EgorKulikov has claimed a clear first place by solving everything with 40 minutes to spare – great job! Of course, well done to all 500 contestants qualifying for Round 3.

I was the author of the hardest problem D in this round, but it's actually problem C which I found the most beautiful. Consider a RxC grid such that every cell has exactly one of its two diagonals drawn. Those diagonals separate the grid into pathways which connect 2*(R+C) unit segments on the sides of the grid to each other. Given a matching telling to which other unit segment should each unit segment be connected, construct any grid that results in such connectivity. R times C is at most 100.

I like this problem so much in part because the solution doesn't rely on any advanced algorithms or data structures – it is a pure thinking challenge. Consider giving it a go!

Russian Code Cup 2016 Qualification Round 2 selected another 200 participants for the upcoming Elimination Round (problems, results, top 5 on the left, analysis). With four easy problems and only one hard one, the competition for the top spots was all about accuracy. Tourist has demonstrated just that and has managed to overcome the early gap vs enot.1.10 to claim the top spot by just 7 penalty minutes. Way to go!

Finally, Google Distributed Code Jam 2016 Online Round 1 on Sunday was the first round in 2016 that challenged contestants with problems that require distributed solutions (problems, results, top 5 on the left, analysis). Unlike last year, the contestants already had quite a lot of experience with the format, and thus breezed through the easier problems. Last year's finalist simonlindholm has solved all problems correctly in just over an hour (out of the three available hours) – awesome job!

In my previous summary, I've mentioned a very nice ACM ICPC World Finals problem: you have n disk drives (n up to 1 million), i-th having capacity a_i. You want to reformat all of them to a new filesystem, and i-th drive will have capacity b_i after reformatting. However, the drives are filled with data initially, and in order to reformat a drive you have to move its data elsewhere, be it other drives that gained more capacity after reformatting, or a new drive that you buy – that one already uses the new filesystem and doesn’t need reformatting. What is the minimum capacity the new drive needs to have in order to support reformatting all existing drives? Note that we are free to pick the order of reformatting the drives, and are free to move the data around arbitrarily between reformattings.

Let's split the drives into two classes: increasing ones have b_i>=a_i, and all others are decreasing. First, we can note that all increasing drives should be reformatted before all decreasing ones (assume we reformat an increasing drive right after a decreasing drive; if we do those actions in reverse order, the end result is the same but the capacity we have before both reformattings is greater or equal).

The remaining part is to find in which order to handle the increasing drives, and in which order to handle the decreasing drives. To see that, consider the drive we reformat the first, with some parameters a_i and b_i. In order to not lose data, we need at least a_i capacity of the new drive. But if we have that capacity, we can also reformat any other increasing drive with the same or smaller a_i, and since increasing drives make our situation strictly better, we can always reformat them as soon as we have enough spare capacity. Because of this, we can always start by reformatting the increasing drive with the smallest a_i. And that, in turn, enables us to see that we can handle all increasing drives in sorted order by a_i. Similarly, all decreasing drives should be handled in reverse sorted order by b_i.

Now that we've figured out the exact order of reformatting the drives, we can find the required spare capacity by simply tracking the total available size after every operation.

Thanks for reading, and check back soon for some June news!

A 7 minute week

The main event of the May 16 - May 22 week was ACM ICPC 2016 World Finals in Phuket (problems, results, top 12 on the left, video broadcast). ACM ICPC remains the most prestigious competition for university students for many reasons. First, a very extensive network of regionals and subregionals ensures high and broad participation. Second, the final event itself is organized on a massive scale, bringing everybody together for 4 days in a new city. Third, the format of the competition stays the same for decades, allowing the students to start preparing well in advance, and leading to the formation of regular training groups in many universities. And finally, this is a self-reinforcing stable state: the competition being the most prestigious results in more great students participating, more great companies hiring the winners and participants, more great problemsetters willing to invest time to prepare the tasks, all of which contribute back to the prestige.

This year’s finals was a great event – thanks a lot to everybody involved, in particular to the organizing ICPC team, to the problemsetters, to the sponsor IBM, and to the hosts from Thailand. This was my 14th World Finals, 2 as a participant and 12 as a spectator, and every year it keeps being exciting! And of course, congratulations to the winning Saint-Petersburg State University team, stealing the victory from the Shanghai Jiao Tong University by a mere 7 minutes of penalty time by solving their 10th and 11th problems 12 and 10 minutes before the end of the contest respectively!

The problemset was quite heavily skewed towards the technical side, but there were three problems that I enjoyed solving algorithmically: F, K and L. Of those, problem L has quite compelling statement: you have n disk drives (n up to 1 million), i-th having capacity a_i. You want to reformat all of them to a new filesystem, and i-th drive will have capacity b_i after reformatting. However, the drives are filled with data initially, and in order to reformat a drive you have to move its data elsewhere, be it other drives that gained more capacity after reformatting, or a new drive that you buy – that one already uses the new filesystem and doesn’t need reformatting. What is the minimum capacity the new drive needs to have in order to support reformatting all existing drives? Note that we are free to pick the order of reformatting the drives, and are free to move the data around arbitrarily between reformattings.

Thanks for reading, and check back soon as I clear the five-week backlog :)

A 400-500 week

Let's take a quick break from the World Finals practice session and take a look at last week's events. Codeforces Round 352 on Wednesday was one of the last chances to practice before this week's event (problems, results, top 5 on the left, analysis). Quite fittingly, three out of top five spots were taken by the World Finals competitors, including yet another first place for subscriber – he is on fire!

TopCoder Open 2016 Round 2A took place a day later (problems, results, top 5 on the left, my screencast). The point values of 400, 500 and 1000 (instead of the usual 250, 500, 1000) gave a hint that this will not be a usual round, and it did go strangely indeed (self-inducing prophecy?..) The 1000 was probably the most "typical" problem of the round, so going for it after the 400 has paid off for me. I've also managed to get the 500 submitted and even accepted, but there actually exists a test that makes my solution time out. Can you come up with one? Here's the solution (requires TopCoder login). Bonus points if your test makes it time out even after shuffling the vertices – I don't know how to do that :)

Here's the problem statement of the hard problem that saved my day: you have 40000 tokens which you can spend using 15 vending machines. Each machine takes tokens, and sometimes gives a prize in response (but sometimes not). The probability of getting a prize after inserting K tokens and not getting a prize on the first K-1 attempts is min(1, K²/L_i²), where L_i is a constant, different for different vending machines. After you get a prize from a machine, its state resets to the initial one (so K in the above formula becomes the number of tokens inserted after that). Your strategy must be to pick some vending machine, keep inserting tokens to it until you get a prize, then pick some different vending machine, give tokens until a prize there, then pick some different vending machine again (this one might be the same as some previous machine used, but not as the vending machine used to get the last prize), and so on until you run out of tokens. The prizes from i-th vending machines have value V_i. How to maximize the total expected value of all prizes you get?

Thanks for reading, and keep checking my twitter for ICPC 2016 updates!

A Polish week

TopCoder SRM 690 took place in the very early hours of Wednesday, May 4th (problems, results, top 5 on the left). Snuke has managed to score 50 additional points during the challenge phase, and that’s what allowed him to jump from third to first place – congratulations on the first SRM victory!

VK Cup 2016 Round 3 on Saturday selected 20 lucky teams to advance to the onsite finals in St Petersburg (problems, results, top 5 on the left, online mirror results, analysis). The rating favorite team “Never Lucky” bounced back from the relatively weak 4th place showing in Round 2 to win this round by over 1000 points – great job! Nevertheless, there are many other strong teams in the top 20 who will make sure the St Petersburg final round isn’t easy for subscriber and tourist.

Google Code Jam Round 1C selected the final 1000 participants for Round 2 (problems, results, top 5 on the left, analysis). Among the top scorers were the reigning champion Gennady.Korotkevich and linguo who doesn’t participate in competitions other than Google Code Jam but nevertheless does very well each year – but they couldn’t take the first place from artberryx – congratulations on the win!

Finally, Russian Code Cup 2016 Qualification Round 1 wrapped up the tournament-heavy weekend late on Sunday (problems, results, top 5 on the left, analysis). Subscriber pulled out another victory just a few days before the ACM ICPC World Finals, suggesting that the St Petersburg ITMO team is still very well in the running for the top spots there – way to go!

The last problem E required one to combine two relatively standard but normally unrelated algorithms into one solution: given two trees with at most 50 vertices in each one, find the size of the largest connected subtree in the first tree that has an isomorphic connected subtree in the second tree.

In my last summary, I've mentioned a problem that I couldn't solve: you are given two strings of the same length consisting of lowercase English letters, and want to transform the first string into the second one. You are allowed operations of two kinds: changing one character into another takes 1 second, and changing all occurrences of some letter into some other letter (the same for all occurrences) takes C seconds. What is the fastest way to do the required transformation?

Tomek Jarosik has posted a link to analysis of the original contest of this task in comments. Here's my rough understanding.

First of all, it's not hard to see that we can do all group changes before all individual changes – if we're going to waste 1 second for a given character, we can do it in the end and change it directly to what we need. Because of this, the task can be reformulated: now we're only allowed to do group changes, each costing C, and need to minimize total cost of group changes plus the total number of positions in which the resulting string differs from the goal.

Now let's draw a graph where the vertices are the 26 letters. The edges, somewhat counter-intuitively, will not be the group changes we make – instead, let's draw an edge from each letter to the letter that all its occurrences will change to after all group changes. For example, if we change all As to Bs, then all Cs to As, and then all Bs to Cs, then our graph will have edges A->C, B->C, C->A. Each letter will have 0 or 1 outgoing edge.

Given such graph, it's easy to count the total number of positions in which the resulting string differs from the goal: since we know how each letter ends up, we know the resulting string, and can simply count the differences. The other part of the value we minimize is not so clear: what is the minimum number of group changes required to construct the given graph?

The lower bound on the number of group changes is the total number of edges in this graph. Moreover, in most cases this lower bound is actually the answer. To see that, let's consider the structure of our graph. Since each vertex has 0 our 1 outgoing edge, the connected component of this graph are either directed trees, or a cycle with a directed tree growing into some of its nodes.

In order to find the group operations that construct the given directed tree, we can start from the root (the "sink"), apply the operations for all letters that need to be changed into the root letter, then continue with the letters that need to be changed to those letters, and so on.

When we have a cycle, we can't do the same. In fact, when a connected component of the graph forms a cycle of length K, we can't really implement the changes using just K group operations – we need K+1 in that case. To see that, notice that the first operation we make can not transform one of the letters in the cycle into another, as that would "merge" two letters together that need to be separate in the end. Instead, we must use an auxiliary letter that's not in the cycle. For example, if we need to build A->B->C->D->A, then we need to do something like: A to Z, then D to A, then C to D, then B to C, then Z to B.

However, when a connected component is not just a cycle – in other words has one or more directed trees going into the cycle's vertices – then we don't need an extra group operation for this cycle. For example, suppose the above A->B->C->D->A cycle also had a E->C incoming edge. Then we can do: B to E, then A to B, then D to A, then C to D, then E to C, handling both the cycle of length 4 and an extra incoming edge in 5 total group operations, and achieving the lower bound. If there's more than one edge going into the cycle, we can handle the rest as separate directed trees after handling the cycle.

There's one more constraint that we need to take care of: the standalone cycle resolution mentioned above needs an auxiliary letter (denoted as Z in the example above). In case there's a letter with an outgoing edge but without incoming edges, it can perform the role of that auxiliary letter: first, handle the component containing it, and then use it as auxiliary letter for all standalone cycles. If, however, there's no such letter – in other words, if the entire graph consists of standalone cycles and isolated vertices, then it's not clear what to do. After some more thinking we can notice in case such graph has at least one standalone cycle (in other words, at least one edge), then it's impossible to construct it at all, since it implements a non-identity permutation on the letters, and our very first group operation will merge two letters together.

Let's summarize what we have reduced our problem to. We need to build a graph on the 26 letters as vertices, with 0 or 1 outgoing edge for every vertex. If we have an edge from letter A to letter B, then its cost is the number of mismatches that yields (number of positions where the first string has A and the second string has not B) plus C (for the group operation corresponding to this edge). If we decide not to have an edge from letter A, this also has a cost (number of positions where the first string has A and the second string has not A). In addition, we get an extra cost of C for any standalone cycle in our graph, and the graph must not be all standalone cycles and isolated vertices, but it can be all isolated vertices. We need to minimize the total cost.

Our team got this far at the actual contest, but we couldn't come up with a way to solve this reduced problem. It turns out that solving it relies one one key insight: first, let's build this graph greedily: for each letter, pick the outgoing edge (or lack thereof) that minimizes the contribution to the total cost (taking account the cost C of having the edge, but not the additional bonus for a standalone cycle or the not-all-standalone-cycles restriction). This will give some graph G₀. If this graph does not have standalone cycles, then we're done. And in case it does, it turns out that those are the only cycles that we need to take care of!

More precisely, we can relax the problem as follows without changing the answer: instead of getting an extra cost of C for any standalone cycle, we will only get an extra cost of C for any standalone cycle that is present in G₀. Similarly, instead of forbidding the graph to consist of only standalone cycles and isolated vertices, we will only forbid the graph to be identical to G₀, and only if the latter consists of only standalone cycles and isolated vertices.

To see why the answer doesn't change, consider some optimal solution for the relaxed problem. Suppose it has some unexpected standalone cycle that is not present in G₀. At least one vertex on this cycle has a different outgoing edge in G₀. Let's change that edge to the one from G₀. The total cost will not increase since G₀ is locally optimal, and at the same time the standalone cycle will be destroyed, and no new standalone cycles will form (since it's impossible to do that with just one edge change). By continuing this process, we can show that there exists an optimal solution for the relaxed problem that is also a valid solution for the original problem.

Finally, we can solve the relaxed problem using dynamic programming: we process all letters in order, and pick the outgoing edge (or lack thereof) for each of them, while remembering which cycles from G₀ we have already broken, and whether our graph is still identical to G₀. Since G₀ has at most N/2 cycles, the running time is O(2^N/2*N²) which is very small for N=26.

Thanks for reading, and check back soon for the last week's summary. Also make sure to check my twitter for the ACM ICPC 2016 World Finals updates!