June 6, 2019 SRM 759 Editorial

Another round by me (espr1t) – this time not a TCO round but a standard SRM. I hope you’re not getting bored by Elly 🙂

Typical for the midday-in-Europe matches there weren’t too many contestants – around 200 in Div1 and another 350 in Div2. Still better than the 4 A.M. matches, though!

The match ran very smoothly with no questions being asked during the *entire* match. Also no technical issues that we know of. Yey!

This was one of the rare rounds in the recent years where two of the problems were shared between Div1 and Div2 – the Div1 250 was the same as the Div2 600 and the Div1 500 was the same as the Div2 900.

There were some blazingly fast solutions for the Div2 250, which was expected, as it was fairly trivial problem. This wasn’t the case in Div1, where the 250 required both an observation and some amount of coding. Solutions slowly started to pour, with the first one being submitted for 238.39 points (by uwi). Around 15 minutes late to the party, tourist opened the first problem and got it for 245.20 – this guy is a machine… In Div2 solutions to the 600 also started to pop here and there, although for much slower times than the Div1 ones (well, duh!). Newcomer diamond_duke was the first to submit the 250, the 500, and the 1000, which lead to his win in the second division. I’m curious if this is a second account, or just someone who is really good but hasn’t participated in TopCoder until now?

As the match revolved, many people in Div1 started submitting solutions to the 500 as well (which was much more standard and some people can even find it easier than the 250). With at least ten people being ready with the first two problems in the first 30 minutes, I started fearing the 1000 may not be hard enough to prevent many people from being done with the whole contest in less than an hour. Indeed, the first person with all three was ecnerwal (around 45 minutes into the match). This, unfortunately, still wasn’t enough to win the match, but at least he/she became target for the first time, woohoo! Congratulations! 🙂

It turned out that ecnerwal was more of an exception, as the second submitted solution was after the one hour mark, and in the end there were only 7 people who managed to submit it (four of them passing).

Div2 was much more balanced, with many people solving the easy, a few (in the order of tens) solving the medium, and just two dealing with the hard.

EllysViewPoints (Div2 250)

The easy problem for division 2 was indeed easy. It was designed for TCO Round 1B, but never used, thus it is slightly easier than a typical Div2 250.

The problem, in short, is given a matrix with N rows and M columns of zeroes and ones, find the number of cells with a zero, such that all other cells in the same row and same column are also zeroes.

There are multiple ways to solve it. The easiest one is to just implement the check with four loops: two to iterate through all cells (all possible viewpoints), and two more to check if there are no “blocked” cells (1s in the abstraction above) in its row and column. This worked for O(N*M*max(N, M)), but  even if implemented in O(N^2 * M^2) would have passed since the constraints were relatively low.

Another option was to realize that the answer is just the number of empty rows multiplied by the number of empty columns. To count this one would need O(N * M), which is also the optimal time this problem can be solved with:

long long rows = 0, cols = 0;
for (int row = 0; row < n; row++) {
    for (int col = 0; col < m; col++) {
        if (a[row][col] == '#') {
            rows |= (1LL << row);
            cols |= (1LL << col);
        }
    }
}
return (n - __builtin_popcount(rows)) *
       (m - __builtin_popcount(cols)));

EllysThreePrimes (Div1 250 / Div2 600)

The easy problem in Div1 (also used as medium in Div2) was maybe slightly harder than I’d like for a 250, but the “hard” part was to make an observation – otherwise the implementation was  fairly easy afterwards.

The problem was the following: given five integers sum1, sum10, sum100, sum1000, sum10000 which are supposed to be the sums of the 1s, 10s, 100s, 1000s, and 10000s of three five-digit  prime numbers, can you find any three such numbers which would give those sums?

The main thing to solve the problem was to realize that there aren’t that many prime numbers in the interval [10000, 99999]. As a rule of thumb we know that a number N is prime with chance in the order of 1/ln(N). Thus, numbers around 10000 have chance of being prime around 1/ 9.2, and numbers around 99999 have chance of being prime around 1/11.5. Thus, we’d expect around 10% of the numbers in [10000, 99999] to be prime, which makes less than 10000 numbers. In fact, it turns out there are exactly 8363 prime numbers in that interval. One could quickly find the primes using Sieve of Eratosthenes – see this tutorial for details if this is new for you.

Having that, we can do a simple “divide and conquer” solution – if we fix two of the numbers, we can get in O(1) the third one. Well, we still have to check whether it is prime, whether it has exactly five digits, and whether it is equal to some of the two fixed ones, but other than that we’re done.

Since we can fix the first two primes in increasing order, we have 8368 * 4184 = 35,011,712 possible pairs. For each of them we need 5 more operations to find the last one and a simple indexing in an array to see whether it is also prime. Please note that many of the pairs can be skipped as we have easy ways to prune the search. Even without the pruning, ~200 million operations aren’t that many on a modern processor, so this would fit in the 2 second time limit.

There are several things to get wrong here. Probably the most common bug was to find an answer, in which some of the numbers are the same. This was mentioned twice in the problem statement (once with italic to stress on it) and it actually makes sense – if you are to tell your favourite three numbers to somebody, would you tell them a number twice? Many people still managed to overlook it somehow, which lead to many happy challengers (some with four or even more successful ones). Gennady was no exception, but his 4 successful challenges actually brought him the victory with a comfortable margin.

The second possible way to fail the problem was to think that if there is a solution, then there are many solutions and just try random pairs of primes until finding a solution (or some time expires, in which case return that there is no solution). Unfortunately, there are tests with very few possible solutions (I couldn’t find any test with exactly one, though). The least I got to was 21 solutions.

All in all, this problem proved to be much more evil than I anticipated. In retrospect, I should have added a sample which checks the uniqueness of the returned numbers!

You can check out an example solution here:

private int MAX = 100001;
public int[] getPrimes(int[] sums) {
    boolean[] isPrime = new boolean[MAX];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAX; i++) if (isPrime[i]) {
        for (int c = i * i; c < MAX; c += i) {
            isPrime[c] = false;
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 10000; i < 100000; i++)
        if (isPrime[i]) primes.add(i);
    for (int i = 0; i < primes.size(); i++) {
        for (int c = i + 1; c < primes.size(); c++) {
            int rem0 = sums[4] - primes.get(i) % 100000 / 10000 - primes.get(c) % 100000 / 10000;
            if (rem0 <= 0 || rem0 >= 10) continue;
            int rem1 = sums[3] - primes.get(i) % 10000 / 1000 - primes.get(c) % 10000 / 1000;
            if (rem1 < 0 || rem1 >= 10) continue;
            int rem2 = sums[2] - primes.get(i) % 1000 / 100 - primes.get(c) % 1000 / 100;
            if (rem2 < 0 || rem2 >= 10) continue;
            int rem3 = sums[1] - primes.get(i) % 100 / 10 - primes.get(c) % 100 / 10;
            if (rem3 < 0 || rem3 >= 10) continue;
            int rem4 = sums[0] - primes.get(i) % 10 / 1 - primes.get(c) % 10 / 1;
            if (rem4 < 0 || rem4 >= 10) continue;
            int num = rem0 * 10000 + rem1 * 1000 + rem2 * 100 + rem3 * 10 + rem4;
            if (isPrime[num] && num != primes.get(i) && num != primes.get(c)) {
                return new int[]{primes.get(i), primes.get(c), num};
            }
        }
    }
    return new int[]{};
}

EllysHash (Div1 500 / Div2 900)

As I feared, this problem turned out to be almost as solved as the 250. It *was* harder, but it was also much more standard, and people with enough experience to see meet-in-the-middle when they encounter it knew what they have to do from the very beginning.

The problem, in short, was given three strings A, B, and C with length N, to create a new string S with length N, in which S[i] = A[i] or S[i] = B[i] or S[i] = C[i] and the hash of S is as low as possible. The contestants had to find that lowest hash (given a concrete hashing function).

Since N was relatively low (N <= 28), that had to ring a bell for many of the contestants that the solution should be built around this.

For each position in S we had three choices – get the letter from A, from B, or from C. 3^28 choices are too many unfortunately, but not *way* too many – there are 22,876,792,454,961 possible strings that can be built, which, in the grand scheme of things, isn’t that enormous. In similar problems we often have to apply “Meet-in-the-Middle” approach – divide the problem in two relatively equal parts, solve each of them independently, and combine the results. In this case, the length of the halves of the string would be up to 14, thus there would be 3^14 = 4,782,969 possible strings, which can be checked in much less than a second. If we split the given problem into two instances with N <= 14, we could solve these quite quickly.

Unfortunately, the hash of the string depends on both parts and the lowest hash cannot be found by simply finding the lowest hash in both parts. One has to combine the results of the sub-problems in a smarter way in order to obtain the real answer.

Fortunately for us, the given hashing function is pretty simple and we can exploit that. Imagine we’ve split the input string (with length N) into two strings with length L and R, respectively (R can be either L or L-1, depending on whether N was even or odd). If we have a string in the left part with hash HL and a string in the right part with hash HR, the concatenation of those two strings would have hash HL * 127^R + HR.

So what we *can* do is find the hashes of all possible strings in the left part and sort them; then find the hashes of all possible strings in the right part and sort them, and finally find which combination of a hash from the left part multiplied by 127^R plus a hash from the right side gives the lowest number. Once we have the hashes sorted, finding the hash in the right part for a fixed hash in the left part can be done easily with binary search. What’s even more, since we’ve sorted also the hashes in the left part, we can do “two pointers” solution (moving a pointer in the left or right arrays of hashes to keep the resulting hash as low as possible, while iterating all hashes on the left).

The described solution has complexity O(3^(N/2) * (N/2) + 3^(N/2) * log(3^(N/2))), which is dominated by the second part, thus O(3^(N/2) * log(3^(N/2)). This is around 4782969 * 25 = 119,574,225 operations – low enough to fit nicely into two seconds on a modern processor.

An example solution (which uses binary search and sorts only one of the halves):

int n;
char a[3][MAX];
long long pwr[MAX];
vector <long long> valuesL;
vector <long long> valuesR;
void recurse(long long hash, int idx, int limit, vector <long long>& values) {
    if (idx >= limit) {
        values.push_back(hash);
    } else {
        recurse((hash + a[0][idx] * pwr[idx]) % MOD, idx + 1, limit, values);
        recurse((hash + a[1][idx] * pwr[idx]) % MOD, idx + 1, limit, values);
        recurse((hash + a[2][idx] * pwr[idx]) % MOD, idx + 1, limit, values);
     }
}
long long solve() {
    int sizeL = n / 2 + n % 2;
    pwr[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--)
        pwr[i] = (pwr[i + 1] * BASE) % MOD;
    recurse(0, 0, sizeL, valuesL);
    recurse(0, sizeL, n, valuesR);
    long long ans = MOD;
    sort(valuesL.begin(), valuesL.end());
    for (int i = 0; i < (int)valuesR.size(); i++) {
        long long target = MOD - valuesR[i];
        int left = 0, right = (int)valuesL.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            valuesL[mid] < target ? left = mid + 1 : right = mid - 1;
        }
        ans = min(ans, (valuesR[i] + valuesL[left % (int)valuesL.size()]) % MOD);
    }
    return ans;
}

EllysTournament (Div1 1000)

This was an easy-to-state problem, and the solution wasn’t too long or too hard either – the problem with it was that it was hard to wrap your head around it (there are so many things happening with each choice)!

Fortunately for the contestants who managed to get to a working solution, the sample inputs were strong (as they pretty much covered correctness). However, what the samples didn’t cover was TL (the largest one was with N = 100 with the limit set to 500). Still, as tests were pretty easy to generate, I expected people to check this themselves and be fairly sure in their solutions (thus no or very few challenges/systest fails on this problem). Surprisingly, 3 out of the 7 submissions failed, thus bringing the accuracy on the problem to slightly over 50%.

The task was the following. Given a list of N integers, you start choosing pairs of neighboring integers and remove one of them at each step. If the integers were X and Y, then X is removed with chance Y/(X+Y) and Y is removed with chance X/(X+Y). If the integer at position i is removed, then the integers at positions i-1 and i+1 (if there are such) are now considered neighboring. The contestants had to find the chance that the number in the K-th position in the original list remains as the last number.

There are multiple solutions here, but most of them are too slow for the given constraints. Fortunately for me, I was able to test each next faster solution using the previous one 🙂

It should have been fairly obvious to all participants who got to the third problem in Div1 that this was a dynamic programming problem. If you don’t know the concept of dynamic programming or want a refresher, you can run through this tutorial.

The real problem here was how to make the state small enough (since O(N^3) memory was too much) and the DP fast enough (since O(N^4) time was too much).

If N was up to 20, there is a bitmask DP solution which keeps track which numbers are already thrown out and which are not. This works in O(2^N * N), but for N <= 500 this was waaaay too slow.

One main observation needed for the next several ideas is that, given an interval [L, R] and a person X (L <= X <= R) whom we want to “win” this interval, splits the task into two subtasks: one for [L, X] (with the person whom we want to win on the right end) and one for [X, R] (with the person whom we want to win on the left end). Thus, we can decrease the state from [L][R][X] to [L][R][2], which solves the problem with the memory. What’s more, since being on the left end or the right end is not really different (well, just a tiny change in the code), for this analysis we’ll only consider the person whom we want to win to be on the left end (position L) – extending the code to handle the other case should be trivial – see the provided code at the end for details.

In the beginning we know that Elly is on the K-th position – since we want her to win, we call the DP function twice – once with [1, K, 1] (she’s in the right end of this interval) and once with [K, N, 0] (she’s on the left end in this interval). We can multiply the probabilities for the two sub-tasks to get the answer for the whole task.

Now let’s see how we can get a working solution for N up to around 100.

For any interval [L, R] we know that we want L to win, but don’t know how this will happen (there are many options for doing so). We do know, however, that L will participate in the last match against some of the other R-L people in the interval. Let’s fix this other person X (L < X <= R)! We do a for loop which checks each of the possible “last” opponents. In order for the last match in the interval [L, R] to be between L and X two things must happen:

1. X wins in the [X, R] interval – which is a sub-task of the original problem, thus can be calculated by the same DP function;
2. The matches in [L, X] end up in such a way, that L and X are the last people left in the interval.

The first point is trivial – just call recursively the DP. The second point is not that obvious, so let’s examine it further.

We can select “where” L and X will “meet” – the position where the last match in [L, X] will happen (let’s say point M (L <= M < X)). We fix that with another for loop. Knowing M, we know that L must win in [L, M] and X must win in [M+1, X]. Those are just smaller instances of the same problem, thus can also be solved by the DP!

So now we have O(N^2) state with O(N) to fix the opponent and another O(N) to fix the meeting point. This leads to a O(N^4) solution, which works okay for N up to 100.

We need to optimize it a bit more, though. Instead of doing two nested loops (one for the opponent and one for the meeting point), we can take out the inner loop into a second DP. It will tell us “Given an interval [L, R], what is the chance that L and R will play as last?” It also has a state with size O(N^2) and this time a single for loop (to fix the meeting point) for a total of O(N^3) runtime. But now the outer DP also becomes O(N^3), for a total of O(N^3) for the whole problem! This solution works fast enough for N <= 500.

The code for this problem is actually relatively simple:

int n, k;
int a[MAX];
double dp[MAX][MAX];
double dyn[MAX][MAX][2];
double recurse(int, int, int);
double go(int left, int right) {
    if (left + 1 == right)
        return 1.0;
    if (dp[left][right] == dp[left][right])
        return dp[left][right];
    double ans = 0.0;
    for (int meet = left; meet < right; meet++)
        ans += recurse(left, meet, 0) * recurse(meet + 1, right, 1);
    return dp[left][right] = ans;
}
double recurse(int left, int right, int side) {
    if (left == right) return 1.0;
    if (dyn[left][right][side] == dyn[left][right][side])
        return dyn[left][right][side];
    double ans = 0.0;
    int pos = !side ? left : right;
    for (int opp = left; opp <= right; opp++) if (pos != opp) {
        double chancePlay = 1.0 / (right - left);
        double chanceWin = (double)a[pos] / (a[pos] + a[opp]);
        double chanceOpp = !side ? recurse(opp, right, 0) : recurse(left, opp, 1);
        double chanceMeet = !side ? go(left, opp) : go(opp, right);
        ans += chancePlay * chanceWin * chanceOpp * chanceMeet;
    }
    return dyn[left][right][side] = ans;
}
double ans = recurse(0, K - 1, 1) * recurse(K - 1, N - 1, 0);