So this one was at a more reasonable time, so I participated. 281st, not as good as I might like, but good enough to get through.
Q1) Given a scrambled list of two item types with a total count of N, and the ability to at most once for each i in 1 to N switch two elements that far apart, determine the minimum number of swaps to order the list, if it is possible.
A1) So, the answer to this question was so obvious that it takes a while to see. In the case of there only being 2 element types a single pivot sort pass will result in an ordered list. If you consider a pivot sort where you walk from the outside towards the middle, swapping if both are on the wrong side, walking a specific end if it is on the right side – you can see that it will perform a minimal number of swaps and that every swap will be closer than the last.
Hence it is always possible to sort, and the answer is just the count of the number of items not in the right spot to start with/2. Or you can simulate the pivot sort, like I did.
Q2) Given a ‘map’ (1 dimensional array) which shows the position of two critter types, which are either grumpy at time t % K = 0 or at t % C != 0, determine the minimum time to get from the left to the right of the map if you cannot by in a cell at a time when its occupant is grumpy, if it is even possible. Maximum value for K,C and length of array are all 50.
A2) So this is really pretty easy, its a shortest path algorithm, with a small twist. Because the behaviour of a critter depends on time, each cell needs to be replicated in the graph to represent how time plays a part. Obviously replicating once for every time step defeats the whole purpose of a shortest path algorithm… but since behaviours are dependent on mod K and mod C, it is pretty obvious that t mod K and t mod C are the only things that matter for a given cells possible future paths. So each cell is replicated K*C times (or LCM(K,C) if you want to get really fancy, but given the availability of primes near 50, worst case for K*C and LCM(K*C) are pretty close…
So 50*50*50 vertexes in the graph, and 3 edges from each vertex. From there you just use a priority queue based Dijkstra algorithm and presto, successful solution done.
I on the other hand used a non-priority queue – which for a while I had convinced myself should perform much slower in the worst case. Shows how rusty I am! graphs with equal edge distances don’t need a priority queue as a normal queue already walks them in breadth first search order. Using a priority queue would only make things slower by adding the logarithmic insert/remove cost overhead. So yeah, in hindsight my algorithm works pretty well… If .Net had of had a built in priority queue I probably would have used it and only made things marginally worse!
Q3) Define S(x) to be the sum of the digits in x. Define D(x) to be the recursive application of S until the input equals the output. Given a range, determine how many of the contained numbers can be represented as y*D(y). Range constraints: less than 10 billion.
A3) This problem was easy! – unfortunately I only realized as much with 10minutes on the clock, and I just wasn’t fast enough to write it all up. I was 4 lines of code from being complete. (Although said 4 lines require a little bit of thought each…) If I had of rushed rather than taking everything at an easy pace I might have saved those extra 2-3 minutes I needed to finish those 4 lines and perform the final debugging. That would have gotten me in the top 40, which is where I know I am capable of reaching.
D(y) = 9 if y is a multiple of 9 else y mod 9. If you’ve played around with digit sums before you would know this, if not a short exploration should make it fairly obvious. So y*D(y) can be decomposed into 9 linear functions, which sometimes overlap. Includes/Exclusion principle applies, so you can sum, subtract, sum, subtract your way through every possible n choose 9. That is quite a few equations to write out, but everyone of them is pretty simple – if you could be bothered…
However! Every one of the 9 equations is of the form a*9k+b. Note that these equations all have constant ‘mod 9’ values and they aren’t all the same. Hence many pairs don’t have any overlap and so the inclusion/exclusion can be simplified significantly. It decomposes into 3 pairs and 1 triple. This means you only need 9 base equations, 5 pair equations, and 1 triple equation. I was half way through the pair equations when time ran out. Interestingly I found one of the pair equations cancels with one of the base equations, and apparently there are more cancellations because looking at once of the successful answers, they only needed 9 equations and 7 of those were base equations. (So technically I was 2 lines of code away from being finished :P, 1 add and 1 delete…)