Author: Tilps

So round 3 was last weekend, and no exceptional circumstances were declared so just the top 500 went through (which didn’t include me).

With only the top 25 going onwards, the questions were always going to be tough, and for the 4 questions, getting all the small inputs and 2 of the large inputs in a decent time was sufficient to get through.

Only 370 people out of the top 500 got a positive score, and having an initial look through the questions I doubt I would have done very well – maybe a couple of small inputs out.  One of the 2 remaining Australians got 66th place, quite impressive.

On to the questions I guess, although I’m going to have to refer to the post contest analysis this time for sure!

Q1) Given a sequence of numbers which are at most D digits in size, determine whether the sequence is predictable if it is governed by S(n) = A*S(n-1)+B mod P and if so return the next number.  P is prime and less than 10^D, A and B are non-negative.

A1) The small input D was at most 4, meaning that a brute force on P and A, solving for B, verifying the rest of the numbers fit, and determining whether the set of next numbers was unique, is easily done.  That would have been easy.  The large input however D is at most 6, making a brute force of P and A impossible.  What we need to do is consider each P and the set of numbers to determine both A and B simultaneously.  If we have 3 numbers, we have 2 simultaneous linear equations, Y=A*X+B mod P and Z=A*Y+B mod P (if we don’t have 3 numbers, the sequence is not predictable… for every A there exists a B which gives the result).  If we subtract these equations we get Y-Z = A*(X-Y) mod P.  and so long as X-Y is non-zero since P is prime, this equation has a unique solution which we can solve using extended GCD (which is in TMD.Algo).  This still leaves a few special cases.  Specifically the X=Y case.  If X=Y then Y will also equal Z, due to symmetry, regardless of A and B and P.  So any case of repeated numbers is predictable. This includes the 2 number case, despite what I said just before…

Looking at the contest analysis seems I was on the money here. So, worst case I would have come 250th… lets see if I can do better…

Q2) Given up to 100 unique integer lengths of fencing, determine the minimum number of fencing pieces required to create a fence with a length of exactly L.  L is between 10^10 and 10^18.

A2) For the small input the maximum length of each piece of fencing was 100.  For the large that jumped to 100000.  I think that a key point to this question would have to be that L has a very large minimum value.   For the small input I would posit that it can be solved using dynamic programming on the lengths of fence to create lengths less than 10000, then for each of positions up to 10k prior to the target L using only the largest piece, check if there exists a way to reach L using the DP table, and find the minimum amongst those options.  When the fence size jumps to 100k, my approach becomes infeasible, because the DP needs to go to 100k squared.  Going to have to check the solutions for this one.

Okay, so I would probably not have gotten the large out, although the intuitive leap does appear within my level.  Take the largest board, use it until we get just short of L (or exactly L).  Then we need to determine how to make the remainder using smaller fences, or to make the remainder + largest fence, or +2 largest fence…  We can do this by creating a graph, starting with nodes 0 to largest fence-1, and adding edges as follows.  For each fence length less than max, add an edge from each node to node + length of weight 1 if node+ length < max or to node + length -max of weight 0 otherwise.  Then given this potentially 100k node graph with, maybe 10million edges, find shortest path from 0 to remainder (This can be done in O(E) time).  The length of that shortest path + number of max length boards to reach 0 is the answer.  This only works because the shortest path will never have more than 100k weight 0 edges, and L is greater than 100k squared.

Based on my reading of the answer, I believe my small input answer is correct, so that would bring me to 21points or 187th place.

Q3) Given up to 200 locations at integer coordinates on a (very long) line each containing 1 or more items, you want to move them so that there is at most 1 at any spot.  However your only option for moving them is if there are 2 or more on a spot you can move 1 to the left and 1 to the right.

A3) Small input is up to 200 items, large input is up to 100k items.  Even the small input seems tricky here… would seem to need some kind of strategy.  Thinking about each move, it doesn’t change the centre of mass, so if we can find the centre of mass, the number of moves is minimally limited to those which spread them to being every spot filled with 1 about that centre of mass. That however may not be possible.  Movements at the centre of mass are more useful than other movements since they are the only ones which actually separate things.  The problem may also be separable into sub problems which don’t interact.  In that case the centre of mass of each sub problem seems important.  Small input I guess can be done via simulation of a strategy of centre of mass first or maybe largest first.  I probably would have just tried one to see if it solved it, since you get answers for the small input immediately.  Large input however requires better than straight simulation…  Time to check the answers again…

Well, turns out strategy isn’t needed for the small input, so I would have solved it ‘by accident’ – the actual series of moves is irrelevant, the final configuration is always the same and takes the same number of moves to get to regardless of strategy.  Apparently this is a ‘famous theorem’ which probably means there are a few thousand people in the world who know it 😛  With this observation (and one other leap I would have been unlikely to get) the problem becomes quite simple.  Simply construct the final answer and from there determine how many moves were required to get to it.  Constructing the final answer can be easily done by simply building up the input.  Adding each stack one item at a time, it either goes into an empty spot, or it causes the current end stack to split in 2.  If you keep a stack of segments, the possible scenarios are, top 2 segments join, top segment splits or top segment splits and the bottom part joins with the one below it.  Each operation is therefore O(1), giving an O(n) simulation to get the final position.  Now the trick to get the number of moves is to take the sum of squares of the original positions and compare them to the sum of squares of the final positions.  What will be found is a difference which when divided by 2 is the number of moves. This can be proven by considering how the sum of squares changes with each move.  I suspect that if I had of known the theorem I would have tried to count the number of moves while simulating building up the stack.  Each addition adds a number of moves related to the lengths of the splits it causes in a segment. Doubt I would have solved that in a competitive scenario anyway…

I’m willing to give myself the small input though, bringing me to 27 points and 158th in my imaginary competition where I hadn’t flunked in the previous round.

Q4) How many ways can you add 1 or more different numbers to give k, subject to a rather complex restriction…  The restriction is, if the numbers are written in base B, the dth digit (counting from the right) of each number will be unique across all the numbers. Different orderings of the same numbers all count as the same way.

A4) This question strikes me as pure evil, but interestingly enough slightly more people got out the large input for this than for the previous question…  The small input limits B to be binary to decimal and k to be no more than 100.  The large input however raises B to being anything up to base 70 and k to be up to 10^18…  I think the key to do even just the small input is to realise that we can reorganise the digits freely between numbers, without changing the sum.  But even with that it seems a bit tricky, dp over sums s less than k, with the number for the largest digit rearrangement being n, also less than k.   Then we need to work out how to multiply the total to get the actual answer.  I think we may need to break the dp down into number of sums of n numbers to get to s, since I think the reordering count depends on that.  However the fact that 0’s on the front don’t need to be distinct is a problem.  At this point I give up and look at the solutions.  Its not like I would have had any time left to solve this question in the competition anyway…

Apparently I was complicating things too much – the small input can be done by simple brute force, the number of partitions of 100 with distinct integers is only a few hundred thousand, you can just generate them all.

However I was starting to get on the right track for the large input.  It is a dynamic programming problem, and the order of digits is not relevant for each column, but the needed approach is to build up one digit at a time, and using a nested DP to count the number of reorderings for each column.  So you need to keep track of the carry, and how many of the numbers are finished and whether there is a 0.  The zero allows for the termination of a number, but I am not sure why just the fact of a 0 rather than the number of 0’s is needed to be known.  It almost makes sense, but I would need to implement it to be sure.

Anyway 0 points for me here so I’m stuck with my theoretical 158th place.

158th would have been close to my best ever placing, which was 115th in the first GCJ when it was still run by top coder… (and 100 people were going to be flown to the US) and the depth of field has definitely increased since back then… (In a super imaginary world where I had made the intuitive leap for Q2 large input, I would have gotten 51st… ahh I can dream :P)

So, 500th place was the same score as me, just 30minutes faster.  If I had of started with question 3 rather than wasting almost an hour on question 1, I would have gotten through.  Had I submitted anything else successfully I would have gotten through.

Exactly 2 Australian’s got through, in 498th and 500th respectively.  I was the third highest Australian, and given how I was doing in the first round, 615th was a fairly successful result, just disappointed I don’t get a t-shirt.

On to the questions…

Q1) Give a set of numbers laid out in a diamond shape (for instance 1 number on the first row, 2 on the second, 1 on the third), determine the smallest diamond shape of numbers which contains the given diamond, and is horizontally and vertically symmetric.

A1) This question had a bit of controversy, up until about the 50minute mark (which was when I switched to Q3) the question text was actually incorrect.  I would claim this as why I failed to solve the problem, but almost certainly the real reason is because of the midnight start, my approaching head cold and general momentary stupidity :P.

Possibly the biggest pain with this question is the diamond shape.  It is not a nice layout of numbers to work with.  I spent a few minutes trying to get my brain cells to work to write code for detecting mirror symmetry in a subset of the diamond before I gave up and rotated the diamond 45degrees, making it a square.  Even writing the code to do that wasted about 15minutes, which indicates how well my brain was working.  Working with a square with diagonal symmetry checking was much easier, although I still had a bunch of off by one errors I had to fix.  In the end I did get that working, but while my answer solved the sample, it did not solve the small…

As I realised after the competition it was because I was completely screwing up my solution.  I was determining 2 mirror symmetries in a subset and mysteriously assuming that could be used as the seed of the smallest double symmetric diamond which contains the original.  I was at least having the requirement that the subset included one of the corners, but this approach is just wrong.  In the end I have all the code I need to solve the problem, just the wrong algorithm!

I believe the correct solution is to find the largest single mirror symmetric (along the axis which doesn’t pass through the corner) subset for each corner.  Then find the largest sum of pair of non-opposite corners.  These 2 will be the seeds of the large diamond.  Final answer is 3*original diamond size – sum of sizes of pair of non-opposite corners half symmetric subsets. (Give or take some off-by ones which I may have missed…)  All in all given how few points this question was worth, I really should have listened to my first instinct and just ignored it completely.

Final results for the competition are not announced yet, leaving a tiny hope that I might get through due to the controversy with this problem, but it would be a cheap win which I don’t deserve.

Q2) Given 2^p teams competing in a knock-out competition, with each match  in the knock-out tree having a specific cost and a list of the maximum number of games for each team you are willing to miss, determine the minimum cost to attend the required number of games worst case. (p is up to 10)

A2) Having up to 1024 teams scared me away from this question quick smart, but it was the one that most people actually solved.  The small data set every cost was 1 dollar, the large, the costs varied between 0 and 100000.  Even so overflow was not going to be an issue.  Even now I can’t immediately see how to solve this, but I am beginning to think that it involves a divide and conquer approach…  And pretty much as soon as I’ve thought about the question properly for a minute I have solved it.  Define the recursion to be over the minimum cost to satisfy all leaf restrictions of a given branch, having already bought n matches at some parents.  Then for each node in the tree, the result is equal to the minimum of the cost of this node and the sums of each child for having bought n+1 matches, and the sum of each child for having bought n matches.   Terminating condition of infinite cost if we fail to satisfy the maximum games missed for a given team.  Finally the result is the grand final match node with having bought 0 already.  This can be done using dynamic programming, with an array p by (2^p)-1 using the /2 to find the parent, *2/*2+1 to find the children packed tree in array representation.  Or you could dynamic program over an actual binary tree, with each node containing an array… performing a depth first walk.  Or you could do memotized recursion.  Whatever, its all easy – and I really should have taken a closer look at this one!

Q3) Given an ‘infinite’ grid with cells which are filled in or not, where each cell which has a north or west neighbour stays alive and which has both a north  and west neighbour, but is empty, comes alive (simultaneously – so a north east pointing diagonal line of cells slow moves and shrinks to the south east).  And up to 1000 large possibly overlapping rectangles which are initially filled in, determine how long before there are no cells filled in.

A3) I managed to solve this as almost O(N^2) in the number of rectangles.  I suspect with the appropriate data structure checking every pair for ‘overlap’ could be reduced to O(N log N) but O(N^2) is plenty for this questions large constraints. (The almost in the first sentence is the O(alpha(n)) amortised cost for each disjoint set tracker union operation.)

First we divide the problem in to sub-problems.  If two sets rectangles are well separated, they do not influence each other in any way.  So first of all what counts as separated?  If 2 rectangles overlap, then presto that is a guaranteed interaction.  If they don’t come close to touching at all (separated by at least one in any axis), they are separate.  If they are horizontally or vertically immediately adjacent, they act together.  This leaves diagonally adjacent.  Corners touching in the north east/south west directions count, but the north west/south east directions do not.  I used a disjoint set tracker (I love this thing!) to track which act together and which do not.  This part of the problem actually turns out to be the most expensive, since the rest runs in O(N).

Once they are separated we can treat each section individually and take the maximum of each problem.  So given n rectangles which interact, how long do they last?  It is fairly easily apparent that no matter how the north west corners get trimmed at each time step, the south east growth areas grow first.  So the last cell to go will be the south east most part that either grows or is already there.  Growth areas are limited by the south most edge and east most edge of all constituent rectangles.  The tricky bit is determining which of the first cells to go will be the start of the cascade which reaches that final location.  Although actually when it is phrased like that, it becomes somewhat obvious.  Since the area which dies moves south east, the most north west point is going to be the start of the final cascade, all other locations will get stuck against one of the walls belonging to that location.  That may sound convincing but proving it is probably more complicated.  I managed to convince myself well and truly before I wrote my solution, but my reasoning is not a proper proof, although I am sure one exists.  So comparing the north west corners to select the one which lies on the most north-west diagonal, and taking the maximum of the south east corners, we have the ‘effective rectangle’ for the group of rectangles which interact.  A single rectangle takes height + width – 1 turns to disappear, and this also works with the effective rectangle.  So we finally return the maximum of each disjoint set, and we’re done.  Only 60 people got this out, so I was quite happy.

Q4) Given N points which each have a goat tied to it, and M possible locations for a bucket which each goat must be able to reach, determine for each bucket the minimum area which all goats can reach, by adjusting the goat ropes to whatever length you like.

A4) I spent my last 25minutes doing the small problem set for this.  If I had of successfully submitted it, I was through, and I realised that at the time, so the pressure was on.  The small problem set limited N to 2, which is the easiest case of the overlapping circles problem.  When I saw this I thought, cool that will be simple I’ll just jump on mathworld copy the formula into my code and submit it… Which I did.  And it failed.  Oh I have a bug.  Fix that, still fails.  Oh what about this special case, fix that (later realise that the problem explicitly excluded it from being possible), still fails.  Hmm maybe numeric accuracy in the acos function parameters, avoid unneeded square roots… still fails.

What can I say it was 2am, I couldn’t quite activate enough brain cells to realise that the formula from mathworld was wrong…  Well not exactly wrong, more, insufficiently correct.  The mathworld solution only handled the case where the circle intersection points form a line which crosses the segment joining the circle centres.  If the resultant area is made up of 2 circle subsections where one of the circle subsections is more than half of a circle, it produces the wrong result.  In that case the area is the sector + the triangle, rather than the sector – the triangle.  If I had of actually sat down and derived the formula I might have gotten this correct, but 25minutes at 2am, it wasn’t going to happen.

The large problem set, N is up to 5000, M is up to 1000.  Even if I had the formula for the area of a truncated circle and an arbitrary convex polygon already written (which is something I should really get around to doing for TMD.Algo), I suspect I would take a long time to write the solution, and even then I think it would be O(N^2 * M) at best, which is very risky timewise.  I think something like the convex hull algorithm must come in to play.  Only 2 people got this problem out and they came 7th and 27th.   The top 6 got everything out except for this.

I actually think I have seen this question asked in topcoder before, so its probably worth being added to TMD.Algo in its entirety.

So that is most likely it for GCJ10 for me this year, I’ll write up the analysis for R3, which will likely contain some interesting questions – they save the best for last…  Next stop is round 1 of TCO10.

Didn’t quite make it through – was happy with my one solution, unhappy that I didn’t get any of the smalls out for the other 3, despite trying 2 of them for about an hour and a half.  I think the one I didn’t try looks like it was the easiest of course.

Final placement was 615th.  Will write up a full analysis after sleep…

So I blinked and I missed the fact that qualifying round 3 had already happened.  I thought it was this coming weekend.  Having got through in QR1, forgetting about it is no drama, but it does mean my analysis of the problems is a bit late.

Q1) Given the top row and left column of a grid of numbers, where each number is supposed to satisfy the property of being equal to the sum of the 3 numbers to the bottom/right/bottom-right of it, determine the value of the bottom right number.  If the result cannot be uniquely determined return 0. Maximum grid size 10×10.

A1) First to get rid of the trivial cases.  If row length is 1, return last column entry.  If column length is 1, return last row entry.  Otherwise we actually have to fill in the grid.  This is pretty trivial since each cell is the sum of the 3 bottom/right/bottom-right, if you know the cell, the bottom and the right, you can subtract the bottom and the right to get the bottom-right cell.  Given you have the top and left sides, you can fill 1 cell immediately.  That cell lets you fill 2 more, and those, 3.  So you could diagonally fill the grid.  Or you could just fill row by row, or column by column.  In any case the cannot be uniquely determined scenario doesn’t exist so it can be ignored.

Q2) Given 6 numbers representing number of semitones to offset a guitar string (or -1 if that guitar string is not played), determine whether a major or minor cord is being played and if so which one.

A2) When I first started reading this question I had dreaded flashbacks to an old Top coder problem which was very similar.  However this one is relatively easy.  Modulo arithmetic comes into play.  Simply add the offsets (where not -1) to the numerical value of each guitar strings open note (as given in the problem for those who don’t play guitar) modulo 12.  Then reduce your (upto 6) notes to the unique values.  If you have more or less than 3 values you can return not-a-chord immediately.  Otherwise, sort the 3 values.  For each of the 3 values, check to see whether the next one (wrapping round if you start with the greatest value) is equal to the original + 4 or 3 modulo 12.  Then check if the remaining value is equal to the original + 7 modulo 12.  If both conditions are matched, return Major ‘letter’ by mapping the original value to the letters if the first condition was +4, or Minor ‘letter’ if the first condition was +3.  Otherwise return not-a-chord.

Q3) Given a pane of glass with width and height (both at most 1000), a starting position, and up to 2500 LRUD unit movements which cut the glass, starting from the starting position, how many pieces has the pane of glass been cut into?

A3) This is a simulation problem combined with a disjoint set enumeration.  The thing I find most annoying with problems like this is the data structure to store the results of the actions.  So used to a grid, storing details about edges is just annoying.  I usually end up storing the 4 edges of each cell and dealing with the fact that most edges belong to 2 cells by ensuring I always update both.  A grid of numbers can be used with numbers between 0-15 indicating which combination of surrounding edges have been cut, you can store these in bytes even making the grid require 1meg of ram.  Once the simulation is complete, calculating the pieces comes in to play.  I would do this with a disjoint set tracker (copying my code from TMD.Algo – since this is top coder… or maybe just writing it from scratch using arrays instead of dictionaries), creating a node for every square, then for each square unioning it with every neighbour which is on the other side of a non-cut edge.  Then for each square get the representative, and use a dictionary to accumulate the count of unique representatives.  Disjoint set tracker is practically O(1) for union and get operations, so even though there are a million cell locations the running time will not be a problem.  Memory usage will be a few megabytes, but within the 64meg limit.  This is really just showing my bias to disjoint set tracker, which I think is awesome.  For a similar approach which uses a tad less memory, you can just do floodfill counting using breadth or depth first searches which can’t pass the cut walls, which is also O(1) per grid cell.

Alternatively one could construct a graph out of the path followed and the edges of the puzzle.  Due to the limit on 2500 moves and 4000 edge positions, the memory usage will be much lower.  You can then walk the graph starting at each edge using a turn right at intersection approach, mapping each location visited (and handling dead-ends by turning around and keeping on walking).  Once you find a loop where you enter an edge from a direction other than the one you left it, you increment a counter and in any loop found case go back to starting at the next edge not already visited.  Once done the counter is the number of pieces. Each edge is visited at most three times, so O(N) in edges (moves + perimeter), which is far more efficient.  I would however consider it more complicated to implement, so I doubt I would have bothered.

All in all this looks like it was a pretty easy set.  Although being a qualifying round that is probably expected.

This round needed at least one problem out entirely, and if it wasn’t the third problem you needed the whole second problem or the small input for the third.  So it looks like it may not have been quite as easy as R1B.

Q1) Given n lines which all start and end with one of 2 x coordinates, and the list of y coordinates for each endpoint which are all distinct, and a guarantee that there will be no coincidence of intersections (no places where 3 or more lines cross), how many intersections are there. Constraint of n < 1000 for the big input.

A1) This is a simple O(N^2) problem, for each line it crosses another if the y coordinate order of one end is the opposite of the other.  I think I recall there being a way to do this faster… indeed the contest analysis mentions that this can be done in O(N log N), it is called the number of inversions in a permutation.  That is first sort the lines by their first end point, then determine how many pairs switch ordering when you sort by the second end point.  Apparently a merge sort can be adapted to perform this calculation, which is equal to the number of neighbour swaps required to sort them, which I have seen in previous problems which I have also solved using O(N^2) because the problem input size has never needed anything else.  I should probably look at adding this merge sort trick to TMD.Algo.

Q2) Given a known range which contains the maximum number of simultaneously connections a computer can handle (the upper end is known failure, lower end known success) and a requirement to reduce that range such that the top end is less than C times larger than the lower end (where C is an integer between  2 and 10, inclusive), what is the minimum number of tests required to guarantee that in the worst case.

A2) Bit of an odd question, one would first think a binary search would be idea, the size of the range would reduce consistently.  However, our target is not the size of the range but ratio of top to bottom.  Therefore we want a skewed binary search where the selection point is the one which results in A/S = S/B so our selection point is the sqrt(AB).  Now since the load tests can only be performed on integers, we’ll have to choose one of the 2 integers near the value of the square root.  In order to be ideal we must choose the one which has the best worst ratio, might as well use fractions just to be safe in comparing them. Then we simulate this process until the ratio is less than or equal to C.  The sample answer is not quite the same, however given that based on the selection point chosen, the ratio is sqrt(A/B) after n steps that is (A/B)^(1/(2^n)),  If we want that to be <=C then A/B <= C^(2^n), which is exactly the formula in the sample answer, so I think my approach is correct and should produce the required results.

Q3) Given a rectangle patterned with white and black squares, you need to make chessboards, starting with the largest chessboards (which can be larger than 8×8) all the way down to the smallest chessboards (1×1).  The largest chessboard available is always taken first, if there are multiple of equal size, top most and then left most are subsequent tie breakers.  Small problem set the input size is 32×32, large problem set the input size is 512×512.

A3) The small problem size isn’t too bad, we can simply brute force it, with a bit of caching to speed things up by a constant factor or 2.  The large problem size however is an entirely different story, an O(N^5) solution most certainly isn’t going to cut it.  Even an O(N^3) solution will likely fail to run in time.  This probably has something to do with the low success rate that this problem had.  So can the problem be done in O(N^2) ?

One trick is to construct the chessboards efficiently, every chessboard is itself a lot of smaller chessboards.  We require overlap to ensure consistency, so if you first identify all 2×2 chessboards. Those 2x2s can be used to create 3x3s.  3x3s can be used to create 4x4s and 5x5s, 4x4s can be used to create 6×6 and 7×7,5×5 can create 8×8 and 9×9.  If we try to race to the largest size and then work our way down filling the gaps in, this has potential. However each time we cut a chessboard out, we need to invalidate efficiently as well, all chessboards which overlap with the area need to be invalidated.  I still am not sure this is fast enough – it looks awfully like even with the best care and data structures it’ll be O(N^3) in the worst case.  Time to check out the sample solution I think…

So yes it can be done better than O(N^3), O(N^2 log N) in fact and the solution is very smart.  First of all we use dynamic programming to find the largest chessboard which has its top left corner positioned at that location.  I’ve seen this before but I’m so rusty I had clean forgotten it.  First check if it is the top left of a 2×2 chessboard, if not the answer is 1. Otherwise it is 1+ the minimum of the largest chessboard sizes for each of the other 3 locations in that 2×2 chessboard.  If we store each cell into a heap ordered by its largest size, y and x coordinates, we have the order to remove things in, the trick becomes the invalidation due to removal.  When you remove an area, every cell in that area now has a largest square of 0, but other cells may need their largest square being updated as well.  As it happens since we just removed the largest square, we know that no locations more than double that square away overlap.  So the number of locations to invalidate, recalculate and re-add to a heap is 4 times the number of locations removed, and since each cell can only be removed once, the number of invalidations is worst case 4*N^2.  Since each invalidation is a heap removal and addition, which is O(log N) each, we get O(N^2 log N)

All in all I suspect I would have placed in the top 300 in this round. top 400 in the previous. Even allowing for the fact I had a below average run in round 1A I probably would have only made top 400 in that round (maybe 250 on a good day).  So it doesn’t look good for getting top 500 and a t-shirt this year unless I do some serious improving.