Wednesday, November 30, 2005 Match summarySRM 275 went off tonight without a hitch, and offered little in the way of surprises. tomek continued his quest to regain top position on the coder rankings list from Petr by easily winning Division 1 by almost 100 points. Rounding out the top 5 in Division 1 with very impressive performances themselves were marek.cygan, krijgertje (who continues his march toward becoming a target!), pparys and haha. Division 2 was dominated by a newcomer, stone, whose new rating was very close to landing a spot on the Impressive Debuts list. The next 4 finishers were dgott, cypressx, aussieviet and marcoloco. Only dgott narrowly missed advancing to Division 1, whereas the others will be moving up for the next SRM. The ProblemsHingedDoorUsed as: Division Two  Level One:
A simple simulation was all that was required to solve this problem. You could choose to run your simulation in two ways: one way was to keep multiplying the current angle by 1/reduction and count how many such multiplications it took for the angle to fall to 5 degrees or lower. Another way was to start with a current angle of 5 degrees exactly and keep multiplying by reduction until the angle increased to initialAngle or higher, counting the number of such multiplications, of course. The second way is better because you can use integer multiplication instead of imprecise double division. C++ code follows: int numSwings(int initialAngle, int reduction) { int angle = 5; while (initialAngle > angle) { angle *= reduction; ret++; } } Haar1D Used as: Division Two  Level Two:
This problem required coders to implement a simple 1dimensional Haar wavelet transform. There isn't too much to do here, just implement the algorithm as described in the problem statement. Clearly, the algorithm can be implemented just as easily iteratively or recursively. In highlevel pseudocode, a recursive solution can be represented as follows: transform(data, N, L) form N/2 pairs from data (note that N is not necessarily the same as data.length) for i:1 to # pairs p = pair i sums[i] = p.first + p.second diffs[i] = p.first  p.second assign the first N/2 elements of data = elements of sums assign the next N/2 elements of data = elements of diffs if L  1 > 0 transform(data, N/2, L  1) The Haar wavelet as described here is used in a number of image compression algorithms, in particular the SPIHT algorithm (actually, the wavelet is missing a normalization constant...) If you look at the output of the wavelet on constant data, say 32 100s, you will see that the output is 3200 followed by 31 0s. This is known as energy compaction. The wavelet transforms the data such that the energy of the input is concentrated into a few coefficients (which occur near the beginning) of the output. It should be easy to imagine why this wavelet is used in image compression. GreedyGovernment Used as: Division Two  Level Three:
First, it should be noted that the sectors and roads between sectors in this problem are a thinly veiled way of saying nodes and edges. With this in mind, it should be fairly obvious how to construct a graph from the input data. In fact, the input data directly defines the adjacency matrix for the graph. This task can then be divided into two subtasks. The first subtask is to count the number of distinct paths from sector 0 to sector N1, subject to the rules in the problem statement. The second subtask is to determine which road's toll should be increased by tollHike to obtain the maximum average cost. Given that the maximum number of sectors in our city was at most 10, the first subtask could be solved by doing a simple depthfirst search (DFS) to generate all the paths in the graph which start from node 0 and end at node N1. In pseudocode, the DFS can be structured as follows: N = # of nodes initialize seen[i] = false for all i // size = N DFS(currentNode) // currentNode is 0based if currentNode == N1 // found new path, add to list of paths return if seen[currentNode] == true return // no cycles seen[currentNode] = true for i:0 to N1 if !seen[i] && toll[currentNode][i] > 0 DFS(i) // backtrack seen[currentNode] = false To solve the second subtask, we can proceed in two ways. The bruteforce approach is to simply add tollHike to each of the roads (there can be at most 90 of them) and evaluate the cost along each of the paths that you discovered using DFS (Note that this implies that you have cached these paths. An alternative is to not cache the paths and rerun the DFS, calculating the cost along each path within your DFS routine. If you choose this alternative, timeout becomes a concern although it is still possible to write a solution that is fast enough). Then, the average cost is just the sum of the costs along all paths divided by the total number of paths from subtask 1. There is a nicer solution, though. Rather than checking each road, we observe that we can greedily add tollHike to the road that appears most often over all the paths from sector 0 to sector N1. This is guaranteed to produce the maximum average cost. Note that a road cannot appear in one path more than once, because this would violate the condition that there are no cycles in the path from sector 0 to N1. Thus, by choosing the road which appears most often over all paths, we have effectively added tollHike to the maximum number of paths that we can. Obviously, when we now divide by the total number of paths to get an average cost, this will be maximized, since we cannot increase the cost along any path any further. InverseHaar1D Used as: Division One  Level One:
This problem is obviously related to the Division 2 Medium. In fact, I used the output of the test data from that problem to generate the test data for this problem! Here, it is not a simple matter of implementing an algorithm that has already been given to you, since what is described in the problem statement is the forward transform, not the reverse. The first step, then, is to figure out how to reverse the transform. The algorithm is best explained by considering a simple case of a 2 element sequence (and obviously, a level1 transform). So, consider the transformed sequence {y_{1}, y_{2}}, obtained from the original sequence {x_{1}, x_{2}}. From the description of the algorithm, we know that the first half of the transformed sequence (i.e. y_{1}) is a result of the summing operation on the original sequence, and the second half of the sequence (i.e. y_{2}) is a result of the difference operation on the original sequence. In other words, y_{1} = x_{1} + x_{2} y_{2} = x_{1}  x_{2} Now, you can easily solve those 2 equations for the 2 unknowns to obtain the original sequence. In general, you want to be able to find 2 equations in 2 unknowns. This is always possible, because you can take the i'th sum and the i'th difference, which will both be formed from the same pair in the original sequence. So now, one begins with the section of the data obtained from the last level of the transform, and reverses that portion. Then, take twice the number of elements and consider this our new transformed sequence, and repeat. Pseudocode for a recrusive solution follows: transform2(data, N) for i:1 to N/2 // over all pairs ret[2*i] = (data[i] + data[i + N/2])/2 ret[2*i + 1] = (data[i]  data[i + N/2])/2 data = ret if 2*N ≤ data.length transform2(data, 2*N) transform(data, L) len = data.length for i:1 to L len/=2 // get the data from the LAST level transform2(data, len) // note we no longer need L! Horoscope Used as: Division One  Level Two:
Intuitively, it would seem that a greedy solution (i.e. always saying a 'G' prediction is Right (if you can) and a 'B' prediction is wrong (if you can)) would not solve this problem correctly. It turns out that intuition, at least in this case, is right. A simple example on which a greedy solution returns an incorrect answer is: {GGB}, with R=1 and W=1. Here, a greedy solution would start off by saying the first day was R, then it is forced to assign the remaining days as W and R. So, we are left with RWR, which gives us a total of 1 Good day (the first one). Clearly, we can do better if we assign the Rights and Wrongs as WRW. This assignment gives us a total of 2 Good days. This problem can be solved in a pretty straightforward manner using memoization. In fact, let's go straight to the pseudocode: R, W as defined in the problem statement p = concatentation of elements in predictions initialize cache[MAX_DAYS][MAX_R][MAX_W] = 1 solve(int curDay, int numRightLeft, int numWrongLeft) if (curDay ≥ total # of days) return 0; // curDay starts at 0 if cache[curDay][numRightLeft][numWrongLeft] > 1 return cached value // this results has already been computed int best = 1; if numRightLeft > 0 // We haven't assigned R Right days in a row // Assign the current day as being Right if p[curDay] == 'G' add = 1; else add = 0 best = MAX(best, add + solve(curDay + 1, numRightLeft  1, W) if numWrongLeft > 0 // We haven't assigned W Wrong days in a row // Assign the current day as being Wrong if p[curDay] == 'B' add = 1; else add = 0 best = MAX(best, add + solve(curDay + 1, R, numWrongLeft  1) cache[curDay][numRightLeft][numWrongLeft] = best the function is called initially as follows: solve(0, R, W) The above function basically tries all the ways of assigning Right and Wrong days for all days but uses caching of previously computed results to run in time. The terminating condition for the recursion is clear: when our current day is larger than the total number of days for which we have predictions, we know that we can have no Good days, so we return 0. Otherwise, as long as we can assign the current day as being Right, we try that possibility. Note that we add 1 to our expected number of Good days if we're assigning a day as being Right and it was predicted as 'G'. Similar logic is applied for assigning the current day as being Wrong. SantaClaus Used as: Division One  Level Three:
By: OlexiyO Now lets look closely how do we improve a group. We take present a_{0} and give it to person a_{1}, give present a_{1} to person a_{2}, ..., present a_{k  1} to person a_{k} and present a_{k} to person a_{0}, closing the cycle. We are interested in the smallest improvable group, so, if a group contains several such cycles, we can split it into several smaller groups. Therefore, having indeces a_{0}, a_{1}, ..., a_{k} chosen, we can construct a cycle in the graph we described above. Analogously, having a cycle in that graph, we can find a group corresponding to it. Adding the costs over all edges used in the cycle, we can check whether the total value in the group will increase after redistributing presents. What we need now is to find the shortest cycle of positive cost in a graph. This can be done by a modification of FloydWarshall's algorithm. We find paths with the highest total value for all pairs of nodes of length 2, 3, and so on. As soon as the path (cycle) from a_{i} to a_{i} has the total value greater than zero for one or more i, we calculate and return the maximal cost among these cycles. See tomek's solution for a short and clean implementation. 
