October 12, 2020 2020 TCO Eastern Asia Regionals Algorithm Editorials

Qualification, 250 points: BicycleLock

Just an implementation problem to make the round beginner-friendly. The biggest “difficulty” lies in the decision what pattern to implement. Instead of checking each dial against all previous ones I prefer simply setting dial n to value n, for all n. Clearly we need at most 9 rotations of each dial + at most 9 finger movements = at most 99 actions total.

Qualification, 500 points: Parabola

There are few enough pairs (A, B) to be able to iterate over all of them. For a fixed A and B we are looking for the C that minimizes the sum of distances between the given points and a parabola. This is simply the “optimal meeting point” in 1D, disguised by the fact that everything is shifted by the parabola. Indeed, if we take the values Y[n] – A*n*n – B*n as the coordinates of “houses” on a straight line, the optimal meeting point for people living in those houses will tell us the optimal C. And it is well-known that the optimal meeting point is the median of all houses (unique for odd n, anywhere in the interval between the middle two houses is optimal for even n). The time limit is loose enough, so we do not have to implement median in linear time, it’s sufficient to sort the houses. Just be careful to pick the right one for even n to meet the tiebreaker criteria.

Qualification, 1000 points: CannonballPyramids

This is some version of the coin change problem. The cannonball pyramid sizes (“square pyramidal numbers”) are the values of coins we have available, and we are trying to pay any sum within the given range using at most six coins. 

In this particular problem and for the given constraints the solution always exists. There are multiple approaches possible. Below I describe one for which it is reasonably easy to prove that it is correct.

For small values of the sum B, the problem is solvable optimally (minimizing the number of coins) via DP.

If we do the DP for B up to, for example, 2,500,000, we may notice an interesting thing. There are indeed some values of B that require us to use exactly six coins. The smallest one is already B = 23 due to the lack of choice among small coins. However, what’s interesting is that B = 908 is the largest of these pathological cases. All bigger sums in the given range can actually be paid using fewer than six coins, as more coins become available once we get to the bigger sums and everything becomes smoother.

The biggest two coins we may ever use are 996,365,040 and 998,441,521, their difference is 2,076,481. Thus, any two consecutive coins have a difference that is significantly less than 2,500,000.

(We may also note that the first two coins below 2,500,000 are 2,490,670 and 2,452,645 with a difference of 38,025. This observation isn’t necessary while solving but it can now give us a stronger conclusion.)

Consider any B in (2,500,000; 10^9]. Due to the difference between consecutive coins, taking the largest coin that is <=B will certainly leave you somewhere in the range for which we know the optimal solutions. And now there are only two possibilities: either (usually) the remainder is a sum we can pay using at most five coins, or (in some unlucky cases) we hit one of the very few small values that require six. In the latter case, we know that we are very close to zero and we can simply use the second largest coin instead of the largest one. That one is guaranteed to leave us with a sum that is still within our DP range and at the same time big enough to avoid all the pathological cases at the beginning.

Summary of the solution we just proved:

1. for B <= 2,500,000 use DP
2. for 2,500,000 < B <= 10^9 greedily use the biggest coin and finish the solution via the same DP as above
3. for 2,500,000 < B <= 10^9 if step 2 did not produce a valid solution, doing the same with the second biggest coin will.

Note that greedily using one of the two biggest coins as your first step is not guaranteed to work if you also try that for smaller values of B. E.g., for B = 4608 taking the biggest coin (4324) leaves you with 284 while taking the second biggest (3795) leaves you with 813; and both 284 and 813 require six more coins. The problem here is that the difference between the two small coins is too small to get us out of the range that contains the pathological cases. Correct solutions that start with a greedy step are still possible but in general they may need to try more possibilities for the first coin they use.

Using one of the two biggest coins does work for all large inputs. Hence, a carefully pruned brute force search can actually pass.

If you still want to play around with this problem, challenge yourself to find out how large the upper bound 10^9 could have been. Are more than six pyramids ever needed?

Elimination round 1: ClimbingCombined

The problem explores a real-life scoring system in which the final rank of a participant is determined by the product of their ranks in three individual events. Suppose we have the situation after two events, we pick a participant A and we ask the question what is A’s best possible placement. How to answer this question in an efficient way?

Clearly, we can have participant A win the last event, so their product of ranks will remain unchanged. In order to give A as good a placement as we can, A must beat as many other competitors as possible.

One way of approaching this task is to phrase it as follows: given x, can A beat at least x other climbers? As this property is clearly monotonous, if we can answer this question, we can then use binary search to find the largest possible x. And once we fix x, the verification is easy. If A should beat some x climbers, we can certainly have A beat those x climbers who are currently the bottom x (not counting A). And if any way of beating those x works, the way where they are the last x in the third event must work. Even more precisely, the best we can to is to place the best of these x last (so that their product, currently the smallest among those x, gets multiplied by the largest value), and so on. Thus, we simply take this one optimal order of those x contestants, calculate their final products of ranks, and verify that none of them beat our contestant A.

Another possible approach is to go full greedy. Again, we will fix the contestant A and then we will try to have them beat as many other contestants as possible. In order to do that, we will process the other contestants from the bottom to the top. Whenever we process a contestant, we find the highest rank (in the ranklist for discipline 3) that is still available and makes that contestant’s final product greater than or equal to A’s product. Clearly, we can greedily assign this rank to this contestant. Once we hit the situation where we don’t have any rank available for the contestant we are processing, we know that we found the maximum.

Both approaches described above can be implemented in O(n^2 log n) quite easily. 

Even faster solutions exist. What is the best one you can find?

Elimination round 2: Leadership

We need to find a clever way of counting. Suppose we have N people in total. Let’s focus on the first person we activate, and imagine their starting skill as a black ball. When we activate this person, everyone else gets 1 ball. When we activate the second person, that person will also start sharing their skill with others, but let’s ignore that for now and focus on the balls only. This person has 1 ball, so again everyone else gets a ball. At this moment, the people who weren’t activated yet have 2 balls each.

We can now continue tracking the black balls. The third activated person will give everyone else 2 balls. The fourth one will give everyone 4 balls, the next one will give 8, then 16, and so on.

So, what’s the final state? We have the one ball we started with, and then there were n rounds of adding balls. In each round N-1 people received new balls, and the counts of those balls were 1, 1, 2, 4, …, 2^(N-2). This gives us a total of 1 + (N-1) * (1 + 1 + … + 2^(N-2)) = 1 + (N-1) * 2^(N-1) balls. Thus, if this person’s initial power is P, their total contribution to the final power is P*(1 + (N-1)*2^(N-1)).

We can now go through the same thought process with the second person to be activated. Imagine this person starting with a red ball. The total number of people remains unchanged, so whenever someone hands out new red balls, these go to N-1 other people. However, the number of such events goes down from N to N-1, as one person was already activated before the whole process of handing out red balls could start. Thus, if this person’s power is P2, their final contribution to the total power of the crowd will be P2*(1 + (N-1)*2^(N-2)).

From these observations we already know everything we need. It is clear that we want to activate the people in decreasing order of their initial power to maximize their contribution to the result. And once we know this, we can group them by power (which is conveniently done in the input already) and for each such group we can then easily compute their total contribution by summing a geometric series.

Finals 200pt: RepeatFreeSquares

This was an easy problem for speed-solving. All we need to realize is that if a number has no repeated digits, it has at most 10 digits. Thus, all possible elements of our sequence are less than 10^10. And as they are squares, they are numbers of the form x^2 with x < 10^5. And this observation tells us that we can afford to generate and filter: try all possible x, for each of them compute x^2 and check whether it has the desired property.

Finals 1000pt: CardConcat

For this problem we clearly need to find some polynomial-time solution using dynamic programming. There are multiple approaches that pass (we intentionally did not push the constraints too much). One possible approach follows.

For each card c and each d we want to count how many numbers contain the card c followed by exactly d other digits. If we denote this count as cnt[d], the answer is clearly the sum of cards * cnt[d] * pow10(d) over all c, d.

For counting cnt[d], we can split it into groups based on how many cards (x) are used to form those d digits after our card. Once we fix x, we can separately count tail[d][x] = the number of ways to form a d-digit number using x of the cards other than c, and head[n-1-x] = the number of ways to form anything using the remaining n-1-x cards. Both of these values can be computed using dynamic programming. A fast way of computing tail[d][x] involves first computing the values tail[d][x] for the situation when we are allowed to use any card, and then for each specific c computing tail[d][x] by subtracting the contribution of card c to tail[d][x].