Thursday, April 14, 2005 Match summary This SRM's early time slot seemed to enhance coder performance. In Division 2, the medium was submitted by more than 80% of the coders, and most were correct. The Div 1 Hard was correctly solved by 18 competitors. Kalmakka, with an amazingly fast submission on the hard problem, lead the pack going into the challenge round. The system tests claimed numerous solutions, and left misof on top by nearly 200 points. petr, competing for the second time, finished in second. Bhageera and pradhan_ptr took first and second place in Division 2. The ProblemsArrayHashUsed as: Division Two  Level One:
To solve this problem, we iterate over the entire input and apply the given formula to each entry. An interesting feature of the formula, is that the position of each letter has no effect on the final return value. The important factors are the number of times each letter occurs, the number of elements in the input, and the number of characters in each element of the input. Java code follows : public int getHash(String[] input) { int ret = 0; for (int i = 0; i < input.length; i++) for (int j = 0; j < input[i].length(); j++) ret += input[i].charAt(j)  'A' + i + j; return ret; }PrintScheduler Used as: Division Two  Level Two: Used as: Division One  Level One:
In this problem we must write code that simulates a multithreaded system. Since we are explicitly given the time slices alocated to each thread, the solution amounts to simple iteration code. In a separate array, we maintain the position of each thread, so that subsequent executions begin properly. Java code follows: public String getOutput(String[] threads, String[] slices) { StringBuffer ret = new StringBuffer(); int[] pc = new int[threads.length]; for (int i = 0; i < slices.length; i++) { String[] toks = slices[i].split(" "); int threadNum = Integer.parseInt(toks[0]), time = Integer.parseInt(toks[1]); for (int j = 0; j < time; j++) { ret.append(threads[threadNum].charAt(pc[threadNum])); pc[threadNum] = (pc[threadNum] + 1) % threads[threadNum].length(); } } return ret+""; }RedundantStrings Used as: Division Two  Level Three:
The key to this problem is given in the statement. Every redundant string has a unique nonredundant root. To count the number of redundant strings of a given length, we only need to consider the possible roots. Based on a divisibility argument, the length of a root must divide the length of the string. Thus, to find all nonredundant roots, we iterate over all possible divisors. Java code follows: public int howMany(int length) { if (length == 1) return 0; int ret = 0; for (int sub = 1; sub < length; sub++) if (length % sub == 0) //# of NonRedundant = Total  Redundant ret += (1 << sub)  howMany(sub); return ret; }SequenceSync Used as: Division One  Level Two:
To solve this problem, we perform a breadth first search over all possible machine configurations.
Each configuration is a set containing the states that the machine could be in. Initially,
the machine could be in any state, so the set of all states is given a cost of 0. Considering all
possible input symbols, we can compute which sets are within 1 step of the initial set. This
process is continued until we find a set containing a single element. If no such singleton set is
reachable, our method returns 1. Used as: Division One  Level Three:
This is one of those problems that becomes extremely easy to code once you have the right idea. Each string in S^{2} will look as follows: # # # # # # # #         a b c d a b c dEach of the #s correspond to some quantity of the letter below it. If all of the lower bounds are positive, we can easily compute the solution by multiplying the number of possible values for each #. In fact, this condition can be weakened: if at least 2 of the lower bounds are positive, the solution can be computed via simple multiplication (why?). When this condition is not satisfied, the simple method may overcount certain strings. The case where fewer than 2 lower bounds are positive will be handled separately. Suppose, without loss of generality, the b's have a positive lower bound, but all other letters have 0 as a lower bound. The simple multiplication method will overcount the case where the c's, d's, and a's between the two groups of b's are all missing. For example, the case where the first group has 5 b's and the second group has 7 will be considered different from the case where the first group has 10 b's and the second group has 2. The following formula describes how far the simple method overcounts: (B  1)^{2}*A*C*DHere A, B, C, and D denote the number of possible values for a's, b's, c's and d's. For example, C = uc  lc + 1. Note that (B  1)^{2} = B^{2}  (2B  1)When the letters between the b's are missing, the simple method counts B*B*A*C*D strings, but in reality there are only (2B1)*A*C*D strings. When all 4 letters have lower bounds at 0, this formula must be subtracted 4 times, for each potential case of overcounting. Java code follows: public long howMany(int[] abounds, int[] bbounds, int[] cbounds, int[] dbounds) { int[][] arrs = {abounds,bbounds,cbounds,dbounds}; int cnts[] = new int[4], lowSum = 0; long ret = 1, simp = 0; for (int i = 0; i < cnts.length; i++) { simp = ret *= cnts[i] = arrs[i][1]  arrs[i][0] + 1; lowSum += arrs[i][0]; } ret *= ret; for (int i = 0; i < 4; i++) if (arrs[i][0] == lowSum) ret = simp*(cnts[i]  1)*(cnts[i]  1)/cnts[i]; return ret; } 
