October 12, 2020 2020 TCO Europe and Central Asia Regionals Algorithm Editorials

300 points: SlowSequence

The differences between consecutive elements of the sequence are +1s and -1s. The sequence of the N-1 differences determines the actual sequence uniquely.

If all differences are +1, the sum of the sequence is N(N-1)/2, if they are all -1, the sum is the opposite. Thus, one necessary condition is that a solution can only exist for sums that lie in this range.

Suppose we start with all differences +1. If we now take the k-th +1 from the end and flip it to -1, this change will decrease each of the following elements of the sequence by 2k. As 2k is even, the parity of the sum won’t change. Thus we get a second necessary condition: the parity of the desired sum S must be the same as the parity of the maximum possible sum N(N-1)/2.

Together these two necessary conditions are also sufficient. In order to construct one solution we need to take the difference D = N(N-1)/2 – S and write it as a sum of distinct even numbers not exceeding 2(N-1). It can easily be shown that a simple greedy algorithm that always takes the largest available number will always construct a valid solution. Hence we get a really simple implementation: start with all the differences equal to +1 and then go left to right and whenever flipping a +1 to a -1 keeps the sum of the sequence at least equal to S, do so.

Qualification, 500 points: RowAcross

The boat must alternately travel there and back again. Each trip in the correct direction transfers at most C people, each trip back transfers at least 1 person back, so each such pair of trips has the net effect of transferring at most C-1 people to the desired side. The last trip will transfer at most C people. Thus, the total number of trips is at least 1 + 2*ceiling( (N-C) / (C-1) ).

As long as we always have C people going in the right direction (or everyone who’s left if it’s the last trip) and only one person going back, we can be sure that our trip count is optimal. Thus, we only need to minimize the maximum strain.

For C >= 3 we get that the above lower bound is at most equal to N. If there are at most as many trips as people, ideally we should find a solution in which no person has to row twice.

For C = 2 we get the lower bound of 1 + 2*(N-2) = 2*N – 3. If N >= 4, this is more than N but less than 2*N, so the optimal solution must have some people rowing twice, and if we find such a solution, we can be sure that it’s optimal. For N <= 3 we could have each person rowing at most once, and this is clearly possible: {A} for one person, {AB} for two, and {AB, B, CB} for three.

To complete the solution for C=2, for larger N we can find a very straightforward pattern: starting with B, each person will take the previous one across and then return if we still aren’t done. The start of this solution looks as follows: {BA, B, CB, C, DC, D, …}

For C>2 we can indeed always construct a solution in which nobody has to row twice, but we need to be a bit careful: some greedy approaches can get stuck in a situation where everybody still left on the original bank has already rowed once. 

One possible solution is to generalize the pattern used for N=2, with the only change being that now with at least three people in the boat we can have the last two alphabetically as the paddlers: one takes it in the other direction, the other returns it back. Here’s an example of the beginning of this pattern for C = 5:

{DEABC, E, HIEFG, I, LMIJK, M, …}

Qualification, 1000 points: MarioJumper

Let’s start with the observation that in cases when we are supposed to go right to left we can reverse the entire input. Hence, we may assume that start is to the left of the desired finish. (We may also observe that steps are useless because jumps of width 1 do at least the same thing.)

As we are going right, if a column is unreachable, all of the following columns are unreachable as well – if we could jump over that column, we could also jump onto it from the same place. Let dist denote the distance from the start to column c. For any two consecutive columns that are reachable there are only two possibilities: either dist = dist, or dist + 1 = dist. This is because the optimal way of reaching column c+1 is either from column c-1 only (in which case the first equality holds because we can reach c from c-1 in the same number of moves) or from column c (in which case the second equality holds). We will call these two possibilities equal and unequal columns.

Next, consider what happens when we encounter one piece of the game world, as described by the input variable pieces[]. If we know the distances to the two columns that immediately precede this piece, we can then simply iterate over the piece from the left to the right and determine the distances for all its columns – and, most notably, for its last two columns. 

If this piece is repeated 147 times, we would like to find its effect and then repeat it 147 times, but it won’t be so easy. The problem is that the repetitions won’t have the same effect. The effect of a piece depends on whether the previous two columns were equal or unequal, and this is not necessarily preserved. However, it is easy to notice that once we repeat a piece a few times, we must get periodic behavior: either each piece has the same effect, or we are alternating between two effects (and alternately end the piece with equal and unequal columns). The conclusion is that in either case we should take two consecutive pieces as the smallest “unit that can be repeated”.

One possible solution with a fairly straightforward implementation therefore looks as follows:

1. for each piece, if its count is greater than, let’s say, 4, reduce it to either 4 or 5, preserving parity
2. the resulting level is small enough to run a general BFS to compute all distances
3. for each piece whose count was reduced in step 1, look at how its last two repeats changed the distances and add the same effect for the missing copies

The problem was hiding one final catch which you may not notice if you actually run BFS in step 2, but which would make your solution fail if you just iterated from start to finish in step 2 instead. The catch is that in some levels the very first jump you make has to be in the direction away from the finish. (E.g., maximum jump height is 3, your column has height 0, the next column in the direction towards the finish has height 5 and the other adjacent column has height 3.)

Elimination round 1: DrawNTrees

If R=1 or C=1, we can divide the rectangle into N pieces for any N, and as each piece is a path, it is a tree.

An example illustrates that for R, C > 1 the input N = 1 has no solution. All other inputs are solvable.

Here’s one possible solution for some arbitrary R, C and for N = 2:

00000000000
01010101010
01010101010
01010101010
01010101010
11111111111

An easy way of finding a solution for larger N: we will start with the above solution and then exactly N-2 times we will find a leaf of an existing tree (i.e., a square with exactly one neighbor of the same color) and turn it into a new component of size 1. 

If we use colors 2, 3, 4, 5 for the new components based on parity of the row and column they are in, we are guaranteed to never have two components of the same color touching each other, and we are done.

Elimination round 2: CoinFlipBetting

Let pH be the probability that Heather wins the series. (The value of pH is easily computed using dynamic programming.) 

Once the entire series ends, we need to have at least S/pH dollars in each situation in which Heather won the series. As we cannot go below zero, we will have at least zero dollars in each situation in which Tasha won the series. On the other hand, we know that our expected profit from each individual bet with Lucy is zero, and therefore our expected profit at the end must be zero. This is only possible if there is an equality in all of the above inequalities: any optimal strategy must have the property that we will have exactly S/pH dollars if Heather wins the series and exactly 0 dollars if she loses the series.

Once we made this observation, it should be intuitive that all the individual bets we’ll need to make will be uniquely determined. This will indeed be the case. Let’s say that a state is the number of heads and tails seen so far. We will show that for each state (h, t) we can uniquely determine both the amount of money you must have whenever in that state and the bet you should make for the next round.

We will go backwards. We already know that money[N][*] = S/pH and money[*][N] = 0 for the terminal states. Suppose we are in some state (h, t). With probability P we will go to the state (h+1, t) and we will need to have exactly money[t] dollars, and with probability (1-P) we will need to have exactly money[t+1] dollars. We now need to determine money[t] and the amount to bet.

We could now consider two options: betting on head or betting on tail in the next flip. However, it is fairly obvious that we must have money[t] > money[t] > money[t+1] and thus we always want to bet on heads. (If you don’t see why or don’t trust your intuition, try calculating what happens if you attempt to bet on a tail. How can you then tell that this is never an option?)

Now we have two unknowns, money[t] and bet[t], and two equations: money[t] – bet[t] = money[t+1] if we lose, and money[t] – bet[t] + bet[t]/P = money[t] if we win. This system of equations has a unique solution: bet[t] = (money[t] – money[t+1]) * P, and money[t] = P*money[t] + (1-P)*money[t+1].

Now that we derived these expressions, we can use a straightforward dynamic programming approach to compute the money and bet for each state.

Finals 300pt: ShippingCosts

Again, the first problem featured in the finals is on the easier side. For each customer we have a window: an interval of prices in which they will make a purchase. We can note that the optimal price will be the upper end of some customer’s window – in all other cases we can increase the price and our profits without losing any customers. We can now easily compute the optimal answer by sweeping: the events are the openings and closings of all windows, and we keep track of the current profit and the current number of buying customers.

Finals 800pt: GreedyKiller

There were two basic strategies to solve this problem: either analyze the algorithm on paper, or implement it most optimistic version (do you see how to deal with ties?) and use it to find a suitable collection of random counterexamples.

There are many different types of counterexamples. Below we show the two used in the reference solution, with a proof that they are sufficient.

Counterexample 1: sometimes taking the shortest interval with the fewest overlaps is bad. If a solution takes the interval marked with asterisks, it can no longer be optimal. Note that each other interval has both strictly more overlaps and a bigger length than the marked one.

--------   --------   --------   --------
     ---------    *****    ---------
     ---------             ---------
     ---------             ---------

Counterexample 2: in other situations, discarding the longest interval with the most overlaps is also bad.

--------   *******************   --------
     ---------             ---------
     ---------             ---------

If takeThreshold >= 2*overlapPenalty + 2*lengthPenalty, counterexample 1 will work.

And in counterexample 2 the badness of each interval is at least 2*overlapPenalty + a_lot*lengthPenalty, so if counterexample 1 did not work, we know that takeThreshold is less than the badness of each interval. Hence, the greedy solution will discard the most expensive interval and counterexample 2 will work.