|
Match Editorial |
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.
In Division 1 the easy and hard problems were easier than usual, but a pretty theoretical
medium tricked many coders. ACRush did
not have a good start, but an amazing 900+ performance on the hard took him near the
top, and three successful challenges got him the rest of the way. A little behind was
venco, who also managed to get three challenges
on top of a solid performance on the problems, and needed only one more to get first.
Completing the podium was tomekkulczynski, who had a solid performance
on all problems but would have needed an incredible challenge phase to get higher in the ranking.
In division 2 the problem set was more balanced and many coders were able to get the three problems right.
The key for winning was the hard problem, where a fast and correct implementation made a big difference.
preyas_p took home a win thanks to fast solutions
in all problems, which gave him enough of a margin to avoid worrying about the challenge phase. In second
place came asal1 and in third
MonEtoile, also thanks to coding and not to challenges.
The Problems
DerivativeSequence
Used 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:
Value 250 Submission Rate 427 / 447 (95.53%) Success Rate 410 / 427 (96.02%) High Score zombiecoder for 249.37 points (1 mins 25 secs) Average Score 221.73 (for 410 correct submissions)
int[] difSeq(int[] a) {
int[] b=new int[a.length-1];
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), n-1);
}
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:
Value 500 Submission Rate 319 / 447 (71.36%) Success Rate 189 / 319 (59.25%) High Score tdc241 for 489.87 points (4 mins 6 secs) Average Score 355.68 (for 189 correct submissions)
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.
Value 250 Submission Rate 467 / 474 (98.52%) Success Rate 394 / 467 (84.37%) High Score sjelkjd for 248.02 points (2 mins 32 secs) Average Score 222.06 (for 394 correct submissions)
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(n2) 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.
Value 1000 Submission Rate 117 / 447 (26.17%) Success Rate 63 / 117 (53.85%) High Score preyas_p for 775.75 points (16 mins 17 secs) Average Score 497.58 (for 63 correct submissions)
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 two-by-two 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<0||j<0||i>9||j>9||mark[i][j]||board[i][j]!='X') return 0;
mark[i][j]=1;
return 1+size(i+1,j,board,mark)+size(i-1,j,board,mark)+
size(i,j+1,board,mark)+size(i,j-1,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.
Value 500 Submission Rate 99 / 474 (20.89%) Success Rate 41 / 99 (41.41%) High Score Eryx for 493.65 points (3 mins 13 secs) Average Score 314.09 (for 41 correct submissions)
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 non-zero 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) = (x-1)*f(x-2) because we get the first element, we select who is its partner (x-1 choices) and then we pair the remaining x-2 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 64-bit signed integer
type, there was no need to worry about overflow, but a piece set that was complete with
exception of 0-1, 2-3, 4-5, 6-7 and 8-9 would have a result that is greater than 263
(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:
Value 1000 Submission Rate 103 / 474 (21.73%) Success Rate 67 / 103 (65.05%) High Score ACRush for 934.19 points (7 mins 38 secs) Average Score 535.39 (for 67 correct submissions)
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 (1018) 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(i-T,1),max(j-T,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 fire-free 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 1022 field areas to check. Each check costs 50, getting to 1022*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*1022, which easily fits on time.
For an implementation with this idea see venco's code.
