So, as predicted by the odds I am out ;). I did at least score some points, so I came 125th. The question structure didn’t favour me, an easy first question jumping to a hard second question. A fast time on the first question was sufficient to get through, or a couple of challenges and a terrible time. However the first problem was so easy the challenges were hard to come by, and the second problem’s input requirements so obtuse that constructing a failing test case was next to impossible.
My time for the first problem was terrible – I had the problem solved in the first minute, but a plus sign where I wanted a minus sign sent me down a warren of verifying things by hand, and quickly half an hour had vanished. That being said I probably would not have gotten through even if I hadn’t screwed up badly, had to be fast. Although an extra 20minutes and I might have actually had a serious attempt at the second question.
For a while I thought maybe I could do the 3rd question, thinking it was a well known computational geometry problem which I could just grab an algorithm off a textbook for. However the closest related problem in the textbook told me the running time would be too slow.
Q1) Given a set of bank accounts with known values, where 1 dollar gets you one ticket in a lottery draw each week for a fixed amount, what is the expectation value of bank account 0 after n weeks. Limits: n up to 1000, winnings per week up to 1000, up to 50 bank accounts, each with a starting balance of up to 1million.
A1) I implemented this as a DP of probabilities of number of wins in a given number of weeks. Note that the total amount of tickets in a given week stays the same regardless of who wins in the previous weeks, so only bank account 0 and the initial total of the incoming bank accounts is of interest. Once DP is formed, simply multiply each probability in the final week by account balance for that many wins and return.
As it turns out the problem can be solved without the DP. It appears that simply using the expectation value of one week can be used to generate the expectation value of the next week. Reducing O(N^2) down to O(N).
Q2) Given a sequence of numbers formed by multiplying the digits of each of up to 50 consecutive integers, determine the location of the first of those integers, assuming the sequence refers to the earliest such match. Limits: the input numbers will be less than 1 billion, output will be less than 2^63.
A2) After the competition I realised that this problem is not as hard as it looks. I really might have worked this out if I had of made a serious attempt (and had that extra half hour :P). If the input is all 0’s you can return 10,100, 1000 depending on input length quickly. In fact brute forcing for possible answers of 1-1000 takes care of some corner cases. Find the first non-zero number, brute force the last 3 non-zero digits and solve for the rest by trying as many 9s then 8s then 7s down to 2s going from right to left, then check against all other numbers in the input to see if it is right. Return the smallest result. For kicks I wrote this up and it failed test cases – but only because of a mistake in my code, fixed that and it now passes system tests. My first thought was brute force 2 digits (well my real first thoughts were more complicated than that), but input size > 12 allows some control over the 3rd digit. A number followed by 12 0s indicates that the last 3 digits were 9s for instance. You can look at the input set and break it down in to all sorts of combinations, but in the end, simply brute forcing all last 3 digit scenarios is easier…
As an aside I was left wondering what checks the challenge system used, since the input limitations are significant. Other than 0 no two consecutive numbers in the input can be equal. No input number can have a prime factor greater than 7. At least 5 of the inputs must be 0, and after the last consecutive 0 every 10th number must be a 0. Two consecutive non-zero numbers must be increasing and the difference must divide them.
Q3) Given up to 1200 points, where no 3 are co-linear and no 2 are coincident, determine the number of line segment intersections from choosing any 4 points of the points.
A3) Brute force is obviously no good. A look on Wikipedia indicates that even the best algorithm for enumerating all intersections of the complete set of line segments from n points is in the order of the number of intersections, and if the 1200 points form a convex hull the number of intersections is well over N^3 (Close to N^4 even I think).
Therefore we can’t enumerate the actual intersections we have to count them in batches. Specifically the time needed needs to be about O(1) for every line segment. O(log n) would be sufficient.
I had a quick look at one solution, and it considers each point, and sorts the other points by angle relative to that point, then for each of those segments in order, mystically calculates the intersection count really quickly. … going to have to read it again after some sleep.
Edit: Post sleep update.
I had a look at some more solutions. General approach seems to be assume everything crosses. Then for every point, sort the other points around it by angle. If you can get 180 degree separation in the sorting, all the points on the left will not form crosses with the points on the right. So you subtract these scenarios away. However there is over-counting which you have to adjust for. Looks like the over-counting adjustment is probably the hardest bit.