No t-shirts for me this year…
Only 760 out of 850 potential contestants turned up, and I came 443rd, short of the required top 350 which advance to shirt round. I think 7 Aussies qualified for this round, but only 6 registered. Out of those 6, 3 failed to get any points (possibly fell asleep!), 2 of us around the 440th place, and John Dethridge advances 315th place.
I could have made it through to get a t-shirt, but I took too long to realise I had an overflow bug in my count number of powers of k less than or equal to n loop. I really should have implemented it using a divide, but also I should stop using 32bit integers – except where absolutely needed. One day I will learn!
I had time enough to do question 2, but it was not easy and I was very tired. I looked for corner cases for Q1 hoping to get the single challenge I needed to get through, but the given examples covered all of them, so there was basically no one to challenge.
Q1) How many boolean sequences of length n are are plausible, if the ith entry is the answer to whether a number is divisible by i. Return answer mod 1000000007 since input can be up to 1000000.
A1) I was a bit slow in realizing the correct approach here, but it wasn’t too long before I realized the answer was related purely based on the primes less than or equal to n. Specifically each prime doubled the answer at a minimum, more if different powers of that prime were less than n as well. More specifically if the maximum power of a prime p less than or equal to n is p^k then the prime independently contributes (k+1) ways to build the final sequence. So, multiply all these factors mod 1 billion and 7 and you have your answer.
What kept me too slow to advance was it took a long time to realize that my loop for determining max power was potentially squaring numbers just less than 1 million, which doesn’t fit into 32bit integer. I had correctly identified that I needed to use 64bit integers for the result as small powers go more than squared and so mod 1 billion and 7 is not sufficient to keep you under 32bit limit, but I should have used them more liberally from the start.
Q2) Given an square array of strings which are built up by concatenating the smallest of the vertically and horizontally previous cells in front of the largest, where the first row and column are provided (and each have a single character in each cell), return up to 50 characters starting at a specific index of the string in the far bottom right corner (the largest string). Note: no character will be repeated in the first row or column.
A2) Pascals triangle gives the length of each cell – and with a worst case of 30×30 the length of the largest string can be very large!
Having built up pascals triangle, all that is really needed is to know for each cell, which of the two vertically and horizontally previous cells is lexically smallest. As usual, ‘all’ is of course the whole actual problem. I thought I was on the right track for this, but I suspect its performance is too slow, the trick being to define a memotizable recursion which doesn’t require an offset and length for comparison for both cells involved.
Edit: Before I managed to fall asleep I think I solved this. The memotizable recursion is ‘which is smaller for 2 cells on a common diagonal?’. If the 2 cells are neighbours on a diagonal, they are built out of the 3 cells on the previous diagonal. From there it can be seen that the middle cell can be ignored as it is either the common start, the common end or transitive property applies and you can just compare the outside pair. If they are not neighbours, you get 4 cells which are in neighbouring pairs. By using the memotized recursion on each neighbouring pair you can then reapply the recursion on the smallest of each pair. Memotization ensures that the algorithm runs in O(n^3), both in space and time.
Now if you can read between the lines there you’ll notice that I have failed to take in to account an important special case. Once the recursion hits an edge we need to compare that edge value to a cell on the same diagonal. Unless that other cell is on the opposite edge of the diagonal, this doesn’t appear trivial. However the original problem was ‘determine the nth character in the bottom right hand corner’, we can trivially expand that to also ‘determine the first character in every cell’. Since the answer to these new questions depends on the which is smaller question, it might seem we are at an impasse – but because each question is entirely answered by considering the previous diagonal alone, we can invoke mutual memotized recursion safely.
All that remains is to prove that this method works. Something which is obvious is that each cell is only made up of characters which appear on the edge in the same or lesser row, or same or lesser column. Thus since every comparison in the algorithm involves two different cells on the same diagonal, it can be seen that the termination comparison is never equal, as an edge on a diagonal compared to a different cell in the diagonal cannot be equal as the cells on the diagonal cannot be made out of that edges character and all edge characters are distinct.
Q3) Given 2 arrays of positions, and a set of ‘connections’ from one array to another, determine the number of orderings of the two arrays such that no connections cross. (Return mod 1000000007 as with arrays of length 50, the answer might be very large.)
A3) Edit: Also solved this one before going to sleep. I think it is easier than Q2 even.
First step, DFS the connections to form them into groups. If you discover a loop, return 0. Now we have our first factor in the answer, n! where n is the number of groups. Each group is going to be independent, since there is no way they can cross each other without causing a crossed connection so the n! comes from the orderings of the n groups.
Each group now contributes an independent factor. There are 2 scenarios, either every edge in the group joins at a common endpoint, or there are 2 or more locations in the group where 2 or more edges join. If it is a single common endpoint the answer is k! where k is the number of edges in the group. If it is more than two common endpoints we can either arrange said endpoints left to right, or right to left – so that gives a factor of 2. Then for each endpoint we also get a factor of (m-2)! where m is the number of edges which join to that endpoint.
Finally we have additional factors for the array locations which do not participate in a connection. These can be added in any place in any order, so if there are n spots in the array and k of them are endpoints of 1 or more connections, the additional factor is n!/k!. Since there are 2 arrays, this gives 2 more factors total. Multiply everything together using repeated modulo and 64 bit integers… and we should be done.
All in all it makes me wish I was less tired when I did the competition. I think I could have solved that second question during the competition if I had of been able to concentrate at all. Third one, well I’m pretty sure I would have run out of time having only opened it with a few minutes to go.
