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. The ProblemsContainersUsed as: Division Two  Level One:
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. DrawingMarblesUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 1E9. 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:
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:
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 nonincreasing 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 ith transmitter and the ith 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[i1][jk] + 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[n1][j] for j from distance  r to distance (as we want the n1th transmitter to be able to be able to connect to city B. You can see the fastest ACRush's solution for reference. Exercises:
Used as: Division One  Level Three:
Number of divisors of integer n = p_{0}^{a0} * p_{1}^{a1} * ... * p_{m}^{am} (where all p_{i} are prime) is equal to (a_{0} + 1) * (a_{1} + 1) * ... * (a_{m} + 1). We want this number to be equal to k, so all (a_{i} + 1) should be divisors of k. Also we want n to be as small as possible, so of course p_{0}, p_{1}, ..., p_{m} should be the first primes. Now, let's imagine that we have all exponents at p_{0} throgh p_{i} fixed already, (a_{0} + 1) * ... * (a_{i} + 1) is equal to l, and we want to choose an exponent at p_{i + 1}. We have to assign it in such way that (a_{i + 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 a_{0} >= a_{1} >= ... >= a_{m}, we can solve the task with a very simple backtracking (that's why it was 950, not 1000). Exercises:

