Thursday, November 6, 2008 Match summaryThis match attracted 1301 participants  561 in Division I and 740 in Division II. Both divisions featured quite easy problemsets. The easy problem in DivI was quite straightforward, 600pointer required some insight to solve and 900pointer was an exercise on using binary indexed trees. Petr was pretty fast and gained his 48th match victory even after scoring 25 during the challenge phase. His concurrents were quite close behind  ahyangyi with the fastest 600pointer submission scored just 18.96 points less than Petr and took the second place. ACRush was the fastest on 900pointer, but he had to resubmit the 600pointer and lose many points because of this. With 125 points during the challenge phase he was able to claim the third position. The winning receipt in DivII was fast solving the Hard problem and having a couple of challenges. rudiso won the match exactly in this way. [G][U]nawan was the fastest on the Hard problem, but without any challenges it was only enough to claim the second spot. The third place was taken by lilu0355. The ProblemsMagicSpellUsed as: Division Two  Level One:
As it often happens with DivIIEasy problems, to solve this one you just need to implement everything from the statement properly. One of the ways to do it is as follows:
Java implementation of this approach can look as follows: public class MagicSpell { public String fixTheSpell(String spell) { // step 1 String az=""; for (int i=0; i<spell.length(); i++) if (spell.charAt(i)=='A'  spell.charAt(i)=='Z') az += spell.charAt(i); // step 2 String res=""; int pos = az.length()1; for (int i=0; i<spell.length(); i++) if (spell.charAt(i)=='A'  spell.charAt(i)=='Z') res += az.charAt(pos); else res += spell.charAt(i); return res; } }ProductOfDigits Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem allows for many different approaches. Let's present 3 of them. 1. Memoization. Let F(X) be the smallest number of digits required to obtain the product X. Obviously, we need to find F(N). There's a following simple reccurrence to calculate F(X). If X < 10, then F(X) = 1 (one digit is enough). Otherwise, iterate through all digits d from 2 to 9 (it never makes sense to use digit 1 because it doesn't change the product of digits), inclusive, such that X is divisible by d and try to use d as a first digit of our number. If d is a first digit, then the product of the rest must be X/d and it requires F(X/d) digits to fill the rest. Therefore, F(X) = min{F(X/d) + 1} by all d, 2 ≤ d ≤ 9, such that X is divisible by d. Having such a reccurrence, we have two ways to evaluate it. The first is to create a table F of size N and to calculate values F[1], F[2], ..., F[N], in order. Unfortunately, N can be as large as 10^9 what makes this approach impossible. The other approach is to use recursion with memoization. Let's estimate the number of states that will be visited if we calculate F(N) in such way. Note that digits from 2 to 9 have only primes 2, 3, 5 and 7 in their factorization. Therefore if N = 2^A * 3^B * 5^C * 7^D * n, each recursive call will be made for a number representable as 2^a * 3^b * 5^c * 7^d * n, where 0 ≤ a ≤ A, 0 ≤ b ≤ B, 0 ≤ c ≤ C, 0 ≤ d ≤ D. It means that the number of recursive calls is at most (A+1)*(B+1)*(C+1)*(D+1) ≤ (29+1)*(18+1)*(12+1)*(10+1) = 81,510. So the number of visited states is not very large and memoization approach will easily run in time. Java implementation of this approach follows. import java.util.*; public class ProductOfDigits { Map<Integer, Integer> memo = new HashMap<Integer, Integer>(); int solve(int N) { if (N<10) return 1; if (memo.containsKey(N)) return memo.get(N); int res = 1000; for (int i=2; i<=9; i++) if (N%i==0) res = Math.min(res, solve(N/i)+1); memo.put(N, res); return res; } public int smallestNumber(int N) { return solve(N) == 1000 ? 1 : solve(N); } } 2. Case analysis. This approach works in O(1), but is somewhat harder to come with. Let's represent N as 2^A * 3^B * 5^C * 7^D * n. If n > 1, then N is not representable as a product of digits (all digits have only primes 2, 3, 5, 7 in their factorization). Let's assume that n = 1. There's only one digit divisible by 7  it's 7 itself. Similarly, only 5 itself is divisible by 5. Therefore to obtain 5^C * 7^D we have only one choice  to include C 5s and D 7s into our number. Now let's find the best way to obtain 2^A * 3^B. Lemma. If B > 1, then there's an optimal solution that contains digit 9. Proof. Suppose there's no optimal solution that contains 9. Then we have at least one of the following possibilities.
End of proof. In a similar way we can prove that if A > 2, then there's an optimal solution that contains digit 8. Therefore we can safely include floor(A/3) 8s and floor(B/2) 9s in our solution and what's left is only to solve the case when A ≤ 2 and B ≤ 1. In this case there are only 6 possibilities: 1 requires 0 digits (having 1 means that we've already obtained the required product using 5s, 7s, 8s and 9s), 2, 3, 4 and 6 require 1 digit and 12 requires 2 digits. Here it's important to not forget about the following corner case: if N is initially 1, it requires 1 digit instead of 0. This solution can be implemented in Java in the following way. public class ProductOfDigits { public int smallestNumber(int n) { if (n==1) return 1; int res = 0; int n2 = 0; int n3 = 0; while (n%2==0) { n/=2; n2++; } while (n%3==0) { n/=3; n3++; } while (n%5==0) { n/=5; res++; } while (n%7==0) { n/=7; res++; } if (n>1) return 1; res+=n3/2; n3%=2; res+=n2/3; n2%=3; if (n3+n2==3) res+=2; else if (n3+n2>0) res++; return res; } } 3. Greedy. It appears that the following greedy algorithm works correctly. Iterate through digits 9 to 2, in decreasing order. For each digit, use it until N is divisable by it. The algorithm has very simple implementation and intuitively seems to be correct, however, as always with greedy algorithms, one needs to be very accurate and it's better to prove the correctness formally. public class ProductOfDigits { public int smallestNumber(int N) { if (N == 1) return 1; int p = 0; for (int i = 9; i >= 2; i) while (N % i == 0) { p++; N /= i; } return (N > 1) ? 1 : p; } } Excercises. 1. Suppose the problem would be stated not in decimal system, but in system with base B. That is, you need to find the smallest amount of numbers, each between 1 and B1, inclusive, such that their product is N. Will the same greedy algorithm as in approach 3 work correctly for every value of B? In case of negative answer, what is the smallest value of B for which it doesn't work correctly? 2. Solve the following generalized version of the problem: find the smallest integer X such that the product of its digits in decimal notation is exactly N. BestRoadsUsed as: Division Two  Level Three:
It's not hard to see that the required set doesn't exist in the following 2 cases:
If we don't have any of these 2 cases, a connected set of M roads can be constructed as follows. First find any spanning tree (it contains N1 roads) and then add any MN+1 free roads to this tree. However, there's one problem  we've constructed an arbitrary connected set of M roads, but in fact we need to construct such set with the highest priority. To find the set with the highest priority, let's make two fixes to the presented approach. First, find the spanning tree with the highest priority and then, add free roads with the highest priority. The second part (adding free roads) is trivial and to solve the first one it's convenient to use Kruskal's algorithm. That is, we assign each vertex into a separate component and check roads in the decreasing order of priority. If a road connects 2 cities from different components, we add it to the tree and merge these components together, otherwise we skip it. Java implementation of this approach follows. public class BestRoads { public int[] numberOfRoads(String[] roads, int M) { // initialization int N = roads.length; char[][] c = new char[N][N]; for (int i=0; i < N; i++) c[i] = roads[i].toCharArray(); // Kruskal's algorithm int[] id = new int[N]; for (int i=0; i < N; i++) id[i] = i; int compCnt = N; int[] deg = new int[N]; for (int i=0; i < N; i++) for (int j=i+1; j < N; j++) { if (c[i][j] == 'N'  id[i] == id[j]) continue; int idi = id[i], idj = id[j]; M; compCnt; c[i][j] = 'N'; c[j][i] = 'N'; deg[i]++; deg[j]++; for (int t=0; t < N; t++) if (id[t] == idi) id[t] = idj; } // the set of all roads is not connected if (compCnt > 1) return new int[] {}; // adding free roads for (int i=0; i < N; i++) for (int j=i+1; j < N; j++) if (c[i][j] == 'Y' && M > 0) { M; c[i][j] = 'N'; c[j][i] = 'N'; deg[i]++; deg[j]++; } // M is greater than the total number of roads if (M != 0) return new int[] {}; // return result return deg; } }StrengthOrIntellect Used as: Division One  Level Two:
Let's describe the state of our character by three parameters: (current strength, current intellect, current free points). Here free points are those points that the character obtained and not yet has distributed to his parameters. Initial state of the game is (1, 1, 0). The following two simple observations are crucial to solving the problem:
The second observation allows us to present the state as (current strength, current intellect). Now it's clear that the character's algorithm looks basically as follows: Set strength=1, intellect=1, free points=0; While True Complete all possible missions that are not completed yet If there is no free points, break Make a decision: increase strength or intellect by 1 End While Our goal is to make decisions in such way that allows to complete the maximum number of missions. Note that this number is also uniquely determined by our final strength and intellect, so in fact it's enough to find which pairs (strength, intellect) the character can achieve and which he can't. After this, we can just choose the pair (strength, intellect) which is possible to achieve and which allows to complete the maximum number of missions. Let can(S, I) be true, if it's possible to achieve strength S and intellect I. Let's also freePnt(S, I) be the number of free points the character has if he achieved strength S, intellect I and completed all possible missions. When discussing the second observation, we gave the way to calculate freePnt(S, I). To calculate can(S, I), we can use the following reccurrence: Can(1, 1) = true Can(S, I) = true, if: a) S > 1, freePnt(S1, I) > 0 and can(S1, I) or b) I > 1, freePnt(S, I1) > 0) and can(S, I1) The idea of this reccurrense is easy: to obtain strength S and intellect I, we must be able to either obtain strength S1 and intellect I and then increase strength by 1, or to obtain strength S and intellect I1 and then increase intellect by 1. Java implementation of this approach is presented below. public class StrengthOrIntellect { public int numberOfMissions(int[] strength, int[] intellect, int[] points) { boolean[][] can = new boolean[1001][1001]; int[][] freePnt = new int[1001][1001]; int res=0; for (int S=1; S<=1000; S++) for (int I=1; I<=1000; I++) { freePnt[S][I] = 2  S  I; int missionCnt = 0; for (int x=0; x < strength.length; x++) if (strength[x] <= S  intellect[x] <= I) { freePnt[S][I] += points[x]; missionCnt++; } can[S][I] = (S == 1 && I == 1  S > 1 && can[S1][I] && freePnt[S1][I]>0  I > 1 && can[S][I1] && freePnt[S][I1]>0); if (can[S][I]) res = Math.max(res, missionCnt); } return res; } }ProductOfPrices Used as: Division One  Level Three:
In order to solve this problem, we need a structure that stores the information about some array A[1..N] of integers, initially filled by zeros, and is able to perform two types of operations:
We need this structure to perform both operations in time O(log N). The way to achieve this is to use Binary Indexed Trees (BIT). For those not familiar with BITs, please look at the following tutorial. In our solution we will use two BITs indexed 1..L. The first one is called cnt and cnt[i] is the number of currently planted trees having a coordinate i (we increase all coordinates by 1 to fit them into interval [1..L]). The second tree is called dst and dst[i] = cnt[i] * i. In other words, dst[i] is the sum of coordinates of all trees planted at point i. Suppose we want to plant a tree at point x[i] and wish to calculate its price in a fast way. There are CL = sum(cnt, 1, x[i]1) trees located to the left of x[i]. Each of these tree with coordinate x_{0} is located on distance x[i]  x_{0} from our tree. So, the sum of all distances is CL * x[i]  sum(all x_{0}) = CL * x[i]  sum(dst, 1, x[i]1). Similarly, there are CR = sum(cnt, x[i]+1, L) trees located to the right of x[i] and the sum of distances for them is sum(dst, x[i]+1, L)  CR * x[i]. So the total price of the tree can be calculated as follows: price = x[i] * (sum(cnt, 1, x[i]1)  sum(cnt, x[i]+1, L)) + sum(dst, x[i]+1, L)  sum(dst, 1, x[i]1) After the price is calculated, we just need to update cnt and dst: cnt[x[i]] := cnt[x[i]] + 1, dst[x[i]] := dst[x[i]] + i. The overall complexity of this approach is O(N * logL), which is fine to fit within the time limit. public class ProductOfPrices { long[] sumDst = new long[200001]; long[] sumCnt = new long[200001]; // BIT operations implementation void add(long[] s, int pos, int value) { while (pos <= 200000) { s[pos] += value; pos = pos  1; pos++; } } long getSum(long[] s, int pos) { long res = 0; while (pos > 0) { res += s[pos]; pos &= pos  1; } return res; } long getSum(long[] s, int l, int r) { if (l > r) return 0; return getSum(s, r)  getSum(s, l  1); } public int product(int N, int L, int X0, int A, int B) { int[] x = new int[N]; x[0] = X0 % L; for (int i=1; i < N; i++) x[i] = (int)(((long)x[i1] * (long)A + (long)B) % L); long res = 1; add(sumDst, x[0] + 1, x[0] + 1); add(sumCnt, x[0] + 1, 1); for (int i=1; i < N; i++) { long price = (long)(x[i] + 1) * (getSum(sumCnt, 1, x[i])  getSum(sumCnt, x[i]+2, L))  getSum(sumDst, 1, x[i]) + getSum(sumDst, x[i]+2, L); price %= 1000000007; res = (res * price) % 1000000007; add(sumDst, x[i] + 1, x[i] + 1); add(sumCnt, x[i] + 1, 1); } return (int)res; } } 
