Match Editorials

Match summary

Achtung-Achtung won the first HS event in three weeks. In his second ever HS match, Achtung-Achtung destroyed the field -- recording the highest score on the hard problem, racking up +475 points on challenges and winning by more than 400 points. HS-veteran tomekkulczynski was second, wintokk finished third, and ahyangyi ended up in fourth place (despite being in the lead after the coding phase).

The Problems

Value	250
Submission Rate	67 / 74 (90.54%)
Success Rate	27 / 67 (40.30%)
High Score	ahyangyi for 245.11 points (4 mins 1 secs)
Average Score	213.99 (for 27 correct submissions)

This problem was a simulation of the process, described in the statement, but a lot of solutions failed because of different tricky cases. The first thing to note is that the album contains at most 20 songs of 180 seconds each, or, in other words, playing all songs will take less than 20 * (180 + 5) < 20 * 200 = 4000 seconds. Therefore, we start checking every second fror the second 0 and until we find the moment when Victor will hear the ring. The phone will ring at seconds with numbers 0, delay, 2*delay, 3*delay, ..., so, as you can see, the phone will ring a second i if (i % delay) == 0. Let's find how to check if the music will play at second i.

The first song will play from second 0 till the second (songDuration - 1), then will be a 5-seconds pause, then the music will play for another (songDuration) seconds, then another pause will start and so on. As you can see, the process is repeated every (songDuration + 5) seconds, with the music playing first songDuration of each such period. Therefore, the music does not play during second i, if (i % (songDuration + 5)) is greater or equal to songDuration (which corresponds to the pause in the interval). Having this formula, we are almost done except the last corner case. If second i is greater than N * (songDuration + 5), then the music cannot play during this second, because all songs from the album were already played. The implementation of this approach follows:

    int waitingTime(int N, int songDuration, int delay) {
    for (int i = 0; ; i++) 
        if (i % delay == 0 && 
        (((i % (songDuration + 5)) >= songDuration || i / (songDuration + 5) >= N))) 
            return i;
    }

Value	500
Submission Rate	57 / 74 (77.03%)
Success Rate	50 / 57 (87.72%)
High Score	Loner for 462.72 points (8 mins 11 secs)
Average Score	337.12 (for 50 correct submissions)

Since each two floors are connected by only 1 stairs, there will be no need to ever go a floor down if the finish is higher than the starting point. Similarly, if the finish is lower than the starting point, you will never need to go a floor up. Also, at every intermediate floor, you will need to go in only one direction - either left or right - and never go both left and right at the same floor. Taking this into account, there will be exactly 1 path satisfying all these conditions. Lets now compute the time you will need to pass it.

The time you'll need to spend can be split in two parts. First, you'll need to pass a number of stairs. If the starting position is located at floor F_s, and the final position is located at floor F_f, the total time you'll need to spend on the stairs will be (F_s - F_f) if the starting floor is located higher than the final floor, and (F_f - F_s) * 3 otherwise. Here you must remember two things. First, the earlier elements of the input represent higher floors, and second, half of the elements of the input represent empty spaces between floors. Therefore, if 'S' is located in the i-th element of the input, and 'F' is located in the j-th element of the input, the time spent on stairs will be equal to:

int time = (i > j) ? ((i - j) * 3 / 2) : ((j - i) / 2);

Since you can calculate the time spent on stairs independently (see the previous paragraph), and because the path from the finish to the start is the same as from the start to the finish, you can assume the start floor to be lower than the final floor (if it isn't so, just swap the start and the finish). As the very last note, don't forget about the special case when start and finish positions are at the same floor:

public int wayTime(String[] s) {
        int rs = 0, cs = 0, rf = 0, cf = 0;
        for (int i = 0; i < s.length; i++) for (int j = 0; j < s[0].length(); j++) 
                if (s[i].charAt(j) == 'S') { rs = i; cs = j; }
        for (int i = 0; i < s.length; i++) for (int j = 0; j < s[0].length(); j++) 
                if (s[i].charAt(j) == 'F') { rf = i; cf = j; }
        if (rs == rf)
                return 2 * Math.abs(cs - cf);
// time spent on the stairs
        int ans = Math.abs(rf - rs) / 2; 
        if (rs > rf) {
                int q = rf; rf = rs; rs = q;
                q = cf; cf = cs; cs = q;
// climbing is 3 times slower than running down
                ans *= 3; 
        }
// time spent on the first floor
        ans += Math.abs(s[rs + 1].indexOf('|') - cs) * 2; 
// time spent on the last floor
        ans += Math.abs(s[rf - 1].indexOf('|') - cf) * 2; 
        for (int i = rs + 1; i < rf - 1; i += 2)
                ans += 2 * Math.abs(s[i].indexOf('|') - s[i + 2].indexOf('|'));
        return ans;
}

Value	1000
Submission Rate	36 / 74 (48.65%)
Success Rate	8 / 36 (22.22%)
High Score	Achtung-Achtung for 946.49 points (6 mins 49 secs)
Average Score	722.17 (for 8 correct submissions)

The first thing to note in this problem is that numDivisible(L, R, a) is equal to (numDivisible(1, R, a) - numDivisible(1, L - 1, a)). This approach -- counting specific numbers not greater than A, instead of counting specific numbers not greater than A and not smaller than B -- is a well-known trick and may help you in future challenges, so don't forget it after submitting this problem!

Now we need to find the number of positive integers not greater than A, which are divided by at least one element of a. Lets start solving this problem from much simpler cases, when the total number of elements in a is small. Let's go step by step:

• If a contains only 1 element, the answer to this problem is the total number of positive integers less than A, which are divided by a[0]. Obviously, this is equal to A/a[0], with the result is rounded down.
• If a contains exactly 2 elements, the answer can be A/a[0] + A/a[1] (total number of integers divided by a[0] plus total number of integers divided by a[1]), but usually it will be smaller. Why? Because the numbers which are divided by a[0] and a[1] will be counted twice. Therefore, the correct answer will be equal to (f(a[0]) + f(a[1]) - f(a[0], a[1])), where f(a, b, c, ...) notes the total number of positive integers not greater than A, which are divided by each of a, b, c... As you see, each of the integers which is divided by both elements of a, is added to the result twice (in f(a[0]) and f(a[1])), but also subtracted once in f(a[0], f(a[1])).
• We can apply similar idea to a, if it contains 3 elements: calculate the result as (f(a[0]) + f(a[1]) + f(a[2]) - f(a[0], a[1]) - f(a[0], a[2]) - f(a[1], a[2])), but this result will appear to be smaller than correct. Why? All integers which are divided by 1 or 2 elements of a will be counted correctly, but the numbers which are divided by all three elements of a will not be counted. Each of these numbers will be added to the result three times (in f(a[i]), 0 <= i <= 2) and subtracted from the result three times. Therefore, each of these numbers should be included into result, and the correct answer for this case will be:

f(a[0]) + f(a[1]) + f(a[2]) - f(a[0], a[1]) - f(a[0], a[2]) - f(a[1], a[2]) + f(a[0], a[1], a[2]).

• We can assume that in a more general case, when a contains K elements, the answer can be computed in the following way:
  Set the result to 0.
  Add f(a[i]) (for all 0 <= i <= K) to the result.
  Subtract f(a[i], a[j]) (for all 0 <= i < j <= K, ) from the result.
  Add f(a[i], a[j], a[k]) (for all 0 <= i < j < k <= K) to the result.
  ...
  In general, for any subset of m indices 0 <= i₀ < i₁ < ... < i_m-1 <= K, f(ai₀, ai₁, ..., ai_{m - 1}) should be added to the result if m is odd (1, 3, 5, ...) and subtracted from the result if m is even.
  ...
  This principle is known as Inclusion-Exclusion principle, and you can find the formal proof if you follow the link.

    public int numDivisible(int L, int R, int[] a) {
        return f(R, a) - f(L - 1, a);
    }
// computes the greatest common dividor for numbers n1 and n2
    long gcd(long n1, long n2) { 
        return n2 == 0 ? n1 : gcd(n2, n1 % n2);
    };
    int f(int A, int[] a) {
        int ans = 0;
        int N = a.length;
// if i has 1 at the j-th bit, this means a[j] is included into the i-th set
        for (int i = 1; i < (1 << N); i++) { 
            long lcm = 1;
            int ones = 0;
            for (int j = 0; j < N; j++) if ((i & (1 << j)) != 0) {
// one more number in the set
                ones++; 
                long r = gcd(lcm, a[j]);
                lcm /= r;
                lcm *= a[j];
// to avoid overflowing the value of lcm, we stop calculations as soon as 
                if (lcm > A) break; 
//the value of lcm is greater than A - the answer for A/lcm will be 0 anyway.
            }
            if (ones % 2 == 1)
                ans += (A / lcm);
            else
                ans -= (A / lcm);
        }
        return ans;
    }