JOIN
 Match Editorials
TCHS SRM 16
Monday, October 16, 2006

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

MissedCall
Used as: Division One - Level One:
 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;
}
```

BrokenElevator
Used as: Division One - Level Two:
 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 Fs, and the final position is located at floor Ff, the total time you'll need to spend on the stairs will be (Fs - Ff) if the starting floor is located higher than the final floor, and (Ff - Fs) * 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);
```
Now you need to find the time you'll spend going left or right on different floors. There can be three different cases. If you are on the starting floor, you'll need from the position of 'S' character to the position of the necessary '|'. If you just entered the final floor, you need to pass the distance between your current position (the position of last stairs) and the 'F' position. If you are at an intermediate level, you need to go from the position of the previous stairs to the position of the next. In all three cases, the distance is twice bigger than the difference between positions of the corresponding characaters in the elements of the input.

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;
}
```

Divisibility
Used as: Division One - Level Three:
 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 <= i0 < i1 < ... < im-1 <= K, f(ai0, ai1, ..., aim - 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.
Since a can contain at most 18 elements, we can easily check all 218 subsets of indices and add or subtract the corresponding numbers to the result. The only tricky part left is to compute the value of f(ai0, ai1, ..., aim - 1). Naturally, this is equal to f(LCM(ai0, ai1, ..., aim - 1)), where LCM(ai0, ai1, ..., aim - 1) - the Least Common Multiple - the smallest possible positive integer which is divided by any of ai0, ai1, ..., aim - 1. The algorithm to compute the LCM of several numbers can be found at this web-page.

Java implementation of the algorithm described above follows:
```    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;
}
```

By Olexiy
TopCoder Member