April 28, 2020 2020 TCO Algorithm Round 1B Editorials

The second round of TCO 2020 was, by intention, quite easier than a usual round (even for Division 2). Indeed, with the top 250 people receiving a bye and another 750 already qualified, the problem set was adjusted for the people who have still not qualified, providing an opportunity to solve 2 or even 3 problems in the 75 minutes of the competition.

With the number of total registrants for the official match being actually less than 750, this seemed like a good call, as basically anyone with a positive score would qualify. On the other hand, the nearly 200 people in the parallel round were going to face a *very* easy problem set, which may lead to unrealistic rating changes, but c’est la vie, I guess. Let’s see if anyone manages to complete it in less than 10 minutes!

EllysCandies

This was a fun problem. In the end it turns out that the initial values of the boxes don’t matter – the winner is always the person who takes the last one.

Why is this true? Whenever you take a box, all of the candies in it are added to *each* remaining box. Thus, the next box someone takes contains strictly more than the one we just took. In fact, if the game has progressed already and each of the players have taken several boxes, the candies of *all* of them is contained in *each* of the remaining ones. Thus, each box contains more candy than the total score of each player (even the sum of their scores). So, the person who takes the last box actually in that single turn takes more candy than all candy that was taken in the entire game so far. So, it only matters who takes the last box.

So, the order in which the girls take the boxes doesn’t matter, so *any* greedy solution would work! Fun, right? Of course, the most trivial solution would be something along the lines of:

public class EllysCandies {
    public String getWinner(int[] boxes) {
        return boxes.length % 2 == 1 ? "Elly" : "Kris";
    }
}

One final touch – the constraints of 20 could actually deceive some of the better contestants that the problem needs to be solved by bitmask DP (which it can, due to the fact that almost any solution solves it). Still, this was mostly because the sum of the scores otherwise overflows 32-bit integers, which we didn’t want. 

EllysWhatDidYouGet

This problem was inspired by a running joke recently – where would you travel to next. The list contains several countries, but at number 9 is “Stay at home”.

Anyhow, for this problem we didn’t have to do anything fancy. The constraints were low enough to brute-force all triplets (X, Y, Z) and count which of them work for all initial numbers in [1, N]. Initially the constraints for X, Y, and Z were up to 100, which required adding a break in the most-inner cycle so it doesn’t time out, but with the current constraints even this is not necessary.

Implementation-wise, the solution could look like this:

public class WhatDidYouGet {
    private int eval(int num, int X, int Y, int Z) {
        int sum = 0;
        for (num = ((num * X) + Y) * Z; num > 0; num /= 10) {
            sum += num % 10;
        }
        return sum;
    }

    public int getCount(int N) {
        int ans = 0;
        for (int X = 1; X <= 50; X++) {
            for (int Y = 1; Y <= 50; Y++) {
                for (int Z = 1; Z <= 50; Z++) {
                    boolean okay = true;
                    int last = eval(1, X, Y, Z);
                    for (int i = 2; i <= N; i++) {
                        if (last != eval(i, X, Y, Z)) {
                            okay = false;
                            break;
                        }
                    }
                    if (okay) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }

This was supposed to be the 250 of the set, but due to the consideration of having more people with positive scores we decided to move it as a Medium.

EllysDifferentPrimes

There are two main things to this problem – one is to check if a number consists only of different digits, and one to check if a number is prime. The first one can be done in various ways efficiently, but here’s an example implementation:

private boolean isDifferent(int num) {
    if (num < 0) return false;
    for (int mask = 0; num > 0; num /= 10) {
        if ((mask & (1 << (num % 10))) != 0)
            return false;
        mask |= (1 << (num % 10));
    }
    return true;
}

The second one was to check if a number is prime or not. For this we need a somewhat efficient implementation – the standard one going to the square root of the number is good enough, as it turns out. There exist even faster ones (either Erathosthene’s sieve or probabilistic ones), but for this problem they weren’t needed. So, we can use the following function:

private boolean isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++)
        if (num % i == 0) return false;
    return true;
}

Finally, since the constraints were low enough we could actually bruteforce the answer – for each candidate (both lower and larger than N) we test whether it is both different and prime, and if it is, directly return it:

public int getClosest(int N) {
    for (int cand1 = N, cand2 = N; ; cand1--, cand2++) {
        if (isDifferent(cand1) && isPrime(cand1))
            return cand1;
        if (isDifferent(cand2) && isPrime(cand2))
            return cand2;
    }
}

Since we start from N, we guarantee that we have found the closest one. Since we check first the lower one, we guarantee we handle the case with two numbers being at equal distance.

With the cycles above we get to the first numbers with different digits in about 1,000,000 iterations (one of the bad cases is, for example, N = 44,500,000)  and after that we find a prime such number relatively quickly (the chance of a number around N being prime is roughly 1 / ln(N)).

This problem was initially with constraints for N up to 10^12. In that case we needed to generate the candidates in a smarter way – we can do with a DFS and sort them, or with a BFS and avoid the sorting. The solution with DFS actually was timing out, thus the initial solution was much harder than this one. After we have a sorted list of numbers with different digits, we needed to find the approximate position of N and go in both directions to test if each of the numbers are prime. Since prime numbers are relatively common, this solution was finding the answers quickly enough.

One tricky test case here is that the answer for N = 50,000,000 is 50,123,467 – a number over 50,000,000. So, if the contestants generated the numbers only up to 50,000,000 they would fail. Let’s see if many people fall for this!