Thursday, November 6, 2008 Match summaryThis TCHS match turned out to be quite easy  out of 87 participants, 42 solved the Hard and 31 solved all three problems. Within such conditions, coding speed was the deciding factor. Young 13year old tourist showed excellent performance and took the first place. For the second HS SRM in a row he makes the fastest submission times on *all* problems! anastasov.bg and UranusX were just a bit slower and took the second and third places, respectively. The ProblemsMagicSpellUsed as: Division One  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 One  Level Two:
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 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. ProgrammingRobotsUsed as: Division One  Level Three:
Let's consider a simplified version of the problem, where we can assign different programs to different robots. In this version, if two robots start in different connected components of the maze, we certainly can't bring them to the same cell. And for all robots starting in the same connected component, they can be moved into the same position. To do this, just choose an arbitrary cell from the component and assign a program to each robot that makes him move the path from his starting position to the chosen cell. So, in order to solve this version, we need to find connected components using BFS or DFS and to choose the component which contains the maximum amount of 'R' cells. This amount will be the answer. Now what changes when we return to the original problem? The answer may seem surprising at the first glance. Absolutely nothing changes. Still, robots from different components can't be brought into the same cell and all robots from the same component can be moved into the same position. The first fact is still obvious, but the second one is far from being obvious. Coders have two different ways of dealing with the second one. They can experiment with several examples and just trust that this is always true. Or they can come with a formal proof. Of course, the second way is safer, but at the same time it's harder and requires more thinking time. Let us give a simple and nice proof of this fact (the idea of the proof belongs to Gluk, the problem writer). Theorem. If two robots start from cells A and B and there's a path between these cells, then there's a program that moves both robots into the same cell. Proof. Let L be the length of the shortest path between A and B. It's enough for us to find a procedure that allows to shorten the length of the shortest path between the robots on at least one cell. Then we can just apply this procedure at most L times and the length of the shortest path between the robots will be 0, i.e. they will be in the same cell. The required procedure can work as follows. Let's make both robots move a shortest path from A to B. One of the robots (that starts at A) will certainly not encounter a wall during these moves. The other robot can encounter a wall, but as only his next move leads to a wall, the shortest distance between the robots becomes at least one cell smaller (the first robot comes a cell closer, while the second one stays in place), so we can stop the procedure immediately after this. If the other robot also never encounters a wall, it's possible that the length of the shortest path is still the same. If this is the case, let's make again both robots move a shortest path between them (note that this path is still the same as from A and B). Repeat moving the shortest path until the second robot encounters a wall. Note that this procedure can't last forever, because the maze is finite and each time we move robots along the shortest path between them, we shift both of them on the same vector A>B. End of proof. Java implementation that uses DFS is provided below. public class ProgrammingRobots { int N, M; int[] dx = new int[] {1,1,0,0}; int[] dy = new int[] {0,0,1,1}; boolean[][] used; int cnt = 0; void dfs(String[] maze, int i, int j) { used[i][j]=true; if (maze[i].charAt(j)=='R') cnt++; for (int t=0; t<4; t++) if (i+dx[t]>=0 && i+dx[t]<N && j+dy[t]>=0 && j+dy[t]<M && maze[i+dx[t]].charAt(j+dy[t]) != '#' && !used[i+dx[t]][j+dy[t]]) dfs(maze, i+dx[t], j+dy[t]); } public int numberOfRobots(String[] maze) { this.N=maze.length; this.M=maze[0].length(); used = new boolean[N][M]; int res = 0; for (int i=0; i<N; i++) for (int j=0; j<M; j++) if (maze[i].charAt(j) != '#' && !used[i][j]) { cnt = 0; dfs(maze, i, j); if (cnt>res) res=cnt; } return res; } } 
