Thursday, July 28, 2005 Match summary In Division 1, after some time spent working on the easy problem, most coders divided into two distinct groups. The first group opened the medium problem (600 points) next, while the second went for the hard (800 points). At first glance the second group seemed to have the better approach, but many of the hard problem solutions turned out to be wrong. bladerunner took the 1st place with the help of 7 successful challenges, lovro was 2nd and Savior finished in 3rd. sabbir_yousuf became yellow by taking the 4th place. Interestingly, dexter_bg gained 297 rating points without passing any problems. In Division 2, the top performer was Protean, followed by crem and xaep. More than 70 coders finished with all three problems correct. The ProblemsSequenceOfNumbersUsed as: Division Two  Level One:
We can convert all elements of the given string array to integers and put them into some numerical array. After that we can sort new numerical array in a usual way and convert its back to the string array. int[] tmp = new int[sequence.length]; for(int i = 0; i < sequence.length; i++) tmp[i] = Integer.parseInt(sequence[i]); Arrays.sort(ret); for(int i = 0; i < sequence.length; i++) sequence[i]=""+tmp[i]; Another way to solve this problem is to use a sort function which receives a comparing function (called 'comparator') as an argument. Arrays.sort(sequence, new Comparator<String>() { public int compare(String a, String b) { return new Integer(a).compareTo(new Integer(b)); } });WordCompositionGame Used as: Division Two  Level Two: Used as: Division One  Level One:
First, we can count how many times each word appears in the player lists. This information can be stored in associative array (like hash map). After that we can iterate over the words of each player and calculate his score. Here is antimatter C++ solution who have made this problem in 1.5 minutes. string score(vector <string> a, vector <string> b, vector <string> c) { map<string,int> C; for (int i = 0; i < a.si; i++) C[a[i]]++; for (int i = 0; i < b.si; i++) C[b[i]]++; for (int i = 0; i < c.si; i++) C[c[i]]++; int AA=0,BB=0,CC=0; for (int i = 0; i < a.si; i++) AA += 4C[a[i]]; for (int i = 0; i < b.si; i++) BB += 4C[b[i]]; for (int i = 0; i < c.si; i++) CC += 4C[c[i]]; char buf[100]; sprintf(buf, "%d/%d/%d", AA,BB,CC); return string(buf); }KthElement Used as: Division Two  Level Three:
The example 2 hints how to solve this problem. Function F(N) can take a very few values within the problem limitations. So the sequence X will be repeated in first 1025 elements and we can find its period. If we know that sequence X has a period of length L starting from the index i (i > K) the X_{K} will be the same as the element with the index (Ki) mod L + i. Here is a sample Java code. Map<Integer, Integer> seen = new HashMap(); List<Integer> sequence = new ArrayList<Integer>(); int X = 0; for (int i = 0;; i++) { if (seen.containsKey(X)) { if (i > K) return sequence.get(K); int L = i  seen.get(X); int ind = seen.get(X); return sequence.get(ind + (Kind) % L); } seen.put(X,i); sequence.add(X); X = A*F(X)+B; }PluCodeGenerator Used as: Division One  Level Two:
It is quite easy to write solution that iterates from 1 to N1 and checks each number if it is a valid PLU code. This solution works much slower than required 2 seconds, but it is acceptable to generate all answers and hardcode each 100000th answer into array inside a solution source. After that we can start counting invalid PLU codes not from 1 but form the index that closer to N. Another (more honest) way to solve this problem is a dynamic programming. Let function A[d1,d2,L,N] be a number of invalid PLU codes of length L that less or equal N. Moreover this function allows PLU code to start from the '0' digit and considers PLU codes started from d2 as invalid if d1=d2. Let n0 be a first digit of N and N1 be a number N without a first digit. Now A[d1,d2,L,N] can be calculated using following algorithm (pseudocode): A[d1,d2,L,N] = 0; for(char ch='0'; ch<n0; ch++) A[d1,d2,L,N] += (d1==d2 && d2==ch) ? 10^{L1} : A[d2,ch,L1,10^{L1}1]; A[d1,d2,L,N] += (d1==d2 && d2==n0) ? N1+1 : A[d2,n0,L1,N1]; Using this folmula it is clear how to solve the task. OddDigitableUsed as: Division One  Level Three:
How are the odddigitable numbers produced? There are five onedigit odddigitable numbers. To produce the odddigitable number of length L (L > 1) we should get the odddigitable number of length L1, multiply it by 10 and add one of the onedigit odddigitable numbers. Let put all onedigit odddigitable numbers into the queue, then put all odddigitable numbers produced from 1, all odddigitable numbers produced from 3 and so on. This way we'll get all odddigitable numbers in the increasing order. Finally, take all numbers in the queue modulo N. There are no sense to put duplicates into the queue because they will generate the same numbers, so we'll skip produced numbers which are already in the queue. Here is the sample Java code. List<Integer> al = new ArrayList(); List<String> as = new ArrayList(); boolean[] mark = new boolean[N]; al.add(0); as.add(""); for (int i = 0; i < al.size(); i++) { int c = al.get(i); if (c == M && i > 0) return as.get(i); for (int j = 1; j <= 9; j+=2) { int x = (c*10+j)%N; if (mark[x]) continue; mark[(c*10+j)%N] = true; al.add(x); as.add(as.get(i)+j); } } return "1"; 
