## Sunday, April 26, 2020

### A caterpillar week

Codeforces Round 635 was the first round of last week (problems, results, top 5 on the left, analysis). Problems A, B, C and E1 were solved by all top competitors, but the next step was less clear. maroonrk went for the hardest problem F, solving it with just two minutes remaining. However, this was not enough to beat boboniu who did not notice the additional difficulty in E2, solving both E1 and E2 together, and then wrapped up their victory with D. Congratulations to both!

TopCoder Open 2020 Round 1A then started a busy weekend (problems, results, top 5 on the left, parallel round results, analysis). Most top competitors got a bye into Round 2, therefore the scoreboard looked more yellow this time. Pasqual45's points just from the coding phase would be enough for the first place, but they made sure of the win with 100 more challenge points. Well done!

Open Cup 2019-20 Grand Prix of Tokyo was next (problemsresults, top 5 on the left, analysis). All teams solving 4+ problems got E, F, H and I, but the remaining problems were significantly more difficult. Even though 9 problems were solved by at least one team, the best teams only got 6. Our team was close to 6 problems as well, as our last submission on K was correct algorithmically but had an off-by-one error. Congratulations to teams ext71, Polish Mafia and USA1 on actually getting to 6!

Solving problem E involved this wonderful feeling where a relatively natural statement hides a solution with multiple interesting layers that "click" together. You are given k (k<=200) distinct positive integers ai (ai<=105). Consider all sequences of length n (n<=1018) with all elements equal to one of the given integers. Count the number of those sequences with the given sum s (s<=1018). Is that number odd or even?

And finally, Google Code Jam 2020 Round 1B wrapped up the last week (problems, results, top 5 on the left). xll114514 was the first to finish all problems, but mnbvmar was the fastest of the European competitors who didn't want to wake up at 3am for Round 1A, and had one less incorrect attempt than xll114514. Congratulations on the win!

In my previous summary, I have mentioned two problems. The first one came from TopCoder: you are given a directed tournament with n<=23 vertices. You are then constructing a "power" of this tournament with nk vertices (k<=1000), with each vertex described with a k-tuple of vertices of the original tournament. The direction of the edge between two k-tuples is given by the direction of the edge between the vertices that appear in the first position the k-tuples differ. For example, the direction of the edge between (a, b, a, c) and (a, b, d, e) is the same as the direction of the edge between a and d in the original tournament. How many subsets of vertices of this big graph induce a strongly connected subgraph, modulo 998244353?

First, let's deal with the k-th power. Consider a set S of vertices of the power graph. Each of those vertices is a k-tuple of vertices of the original graph. Let's consider the first position p in those tuples which has at least two different vertices. For example, if S has vertices (abac), (abad) and (abbc), then we're interested in the third position since both a and b appear there, while in the first position we always have a, and in the second position we always have b.

Now let's consider the set T of all vertices of the original graph that appear in this position. If S is strongly connected, then T is also strongly connected, because any path can be "projected" to T and still be a valid path due to the construction of the power graph.

Now suppose T is strongly connected. It turns out that then S is strongly connected as well, because when there's an edge from a to b in the original graph, there's an edge from any vertex with a in position p to any vertex with b in position p, therefore in order to find a path from any vertex in S to any other vertex in S it suffices to find a path between the corresponding vertices in the p-th position, and then pick any matching vertices for the intermediate stopping points. Note that we rely on the fact that T has at least two vertices here, as we need a cycle in T to build a path between two vertices in S that have the same vertex in the p-th position.

We have found that the strong connectivities (is there such a word?) of S and T are equivalent. Therefore if we can solve our problem for k=1, we can solve it for any k: consider a subset T of size m>=2 of the original graph that is strongly connected. How many sets S correspond to T in the p-th position? For each of the m vertices of T we have nk-p vertices of the power graph with this vertex in the p-th position, and we need to take any non-empty subset of those, so in total we get (2nk-p-1)m subsets.

Here comes the more interesting part of the problem: what to do for k=1? More specifically, how to count the number sets of vertices of each size that induce a strongly connected subgraph in a given graph with n<=23 vertices?

My approach was based on the Floyd-Warshall algorithm. We would like to run it on all 2n subsets, which would take O(2n*n3), which is too slow for n=23. We can replace the inner loop with one bitwise or operation, bringing the running time down to O(2n*n2) — still too slow.

However, we can now merge the iteration over subsets with the Floyd-Warshall algorithm! The outer loop of Floyd-Warshall iterates over intermediate vertices, so if we take a recursive algorithm that iterates over the 2n subsets, we can do one iteration of Floyd-Warshall outer loop as soon as we've decided that a vertex belongs to the subset. Therefore we will need to do at most one iteration of the Floyd-Warshall outer loop at each level of recursion, bringing our running time to O(2n*n+2n-1*n+2n-2*n+...)=O(2n*n)!

Here is the relevant part of my contest submission with some comments:

// Recursive search: we have decided that from the first
// "at" vertices we have taken the subset "mask",
// and the intermediate state of Floyd-Warshall after
// iterating over them is in "preach".
private void rec(int at, int mask, int[] preach) {
if (at >= n) {
// Check if the graph is strongly connected.
// "preach" already has the transitive closure for the
// chosen subset, so we check if it's complete.
int count = 0;
for (int i = 0; i < n; ++i) if ((mask & (1 << i)) != 0) {
++count;
return;
}
}
if (count >= 2) {
++res[count];
}
return;
}
// Do not take at-th vertex.
// Take at-th vertex, meaning that we need to do one more
// iteration of Floyd-Warshall outer loop.
// To avoid allocating new arrays in Java too often,
// I have pre-allocated one array per level of recursion
// which I overwrite here.
int[] nreach = reach[at + 1];
System.arraycopy(preach, 0, nreach, 0, n);
for (int i = 0; i < n; ++i) if ((nreach[i] & (1 << at)) != 0) {
nreach[i] |= nreach[at];
}
rec(at + 1, mask | (1 << at), nreach);
}

The second problem was from Codeforces: you are given a tree with n<=105 vertices. You want to draw n closed curves on the plane, one per vertex, in such a way that two curves intersect if and only if the corresponding vertices are adjacent in the tree. What is the maximum size of a chain of curves that are nested in one another (but do not intersect) in such drawing?

The space of possibilities for drawing arbitrary curves on the plane is enormous, so it's not clear how to approach this problem. First, we can notice that the curves for adjacent vertices intersect, and therefore can't be nested in one another. Is that the only restriction? In other words, can we choose the curves in such a way that any two curves either intersect (when the corresponding vertices are adjacent) or are nested (if they're not)? At first I believed it was always possible, then finding the size of the longest chain is just finding the size of the largest independent set in a tree, which can be done with a simple greedy from the leaves. I made a quick submission, which turned out to be incorrect :)

Then I started to think when does this approach fail. After some doodling on paper, I have found a relatively small counterexample (on the left). Moreover, I have also come up with a description of cases where it does in fact work: they all seemed to be caterpillar trees! After some more doodling, I was able to build the set of curves that achieves the perfect nesting for any caterpillar tree (on the right, the curves corresponding to the main path of the caterpillar are red, and the dotted blue curves corresponding to the legs of the caterpillar could be multiple at each level).

Finding the size of the largest independent set in all sub-caterpillars of the given tree is slightly more tricky, but still doable with dynamic programming on the tree. However, is it the correct solution? I did not have a proof, but after so much doodling that didn't provide a counterexample it felt right, so I decided to try with another submission, which worked. You can find the proof in the editorial :)

Thanks for reading, and check back for this week's summary!

## Monday, April 13, 2020

Last week saw the first elimination round of Google Code Jam 2020, Round 1A (problems, results, top 5 on the left). Gennady.Korotkevich started his title defense with another commanding performance in the middle of the night, wrapping up 10 minutes before everybody else. Well done!

TopCoder SRM 783 followed later on Saturday (problems, results, top 5 on the left, my screencast, analysis). tourist, bqi343 and scott_wu were much faster than other top competitors on the 1000, but Scott's 250 failed to handle perfect squares correctly, and Ben's single challenge was still not enough to catch Gennady. Congratulations on the second victory of the day!

The hard problem had two almost independent parts: solving the k=1 case, and understanding how to reduce k>1 to k=1. The problem statement was: you are given a directed tournament with n<=23 vertices. You are then constructing a "power" of this tournament with nk vertices (k<=1000), with each vertex described with a k-tuple of vertices of the original tournament. The direction of the edge between two k-tuples is given by the direction of the edge between the vertices that appear in the first position the k-tuples differ. For example, the direction of the edge between (a, b, a, c) and (a, b, d, e) is the same as the direction of the edge between a and d in the original tournament. How many subsets of vertices of this big graph induce a strongly connected subgraph, modulo 998244353?

The k=1 part — where the graph with at most 23 vertices is just given to you directly — allowed quite a lot of interesting and different solutions, so I encourage you to try solving at least that part :) I believe my solution did not in fact need the graph to be a tournament, it could handle any directed graph, so you can try solving either version.

This was the first time I was recording a screencast while using an external 4K monitor, which brought a couple of challenges: first, it seems that encoding a 4K video was using nearly all resources of my machine, even though I was using the same bitrate as I did for the 1080p video. This meant I had to wait for half a minute every time I ran my solutions, somewhat suboptimal :) Second, the fonts in the arena looked really funny, most likely because I had font scaling enabled in Windows to be able to read text in such resolution. Any suggestions on how to resolve those?

Codeforces Round 633 took place on Sunday (problems, results, top 5 on the left, analysis). My approach turned out to be very similar to previous week's Codeforces round, solving four problems at reasonable speed but then giving up too easily on the fifth, instead looking for challenges when there were virtually none available — the only failing solution in my room was hos.lyric's D, and I did not really suspect it to be incorrect. tourist was in a similar spot in the middle of the leading pack after solving four problems, but went on to win the round after solving E. Congratulations on three wins in a row!

Radewoosh jumped into the second place with a correct submission on E with 7 minutes remaining, then almost blew it by actually submitting a version without bitsets, and then some version with bitsets but also with too much debug enabled, and finally submitting the correct bitset solution again with just seconds remaining in the round. What was that? :)

Problem D was quite nice: you are given a tree with n<=105 vertices. You want to draw n closed curves on the plane, one per vertex, in such a way that two curves intersect if and only if the corresponding vertices are adjacent in the tree. What is the maximum size of a chain of curves that are nested in one another (but do not intersect) in such drawing?

Thanks for reading, and check back next week!

### A cheese week

Codeforces hosted its Round 631 during the Mar 30 - Apr 5 week (problems, results, top 5 on the left, analysis). I had a relatively good start on the first four problems, but could not make progress in the last one and switched to challenging with about 20 minutes remaining, also without success. Um_nik, on the other hand, had an even better start and did not give up so easily on E, earning the ultimate reward of being the only contestant to solve all problems. Great job!

When solving problem C, I could not come up with a solution analytically for quite some time, so I've used the adage "so many people got it accepted, the solution must be simple!" and started thinking in terms of what a simple solution might look like. I've came up with the [ultimately] correct greedy very quickly, but could not prove that it works. After some more time, I've decided to just implement and submit it, relying on pretests and the adage to help :)

When this approach works, it is satisfying, but I feel that using it might be detrimental in the long run: it greatly reduces the motivation when solving the problems analytically, the opportunity to just start submitting good-looking solutions is too tempting. Or maybe it really is a part of the game?

Thanks for reading, and check back for more!

## Saturday, April 11, 2020

### A Geronimo week

The Mar 23 - Mar 29 week had two events on the weekend. TopCoder SRM 782 was the first one to go (problems, results, top 5 on the left, TCO stage 2 resultsanalysis). With about 30 seconds remaining in the challenge phase I've noticed that I need one more successful challenge for the first place, but I did not find any bugs. Therefore I decided to guess which solution is most likely to have a bug, and to challenge it with a large testcase that I prepared earlier. I was extremely lucky that this strategy worked, given that the solution I chose — Egor's 1000 — turned out to be the only remaining incorrect solution in the room at that point :)

Open Cup 2019-20 Grand Prix of Wroclaw took place on Sunday (results, top 5 on the left, analysis). Since Open Cup is a (multi-)onsite team contest, this required some big changes, as teams were asked to all participate online without even gathering a team together in one place, instead using audio/video conferencing and coordinating to use at most one computer at the same time. Team USA1 has been participating like this all season and therefore maybe had a slight edge over the competitors, winning by 11 problems to 10. Well done!

Team HDU-Coach in the second place is doing very well this season in general, however unlike other top teams their team members are not listed in the standings. Does anybody know their Codeforces handles, for example?

In my previous summary, I have mentioned an AtCoder problem: you are given a sequence of n<=106 numbers, each number is 1, 2 or 3. Then, you create a new sequence of length n-1 by taking the absolute values of the differences between adjacent numbers. Then you create a new sequence of length n-2 from the sequence of length n-1 in the same way, and so on until there's just one number in the sequence. What will this number be?

First of all, it's convenient to subtract 1 from all numbers in the input so that we have 0, 1 and 2 — this will not change the differences.

Then, let's assume the input sequence contains just 0s and 1s. The absolute difference in this case is the same as addition modulo 2, so for example starting from five numbers a, b, c, d, e, we'll get: a+b, b+c, c+d, d+e; then a+2b+c, b+2c+d, c+2d+e; then a+3b+3c+d, b+3c+3d+e; and finally a+4b+6c+4d+e (everything modulo 2). We can now notice (and prove) that the coefficient next to the k-th input number is equal to C(k-1,n-1), and thanks to Lucas's theorem we know it's equal to 1 modulo 2 when (k-1)&(n-1)=k-1 (& is bitwise and), and to 0 modulo 2 otherwise, which allows us to solve this case by summing the input numbers multiplied by the corresponding coefficients.

What can we do if the input sequence also contains 2s? First of all, we can notice that if we declare that 0 and 2 are the same, then our operation is still equivalent to addition modulo 2! This allows us to determine if the final number is 1, or if it's 0/2. If it is 1, we're done, but how to decide between 0 and 2 in the other case?

It turns out that if the input sequence contains a 1, then the final number will never be 2. To see that, we can notice that if the sequence contains at least one 1, and at least one 0/2, then two of those will be adjacent, and therefore the next step will also contain at least one 1. So the only way to get rid of all 1s if there were any is to get a sequence with all numbers equal to 1, in which case all following steps will have all numbers equal to 0. In any case, if the input sequence contains at least one 1, the final number will always be a 0 or a 1, therefore the above approach solves this case.

The only remaining case is: the input sequence contains only 0s and 2s. In this case we can just divide all numbers by 2 to reduce the problem to the one with only 0s and 1s, solve it and then multiply its answer by 2.

I found it very enjoyable that such simple problem statement requires one to unwrap multiple layers to solve it, even if each layer by itself is not very hard.

Thanks for reading, and check back for more!

### A topology week

The Mar 16 - Mar 22 week had competitions from the three main platforms. Codeforces was the first to go, with its Global Round 7 on Thursday (problems, results, top 5 on the left, analysis). Um_nik was the first to finish solving the problems, but tourist had beaten him to the first place because he solved the problem F1, which is a reduced-constraint version of problem F2, separately and much faster, while Um_nik just solved F2 directly and got F1 accepted at the same time with a lower score. Congratulations to both!

TopCoder SRM 781 followed in the middle of the night on Friday (problems, results, top 5 on the left, analysis). My lead in the TCO qualification before this round was considerable at 31 points to 24, so I've decided to not wake up at 2 in the morning, even though mathematically I could still lose my spot if I do really badly in SRM 782. Congratulations and big thanks to Egor who made sure the five points did not go to one of the 24-point pursuers :)

Finally, AtCoder Grand Contest 043 marked the start of a new season there (problems, results, top 5 on the left, analysis). apiad started with the hardest problem F and got it accepted with 47 minutes remaining in the contest, probably realizing that others are not likely to get it. There were therefore a few paths to the first place open for him. Solving B+C+D in 47 minutes was probably the most realistic by looking at the scoreboard, but he went for the very interesting and unusual problem E (D+E would be enough for the first place) and didn't manage to get it in time. tourist was the fastest of those on a more traditional problem solving order, and won the round with a 11-minute gap. Well done!

There were several nice problems in this round, so let me highlight an easier problem for a change, problem B: you are given a sequence of n<=106 numbers, each number is 1, 2 or 3. Then, you create a new sequence of length n-1 by taking the absolute values of the differences between adjacent numbers. Then you create a new sequence of length n-2 from the sequence of length n-1 in the same way, and so on until there's just one number in the sequence. What will this number be?

Thanks for reading, and check back for more!

### A monotonic week

The Mar 9 - Mar 15 week was light on contests, so let's come back to the Codeforces problem from the previous summary: you are given a sequence of at most 500000 numbers. In one step, you simultaneously replace every number except the first one and the last one with the median of the following set: this number itself, the number on the left, and the number on the right. For example, if you start with 3 1 4 2 5, then after one step you get 3 3 2 4 5, after two steps it becomes 3 3 3 4 5, and then it does not change anymore. What will be the stable state of the sequence, and how many steps are needed to reach it?

Since I did not solve the problem myself, I will describe the solution from the tutorial. First, let's assume that the input sequence has only numbers 1 and 2. Then the process is somewhat straightforward: if there are two or more adjacent numbers that are equal, they will never change; and for each maximal subsegment of alternating numbers, at every step all numbers in it except the first and the last one will flip from 1 to 2 and vice versa, thus reducing the length of the alternating sequence by 2, until it eventually disappears: 12121212 -> 11212122 -> 11121222 -> 11112222 -> 11112222 -> ...

Here comes the most beautiful part of the solution: we can notice that the process is in some sense monotonic. More specifically, if we take the input sequence, replace all numbers that are less than or equal to some boundary b by 1, and all numbers greater than b by 2, then run the process on this sequence of 1s and 2s in parallel to the process on the original sequence, then the relation between them will always stay the same: after any number of steps, all numbers less than or equal to b in the first sequence will correspond to 1s in the second sequence. Since we know how to find the stable state for the sequence of 1s and 2s, we know which numbers in the stable state of the original sequence are less than or equal to b, and which are greater than b!

Since we also know that all numbers in the stable state are equal to some number of the original sequence, doing the above process for all values of b equal to some number of the original sequence allows us to reconstruct the steady state: every number can be determined as the lowest value of b for which it corresponded to a 1.

When implemented naively, this solution would be quadratic which is not good enough. However, we can process the values of b in increasing order, and maintain a set of all alternating sequences of 1s and 2s in the second sequence in a balanced tree. We have n events, in each of those one of the 2s becomes a 1, and in each event at most two alternating sequences adjacent to the place of modification will be affected. The balanced tree allows to find, add and remove those in logarithmic time, therefore we can simulate the entire process in O(n*logn). And in order to construct the answer, we can maintain the set of positions which still have a 2 in the steady state in another balanced tree, and remove appropriate positions from it whenever a new alternating sequence appears, since each alternating sequence produces at most one segment of consecutive 1s in the steady state, which ends up being amortized O(n*logn) as well.

Thanks for reading, and check back for more!

## Friday, April 10, 2020

### A higher-order week

The Mar 2 - Mar 8 week's contests started with the Ozon Tech Challenge 2020 hosted by Codeforces (problems, results, top 5 on the left, analysis). Only three contestants were able to solve G or H, but Um_nik's F failed due to checking all divisors instead of only prime divisors, and maroonrk's C failed due to trying to squeeze 108 modulo operations in the time limit (replacing the modulo in the inner loop with an if makes it pass). Therefore only tourist was able to keep 7 problems, and he got a clear first place. Congratulations!

Codeforces Round 626 followed on Saturday (problems, results, top 5 on the left, analysis). Once again just 3 contestants were able to solve any of the last two problems, and once again only one of them solved all previous ones. Congratulations to zhouyuyang!

I was unable to solve problem E, but I found the reference solution idea very nice. You are given a sequence of at most 500000 numbers. In one step, you simultaneously replace every number except the first one and the last one with the median of the following set: this number itself, the number on the left, and the number on the right. For example, if you start with 3 1 4 2 5, then after one step you get 3 3 2 4 5, after two steps it becomes 3 3 3 4 5, and then it does not change anymore. What will be the stable state of the sequence, and how many steps are needed to reach it?

TopCoder SRM 780 wrapped up the week (problems, results, top 5 on the left, analysis). The problems were on the easy side this time, and still tourist was able to solve both 450 and 1000 significantly faster than everybody else. Well done!

In my previous summary, I have mentioned an Open Cup problem: you are given a string s of length up to 10, and a positive integer d also up to 10. How many strings consisting of letters A-Z are at the Levenshtein distance of exactly d from s? Compute the answer modulo 998244353.

First of all, how does one compute the Levenshtein distance between the string s and some other string t? This is one of the textbook examples of dynamic programming, and even the Wikipedia article has the formula. We compute the dynamic programming table dp[a,b] which contains the Levenshtein distances between the prefix of s of length a and the prefix of t of length b.

For example, for s="havka" and t="papstvo", we get the following table:
h a v k a
0 1 2 3 4 5
p 1 1 2 3 4 5
a 2 2 1 2 3 4
p 3 3 2 2 3 4
s 4 4 3 3 3 4
t 5 5 4 4 4 4
v 6 6 5 4 5 5
o 7 7 6 5 5 6

In order to compute a row of this dynamic programming, we only need to know the values in the previous row, the string s, and the next character of the string t.

This observation allows us to apply higher-order dynamic programming to count the number of strings t at the given distance from s! We will construct the string t character by character, and the state of our dynamic programming will be the row of the above matrix. For each possible row of values we will compute how many possible choices of a prefix of t yield that row.

How many states does this dynamic programming have? It's not hard to notice that the first value in a row is always equal to the length of our prefix of t, and each consecutive value differs from the previous value by -1, 0 or +1. This follows most directly from the fact that the Levenshtein distance satisfies the triangle inequality. Therefore when s has length n and the maximum length of t is m, the number of states does not exceed m*3n. In our case n=10, m=20, so we have at most 1.2 million states.

Thanks for reading, and stay safe!

## Saturday, April 4, 2020

### A random week

The Feb 24 - Mar 1 week had two Codeforces rounds and an Open Cup. The first one was called Kotlin Heroes: Episode 3 and accepted solutions in Kotlin only (problems, results, top 5 on the left, analysis). Only Egor and tourist managed to solve all problems, with the former seemingly writing in Java and converting the code to Kotlin automatically right before the submission, and the latter using more idiomatic Kotlin style. The Java way was the better way this time, in large part thanks to tourist's 6 incorrect submissions. Congratulations to Egor!

The Open Cup round was called the Grand Prix of North America, and it was based on the problems from ICPC North American Championship (problems, results, top 5 on the left, onsite results, video analysis). Team Almost Retired really aced it this time, solving 12 problems from 12 attempts, congratulations! The performance of Gennady Korotkevich is also worth mentioning, as he solved all problems in order despite the fact that two most difficult problems were D and E, most likely because he did not know it would become an Open Cup round when he was solving the online mirror of NAC.

I found problem I educational: you are given a string s of length up to 10, and a positive integer d also up to 10. How many strings consisting of letters A-Z are at the Levenshtein distance of exactly d from s? Compute the answer modulo 998244353.

The second Codeforces round of the week was the Round 625 (problems, results, top 5 on the left, parallel round results with more problems, analysis). ksun48 was the only contestant to solve all problems, and 300iq achieved the same feat in the parallel round. If one excludes the problems A and C from the parallel round that did not appear in Round 625, ksun48 and 300iq would be neck and neck. Congratulations to both!

In my previous summary, I have mentioned two problems. The first one came from the Open Cup: find three points in three-dimensional space with integer coordinates up to 106 that would present a hard testcase for floating-point geometry code. More specifically, let's project these three points to the unit sphere (x/sqrt(x2+y2+z2), y/sqrt(x2+y2+z2), z/sqrt(x2+y2+z2)). The plane passing through those projections must pass very close to the origin, but not exactly through it: the distance from the origin to this plane must not exceed 1.5*10-19. Moreover, probably for the sake of the numeric stability of the checker, the three points have to be far apart on the unit sphere: at least 1.7 from each other (note that the diameter of the unit sphere is 2).

This problem was solved by Ilya Kornakov in our team, so I'm explaining his solution. First, let's find some way to generate random 3x3 matrices with determinant 1/-1 and values up to a 106 by absolute value. We did it by starting with a random upper triangular matrix with ones or negative ones on the diagonal, and then trying 100 times to add or subtract one of the rows/columns to another row/column (which does not change the determinant), only doing the addition/subtraction if the values stay small enough.

Then, it turns out that such matrix has a reasonable probability of being our answer! To see why, note that the matrix having determinant 1 means that the corresponding pyramid has volume 1/6. Its height can be computed using the formula h=3*volume/base_area. Since volume is 1/6, we have h=0.5/base_area. base_area can be computed as one half of a determinant of a 2x2 matrix with values up to 2*106, so it is up to 4*1012, therefore its height could be as small as 0.125*10-12.

Now, the problem asks for the height of a different pyramid: the one obtained by projecting the original three points onto the unit sphere. Let's split this projection into two parts:
1. Projecting all points into a sphere with radius equal to minimum distance l from origin to one of our three points (one of the points remains unchanged in this step).
2. Contracting that sphere l times.
The second part reduces the height of the pyramid l times, but what about the first part? We claim that it's very likely that the height of the pyramid decreases during this step! I don't have a strict proof here, but the picture on the left demonstrates two-dimensional analogy: the height AF of triangle ABD is bigger than the height AE of triangle ABC because it intersects the segment BC, and AE is the shortest path from A to BC. This argument breaks if F lands outside of the segment BD (more precisely, the line BD has to intersect the dotted circle, which is an even stronger requirement). Since the problem requires the three points to be at least 1.7 apart on the unit sphere, they form a pretty big triangle and therefore it's likely that the height still passes through it after the projection.

Since l can be up to sqrt(3)*106, the final pyramid could have its height as small as 0.125*10-12/(sqrt(3)*106) which is approximately 7*10-20. Our goal is 1.5*10-19, so we have a ~2x gap, and after a sufficient number of attempts we will find a good example.

Note that the argument above also gives us a way to obtain a numerically stable upper estimate of the height: h=0.5/base_area/l. Computing the required height directly is hard to do in double or even long double, but this estimate is computed very precisely as there's no subtraction of close numbers at all. If this estimate is below 1.5*10-19, the true height is even lower and therefore is also small enough.

Of course the fact that the first projection above does not increase the height is the most shaky part of this solution. To our defense, I can say that I've ran it with three different random seeds and it got accepted every time :)

What was your approach? Is there a way to avoid shaky arguments?

The second problem I mentioned came from Codeforces: you are given a complete directed graph on n vertices (n<=80), with each arc having its own non-negative cost. Your goal is to find a cyclic route of length exactly k (k<=10) from vertex 1 to itself with the lowest possible cost such that this route does not have sub-cycles of odd length (therefore k is always even).

The route not having sub-cycles of odd length is equivalent to saying that the vertices of the route can be colored with two colors such that the colors always alternate along the route. Since the length of the route is at most 10, it has at most 9 intermediate vertices. Therefore if we pick a random coloring of all vertices, with probability 1/29=1/512 we will guess the right colors for the route from the optimal solution!

This leads us to the solution: let's repeatedly pick a random coloring of all vertices, and find the shortest cycle of length k where the colors alternate. We will do this until the time runs out, and print the shortest cycle that we found among all attempts. Finding the shortest cycle of length k can be done in O(n2*k) in a pretty standard fashion.

Since the probability of failure of each particular attempt is 511/512, if we manage to do t attempts our probability of failure will be (511/512)t. For t=10000, this gives about 3*10-9, which is good enough, and 10000 runs of a O(n2*k) algorithm should be fast enough for n<=80 and k<=10.

I find the way randomization helps us make 9 tough decisions pretty amusing :)

Thanks for reading, and check back for more!