Author: Tilps

Not sure whether attendance for 1B was higher or the problems easier, but the cut-off for getting through was a much higher score…  Unlike my round where solving any single problem with a decent time was sufficient, this round you needed at least 2.

Q1) Given a command for making new directories, which will only work if the parent directory exists, a list of current directories, and a list of directories required, determine how many command calls are required.  Constraints are up to 100 existing paths, 100 desired paths and each path at most 100 characters (and hence at most 50 deep)

A1) This problem makes R1A Q1 almost look tricky – just maintain a dictionary of existing paths and for each new path add/trim/add/trim until the add fails – and count each add.  The constraints are so small that the cost of generating alot of garbage strings isn’t even a problem – so no need for any kind of optimisation.  Do need to be careful you don’t try and add the empty string, but otherwise trivial.

Q2) Given a set of ‘points’ at different locations, and their velocities, and the position of some goal, and a restriction that in order for one point to pass another requires a ‘cost’ of 1, what is the minimum cost to have at least N points at the goal by time T.

A2) Okay, so this one is an actual problem… We can start by considering for each point, whether it can reach the goal based on its own velocity. If not we can kind of ignore those points.  If the number of points which can reach it based on own velocity is less than N, we can fail immediately.

At this point I would think that the right most N points which can reach the destination in time will be the ones we want.  Then the cost is the number of non-reachables to the right of each of those N points, as summed for each point.  If we were to choose a point which is more left, it would have to pass more non-reachables to get to the goal in time, increasing the cost.  This greedy approach seems sound, I’ll just check someone’s solution… yeap it is sound.  I now can see why you had to solve 2 problems to get through…

Q3) Given a set of numbers 2 to N, determine the number of subsets which contain N and its rank (ordered inclusive position 1-based), its rank’s rank, its rank’s rank’s rank, and so on until you get to the first element in the set.

A3) A math problem… and by far the hardest problem.  Constraints are N is 25 or smaller, or 500 or smaller for the large.  Quite a few got out the small constraint, but not so many for the large.

That being said, it isn’t really that hard of a problem.  Its a dynamic program over sets of length k, which end with m and satisfy the input constraint given m.  Both k and m are limited to being less than or equal to N, and the recursion is going to have to consider each shorter length, so O(N^3) is in play.  With N of 500, that is 125million steps, so each step itself better be quick.  So we’ll need a closer look to be sure.

Recursion shall be defined as the sum over each shorter length with m equal to the current k.  However each of those sum components need to be counted by the number of possible ways to choose the difference in lengths -1 extra numbers which are greater than k and less than m.  A direct approach results in that being O(difference in lengths) which is worst case O(N), which is nowhere near fast enough.  However all of the possible choose calculations can be precalculated in O(N^3) (or O(N^2) if you cache factorials and inverses mod p).  The important bit here is that the value of n choose k might be huge and the problem requires results modulo 100003.  Using TMD.Algo this will not be a problem, as I have an efficient n choose k mod p implementation already done and 100003 is prime (see, implementing stuff useful for last years GCJ, also useful for this year…).  Net result is a couple of hundred million multiplications  and additions and modulos.  The same lookup table can be used to answer all 100 inputs, so 8minutes is plenty of time.  In fact that last realisation is one I would have been at risk of missing during the contest, or I would have said I would have gotten all 3 problems out for sure if I was in this round.  Without reusing the table, the time constraint might be an issue, possibly depends on how fast your computer is… the look up tables will be close to fitting into cache on a good processor, but even then it might not be enough.

So, google code jam round 1A was today, and while I got through in 876th place (and so I won’t need to stay up for 1B or 1C), I feel the need to grumble a bit.  I started with the first problem, it was nice and simple (Especially considering I wrote AppleHunt…), I then went to the 3rd problem because I noticed that it was doable with the small input constraints and the constraints on the large input were the same as the small input.  By the time I had written my first non-functioning prototype for the solution, they had changed the constraints for the large output and my code wasn’t going to even come close to running in time. (and it would have required a couple of terrabytes of ram…)  I spent a few minutes working on the a different approach, since I had already done a bit of work on the problem, and the relaxed constraints actually suggested how the problem had to be solved. However, it quickly became apparent that I should go back to problem 2.  Another look at problem 2 and I was convinced that it was a simple dynamic programming problem.  However despite 3 submissions (including me noticing a blindingly stupid bug with <2min left on the clock) I wasn’t able to get something which solved the problem.  I have no clue why…  If I hadn’t of been mislead into to trying problem 3 first, I almost certainly would have either gotten problem 2 out, or at least submitted a solution for the small input size which used brute force rather than dynamic programming.

So I just had a look at a solution to problem 2 and I worked out why my solution failed, a subtle error in my thinking while constructing the dynamic programing resulted in it failing to consider the combination of 2 scenarios I had considered.  I also looked at problem 3 and have to say that the cool solution is excessively mathematical, but there is an option which performs reasonably which is more about programming…

So on to my analysis…

Q1) Given a board up to 50×50 with red/blue pieces on it – cause them to slide to form stacks coming left from the right hand side of the board.  Then determine for each of blue or red whether there exists k or more in a row either horizontally, vertically or diagonally.

A1)This problem is easily implemented in O(N^3) (where N is the width of the board) and that is actually sufficient, however I saw an O(N^2) solution and took it for the hell of it.  First step is to slide all the pieces – for each row you simply perform an order maintaining sort over empty-non-empty – or given that empty has no state, you maintain the last moved to position, move each piece to one left of that as you find them, either using actual moves, or simple assignments with a clear of all positions to the left of the top of the created stack afterwards.  O(N^2) for this step or up to O(N^3) if you ‘stable bubble sort’ the pieces in to position for each row.

Once the board is set, you have to determine who has ‘won’.  A simple walk of every square, and foreach walk in each of the 8 directions will determine this, or even only 4 directions.  This gives O(N^3).  I used DisjointSetTracker from TMD.Algo to create disjoint set collections for each of the 4 types of win.  For each square I unioned it with its win type neighbour set if they were the same colour – O(N^2).  I then determined the size of each disjoint set, using dictionaries to accumulate how frequently each representative member appears for every possible input square – O(N^2) – if the disjoint set size is greater than or equal to k, we look up who owns the representative member and they are a winner.

Q2) Given a sequence of numbers between 0 and 255 inclusive, and the ability to delete (for cost D), insert (for cost I), or change (for cost absolute difference between value before and value after) each number, determine the minimum cost to make every number have an absolute difference with its neighbours of less than or equal to M.

A2) The small problem constraints had a maximum of 3 inputs, something you could brute force.  However with up to 100 numbers, the large problem (which is the only one I actually attempted) required some other solution.  It was fairly obvious that you could define the problem recursively being the minimum cost to satisfy the first n numbers ending with value k.  And that is where I made my mistake.  I defined ending with value k to be after inserts were added, which is incorrect, it has to be ending with value k after modifying the value only.  With that correction we can proceed.  Cost for 1 element is 0, otherwise it is the minimum of satisfying scenarios with 1 less element.  The are 3 scenarios which need to be considered. Deletion, which is cost of the same final value with 1 less element + D. Change, which is the cost of each possible previous ending value which is within M of the current target value + the absolute difference between the current actual value and target value. Insertion, which is a bit more subtle – so long as M is non-zero it is the cost of each possible previous ending value + the I times the the difference between previous and target divided by M (using ceiling rather than floor to convert to integer) – I + Change cost.

Using dynamic programming you have a table of size 100*256 and a net cost of 100*256*256 since each entry requires an inner loop over previous values.  Apparently there is a way to calculate the table entries in average O(1) time each, but it is beyond my skill level.  On the other hand it actually starts with making the same mistake I did, but fixing it using some serious smarts.

Q3) Given 2 numbers A and B, you can subtract a multiple of the smaller from the larger (even if that multiple is 1) and end up with a non-negative number.  If we turn this into a game, where the aim is to not be left in a scenario where you are forced to end up with one of the numbers being 0, determine how many winning scenarios there are for you given all combinations of 2 input ranges for A and B (both being at most 1 to 1000000).

A3) The small input constrained the 2 ranges to being at most 30 wide, meaning only 900 games needing solving for each problem.  Given that I was looking at GCD in qualifying round for another problem I immediately recognised the potential for GCD to be related to this problem.  I determined that there is no difference between Solve(A, B) and Solve(A/GCD(A,B), B/GCD(A, B)), and I was going to use this to accelerate my solving of the problem. Assuming A>=B, A=B is a loss, A%B=0 is a win since you can leave B = B.  I then used GCD as an accelerator to reduce the number of subproblems to solve and Memoitzation.  Obviously I made a mistake as it didn’t produce the right results for the test inputs, but I think the approach would have been sufficient for the small input.  What I had failed to see was that there was a much better minimum condition for obvious win than A%B=0.  A >= 2B is a win.  This can easily be seen because either the smallest possible next non-zero value for A is a win, or it is a loss and smallest next value for A + B (which is <2B) will force force the opponent to create the small next non-zero value of A, B combination which you just found was a loss.  This is much more powerful and certainly puts the small solution easily within reach.

So what about the large problem set, where the ranges for A and B in inputs both can be up to 1 million wide?  Testing every possible scenario is … infeasible, so there obviously has to be some approach for determining whether a combination is a win or loss, for each possible value of A, in constant time for the entire range of the B inputs at once.  This is where I think the problem becomes a failure. If A >=2B is a win, then 2B>A>B is the interesting range for A. In this scenario we only have one possible move, which is to end up with B and A-B (which is now the smaller one).  If B>=2(A-B) it is now a win, which means the original position was a loss. Thus if A < 3B/2 the original position is a loss.  And we can keep recursing like this, chipping away at either side of the interesting range until it disappears.  That is okay and you can perform that recursion in log time – which while not constant time, is plenty good enough.  Where the problem fails is that this recursion can all be thrown away by a single comparison to the golden ratio, which is what the outside edges of the interesting range converge on, from above and below.  Why does that make the problem a failure?  Because its interesting enough that it has been solved before – so you have a number of people who will just pull the golden ratio out of nowhere and submit a solution, which is all math and requires no algorithms.

An alternative approach which is inspired from seeing that the interesting area can be recursively chipped away on the left and right, is that there is ultimately a single number which is the transition from win to lose.  You can then binary search to find that transition point, which is again fast enough, I think that solution ends up being O(N log^2 N) – maybe better with memotization…

R1B is tonight – I’ll do a write up for it tomorrow.

So QR2 for TCO10 was yesterday, and I decided to take a look at the questions today.

Q1) Given a list of sell prices and buy prices for a specific type of object, and a tax on selling, determine maximum profit given you start with none of the item.

This is pretty easy.  Calculate the tax for each sale and reduce the sell price accordingly.  Then sort the adjusted sell prices descending and buy prices ascending, then while adjusted sell price is greater than the buy price, add the difference to the profit.

Q2) Given a square array of live, dead, unknown, determine the optimial values for unknown to ensure the maximum number of live cells after 1 round of the rules for Conway’s game of life.  Important restriction that no cell will have 2 or more unknowns in its set of neighbours.

Again this is pretty easy, al because of the restriction, but there are a few tricks.  First you need to put the the input array into a larger array so that you have a border (for easiest implementation a border of width 2), since cells may come to life outside of the input array.  Because of the restrction, every unknown can be considered seperately, which means the algorithm runs O(n) in cells. For each neighbour of an unknown, calculate whether it will be alive or dead for each of live and dead options for the unknown.  Do the same for the unknown itself. Chose the maximum sum of live cells for each of the two cases and set the unknown to that case.  Once all unknowns are set, simulate the entire board for one step and return the live count.

Q3) Given a paragraph (upto 1000 characters) with all the spaces and puncuation removed, and a list of up to 50 words (each up to 50 characters) determine a ’tiling’ of the paragraph using the words (each word may be used 0 or more times) which maximizes the value of the square of the longest consecutive tiled sequence minus the number of uncovered characters.

This is a big jump in difficulty and I have to say that I probably would not have gotten this one out.  It is fairly obviously dynamic programming, the problem comes in determining the right way to achieve it.  My first guess was to dynamic program over the first N characters, with the last M covered, but I realised I also needed have the largest consecutive cover P as a variable parameter too.  This meant that the dp space was length cubed, way too large.  After looking at another competitors solution I now see the correct approach.  Use dynamic programing to calculate the minimum number of uncovered tiles for a range starting at i and finishing at j.  This can be achieved by starting with the minum for a range of one less length + 1, and then minimizing by checking which words match at the end of the range and using the minimum for the range minus the matched word.  Note that the act of checking the words is quite expensive in the worst case, so pre caching whether each word matches for each location keeps the runtime under control.

Once we have the minimum number of uncovered tiles for each possible range, we loop over each possible range where that minimum is 0, square the range length and subtract the minimum number of uncovered tiles before and after the range. Return the maximum of all of those possible values and -length.  This works because although it doesn’t descriminate as to whether the range selected is the maximum consecutive uncovered section, when the maximum consecutive uncovered section is selected, it will receive a larger score because the number of uncovered tiles will be the same and the selected range length will be larger.

So the qualifying round is over and ~1500 people (including me ) got all the questions out successfully. 8523 people got the required 33 points to advance to the first round.

Questions were very mathematical, only the 3rd question really had any algorithmic design to it.

Q1) This was an amazingly convoluted way of asking when an n bit integer is all 1’s.  It boiled down to k % (1 << n) == (1<< n)-1, a single line.  I suspect the problem was inspired by reading Knuth.  He has a section where he describes the bit effect of adding 1 to a number (among other things…) the least significant 0 and all less significant bits toggle.  Which is the same as how a chain of ‘snappers’ was described to work.

Q2) This was a very mathematical question, with a barb to annoy anyone who’s programming language doesn’t include a big integer.  The question was given a set of up to 1000 numbers, what is the maximum common divisor you can get by increasing them all by the same a non-negative integer, and more specifically what is the minimum non-negative integer which gives that maximum common divisor.  The kicker being that the numbers were anything up to 10^50, so they won’t fit in a 64bit integer.

The solution comes from identifying an upper bound on the common divisor of n numbers is the GCD of the absolute differences between the numbers.  Then if the minimum number is a multiple of the GCD the rest of the numbers will be as well, which is always achievable for any set of numbers.  For .Net 4 the problem was trivial – BigInteger has a GCD method, so you just parse the numbers, calculate the absolute differences, calculate the gcd, calculate the mod of any entry with respect to the gcd, and if non-zero subtract that from the gcd to get the minimum shift.  GCD can be implemented using euclid algorithm if it wasn’t there.  And if you didn’t have biginteger, good luck…  My code had one change compared to the description above.  I sorted the entries rather than calculate absolute differences, but I’m pretty certain that isn’t required.

Q3) This problem had the longest implementation, but is mathematically simpler than problem 2.  The question was given a roller coaster with k seats and n groups of people of specific sizes in a specific order and the roller coaster does R runs per day and every paying customer is worth 1 dollar and everyone who went on the roller coaster goes back on the end of the queue in the same order they went on to the rollercoaster (no one ever leaves), how much money will the roller coaster operators get in a given day?

So it is a simple simulation problem, but R can be extremely large, making simulating all of them too expensive.  Also k*R can be larger than 32bit integer, so you need to be careful you don’t overflow using 32bits at inappropriate times.  The algorithmic key here is to identify that the simulation of a run is always the same for any given starting offset into the queue, so you only have to consider at most 1000 simulations (the maximum value for n).  The final piece is to realise that if you ever get back to the same starting person, you have started a loop and that sequence of simulations will be repeated.  The loop may not start from the first simulation, but a loop will exist eventually, the loop cannot be longer than 1000 entries.  So to calculate the answer you break it into 3 parts.  1) Simulate until loop discovered. 2) Calculate the sum of the loop and determine how many more times it needs to be run to get up to R (using integer division).  Calculate that product. 3) Calculate the modulo to determine the final partial loop and sum those steps.  Those 3 numbers are summed to give the answer.  Of course if R is too small you may not need step 2 or 3.

I’ll only cover the take 2 questions here, even though I thought the take 1 questions were better…

Q1) This question was a convoluted way of asking ‘what is the minimum number of neighbour swaps to sort a list containing 2 unique (but potentially repeated) elements’.  It was phrased a bit to confuse, but that is what it boiled down to.

I implemented this by hand writing a bubble sort and counting every swap, which was simple and for the input size, easily going to perform in time.  A more optimal solution (which takes advantage of there only being 2 entry types)  is to step through each entry, keeping a counter of how many of the type of element you want to be first you have seen so far.  Each time you encounter an element of that type, increase your result field by the difference between the current position and the number of elements of that type already seen.  This computes the result in O(N) rather than O(N^2). Oddly enough I swear I’ve seen this question somewhere else recently…

Q2) This one was a bit more tricky.  The question was, given a short (up to 10) list of UDLR direction commands, and a number of times to repeat them, and assuming every move is unit size, how many unique locations will you end up visiting?  The trick being the number of times to repeat them was up to 100 million…

The solution to this comes from realising that after the first few repetitions of the direction commands the number of new unique spots per repetition will always be the same.  I didn’t bother proving a minimum number of repetitions before it stabilises, which I suspect may be quite low, I just chose 20 to be on the safe side (current estimate is that 4 repetitions is sufficient for a command list maximum length of 10).  Use a set (dictionary since topcoder still only supports .Net 2.0) to store the locations you have visited, and simulate the the first few replications, storing how many new are added for every attempt. Then simply multiply the last number of new spots by the number of repetitions left, and add that to receive your final total.  I simplified my code by storing my location as a single integer rather than a pair, using 15 bits for one axis and the rest for the other.  Since the number of repetitions simulated is only 20 and the number of steps per reptition is 10, 15bits is overkill, but whatever…

Q3) This of course was the hardest question, and I didn’t get it completed in time. This question was a bit complicated, but it involved up to 50 different ‘lists’ being unioned together and sorted.  The lists themselves could be distinct values (stored in 50 characters, so at most 24 numbers) or a description of an arithmetic or geometric sequence.  The sequences were defined with start number, step/multiplier, number of elements in the sequence.  The program had to take this sorted union and return what element was at a given position in the list (for up to 50 positions).  Where that position was anything up to 1billion.  To simplify things a bit if the value at a position was over 1 billion, you were to return -1, and if the position asked was beyond the end of the sorted union, also return -1.  However to annoyingly complicate things, the input numbers were not gauranteed to fit in 64bit integers, although it was guaranteed that they would all be greater than 0.

Parsing the input was really much of the problem.  The restriction that values over 1billion return as -1 and positions beyond the end of the sorted union return -1 means that because it is sorted, you can ignore every value over 1billion and pretend it is not in the list.  Therefore int.TryParse and a check that the result if valid was less than or equal to 1 billion was sufficient for each field of the input.  Depending on which field what to do with the fact that the value is > 1billion you did have to treat it differently.  For the exact lists you could just throw each excessive element away.  For the sequences if it was the starting value, you could throw the entire sequence away.  If it was the multiplier/increment then you could replace the sequence with an exact list containing just one value.  However if it was a sequence length, you need to treat it as at least 1 billion.

Another side step which can be performed to reduce the problem space a bit is to realise that geometric sequence with a multiplier greater than 1 will all exceed 1 billion in 30 repetitions or less – so you can expand them into exact element lists.  With a multiplier of 1, you can replace them with an arithmetic sequence with step 0.  Therefore the rest of the code only has to handle arithmetic sequences and exact lists.  All of the exact lists can be combined and sorted so all that is left is a single exact list (might be empty) and up to 50 arithmetic sequences.  If you wanted all arithmetic sequences with length less than 30 or so could be treated as exact lists as well, but it doesn’t really help anything.

Finally now that the data is all prepared you have to find the actual values at given indexes.  This cannot be done by generating the first 1 billion entries, for one thing it would exceed the time limit, but for the other it most certainly would exceed the memory limit.  The solution comes from performing a binary search.  A binary search on what? A binary search on the ranges of positions which have a given value.  If the position we are after is in a range, it has the value for that range.  The function we need to implement the binary search is ‘how many numbers are less than n’.  We then binary search on n over the range 0 to 1billion asking the function for n and n+1. If the answer to the first question is greater than our required index, the answer must be smaller than n.  If the answer to the second question is less than or equal to our required index the answer must be greater than n.  Otherwise the answer is n.

Answering how many numbers are less than n for the exact list is trivial, since we sorted it.  You can even use a binary search, since the number of elements may be as high as 1500.  For the arithmetic sequences you can take n+1 subtract the start value, if result is negative return 0 else divide by the step size (using integer division) and add 1. Unless the step size is 0, which we introduced when getting rid of the  geometric sequences, in which case the answer is infinity (aka 1 billion) if n+1 is greater than or equal to the start value.  Whatever answer found has to be capped by the maximum number of entries for the sequence as defined previously. Finally the answer for each sequence and the exact list are summed, being careful not to overflow integer (since you could be adding the number 1 billion 50 times).  For an added performance kick this function can be memotized in case the different position queries end up passing in the same values.  It won’t make a huge difference to performance since the input values can be spaced such that only 5-6 out of up to 30 binary search steps will overlap for each query.

I ran out of time when I was just about to start implementing that final paragraph – but there was plenty of opportunity for off by one errors which I probably would have wasted a good 10 minutes fixing.

So the reschedule turned out to be 24 hours after the original time. So another extremely late night for me…
Results aren’t finalised yet, but I didn’t get round to submitting the 1000pt question which is still to be retested due to some bug in the writer’s solution… so my 139th position shouldn’t change much.
139th is probably not where I want to be, but its a start – I wasted a bunch of time deciding whether to go to bed or work on the 1000pt problem, was probably the difference between me getting a chance to make a submission or not. I had the right idea for the answer, but there was a lot of edge cases to screw up so even a submission might not have gotten me any further.
I’ll write up some analysis tonight I guess.

So this is where I would usually post my post match analysis … (and given the contest only started 50minutes ago, this post is way too soon…)

Topcoder servers have ‘crashed’ multiple times.  I managed to solve the first problem, but not before the system became so unresponsive that I couldn’t submit it…

I did however discover a cool new feature in google as a result.  Since the topcoder website was down I thought I would try a google search to see if someone had posted something which was already indexed… and it appears that google now indexes twitter in real time.  You get a section in the search results which updates dynamically pushing new twitter posts which correspond to your search times.  This is how I discovered that everyone else was also suffering from the crashing issue which was affecting me…

Maybe they will reschedule, otherwise qualifying round 2 is my only chance to qualify – qualifying round 3 is during work hours.

Edit: Well they finally got the servers going, and I managed to submit my answer. Currently pending system tests, but assuming I pass those I am in the 600 who theoretically advance if they don’t declare the entire event invalid…

Edit2: Systests complete, I’m 385th of 474 people who got a > 0 score (out of ~1200 contestants) – still no word on whether the event is being marked invalid.

Edit3: Apparently just before they got the servers running again they posted a broadcast which I didn’t get because I was crashed, which declared the event invalid.  It is going to be rescheduled at some time to be announced in the future – I’ll probably write up an analysis of the problems tomorrow anyway…

Registration is now open for code jam 2010.

Also registration for top coder open 2010 (they are kind of both running at the same time… although there are no conflicts) opened last week.

GCJ however is my favourite of the two this year, it appears the later online rounds (which only have a single start time) will occur at midnight local time, which is a time I can potentially be a serious competitor at, unlike the 2am starts for the TCO.