Well, looks like I am through… was a very strange round. Apparently several people got through with no successful solutions. Only 174 people had positive scores!
119th – although my code for Q1 seems to succeed by fluke rather than me having correctly solved the problem in my head… Q2 on the other hand I thought my solution was dodgy, but then it looks the same as passing solutions, so I am not yet sure why it failed… (probably a ‘thinko’ which just happened to pass all the provided test cases… …)
3rd problem was evil. I’ll leave the write ups until after I’ve had some sleep…
Edit: Some sleep had… probably not enough… but here we go with the rest.
If I hadn’t of broken Q2 I was looking at a top 40 finish, which is enough to make me think maybe I can make it to round 5 yet….
Q1) Given a number, return the last number less than or equal to that number which is removed while implementing the standard Sieve of Eratosthenes.
A1) So its morning now and I remember some more of my thought processes that happened at 2am, that I had already forgotten by 4am… It was less by fluke that I solved this after all, just insufficient consideration of the ways that I could have screwed up my implementation using over-optimisation…
In uni there was an assignment to implement fast prime listing, and I got a bit competitive micro-optimising Sieve of Eratosthenes to shave precious seconds off of generating all prime numbers less than 2billion. So I had plenty of experience to make solving this problem easy. I pretty quickly wrote down the 2 sentence solution in a comment – find the largest prime p less than or equal to the square root of n, find the largest multiple of that prime less than or equal to n which is co-prime with all primes less than p. First part can be implemented with … the Sieve of Eratosthenes … then the second part can be done by dividing n by the largest prime to get the largest multiple and stepping down through each possible multiple while the multiple is not co-prime with all smaller primes. This is what I implemented and had work.
The reason why I was so confused, was immediately after the contest (which had had a lot of challenges succeed) the test case of n=8 came up in discussion. My sleep-deprived brain couldn’t work out why my solution worked immediately and then upon realising my stupidity at thinking largest prime less than or equal to square root of 8 was 3 (?!?), was worried that there was some case where the second largest prime less than the square root would be involved. Again this was 4am stupidity as obviously the largest prime less than the square root, squared, will be among the last to be removed.
However it is probably worth discussing the case of n=8. This is a special case because the answer is not the product of 2 prime numbers, it is instead a prime number cubed, 8 itself. I suspect that for all n > 8 the answer is the product of 2 prime numbers, and over-optimisation could lead to making this assumption as part of your answer, resulting in 8 being wrongly returned as 6.
Q2) Given a set of starting points, and associated destinations, a travel speed of 1 distance unit per time unit and instantaneous but not simultaneous teleportation of any one person to another, what is the minimum time for all people to arrive at their destinations if there is 1 person at each starting point, at time 0.
A2) I was quite happy with myself for this question. I solved it. Unfortunately my solution in my head didn’t make it into the code correctly and hence I failed. Not really surprising it was 3am and solution in my head was so foggy I could hardly make it out.
First observation is that there is no point teleporting at any time other than t=0. This observation is pretty easy to self-justify, but a formal proof would probably take more than a couple of lines.
Second observation is that no one can teleport to the location the first person to teleport, teleports from. This is trivial stuff, but it leads us to the 3rd observation, after one person teleports the remaining people can teleport however they want, any rearrangement is possible, so long as they don’t want to go where the first person teleported from. I made this observation which is the key to solving the problem, but I failed to fully understand why it was true and that was probably my undoing. The reason this is true is because after the first person teleports there are 2 people in the one location. This 2 people in one location scenario allows for trading, any person can switch locations with one of those 2 people (specifically not the first teleporter since that person is where they want to be). After sufficient swaps, everyone will end up where they want to be.
So now for implementation. There are 2 cases (which is what I failed on, my solution tried to merge both cases together and inadvertently allowed the return of answers which are smaller than possible). Case 1, no one teleports, everyone goes straight to their destination. Determine the latest arrival, this is the benchmark. Case 2, one person teleports first. For each possible first teleporter consider the latest earliest arrival if no one is allowed to travel to their destination from the first teleporters starting location but can travel from any other starting location. This *includes* the first teleporter. That specifically was my mistake – I thought that by allowing the ‘first teleporter’ to not teleport I was covering case 1 at the same time as implementing case 2, but I wasn’t forcing *everyone* to not teleport, so I was ending up with erroneous simulations producing the possibility of wrong answer (although not in the provided sample test cases). If any scenario in case 2 improved upon the benchmark, update it with the best and return it as the result.
Q3) Modulo 1 billion and 9 (large prime), how many unique alphanumeric passwords are there of length N which have at least D digits, U upper case letters and L lower case letters? All of N, D, U and L may be up to 200000.
A3) My best effort at solving this had a running time in 10’s of billions of memory lookups (using an inclusion/exclusion principle approach), so I gave up and looked at how other people solved it.
First get the trivial out of the way… If D+U+L > N return 0.
Then also obvious, generate tables of powers of 10, 26, factorials and inverse factorials mod P. We are going to be doing a lot of choose function calls, so the factorial/inverse factorial cache will be valuable…
Perform a summation over each possible number of digits d = N-U-L down to D.
For each of these the number of passwords is N choose d times 10 to the d times 26 to the (N-d) times the sum of N-d choose u for u=N-d-L down to U.
The problem is the inner summation is too expensive (just like my inclusion/exclusion approach). The trick is to relate one inner summation to the next as d decreases, so we don’t have to recompute it fully for each outer loop. The other part to this trick is to realise the only reason we can do this easily is because the size of the set of lower case letters is the same as the size of the set of upper case letters (which would not have worked for my inclusion/exclusion approach). As d decreases the inner sum gets one extra new term and the size of the choice goes up by one. This can be thought of in terms of Pascal’s triangle, which leads to the result that the new sum is double the old one, plus the immediate outside neighbours of the previous summation. This can be done in O(1) time, allowing for efficient solution.
This pattern, that the sum of a part of a row of Pascal’s triangle can be used to efficiently generate the sum of a similar part of the next row is something I haven’t seen before (or at least not as far as I can remember), looks useful.