July 9, 2020 2020 TCO Algorithm Round 2A Editorials

GridSpiral

Here’s a slightly bigger spiral:

25 26 27 28 29 30
24  9 10 11 12 31
23  8  1  2 13 32
22  7  0  3 14 33
21  6  5  4 15 34
20 19 18 17 16 35

Look at any straight segment of the spiral, e.g., the numbers 12 to 16. A number x that lies on the inside of this segment (e.g., the number 14) has four neighbors: x-1, x+1, a smaller neighbor, and a bigger neighbor y. But then we can observe that the number x-1 has the neighbor y-1, and these have the same difference y-x. Hence, the numbers that are on the segments of the spiral are never the smallest answer for any difference.

This means that the candidates are only the corners of the spiral. And we can easily determine that 0 is the answer for differences 1, 3, 5, and 7, and then for each other odd difference we have to move to the next corner of the spiral. Thus, the answer for difference 2k+7 is the value in the k-th corner of the spiral. Determining this value can be done simply by counting the steps we made until we got there, which involves summing some simple arithmetic series and can be done in constant time.

If we color the entire grid as a checkerboard, we can easily verify that the colors correspond to parities of numbers, hence the difference can never be even.

PrimeSubstrings

The task is easy for L=1: just print any number whose every digit is a prime. Similarly, there are easy solutions for L=2, such as 1111111… and 13131313…

Ideally, we would hope to find, for each L, a number of length 1000 such that absolutely all of its substrings of length L are primes. (The answer for N < 1000 can then simply be a prefix of length N of this number.)

How can we verify whether such a number exists? We can generate all L-digit primes and build what’s essentially a de Bruijn graph. The vertices are sequences of L-1 digits and each prime gives us one directed edge. For example, if you have the prime 12347, it gives you an edge from 1234 to 2347. This edge tells you that in your number the substring 2347 can follow the substring 1234.

Each valid number corresponds to a walk in this graph. Thus, we are looking for a walk of length (approximately) 1000. And the easiest form such a walk can have is, obviously, a cycle. If our graph contains a cycle, we win: we can walk along it forever to generate longer and longer numbers.

Example for L=3: The numbers 113, 131, and 311 are all primes. In our graph they give us the edges 11 -> 13, 13 -> 31, and 31 -> 11. These three edges form a cycle. Walking along this cycle creates the number 113113113113… with the property that each 3-digit substring is a prime.

For L=4, 5, 6 we can find such cycles with a very simple form: just like for L=3, there are primes such that all their cyclic shifts are primes, too. Examples include 1193, 11939, and 193939.

For L=7 there is no such prime, but we are in luck and there are still cycles in the graph. One such cycle corresponds to the number formed by periodically repeating the sequence 13339913.

(Building the full de Bruijn graph is not necessary. In my precomputation I just used a sieve to generate all primes up to 10^7 and then a simple DFS on primes themselves that used a set of primes to check whether a vertex is valid. The implementation of the actual solution is then trivial: just hard-wire one period (or one full string of length 1000) for each L.)

Exercise: What happens for L=8?

PairsOfHouses

Let’s start with a 1-dimensional version of this problem. If we have C houses in a row, clearly the smallest number of pairs of houses that can communicate is C-1: the neighbors can always communicate, and e.g. if all the houses have the same height, no one else can.

The largest number of communicating pairs is C*(C-1)/2: all pairs. This is achieved whenever the polyline that passes through all the tops of buildings in order is convex. One simple way of constructing that is to place the points onto some parabola. For example, we can use heights 1, 1, 2, 4, 7, 11, 16, … (the differences between these are 0, 1, 2, 3, 4, 5, …).

A simple solution (in terms of implementation, not idea) can be produced by looking for the solution in a very constrained form. The maximum number of M = R*C*(C-1)/2 + C*R*(R-1)/2 is achieved for a city in which each row and each column is convex, for example the city where the building at (r,c) has height r*r + c*c + 1. This city can then be modified to decrease the total number of visible pairs by a very small constant. We can do that with small local tweaks to the heights. (E.g., note that increasing values in the first column does not violate visibility in rows, so if we can do that to reduce the number of visible pairs in the first column by any small constant, we have won.)

And we can easily prove (or verify by brute force) that if we can produce all values in the interval [M-R+1,M] for each pair R, C, we can cover all possible outputs. Below I explain an alternate solution that is more complicated to implement but can also construct grids that have a number of visible pairs that is significantly below M.

For that, let’s go back to the 1D version for now. We’ll need to check that not just the minimum and maximum, but also all values between those two can be achieved, too. One particular way to construct a sequence of heights for each particular number of visible pairs is to only look for non-decreasing sequences and to do it incrementally: we start with just the sequence [1] for C=1 and then we go through C=2, 3, … and each time we take all the sequences for C-1, try all reasonable possibilities for the next term, count the number of visible pairs for each of them, and verify that we hit all the counts we needed for the current C.

Other constructions are also possible. For example, we can construct all the 1D solutions by combining parabolic pieces (everyone sees each other) and linear pieces (just the neighbors see each other) as necessary in a knapsack-like fashion.

(The limit on R and C was kept quite low to allow various kinds of inefficient precomputations of these solutions.)

What remains is combining the 1D solutions for individual columns and rows into a full city. We will use one more trick to make sure we can get the necessary patterns without conflicts: we will use the same maximal pattern for each row and different patterns for the individual columns to get the total we need. The final height of the building at (r,c) will be L * same_row_pattern + this_column_pattern[r], where L is a large enough constant.

This way, each column still has its pattern preserved (the entire column is just shifted by the same constant) and each row still has its pattern preserved well-enough because multiplication of its pattern by L can make the small changes from the added column patterns negligible enough, so all pairs of buildings within a row will still see each other. 

The constraints should be small enough to allow us to test on all test cases locally and make sure our solution never produces an invalid output, so if you were not sure whether your construction always works, the best course of action was implementing your own checker and making sure it does.