|
Match Editorial |
Tuesday, October 9, 2007
Match summary
During SRM 370, division one coders were presented with a rather easy problem set, while division two, after fast submissions on easy and
medium couldn't get through the hard. The success rates for division one proved that the problems were well chosen, while 0% accuracy on
division two hard was a bit surprising, as the problem was rather standard. In both divisions, all top coders after coding phase were
pretty close to each other so the challenge phase was a great show. ACRush, who has
taken the lead of division one during the coding phase stayed on top thanks to 300 points gathered during the challenges.
gevak and Egor rounded up
the top three in the division one.
Division two was ruled out by armansuleimenov with other coders (including
vinodkumar and frisbeejoecrow
rounding up the top three) being very close to each other. That's probably due to the fact that the easy and medium were
relatively easy this time.
The Problems
Containers
Used as: Division Two - Level One:
Value 250 Submission Rate 613 / 645 (95.04%) Success Rate 508 / 613 (82.87%) High Score narri for 249.64 points (1 mins 5 secs) Average Score 205.85 (for 508 correct submissions)
Although the constraints for this problem are low enough to solve it by a simple simulation, we can do it even faster. The problem statement says that we can always put all the packages inside the containers using given procedure. So it is obvious that the answer will be the sum of capacities of all containers minus the sum of sizes of all packages.
DrawingMarbles
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 555 / 645 (86.05%) Success Rate 480 / 555 (86.49%) High Score domeng for 481.94 points (5 mins 32 secs) Average Score 369.02 (for 480 correct submissions)
Value 250 Submission Rate 558 / 563 (99.11%) Success Rate 516 / 558 (92.47%) High Score ainu7 for 248.64 points (2 mins 6 secs) Average Score 222.62 (for 516 correct submissions)
Let's try to find a probability that all n marbles drawn will be of color i. Let C(m, n) denote a binomial coefficient - number of ways to choose n differents element from the set of m elements. The probability we'll looking for is obviously C(color[i], n) / C(total, n), where total is the sum of all elements of color. Summing these possibilities for all colors will give us the answer. We can compute all binomial coefficients with the memoization using the following formula:
C(m, n) = C(m - 1, n - 1) + C(m - 1, n) .As these numbers can be really large, we should use doubles to compute the answer. Precision issues are not so important here, as for big n the answer is smaller than 1E-9. The problem can be also solved without using binomial coefficients. Note, that when we have drawn j marbles of color i, the probability that the next drawn marble will be of color i is equal to (color[i] - j) / (total - j). So the probability for a single color can be computed as:
p(i) = product for all j from 0 to n - 1 ( (color[i] - j) / (total - j) ) .Of course when color[i] is smaller than n, p(i) is equal to 0. JohnnysPhone
Used as: Division Two - Level Three:
Value 1000 Submission Rate 10 / 645 (1.55%) Success Rate 0 / 10 (0.00%) High Score null for null points (NONE) Average Score No correct submissions
The message is a list of words separated with spaces (not necessarily single). Thus, we can count spaces to know how many we will have to press "Space" button and then consider each word separately. So, we're given a word and a dictionary and we want to find the minimal number of button presses necessary to type such word. Of course the process of typing this word will looks as follows. At the beginning we have to type the digits corresponding to some prefix of a word and then possibly press "Next in dictionary" several times, until we'll see the exact prefix of our word. If we don't have the whole word written yet, we must press "New word" and type the digits corresponding to the prefix of the rest of the word and so on. Let's assume that we have function g(i, j) that returns the minimal number of button presses needed to type the subword starting at position i and ending at position j of the word we want to type if we typed it in the most obvious way (by just pressing digits corresponding to the following letters and then possibly pressing "Next in dictionary" several times) or infinity if it's not possible. Let f(i) denote the minimal number of button presses necessary to type the word assuming that we've typed i digits so far and we pressed "New word" already. Our last thoughts immediately lead to the following recurrence:
f(i) = minimum for all j from i to length - 1 ( g(i, j) + 1 + f(j + 1) ) ,where length is the length of our word and f(length) = -1. Why do we want it to be -1? Because we won't have to press "New word" when we finish our word (and we've already added 1 in the recurrence). How can we compute g? Of course it will be j - i + 1 + the number of necessary pushes of "Next in dictionary". How can we found the latter? We can iterate over the whole dictionary and check how many words have prefixes fitting to the digit pattern of our subword until we reach what we want (or if we never reach it we return infinity, as it's impossible to type the given subword). Sample Java solution with memoization follows:
public class JohnnysPhone {
String cur, dict;
int inf = 1000000000;
int[] tab = { 2, 2, 2,
3, 3, 3,
4, 4, 4,
5, 5, 5,
6, 6, 6,
7, 7, 7, 7,
8, 8, 8,
9, 9, 9, 9 };
int[] dp;
public int check (String word, String pattern) {
StringTokenizer st = new StringTokenizer(dict);
int res = 0;
while (st.hasMoreTokens()) {
String tmp = st.nextToken();
if (tmp.length() < word.length()) continue;
if (tmp.substring(0,word.length()).equals(word))
return res;
String pat = "";
for (int i = 0; i < word.length(); i++)
pat += tab[tmp.charAt(i) - 'a'];
if (pat.equals(pattern)) res++;
}
return inf;
}
public int recur (int i) {
if (i == cur.length()) return -1;
if (dp[i] == -1) {
dp[i] = inf;
String tmp = "", pat = "";
for (int j = i; j < cur.length(); j++) {
tmp += cur.charAt(j);
pat += tab[cur.charAt(j) - 'a'];
dp[i] = Math.min(dp[i], j - i + 1 +
check(tmp, pat) + 1 + recur(j + 1));
}
}
return dp[i];
}
public int minimizePushes(String[] dictionary, String message) {
dict = "";
for (int i = 0; i < dictionary.length; i++)
dict += dictionary[i];
StringTokenizer st = new StringTokenizer(message);
int res = 0;
for (int i = 0; i < message.length(); i++)
if (message.charAt(i) == ' ') res++;
while (st.hasMoreTokens()) {
cur = st.nextToken();
dp = new int[cur.length()];
for (int i = 0; i < cur.length(); i++) dp[i] = -1;
res += recur(0);
if (res >= inf) return -1;
}
return res;
}
}
ConnectTheCities
Used as: Division One - Level Two:
Value 500 Submission Rate 366 / 563 (65.01%) Success Rate 213 / 366 (58.20%) High Score ACRush for 485.63 points (4 mins 54 secs) Average Score 321.95 (for 213 correct submissions)
Imagine that we know how to compute the minimal cost of rearranging the transmitters so that there exists a connection between the cities, given a fixed transmission range. If we're able to do that we can do a search for the answer. We don't even need a binary search as the constraints are low enough for a linear one. But of course the function of cost with respect to the transmission range is non-increasing so binary is indeed correct. Ok, so let's assume that we have fixed transmission range and let it be r. How can we find the minimal cost of setting up a connection? If we look at the sequence of transmitters in the order of increasing distance from the city A, we will see that in the optimal solution we won't change this order itself. We're slowly approaching to a dynamic programming solution. Let A[i][j] be the minimal cost of rearranging the transmitters 0 through i in such way that there is a connection between the city A and the i-th transmitter and the i-th transmitters is exactly j units away from city A. How can we compute it? Simply:
A[i][j] = minimum for k from 0 to r ( A[i-1][j-k] + abs(j - position(i)) ) .Of course we should initialize A[0][j] for all j prior to the rest of the algorithm. The answer for the case will be the minimum over all A[n-1][j] for j from distance - r to distance (as we want the n-1-th transmitter to be able to be able to connect to city B. You can see the fastest ACRush's solution for reference.
Exercises:
- prove that there always exists an optimal solution with the transmitters being in integer coordinates even if we're not limited by the problem statement
- prove that the function of cost with respect to the transmission range is non-increasing
Used as: Division One - Level Three:
Value 950 Submission Rate 276 / 563 (49.02%) Success Rate 108 / 276 (39.13%) High Score Daumilas for 921.47 points (5 mins 1 secs) Average Score 597.73 (for 108 correct submissions)
Number of divisors of integer n = p0a0 * p1a1 * ... * pmam (where all pi are prime) is equal to (a0 + 1) * (a1 + 1) * ... * (am + 1). We want this number to be equal to k, so all (ai + 1) should be divisors of k. Also we want n to be as small as possible, so of course p0, p1, ..., pm should be the first primes. Now, let's imagine that we have all exponents at p0 throgh pi fixed already, (a0 + 1) * ... * (ai + 1) is equal to l, and we want to choose an exponent at pi + 1. We have to assign it in such way that (ai + 1 + 1) is a divisor of (k / l). Ok, so our state looks like a pair (i, l) where i denotes which prime we want to assign an exponent to and k / l is the number of divisors we need. Again, we can solve it with dynamic programming (but we have to be careful not to overflow types):
public class NumberOfDivisors {
boolean prime[] = new boolean[1005];
long A[][] = new long[101][50001];
int P[] = new int[100];
long lim = 1000000000000000000L;
public long pow (long a, int b) {
long res = 1;
while (b-- > 0) {
if (res > lim / a) return lim + 1;
res *= a;
}
return res;
}
public long recur (int id, int div) {
if (div == 1) return 1;
if (A[id][div] == -1) {
A[id][div] = pow(P[id], div - 1);
for (int i = 2; i * i <= div; i++) if ((div%i) == 0) {
long tmp = pow(P[id], i - 1);
if (tmp > lim / recur(id + 1, div / i))
tmp = lim + 1;
else
tmp *= recur(id + 1, div / i);
A[id][div] = Math.min(A[id][div], tmp);
tmp = pow(P[id], (div / i) - 1);
if (tmp > lim / recur(id + 1, i))
tmp = lim + 1;
else
tmp *= recur(id + 1, i);
A[id][div] = Math.min(A[id][div], tmp);
}
}
return A[id][div];
}
public long smallestNumber (int k) {
int upper = 1000;
for (int i = 2; i <= upper; i++) prime[i] = true;
for (int i = 2; i * i <= upper; i++) if (prime[i])
for (int j = 2*i; j <= upper; j += i) prime[j] = false;
int tmp = 0;
for (int i = 2; tmp < 100; i++) if (prime[i]) P[tmp++] = i;
for (int i = 0; i < 100; i++)
for (int j = 0; j <= 50000; j++)
A[i][j] = -1;
return recur(0,k) <= lim ? recur(0,k) : -1;
}
}
In the above approach we're trying every possible prime factorization of n, so it's trivially correct. Also, when we observe that
there will always be a0 >= a1 >= ... >= am, we can solve the task with a very simple backtracking
(that's why it was 950, not 1000).Exercises:
- if you're not sure about the given formula for the number of divisors, try to find it out yourself
- try to prove how many first prime numbers are needed given that k is not greater than 50000
