Match summary

This round brought the online phase of the tournament to a conclusion, with another 25 skilled coders claiming their spots in what is sure to be an exciting on-site event. Good luck to all advancers in the final rounds!

The match started off with a very easy 250 problem that everyone was able to solve. The medium was a little trickier, but didn't stop a respectable number of coders from earning high scores on it. The third problem was supposed to reward the competitors able to grasp the idea behind it but, unfortunately, in the end dealing with precision issues was the most important part. Even though a lot of coders submitted or compiled solutions that were on the right track, few passed it. Achtung-Achtung spotted this issue and, along with his challenges on the medium, earned no less than 450 points during the challenge phase, securing him the win. In second and third came MB__ and sluga. In the end an accumulated high score on the first two problems was required in order to advance on-site.

The Problems

CandyBoxes

Used as: Division One - Level One:

Value 250

Submission Rate 81 / 81 (100.00%)

Success Rate 81 / 81 (100.00%)

High Score fpavetic for 249.19 points (1 mins 37 secs)

Average Score 231.70 (for 81 correct submissions)

This problem is a generalization of Euclid's algorithm (the subtracting version) for calculating the greatest common divisor of two numbers. Specifically, after the algorithm terminates, the result is the greatest common divisor of the numbers in candies. Because of the low constraints, a successful submission didn't need anything more than just implementing the algorithm described in the problem statement. However, an approach based on this observation can handle numbers much higher than those that were given. For a clean implementation see Prostu's solution.

StringOfNumbers

Used as: Division One - Level Two:

Value 500

Submission Rate 64 / 81 (79.01%)

Success Rate 42 / 64 (65.62%)

High Score fpavetic for 494.88 points (2 mins 53 secs)

Average Score 381.34 (for 42 correct submissions)

The first and most important step in solving this problem is figuring out if a fixed value of N is a solution to the problem and a candidate for the return value. A simple solution is to concatenate all the numbers from 1 to N, obtaining the original string, and then check if the given string is a substring of this resulting string. This can be done with a greedy method. For each character of the given string, find its first occurrence in the original string, starting from the character next to the one found in the last search. Let's say that we are interested in finding out whether the string s1 = "3702" is a substring of s2 = "123456789101112." First, we search for the first occurrence of character '3' in s2, and get index 2. Next, we search for the first appearance of '7', starting from index 3, and get the new index 6. Similarly, we find that the last two characters appear in s2 in positions 10 and 14, so we conclude that s1 is indeed a substring of s2. However, if s2 was two characters shorter, we would have reached the end of s2 before succeeding in finding the character '2', so s1 would not have been a substring of s2.

Now we try all possible values of N starting from 1, and return the first value of N that works. We have to be careful though, because applying the above method exactly as described may result in exceeding the time limit. The key observation is that, for a given N higher than 1, we don't need to restart the whole process all over again, and can use the information obtained from the previous step, when we tried N-1. Specifically, we concluded that N-1 is not a solution to the problem since the search for some character c of leftDigits was unsuccessful, and the end of the original string was reached. If we concatenate the string representation of N, s, to the original string, the search for all characters before and including c would go on in the same fashion until we reach s. Now we can continue with the search of c in s. If this search is successful and c is the last character of leftDigits, we can return N. Otherwise, we continue in a similar manner with the character following c in leftDigits. For a clean implementation of this approach, see fpavetic's solution.

SafeDrive

Used as: Division One - Level Three:

Value 1000

Submission Rate 31 / 81 (38.27%)

Success Rate 7 / 31 (22.58%)

High Score otinn for 643.29 points (24 mins 11 secs)

Average Score 442.88 (for 7 correct submissions)

The constraints in this problem were higher than they needed to be, and made this problem a lot harder than it was supposed to be. In fact, not even the original reference solution has handled correctly the unforeseen precision issues that had appeared. While this wasn't reflected in the system tests, Achtung-Achtung came up with a killer test during the challenge phase. Let's analyze the algorithmic part of the problem first and then see how to safely deal with floating point arithmetic in this case.

The key observation to this problem is actually contradicting the annotation given in example 2. It is of no use to travel with a variable speed: if you are going to reach a certain speed s at some point in time anyway, why not drive at this speed at all times? The time needed to get to the destination may improve, but would certainly not be worse.

Now, given a speed s, you need to see if driving at this speed allows you to arrive on time at the meeting — that is, check whether the time needed to reach position D is less than or equal to T. This could be done with a simulation: for each traffic light on the way, calculate the time of your arrival at that light, using the time of departure from the previous light. If this time is during an interval in which the light is red, wait until it switches to green, otherwise you don't need to stop.

Situations like this, when it is possible to find a method (a predicate) to check if, by keeping a parameter constant (fixing it), you have a solution to the problem, should activate a binary search trigger. Of course, to be possible to use binary search, another property must hold: the method should give the same answer if you increase (or decrease in case a maximum is asked) the value of the parameter. For more details and a nice introduction to binary search, see this tutorial. Applied to this problem, it is obvious that this property holds: if we reached the destination in time driving at a certain speed, we would arrive on time for any higher speed. This solves the last piece of the puzzle, and you can use binary search to find the minimum speed.

While all the above looks nice in theory, strange errors could occur in practice, especially when dealing with floats or doubles. Many competitors, even though they got the right idea, were burnt by these kinds of errors. What happened in the case of this problem? Let's say we are given two doubles a = 750000000.0 and b = 0.00000005 (that is 7.5e8 and 5e-8 respectively). Due to the way the doubles are stored (see this nice tutorial for all the details), a + b would be stored as 750000000.0 rather than the actual result 750000000.00000005. Briefly, about 17 digits are needed to store the correct result while doubles are able to provide only about 15 digits. Achtung-Achtung's test case uncovered this aspect. To work around this, my (new) solution stores the time needed to get to the destination, for a fixed value of the speed, as two numbers -- an integer for the integral part and a double for the fractional part -- rather than only one double. Even though the computations are still not entirely accurate (for example, try dividing the integer 999999999 by 999999999.00000001 and see what happens), it is more than enough to return an answer accurate to the most significant 9 digits, as is needed to pass. Note that comparing doubles using a tolerance is not needed in this case.

struct light {
    int a, b, pos;
    light() {}
    light(int na, int nb, int npos): a(na), b(nb), pos(npos) {}
};
bool operator < (const light& a, const light& b) {
    return a.pos < b.pos;
}

struct SafeDrive {
    double minSpeed(vector <string> lights, int T, int D) {
        int N = 0;
        light ls[64];

        for (int i = 0; i < lights.size(); ++i) {
            int a, b, pos;
            sscanf(lights[i].c_str(), "%d %d %d", &a, &b, &pos);
            if (pos < D) ls[N++] = light(a, b, pos);
        }
        ls[N++] = light(0, 0, 0);
        ls[N++] = light(0, 1, D);
        
        sort(ls, ls + N);

        double lo = 1.0 * D / T, hi = 1e10, res = -1.0;

        // it is better to loop through a predefined number of steps 
        //than checking whether lo and hi are equal within a given tolerance
        for (int steps = 0; steps < 200; ++steps) {
            double mid = 0.5 * (lo + hi);

            long long intTime = 0;
            double fracTime = 0.0;
            for (int i = 1; i < N; ++i) {
                long long n = ((long long)ls[i].pos - ls[i-1].pos) / mid;
                double z = (ls[i].pos - ls[i-1].pos - n * mid) / mid;

                // just to make sure
                if (z < 0) {
                    intTime--;
                    z += 1.0;
                }
                if (z >= 1) {
                    intTime++;
                    z -= 1.0;
                }

                intTime += n, fracTime += z;
                if (fracTime >= 1) {
                    intTime++;
                    fracTime -= 1.0;
                }

                if (intTime % (ls[i].a + ls[i].b) < ls[i].a) {
                    intTime += ls[i].a - (intTime % (ls[i].a + ls[i].b));
                    fracTime = 0.0;
                }
            }

            if (intTime < T || (intTime == T && fracTime == 0.0)) {
                hi = mid;
                res = mid;
            } else {
                lo = mid;
            }
        }

        return res;
    }
};

By _efer_
TopCoder Member