Tuesday, November 27, 2008 Match summaryThis SRM featured sets of an average difficulty in both divisions. In DivI, the battle for the first place arose between Psyho, author of the fastest 900pointer, and Petr, author of the fastest 600pointer. Psyho was the first after the coding phase and strengthened his lead on the very beginning of the challenge phase by making +50. However, than Petr retook the lead by making two successfull challenges. Psyho didn't give up and, 4 (!!) seconds before the end of the challenge phase, he reclaimed his lead by making another successfull challenge and leaving Petr on the second place. The excellent performance allowed Psyho to get 126 rating points and become a target. Congratulations to Psyho with very nice match, his first SRM victory and becoming a target! Third place went to Petr who was behind Petr on slightly more than 200 points. In DivII, the first three places were taken by AlexandeR, Tomik and happywy. All of them solved all three problems. Newcomer DanilaVas9ev made the fastest submission on 1000pointer, but took just 7th place because his submission on 500pointer failed systests. The ProblemsLoveCalculatorUsed as: Division Two  Level One:
The solution for this problem can be broken in two parts. First, let's implement the method which takes two names and calculates the probability of love between them. The implementation directly follows the problem statement: int loveProb(String a, String b) { String s=a+b; int L=0, O=0, V=0, E=0; for (int i=0; i<s.length(); i++) { if (s.charAt(i)=='L') L++; if (s.charAt(i)=='O') O++; if (s.charAt(i)=='V') V++; if (s.charAt(i)=='E') E++; } return ((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E)) % 100; } Now, having such method implemented, we can easily complete the rest of the solution: public String findBoy(String girl, String[] boys) { int bestProb = 1; String best = ""; for (int i=0; i < boys.length; i++) { int cur = loveProb(girl, boys[i]); if (cur > bestProb  cur == bestProb && boys[i].compareTo(best) < 0) { bestProb = cur; best = boys[i]; } } return best; } Exercise. It may seem that (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) doesn't always fit within 32bit signed integer value (each multiplier can be up to 40, so the upper bound for the whole expression is 40^6 = 4,096,000,000). If it's really true, then there can occur an overflow in loveProb method implementation provided above. Construct an example, that makes (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) overflow 32bit signed integer value, or prove that such example doesn't exist. DesignCalendarUsed as: Division Two  Level Two: Used as: Division One  Level One:
In order to solve this problem, let's do some simple math. First, we need to introduce several variables:
The statement asks us to choose P, N and L in such way that each P calendar years sum to the same amount of days as P real years. It means that the average year length (in days) according to our calendar is the same as the number of days in a real year. The number of days in a real year is yearLength/dayLength. The total number of days in P calendar years is (P  L) * N + L * (N + 1) (L leap years have N + 1 days and the other years have N days). Therefore, the average year length according to the calendar is ((P  L) * N + L * (N + 1)) / P = (P*N  L*N + L*N + L) / P = (P*N + L) / P = N + L/P. So we have an equation to solve: N + L/P = yearLength/dayLength. Let's reduce the fraction yearLength/dayLength. Set yearLength' = yearLength/d, dayLength' = dayLength/d, where d is the greatest common divisor of yearLength and dayLength. Then the equation from the previous paragraph can be written as (N*P + L) / P = yearLength' / dayLength'. Now, since the fraction in the right part is irreducible, it becomes clear that the minimum possible value of P is dayLength'. It's left to show that this value for P is feasible, i.e. to provide the correct values for N and L, but it's easy to do: N = yearLength' DIV dayLength' and L = yearLength' MOD dayLength'. These values will work because (N*P + L) / P = ((yearLength' DIV dayLength')*dayLength' + yearLength' MOD dayLength') / dayLength' = yearLength' / dayLength'. The implementation is really easy and straightforward. We just need to calculate dayLength / gcd(dayLength, yearLength): public class DesignCalendar { int gcd(int a, int b) { while (a>0 && b>0) if (a>b) a%=b; else b%=a; return a+b; } public int shortestPeriod(int dayLength, int yearLength) { return dayLength / gcd(dayLength, yearLength); } }Teaching Used as: Division Two  Level Three:
This problem is solved using brute force, i.e. by checking all possibilities. The basic idea is simple: we need to iterate through all subset of K letters, check for each of them how many words it allows to read and return the maximum. However, inefficient implementation of this approach will lead to time out. There can be up to C(26, 13) = 26! / (13! * 13!) = 10,400,600 possible subsets and checking each of them requires iterating through each letter of each word (at most 50*15 = 750 operations). Overall, it gives 10,400,600 * 750 = 7,800,450,000 operations, what is obviously way too much. To obtain working solution, let's apply two optimizations:
With these 2 optimization, in the worst case our solution will require 352,716 * 50 = 17,635,800 checks, what is still pretty much, but enough to fit within 2 seconds time limit. Java implementation of this approach follows: public class Teaching { int K; int[] wordMask; int res = 0; // recursive method for checking subsets // pos is the index of letter we are currently at // have is the number of taken letters // mask is the mask of taken letters void go(int pos, int have, int mask) { // if the subset is completely formed if (pos == 26) { // if the number of taken letters is not K, skip the subset if (have != K) return; // calculate how many words we can read int cnt = 0; for (int i=0; i < wordMask.length; i++) if ((wordMask[i] & ((1<<26)mask1)) == 0) cnt++; // update maximum if needed if (cnt > res) res = cnt; return; } // if the letter is none of 'a', 'n', 't', 'i', 'c', try skipping it if ("antatica".indexOf((char)((int)'a'+pos)) == 1) go(pos+1, have, mask); // try learning the letter go(pos+1, have+1, mask + (1<<pos)); } public int count(String[] words, int K) { // precalculate the masks for all words wordMask = new int[words.length]; for (int i=0; i<words.length; i++) for (int j=0; j<words[i].length(); j++) wordMask[i] = (1 << (words[i].charAt(j)  'a')); this.K = K; // start recursive checking of all subsets go(0, 0, 0); return res; } }LocateTreasure Used as: Division One  Level Two:
The key idea for solving this problem is the following lemma which provides a very simple way to calculate d(x). Lemma. If x>0, then d(x) = (x%9 == 0 ? 9 : x%9). Proof. First, note that 10^n % 9 = (10 % 9)^n % 9 = 1^n % 9 = 1. Now let n = (a_k a_{k1} ... a_1 a_0)_{10}. Then n % 9 = (a_k * 10^k + a_{k1} * 10^{k1} + ... + a_1 * 10 + a_0) % 9 = (a_k * (10^k % 9) + a_{k1} * (10^{k1} % 9) + ... + a_1 * (10 % 9) + a_0 * (1 % 9)) % 9 = (a_k + a_{k1} + ... + a_1 + a_0) % 9. So each number has the same remainder modulo 9 as the sum of its digits. When calculating d(x), we repeatedly change number by sum of its digits until it becomes less than 10. As number modulo 9 always remains the same during the process, the result is x%9 if x is not divisible by 9. If x is divisible by 9, we have two potential choices  0 and 9. But it's easy to see that sum of digits of positive number is always a positive number, so the right choice is 9. Corollary. d(mul*x) = d(d(mul) * d(x)). It follows from the corollary, that without loss of generality, we can assume that 1 ≤ mul ≤ 9 (otherwise just replace mul by d(mul)). Consider the sequence d(1), d(mul), d(mul^2), ..., used in the algorithm we need to implement. As each next element depends only on previous one, very soon this sequence becomes periodical with very small period:
mul = 1: [1]; Quite surprising, but the sequence of coordinates, produced for a fixed mul and K=1,2,3,..., is also periodical:
mul = 1: [(0, 0), (0, 1), (1, 1), (1, 0)]; To obtain this data, you can write an easy program that prints first 100 members of each sequence and manually check for repeats within the printed coordinates. We see that period length is either 4 or 12, and preperiodic part can contain 0, 1 or 2 elements. Based on this knowledge, it's easy to write a program to solve the problem: public class LocateTreasure { public String location(int K, int multi) { // if K is large, then make it smaller if (K >= 12) { // K can be taken modulo 12, because the period length is // 12 or 4 (a divisor of 12) K %= 12; // K can fall within preperiodic part after taking // modulo 12, so add 12 for safety if (K <= 2) K += 12; } // calculate Kth member of the sequence // K can be at most 14 here int x = 0, y = 0; int[] dx = new int[] {0, 1, 0, 1}; int[] dy = new int[] {1, 0, 1, 0}; int d = 1; for (int step=0; step<K; step++) { x += dx[step%4] * d; y += dy[step%4] * d; d *= multi; while (d>9) d=9; } // return the result return x+" "+y; } }PSequence Used as: Division One  Level Three:
Let's first describe how to solve the problem using brute force. Let's build all possible psequences recursively. Our method count will take two parameters  an integer prev, describing the number we've put onto the previous position in the builded sequence (we can use some special value BEG to indicate the first position of the sequence when there's no previous position), and an array of integers left, describing all the integers that haven't been put yet into the sequence. The method count will return the number of ways to complete the sequence by all numbers from left to obtain psequence. The algorithm is simple: we iterate through all numbers X from left such that X  prev is not divisible by p (in case left = BEG we just iterate through all numbers from left) and sum the results of calls to count(X, left/X), where left/X is an array left with element X being removed. Each such call corresponds to extension of the builded sequence by number X and condition (X  pref) % p != 0 ensures that we check only psequences. In case when left is empty, there's exactly one way to obtain psequence – do nothing, so we return 1. The answer for the whole problem is count(BEG, S). The described method count works nicely, but it's awfully slow. One useful method that allows to speed up recursion is memoization, i.e. ensuring that method is called exactly once for every combination of its input parameters by saving the results of all calculations in some data structure. However, with the approach we've just described, values of the input parameters don't tend to repeat often, so it doesn't directly help here. So our goal is to modify input parameters in such way that memoization can be used. Let's make several observations:
After we apply these 3 observations, left will always contain a partition of some number less than or equal to N = length of S. There are at most 28,628 partitions of numbers ≤ 30, and there are at most 31 possible values for parameter prev (at most 30 positions in left and one special value for BEG). Overall, there are at most 28,628 * 31 = 887,468 combinations of input parameters' values for method count. Note that this bound is not strict, and in actual cases the number of appeared combinations is much less – 10,275 in the worst possible case. So now we can successfully apply memoization to method count to obtain working solution. For an example implementation of this approach, you can check Petr's submission. Note that in his code parameter prev (it's called numForbidden) there) has a bit different meaning – instead of the index of the group from which the previous element was taken, it gives the current number of elements in this group. Exercise. The described algorithm is exponential, because the number of partitions of number N is not bounded by any polynomial on N. Find a polynomial algorithm for solving this problem or prove that it doesn't exist unless P = NP. 
