Google Code Jam 2019 Qualification Round

It was probably depressing to realize that I have not participated in any programming competitions since the last October. It is more depressing that I nearly missed the Code Jam of this year: I received no notification mails and I did not think of it either. Anyway, I was lucky that someone informed me that it has begun in the last few hours, and here I come.

Problem 1 Forgone Solution

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an oversized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a 4… and the 4 key on the keyboard of our oversized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

Since you can provide any solution, avoiding any carrying in your solution makes things easier. And it is good enough: just design a way to split each digit into the sum of two digits that are not 4. An obvious one is to split 4 into 3+1 and everything else into themselves plus 0.

Problem 2 You Can Go Your Own Way

You have just entered the world’s easiest maze. You start in the northwest cell of an N by N grid of unit cells, and you must reach the southeast cell. You have only two types of moves available: a unit move to the east, and a unit move to the south. You can move into any cell, but you may not make a move that would cause you to leave the grid.

You are excited to be the first in the world to solve the maze, but then you see footprints. Your rival, Labyrinth Lydia, has already solved the maze before you, using the same rules described above!

As an original thinker, you do not want to reuse any of Lydia’s moves. Specifically, if her path includes a unit move from some cell A to some adjacent cell B, your path cannot also include a move from A to B. (However, in that case, it is OK for your path to visit A or visit B, as long as you do not go from A to B.) Please find such a path.

It is easily provable that

• an eastward move never coincides with a southward move;
• the i-th move in Lydia’s sequence can only coincide with the i-th move of yours;
• a path is legal if and only if it has N-1 eastward moves and N-1 southward moves.

Hence, even if coming up with a legal path that does not coincide with Lydia’s one is never a hard task, just swapping all E’s with S’s and vice versa is the easiest construction.

Problem 3 Cryptopangrams

On the Code Jam team, we enjoy sending each other pangrams, which are phrases that use each letter of the English alphabet at least once. One common example of a pangram is “the quick brown fox jumps over the lazy dog”. Sometimes our pangrams contain confidential information — for example, CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS — so we need to keep them secure.

We looked through a cryptography textbook for a few minutes, and we learned that it is very hard to factor products of two large prime numbers, so we devised an encryption scheme based on that fact. First, we made some preparations:

• We chose 26 different prime numbers, none of which is larger than some integer N.
• We sorted those primes in increasing order. Then, we assigned the smallest prime to the letter A, the second smallest prime to the letter B, and so on.
• Everyone on the team memorized this list.

Now, whenever we want to send a pangram as a message, we first remove all spacing to form a plaintext message. Then we write down the product of the prime for the first letter of the plaintext and the prime for the second letter of the plaintext. Then we write down the product of the primes for the second and third plaintext letters, and so on, ending with the product of the primes for the next-to-last and last plaintext letters. This new list of values is our ciphertext. The number of values is one smaller than the number of characters in the plaintext message.

For example, suppose that N = 103 and we chose to use the first 26 odd prime numbers, because we worry that it is too easy to factor even numbers. Then A = 3, B = 5, C = 7, D = 11, and so on, up to Z = 103. Also suppose that we want to encrypt the CJ QUIZ… pangram above, so our plaintext is CJQUIZKNOWBEVYOFDPFLUXALGORITHMS. Then the first value in our ciphertext is 7 (the prime for C) times 31 (the prime for J) = 217; the next value is 1891, and so on, ending with 3053.

We will give you a ciphertext message and the value of N that we used. We will not tell you which primes we used, or how to decrypt the ciphertext. Do you think you can recover the plaintext anyway?

This problem is a cautionary tale that how a cryptographically uneducated person could devise something that looks secure but is utterly broken. One might think factorizing a number is hard. However, it is not hard if it is known to share a common non-trivial factor with another number!

Find any two adjacent number that are not the same. The existence of such pair is guaranteed because it is a pangram. Calculate their largest common divisor, which is just their only common prime factor. Use this factor to chain calculate all other primes in the question, and problem solved.

Problem 4 Dat Bae

A research consortium has built a new database system for their new data center. The database is made up of one master computer and N worker computers, which are given IDs from 0 to N-1. Each worker stores exactly one bit of information… which seems rather wasteful, but this is very important data!

You have been hired to evaluate the following instruction for the database:

• TEST_STORE <bits>: The master reads in <bits>, which is a string of N bits, and sends the i-th bit to the i-th worker for storage. The master will then read the bits back from the workers and return them to the user, in the same order in which they were read in.

During normal operation, TEST_STORE should return the same string of bits that it read in, but unfortunately, B of the workers are broken!

The broken workers are correctly able to store the bits given to them, but whenever the master tries to read from a broken worker, no bit is returned. This causes the TEST_STORE operation to return only N–B bits, which are the bits stored on the non-broken workers (in ascending order of their IDs). For example, suppose N = 5 and the 0th and 3rd workers are broken (so B = 2). Then:

• TEST_STORE 01101 returns 111.
• TEST_STORE 00110 returns 010.
• TEST_STORE 01010 returns 100.
• TEST_STORE 11010 also returns 100.

For security reasons, the database is hidden in an underground mountain vault, so calls to TEST_STORE take a very long time. You have been tasked with working out which workers are broken using at most F calls to TEST_STORE.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 1024.
1 ≤ B ≤ min(15, N-1).

Test set 1 (Visible)

F = 10.

Test set 2 (Hidden)

F = 5.

I wonder how many people have tried to write database puns with “bae”. Admittedly I have also tried that before, so I smiled when I saw the title.

This is the only problem that I included the limits here, because they matter.

For the easy test case, it is easy to design a divide-and-conquer strategy. In the beginning all you know is N and B. You send a sequence of N/2 0’s and N/2 1’s, and from the answer you can infer how many of the B broken workers belong to the former N/2 and how many belong to the latter. Hence, with one query, you divide your question into two smaller ones, which can be further queried in parallel. Hence, with 10 queries, you can solve any combination of N and B as long as N is not larger than $2^{10}=1024$.

The hard test case requires to use the fact that B is at most 15. The basic idea is the same, but in your first query you send a sequence of alternating 16 0’s and 16 1’s. Since there are at most 15 broken workers, you can still infer how many of the broken workers belong to each of the 16-worker groups. Hence, N does not actually matter if B is limited to 15.

Afterthoughts

Google Code Jam has, once again, migrated to a cool new system. While the qualification round is definitely not hard, it offers a good opportunity to get a taste of the upcoming challenges.

I decided to use Python to solve problem 3 since I do not have a C++ library to deal with big numbers. I could have written one, but it would be annoying since I need to cover modulo and division. This has brought my regret during my Code Jam Final session last year: I wanted to use Python but since I have never used it in a competition, I didn’t want to take the risk. I should definitely get myself prepared for situations like this. And I should definitely have a C++ big number library ready. This kind of things reduce the frustration when you know the solution, but don’t have the time to type the routines.