April 21, 2019 2019 Topcoder Open Algorithm Round 1A Editorials

Match Overview

TCO19 Round 1A
Saturday, April 20th, 2019

Match summary

The 20-th of April marked the start of the Algorithm track of 2019 Topcoder Open with Round 1A. Out of the 1514 registered a bit less than 600 didn’t open any of the problems, making it fairly obvious that a non-zero score would be enough to qualify for round 2. In the end only 649 people managed to do so and will join the 250 byes there. For the rest of the people – both those who didn’t participate and those that couldn’t get a positive score there will be Round 1B scheduled for the first of May (International Worker’s Day, also known as Labour Day, which, ironically, is non-working in many countries).

The problem set was prepared by me – espr1t – this being the 17-th round I’ve given in Topcoder (either TCO or SRM). I’ve always liked problems which allowed multiple challenges (remember Sheep?), and today’s problems were no exception. Both the 500 and the 1000 had to be implemented very carefully, in the first taking care of the multiple corner cases, and in the second, possible problems with precision.

In the end coming up with a good test case on the 1000 proved somewhat hard, thus not many people used the opportunity for challenge. The 500, on the other hand, was much easier in that regard, which lead to literally hundreds of people being challenged.

After the dust settled, mrho888 claimed the top spot (not without the help of 5 successful challenges, on the 500 and 1000). Within a challenge of him was Ping_Pong who had slightly faster 1000, but “only” 3 challenges. The user EveRy rounded up the top three with slightly slower times, but again 5 successful challenges.

The Problems

EllysAndXor

The first problem was supposed to be rather trivial, but still, some people managed to fail it (some of them yellows, nonetheless!).

The task required to put bitwise AND (&) and XOR (^) operators between up to 10 numbers in such a way that the result of the expression is as large as possible. This was further simplified by stating that the operators have equal precedence, thus the expression is evaluated left to right.

The low count of the numbers should be a clear indicator that a bruteforce solution might be viable here. Indeed, a simple backtrack that tests all possible expressions runs in milliseconds. Another option would be to use iterative bruteforce (testing all bitmasks below 2**N). Both of these solutions have complexity of O(2**N), which, for the given constraints, was more than enough.

The recursion might have looked as follows:

int recurse(int idx, int num) {
    if (idx >= n)
        return num;
    return max(recurse(idx + 1, num AND a[idx]),
               recurse(idx + 1, num ^ a[idx]));
}

Alternative solutions and additional comments.

An alternative approach here (which would have worked for much larger constraints) would be to use a dynamic programming (the state being [current_index][current_number]). Thus would have complexity O(N * 1024), as all the numbers we could get are between 0 and 1023, inclusive.

EllysCodeConstants

Used as: Division One – Level Two:

This was (expectedly) a very easy-to-get-wrong problem, which lead to a bloodbath during the challenge phase. Out of the 670 submissions at the end of the coding phase, only 250 survived the challenge and testing phases. This isn’t too bad, actually, as the vast majority (>90%) of the participants submitted a solution and around 1/3 of them got it right, thus still not a hard 500 – just deceivingly easy.

The problem itself was, given a string, to express it as a hexadecimal literal (using the hex digits A-F, as well as 1 as ‘I’, 2 as ‘Z’, 5 as ‘S’, 7 as ‘T’, and the possible suffixes U, L, LL, UL, ULL, LU, and LLU). This way, for example, the word TASTEFUL could be expressed as the hexadecimal literal 0x7A57EFUL.

The solution was to just implement the decomposition of the string to digits and a suffix and check whether the digits contain invalid characters. And do it very, very carefully.

There are multiple things to get wrong here:

1. Only suffix, which violates the rule “A hexadecimal literal must have at least one valid digit (0-9, A-F).”. For example, 0xUL is invalid.
2. Have multiple suffixes. An example invalid literal would be 0xALLLL
3. Have a suffix not at the end. An example invalid literal would be 0xBLUE

Implementing this carefully was the key to success in this problem. One should have not cared about efficiency, as the constraints were really low. Inefficient implementations could simplify the code and actually be a good thing here:

map <char, char> REP = {
    {'O', '0'}, {'I', '1'}, {'Z', '2'}, {'S', '5'}, {'T', '7'},
    {'A', 'A'}, {'B', 'B'}, {'C', 'C'}, {'D', 'D'}, {'E', 'E'}, {'F', 'F'}
};
set <string> SUF = {"", "L", "LL", "U", "UL", "ULL", "LU", "LLU"};
string getLiteral(string str) {
    string ret = "";
    while (!str.empty() AND-AND REP.find(str[0]) != REP.end()) {
        ret += REP[str[0]];
        str.erase(str.begin());
    }
    return (ret == "" || SUF.find(str) == SUF.end()) ? "" : "0x" + ret + str;
}

Alternative solutions and additional comments.

An alternative solution would be to use regular expressions, which could make the code very short and tidy. See EveRy’s solution for a reference implementation.

EllysTicketPrices

Used as: Division One – Level Three:

 

Value	1000
Submission Rate	425 / 909 (46.75%)
Success Rate	146 / 425 (34.35%)
High Score	SpyCheese for 911.37 points (9 mins 2 secs)
Average Score	623.41 (for 146 correct submissions)

The second deceivingly easy problem in the set was the 1000. It looked like a simple binary search, and the rounding to two digits after the decimal point seemed to take care of possible rounding errors which often arise when dealing with floats.

It turns out that exactly this rounding is the thing that leads to problems! As it happens multiple times (approximately O(log * N)) the chance that at least once it is computed wrong become high. My various implementations show that a random test (which has a valid answer) has chance around 1 in 4 to yield wrong results with doubles. To make the problem fun, I chose such examples that neither of my four implementations with floats fails on them.

The problem, in short, is the following. Assuming you have a number X, you are given rules how to mutate it N-1 times so you generate N floats with exactly two digits after the decimal point. You want the average of these N numbers to be a certain value. You are to find a X that leads to this target average.

Since the mutation of X was fixed, it was fairly obvious that larger X would yield larger average, and lower X would yield lower average. This monotonically changing average was a hint towards binary search – which, in fact, was indeed the solution. However, one had to see that floats are likely to lead to precision errors, thus one should multiply all numbers by a 100 and work with integers only. A very good article on the topic of floats is written by none other but the current Algorithm admin misof! You can find the relative topics here and here.

So, after converting floats to integers, the solution was as follows. Do a binary search over X (the answer). For each value of the binary search, apply the mutation, compute the average, and compare with the target. If it is lower, increase X. If it is higher – decrease it. And that’s it!

long divNum(long num, long divisor) {
    if ((num % divisor) * 2 >= divisor)
        num += divisor;
    return num / divisor;
}
long eval(long price, int n, int[] change) {
    long average = price;
    for (int i = 0; i < n - 1; i++) {
        price = divNum(price * (100 + change[i]), 100);
        average += price;
    }
    return divNum(average, n);
}
public double getPrice(int N, int[] C, int target) {
    long left = 0, right = 1000000001L;
    while (left <= right) {
        long mid = (left + right) / 2;
        if (eval(mid, N, C) < target * 100) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return (right + 1) / 100.0;
}

Alternative solutions and additional comments.

In terms of complexity, this was O(N * log(target * N)), since X was in the range [0, target * N], and for each iteration of the binary search we need to compute the average, which is an O(N) subroutine. An interesting question is why X is in [0, target * N] – can you figure that out?

By espr1t
Topcoder Member