Tuesday, April 11, 2006 Match summary Since this Single Round Match took place during the ACM ICPC finals, it was surprising (and nice) to see such a big crowd attending, that almost reached a thousand participants. This was the first competition in which char type was used as input, so it was good to have so many testers. In division 1 the problem set seemed easy, with a great number of coders finishing all three problems with good times. Also with a good number of challenges, mostly because of a 500point problem with many things to consider, the top scorers finished with a lot more points than what's usual. ivan_metelsky took the first place thanks to good times in all problems and two succesfull challenges that gave him the extra points needed to reach the top. Behind him, Crush with an amazing performance on 1000point problem and also good times in the other two managed to get second position, less than 100 points ahead of ACRush, who had the best time in both 250 and 500. misof, gawry and Ying rounded up the top 6, within 100 points from the top 3. Division 2 was a whole different story, with no coder correctly finishing the hard problem, the match was decided with speed in the other two problems, but mostly with challenges. Specially in 250 problem, where many coders failed to correctly handling all the cases of the simulation and some having trouble using the '\' character in output, challenge points were there to take them, and crucial to the final score. nirmal_mehta took the first spot, thanks to a carefully but not too slow performance in the 250 problem, a really quick programming of the 500, but specially, to 6 succesfull challenges that made his only unsuccesfull one look like nothing. In second place by a difference of less than 100 points, came RakeshN, that have a similar performance on problems, but "just" 3 succesfull challenges. emka207 completed the top 3 with a really fast implementation in the 250, but a slower one in the 500, and also 3 correct challenges. The ProblemsIndicatorMotionUsed as: Division Two  Level One:
This problem was quite straightforward, but it needed to be programmed carefully because all the bar transformations could be confusing.
The idea was doing a simple simulation taking into account all that's said in the problem statement.
With this ready, initialize the return string with startState
and the actual state also, and the repeatedly apply the function for
each instruction the number of seconds given while appending the
resulting state to the result string. String sts="\\/"; //this is a good and fast to code way to map characters into consecutive integers String instrs="SRFL"; //S=move 0, R=move 1, F=move 2, L=move 1=move 3 int ist=sts.indexOf(startState); //index of current state StringBuffer r = new StringBuffer("" + startState); //result string for(int k=0;k<p.length()/3;k++) { //iterate instructions int v=Integer.parseInt(program.substring(3*k+1,3*k+3)); //times to repeat instruction int o=instrs.indexOf(program.charAt(3*k)); //it says how much to move in sts for(int j=0;j<v;j++) { ist=(ist+o)%4; //execute instruction r.append(sts.charAt(ist)); //append result } } return r.toString();FibonacciPositioning Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem can sound mathoriented and maybe difficult at first, but is truly a quite simple simulation, so a bunch of coders of both divisions managed to solve it really quickly. Since fibonacci sequence has an exponencial explosion (this you could know ahead or maybe have figured out trying a few values), it is the fact that the maximum fibonacci number that is important here has low index. More specifically, F_{40} is greater than the 10000000 upper bound for the input n. Also, if looked carefully, the formula for the third case (when the number was in the middle of two consecutive fibonacci's) also works for the case that the number is an exact fibonacci number, because the second part of the formula is either 0 if n is the lower bound used (F_{i}) or 1 if it is the upper bound (F_{i+1}), so you can use that formula for all the cases (if you start from F_{2} to avoid 1 to be given position 1). So, the solution to this problem is finding two consecutive fibonacci numbers that have n between them and make the calculation as it was presented in the problem statement. Start with 1 and 2 and iterate over each subsequent pair of fibonacci numbers to find the interval, and then let your language do the math. Java/C++ code follows: int a=1,b=2,i=2; //a and b are cosecutive fibonacci numbers, i is the index of a while(n>b) { //n is outside [a,b] interval b=b+a; // a little trick to get next pair of fibonacci's without aux variable a=ba; // since b here equals oldB+oldA, a = ba = oldB+oldAoldA = oldB i++; } return ((double)i)+((double)(na))/((double)(ba));IndicatorMotionDrawing Used as: Division Two  Level Three:
This problem was really difficult for division 2, and that was reflected in the fact that no coder was able to solve it properly (only one submission made it through challenge phase, but failed to pass the system tests).
When seeing that you have to move around the screen, you can
immediatly think that this is a labyrinth problem, but if you look
carefully at example 2, you see that you may need to go back, so it's
not a standard labyrinth problem anyhow. We can say that the entire state of the screen can be represented with 12 state variables of 5 values each (space and the four bar states) and 2 variables r and c with 3 and 4 possible values, respectively, for the current position of the bar. This gives a total of 5^{12}x3x4 = 2929687500 which seems a little too much, but it didn't stopped a couple of coders from trying this approach. But thinking a little more you could realize that, with exception of the actual position, you don't care about the other places state. If it is not in it's correct state (ie. the one in desiredScreen), we must pass through it again, so the current state of the cell does not really matter. So what we should keep in each state is whether each square is in the desired state already, the current state of the bar and its position (row and column). This gives us a total of (2^{12})x4x3x4 = 196608 states. This is much smaller than the previous estimation and can be processed. Then we have to connect each state with the ones we can arrive from it in one instruction, to get a graph in which we can simply run a BFS. This can be done by carefully simulating each one of the 7 instructions and setting the state of the current position to 0 or 1 depending on whether we got it to the desired state or not. The initiating state will have 1 in the positions where there are spaces in desiredStates and 0 in the rest, with the exception of (0,0) that will have 0 or 1 depending on whether startState and the first character in the first element of desiredScreen are equal or not. To make the implementation easier we can complete smaller screens with spaces and work always with a 3 by 4 screen. Also, you can notice that any bar state can be reached from any other bar state sing only one of the instructions. Therefore, you don't need to care about exact instructions, and can either just change your bar to whatever you want or move it in any direction. Java implementation follows: private int setBit(int n, int p, int v) { return (n & ~(1<<p))  (v<<p); } private class state { public int x,y,p,s; } private static int all = (1<<12)1; private int memo [][][][]; private boolean isFinal(state s) { return s.p==all; } //first 4 are movements, the other 4 are the changing state //we are adding the possibility of changing to the actual state, but //this doesn't change because it is //never usefull to do it private static int dx[]={0,0,1,1,0,0,0,0}; private static int dy[]={1,1,0,0,0,0,0,0}; private static int fs[]={0,0,0,0,1,2,3,4}; //0 means remain in current state (when moving), the other are the next states public int getMinSteps(String[] dS, char startState) { Queue<state> q = new LinkedList<state>(); String barStates=" /\\"; state start=new state(); start.x=start.y=start.p=0; start.s=barStates.indexOf(startState); int [][] ds=new int[3][4]; for(int i=0;i<dS.length;i++)for(int j=0;j<dS[i].length();j++) ds[i][j]=barStates.indexOf(dS[i].charAt(j)); for(int i=0;i<3;i++)for(int j=0;j<4;j++) if (ds[i][j]==0) start.p=setBit(start.p,i*4+j,1); start.p=setBit(start.p, start.x*4+start.y, (ds[start.x][start.y]==start.s)?1:0); memo = new int[3][4][all+1][5]; memo[start.x][start.y][start.p][start.s]=1; q.offer(start); while(!q.isEmpty()) { state s=q.poll(); int a=memo[s.x][s.y][s.p][s.s]; if (isFinal(s)) return a1; for(int d=0;d<dx.length;d++) { state ns=new state(); ns.x=s.x+dx[d]; ns.y=s.y+dy[d]; ns.s=fs[d]; if (ns.s==0) ns.s=s.s; if (ns.x<0ns.x>2ns.y<0ns.y>3) continue; ns.p=setBit(s.p, ns.x*4+ns.y, (ds[ns.x][ns.y]==ns.s)?1:0); if (memo[ns.x][ns.y][ns.p][ns.s]==0) { memo[ns.x][ns.y][ns.p][ns.s]=a+1; q.offer(ns); } } } return 1; }OrderDoesMatter Used as: Division One  Level Two:
Even though there can be at most 50 matrices, it is clear that trying all the possible orderings it's not the way to go, even if you try to use backtracking to cut some parts. The best way to think about the problem is to start from the end of the problem statement: when is it even possible to achieve such an ordering? If we try to construct the sequence by appending a suitable matrix to the right side of the current order, each appending operation only changes the number of columns of the result of the constructed prefix from one number (that have to be the number of rows of the appended matrix) to another (the number of columns of the new matrix). The number of rows will never change and is equal to the number of rows of the very first matrix used. Thus we can reword the problem in terms of graph theory. Think of a graph with nodes representing integers between 1 and 1000, and with directed edges representing the matrices from the input (an AxB matrix maps to an edge from A to B). This graph can contain loops (edges from one node to itself, representing square matrices) and multiple edges between the same pair of nodes (several equal size matrices). The problem asks us to find a path which goes through each edge (i.e., uses each matrix) exactly once. The resulting matrix's size can be computed multiplicating the values of the starting and ending nodes of the path. The path we described above is known as Eulerian path in a graph. Graphs which allow the construction of Eulerian cycles are called Eulerian graphs. Euler observed that a necessary condition for the existence of an Eulerian path is that all but two vertices in the graph have a degree of 0. The two other nodes must either have degrees of 1 and 1, or both of 0. A degree of a node can be computed as the difference between the number of edges coming to this node (indegree) and the number of edges outgoing from the node (outdegree). This is because all but the starting and ending nodes of the path will be entered and left the same number of times, the starting node will be left once more than it is entered (vice versa for then ending node). If all nodes have degree of 0, we can go through each edge exactly once starting and ending at the same node. Also, we need the underlying undirected graph to be connected (to be able to reach every node in the same path). The Euler theorem states that these two conditions are enough for the path to exist (read more about Eulerian paths and cycles here). Since we already can determine the cases where no Eulerian path exists, lets look at the second part of the problem. We need to find the maximal number of elements the resulting matrix can contain. If there are nodes A and B which degrees are 1 and 1, these two must be the start and the end of the path. In this case the resulting matrix will contain A * B elements. Otherwise, if every node has a degree of 0, this an Eulerian cycle exists. In other words, the path will start and end at the same node, and any node from the cycle can be chosen as the start. Therefore, we find the maximal node A in the cycle, and the largest resulting matrix will contain A * A elements. (because the result will be an AxA matrix). For a clean implementation see misof's solution. CountingCommonSubsequencesUsed as: Division One  Level Three:
As many counting problems, this one cries to be solved with dynamic programming. In this case, things become easier if we find a recursive function and then memorize the results instead of thinking directly in traditional DP iterative implementation. First, lets define the function f(i,j,k) as the number of common subsequences (including the empty one) that the strings s, t and u have, where s is a but starting from the character i, and similarly with t, j and b, and u, k and c.
It's clear now that f(0,0,0)1 is the answer for the problem, because
it's the same number minus one for the empty sequence. Since g can be "built in" f with a simple for to iterate over all possible l's, in f there is a perfectly recursive especification of the problem.
Also, we can remember the results for f in a 50x50x50 matrix (the possible values for i', j' and k'),
and the number of operations is in the order of 50x50x50x26x150 (in
each position we do a 26 loops, once for each character and 3 searches
for the character in each of the strings, with each search bounded with 50
character comparissons), this should work fine. String a,b,c; //the input strings long f(int i, int j, int k) { long r = 1; for (char l='a'; l<='z'; l++) { int npa = a.indexOf(l, i), npb = b.indexOf(l, j), npc = c.indexOf(l, k); if (npa >= 0 && npb >= 0 && npc >= 0) //they all exist r += ccs(npa+1, npb+1, npc+1) ; } return r ; }For an iterative, fastly coded implementation, see gawry's code. 
