Monday, October 9, 2006 Match summary
Single Round Match 322 had a fairly high number of registrants (985) and a very dynamic
start, with several coders of both divisions getting the easy problem in much less than five
minutes.
The ProblemsDerivativeSequenceUsed as: Division Two  Level One: This problem simply asked to simulate the given process. The easiest way was to carefully translate the rules of the difference sequence into your language like this: int[] difSeq(int[] a) { int[] b=new int[a.length1]; for(int i=0;i<b.length;i++) b[i]=a[i+1]a[i]; return b; }And implement the order iteration recursively like this: int[] derSeq(int[] a, int n) { if (n==0) return a; return (difSeq(a), n1); }It was also possible to do a fully iterative approach. To see that approach, check out elmariachi1414's code. GroupWork Used as: Division Two  Level Two: Used as: Division One  Level One: In this problem you can start by looking at the constraints. Seeing that the number of total people is inaccesible for an iteration, it immediately follows that it is necessary to simplify the problem. Since we need to maximize K*X, and iterating among all possible K is not feasible, we can try iterating every possible X. There are at most 50, because X is the skill level of some workers in the group, and there is at most one different skill level per element in the input arrays. Now, with X fixed, we would like to get K as big as possible. You can see that all workers with skill level less than X cannot be a part of the group, but all others can, so we recruit them. This leads to a O(n^{2}) implementation that is good enough to solve the problem. Check out gawry's code for a readable implementation. It was also possible to sort the pairs by skill level  with this approach, you don't need the inner iteration to count the number of workers with skill level greater than or equal to X, leading to an overall O(n log n). For code with this idea, see Zuza's solution. BattleshipChecker Used as: Division Two  Level Three: This problem only needed a careful implementation, so many coders were able to get it right. The large amount of examples also prevented many failures leading to a big success rate for a hard problem. Not all correct answers were equal, however  some clever implementations were much faster to code and get bug free. The best way to check if the board was correct (the hardest part of the problem) was to first look for diagonal touching. Any two cells that were both diagonally connected and occupied indicate that the board is wrong, so we returned "REJECTED." This can be done easily with a single iteration over each possible twobytwo square on the board. for(int i=0;i<9;i++)for(int j=0;j<9;j++) if ((board[i][j]=='X' && board[i+1][j+1]=='X')  (board[i+1][j]=='X' && board[i][j+1]=='X')) return "REJECTED";Knowing that there is no diagonal touching, it's easy to see that every connected component has to be a straight line, so we get the connected components (with a flood, DFS or BFS) sizes collection (sizes can be from 1 to 10) and check that there are exactly 4 of size 1, 3 of size 2, 2 of size 3, 1 of size 4 and zero of sizes greater than 4. //example with a flood or DFS int size(int i, int j, char[][] board, boolean[][] mark) { if (i<0j<0i>9j>9mark[i][j]board[i][j]!='X') return 0; mark[i][j]=1; return 1+size(i+1,j,board,mark)+size(i1,j,board,mark)+ size(i,j+1,board,mark)+size(i,j1,board,mark); }Having checked if the board is correct, all that's left is to iterate the rows and columns with a simple simulation to count the points  and that's it. int[] rowNP=new int[10],colNP=new int[10]; for(int i=0;i<10;i++)for(int j=0;j<10;j++) if (board[i][j]=='X') rowNP[i]=colNP[j]=1; int pts=20; for(int i=0;i<10;i++) pts=rowNP[i]+colNP[i]; return "ACCEPTED, " + pts + " POINTS"; ExtendedDominoes Used as: Division One  Level Two: This does not seem like a graph problem at first. The fact that the input is limited to 10 different numbers can be misleading  and could make you think that the solution is somehow exponential  but there is a quite simple an efficient idea using graphs. If fact, this is yet another eulerian graphs problem. First, let's translate the input into a graph that has digits from '0' to '9' as nodes and one edge connecting the 2 numbers of each piece (of course, these edges are bidirectional, as are the pieces). Now, the problem is to divide the set of edges into cycle collections. Based on the mentioned eulerian graphs property, we can see that this can only be done if the degree of each node is even. Of course, we do not only want to know whether this is possible or not, since this just distinguishes between zero and nonzero cases, but we also want the exact number. Let's look at each node separately. A single node has some number of edges d that have it as an endpoint. Each time we enter the node in a cycle, we must also leave, so we have to put the d edges in d/2 pairs  meaning that if we enter the node using one edge, we leave it using the one that was assigned (pairs are bidirectional). Now, each cycle collection is completely defined by the pairings defined of all nodes. By the definition given in the problem statement, we can see that cycle collections are the same if pairings are the same (because the connected pieces to a given piece p are given by the pairings of the each of the nodes representing the two numbers in p). So, we calculate the number of distinct pairings of each node and the result is simply the product of those 10 numbers. The number of pairings of an odd number is of course, zero (because we can pair them all without repeating). The number of pairings of 0 is 1, and the number of pairings of an even number greater than 0 is f(x) = (x1)*f(x2) because we get the first element, we select who is its partner (x1 choices) and then we pair the remaining x2 elements. Since x can only have a value between 0 and 9, there is no need to memoize or hardcode this values, although it could easily be done. Java code for a simple solution follows: int[] f={1,0,1,0,3,0,15,0,105,0}; public long countCycles(String[] p) { int[] d=new int[10]; for(String s : p)for(int i=0;i<2;++i) d[s.charAt(i)'0']++; long r=1; for(int di : d) r*=f[di]; return r; }Note: Since the constraints guarranted that the result will fit in a 64bit signed integer type, there was no need to worry about overflow, but a piece set that was complete with exception of 01, 23, 45, 67 and 89 would have a result that is greater than 2^{63} (this has all nodes with degree 8). In fact, 9 nodes with degree 8 and 1 with degree 6 would also cause overflow, but neither of these combinations were allowed. Just as a comment: see the incredibly fast Eryx's submission, with an amazing set of define's. StrawberryFieldsOnFire Used as: Division One  Level Three:
Happy birthday to you, happy birthday to you, happy birthday, dear John... happy birthday to you. The day this problem was used (October 9) was John Lennon's birthday, and the title, the initial quote and the name of the farmer are in his honor (if you do not know what I'm talking about, wikipedia does). Getting to the problem, it was easier than many other hard ones, and many coders were able to finish it, some with really high scores. The function that you were required to calculate may look hard at first glance  there can be a lot (10^{18}) of cells, and just calculating the time it takes each one to be covered can be expensive. But seeing that the number of burned cells is monotonically increasing (a fact that regular TC members probably saw pretty fast), it follows that a binary search is in order (iterating every possible time was also not a good option because, as examples showed, the answer can be pretty big). To be able to do a binary search, we must provide a way to calculate, for a given time, if the need of farmer John was fullfilled, or, in other words, if the number of not burned cells was greater than or equal to need. Since, as we mentioned previously, there are many cells, we need to do something clever here. The limited number of places where the fire can start (50) give the burn after some time a shape of many overlapped rectangles. This regular form needs to be used to cut time down. If we calculate the rectangles  at time T the rectangle that is made by the fire starting at i,j has one corner at max(iT,1),max(jT,1) and the other one in min(i+T,w),min(j+T,h)  and then extend the all rectangle borders we get rectangle areas that are either entirely burned or entirely alive. Accordingly, we can iterate only those areas and, for each of them, check any of its cells to see if it is burned or not. If it's not, we add to the counter the area's surface. In the above picture, red squares are the fire starters, yellow ones are the ones that are on fire now (at time 2) and the black lines are the mentioned rectangles (at distance 2 from the red squares) and their extension. As you can see, each black delimited area is either entirely red/yellow or entirely white. To do the aforementioned division, you need to get the set of all x coordinates and all y coordinates in each rectangle, and add the borders (0 and w or h respectively), then sort each set and do the iteration of each rectangle. For each i,j you either sum (x[i+1]x[i])*(y[i+1]y[i]) if cell x[i],y[i] is firefree or don't. To see if a given cell is free, simple iterate all rectangles and check if it is contained. Since the number of elements in each of x and y sets is bounded by twice the number of rectangles plus the borders of the field, each one can have at most 102 elements, and therefore there are at most 102^{2} field areas to check. Each check costs 50, getting to 102^{2}*50. Finally, the binary search cannot take more than 64 steps (because is a 32 bit number), so the overall number of iterations is upper bounded by 64*50*102^{2}, which easily fits on time. 
