Monday, October 16, 2006 Match summaryAchtung-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 ProblemsMissedCallUsed as: Division One - Level One:
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:
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:
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:
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]).
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; } |
|