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.\u00a0 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.\u00a0 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…)\u00a0 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.\u00a0 Another look at problem 2 and I was convinced that it was a simple dynamic programming problem.\u00a0 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.\u00a0 I have no clue why…\u00a0 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.<\/p>\n
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.\u00a0 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…<\/p>\n
So on to my analysis…<\/p>\n
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.\u00a0 Then determine for each of blue or red whether there exists k or more in a row either horizontally, vertically or diagonally.<\/p>\n
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.\u00a0 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.\u00a0 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.<\/p>\n
Once the board is set, you have to determine who has ‘won’.\u00a0 A simple walk of every square, and foreach walk in each of the 8 directions will determine this, or even only 4 directions.\u00a0 This gives O(N^3).\u00a0 I used DisjointSetTracker from TMD.Algo to create disjoint set collections for each of the 4 types of win.\u00a0 For each square I unioned it with its win type neighbour set if they were the same colour – O(N^2).\u00a0 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.<\/p>\n
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.<\/p>\n
A2) The small problem constraints had a maximum of 3 inputs, something you could brute force.\u00a0 However with up to 100 numbers, the large problem (which is the only one I actually attempted) required some other solution.\u00a0 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.\u00a0 And that is where I made my mistake.\u00a0 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.\u00a0 With that correction we can proceed.\u00a0 Cost for 1 element is 0, otherwise it is the minimum of satisfying scenarios with 1 less element.\u00a0 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.<\/p>\n
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.\u00a0 Apparently there is a way to calculate the table entries in average O(1) time each, but it is beyond my skill level.\u00a0 On the other hand it actually starts with making the same mistake I did, but fixing it using some serious smarts.<\/p>\n
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.\u00a0 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).<\/p>\n
A3) The small input constrained the 2 ranges to being at most 30 wide, meaning only 900 games needing solving for each problem.\u00a0 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.\u00a0 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.\u00a0 I then used GCD as an accelerator to reduce the number of subproblems to solve and Memoitzation.\u00a0 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.\u00a0 What I had failed to see was that there was a much better minimum condition for obvious win than A%B=0.\u00a0 A >= 2B is a win.\u00a0 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.\u00a0 This is much more powerful and certainly puts the small solution easily within reach.<\/p>\n
So what about the large problem set, where the ranges for A and B in inputs both can be up to 1 million wide?\u00a0 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.\u00a0 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).\u00a0 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.\u00a0 And we can keep recursing like this, chipping away at either side of the interesting range until it disappears.\u00a0 That is okay and you can perform that recursion in log time – which while not constant time, is plenty good enough.\u00a0 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.\u00a0 Why does that make the problem a failure?\u00a0 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.<\/p>\n
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.\u00a0 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…<\/p>\n
R1B is tonight – I’ll do a write up for it tomorrow.<\/p>\n","protected":false},"excerpt":{"rendered":"
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.\u00a0 I started with the first problem, it was nice and simple (Especially considering I wrote AppleHunt…), I then went … Continue reading GCJ10 R1A<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-146","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=146"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/146\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}