Match Editorial

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 500-point 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 1000-point 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 Problems

Value	250
Submission Rate	373 / 499 (74.75%)
Success Rate	258 / 373 (69.17%)
High Score	filthy for 249.63 points (1 mins 6 secs)
Average Score	157.48 (for 258 correct submissions)

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.
First you parsed the input string into pieces of 3 characters each, and this pieces in the instruction character (the first one) and the number (the last two). Depending on the language, there are several forms to do that easily enough.
After that, all that was needed was a function or method that given the current state and the instruction to perform, gives you the next state. This could be done with a bunch of "if"s or cases or having a precomputed table.

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.
The faster and cleaner way to implement the changing state function is having a string with all the states in 'R' or 'L' order "-\\|/" for example, and remembering the position of the current state. Then, each instruction is moving a number of spaces in that string in circular fashion (ie. doing the operations modulo 4). See below for Java code with this idea.

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();

Value	500
Submission Rate	356 / 499 (71.34%)
Success Rate	296 / 356 (83.15%)
High Score	filthy for 499.73 points (0 mins 40 secs)
Average Score	378.60 (for 296 correct submissions)

Value	250
Submission Rate	364 / 365 (99.73%)
Success Rate	347 / 364 (95.33%)
High Score	ACRush for 248.17 points (2 mins 26 secs)
Average Score	223.27 (for 347 correct submissions)

This problem can sound math-oriented 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₄₀ 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₂ 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=b-a; // since b here equals oldB+oldA, a = b-a = oldB+oldA-oldA = oldB
 i++;
}
return ((double)i)+((double)(n-a))/((double)(b-a));

Value	1000
Submission Rate	16 / 499 (3.21%)
Success Rate	0 / 16 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

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.
The first thing to notice are the constraints. Since the input field can contain at most 3 * 4 = 12 characters, an exponential idea should come directly to your head.

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¹²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¹²)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 a-1;
       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<0||ns.x>2||ns.y<0||ns.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;
}

Value	500
Submission Rate	236 / 365 (64.66%)
Success Rate	72 / 236 (30.51%)
High Score	ACRush for 463.10 points (8 mins 8 secs)
Average Score	302.50 (for 72 correct submissions)

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 (in-degree) and the number of edges outgoing from the node (out-degree). 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.

Value	1000
Submission Rate	60 / 365 (16.44%)
Success Rate	50 / 60 (83.33%)
High Score	Crush for 933.33 points (7 mins 42 secs)
Average Score	634.45 (for 50 correct submissions)

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.
For arbitrary i,j and k, the subsequences counted in f(i,j,k) are either the empty sequence or starts with a lowercase letter, so we can sat that f(i,j,k) = 1 + g(i,j,k,'a') + g(i,j,k,'b') + ... + g(i,j,k,'z'), where g(i,j,k,l) is the function that counts the number of subsequences that start with the letter l and i, j and k represent the same as in f.
We can note then that g(i,j,k,l) = f(i',j',k') where i', j' and k' are the next occurence of the letter l after i, j and k respectively (we use that l and continue with following existent subsequences). If there isn't such i', j' or k', then clearly g(i,j,k,l) = 0.

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.
Actually the order of the number of operations gives 487500000 which is a little tight, but is acceptable as an upper bound taking into account that there are a lot of i',j',k' combinations that are never used (only 0,0,0 and the ones where i-1, j-1 and k-1 character is the same are actually visited) and that the actual search for a character in the string is not always 50.
Is possible to establish much more tight bounds to this problem with a more precise analysis on the frequency of each character in the input and the relationship between the length of the search part and the number of visited i',j',k' combinations, but with this we should convince ourselves that the idea works in time.
A short implementation of method f without the memo part follows:

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 ;
}