Since I got through in round 1A, there was no need for me to get up at 2am and try this round. Apparently 53 other Aussies did though. This time round a fast time on question 1 was not sufficient, you needed to get out a small input from either the second or third questions as well. Third question was probably a good choice there because it was a simple brute force on that input size – but it appears most people just went for question 2.
Q1) Given a matrix of teams, where each team has played at least 2 matches, and there are no draws just win/loss/hasn’t played yet – determine the RPI for every team. RPI is defined as 0.25*WP + 0.5*OWP + 0.25*OOWP. WP is the percentage of games a team has won. OWP is defined as the average of the WP for each opponent of the team, where that WP has been calculated excluding the current team. OOWP is defined as the average of each opponents OWP, defined as above.
A1) Pretty straight forward question – as the 97% success rate from 4500+ people suggests. Large input there are up to 100 teams, but all but the most brute force of approaches will pass this. To be sure you pass the large input, the approach to take is to not start by trying to calculate the RPI of each team, but instead trying to calculate sub problems and then build the results from that. A memotized recursion approach would work as well, but the problem is a bit simple for that level of code complexity.
The basic sub-problem is ‘what is the WP for team a, optionally excluding team b as an opponent’. This can be represented in a square array, using the diagonal for the WP for the team, since excluding self achieves nothing. This can be calculated in O(N^2) time by using a multiple pass approach. First fill the array with the WP for each team, then deviate each point by removing the a vs b game from the average. (Use fractions rather than real numbers by storing it in 2 arrays.) Given the constraints though, a brute force O(N^3) algorithm is fine…
Next up is the OWP list, filled in O(N^2) trivially using the previous array. Finally we can do the RPI, using the diagonal of the first array, the values in the OWP list, and calculating the OOWP as we go by averaging OWP entries as appropriate. Again filled in O(N^2) so overall algorithm is achievable in O(N^2).
Q2) Given positions of groups of shop carts, and a minimum distance required between each shop cart, and a moving speed of 1m/s, determine the minimum time for them to satisfy these constraints.
A2) Small input wasn’t too bad, at most 100 carts, at most 20 groups, at most a 5 meter separation. Large input however was up to 1million carts, in up to 200 groups, and required separation might be 1000km. Initial positions were all within a 200km range for both. It is worth noting that with 1million carts and a 1000km separation 64bit integers will be required.
For a single group the answer is easy enough, (cart count-1)/2 * min seperation. The problem comes when the groups interact, forcing the centre of the group to move. However it seems fairly obvious to me that that is all that happens, the centre of a group moves and that adds to the min required time for that group. The final distribution of carts from a single group, relative to that group never changes. So we can reduce the problem to groups, just with a varying separation requirement, which is governed by the sum of two neighbours cart counts.
One more point to prove and I think this problem is solved. That is that the centre of two groups will never pass one another while going from start position to final position. This is pretty simple because if the centres pass then at least 2 carts have passed. And no 2 carts should pass because it would take the same time for them to meet and turn around and go to each others former destination instead, which is obviously inefficient.
Right so we have a list of groups with a minimum separation between each neighbour, so we can determine exactly where the centre of each group will be relative to a single number, the far edge. So now we can do a binary satisfiability search on time to work out the minimum time. Starting with a minimum bound which is the time to spread out the largest group without moving its centre, and an upper bound which is derived from the scenario of a single group of 1million carts with a 1000km separation requirement, the binary search then proceeds. Satisfiability is determined by walking each group left to right – the centre of the left most group is moved as far left as the time will allow – from that onwards the time constraint and the border of the group to the left both contribute to where to place the centre of the next group. If the problem is not satisfiable, the position of the group to the left will eventually be so close (or even past the starting position to the right) that there is no way to move the centre of the current group right far enough in time.
Binary search can be performed on floating point numbers, or it can be seen that the answer is always a multiple of 0.5, and so an integer binary search on 2*t will also work.
I think I probably would have solved this in time, whether I would have remembered to use 64bit integers (as I probably would have used the integer binary search approach) is a different question.
Q3) Given an N vertex convex polygon, and M internal non-intersecting walls (which create M+1 internal polygon partitions), determine the maximum number of different colours which can be used to paint each vertex, such that every partition has every colour present for 1 or more of its vertexes. Also output any such colouring to prove it possible.
A3) Obviously the answer is at most N. We can fairly easily go further and say that the answer is at most k where k is the minimum over vertex count for each internal partition. Minimum answer is also obviously 1, or we can go further and say that it is 1 + the minimum of the number of ‘non-shared’ vertexes for each internal partition. For the small input the maximum for N was 8, which made a brute force of every possible colouring perfectly feasible.
Problem can be turned into a graph, but with up to 2000 vertexes, it isn’t obvious to me how this could be implemented with a fast enough running time. Time to look at the answers… (Because I am lazy and don’t want to keep thinking about this problem at this point…)
So, the key here is realizing that each partition joins to another by a single wall, and there is no set of 3 or more partitions which join in a circle, partitions form a tree joined by specific vertex pairs. If you choose a random partition and colour its vertexes, so long as the two vertexes on each partition wall aren’t the same, you aren’t limiting the other connecting partitions in any way, except that if you colour this partition with too many colours, the next partition might not be able to use all of those colours as well. From this you can see that the partition with the least number of vertexes is the critical bottle neck. If you label every one of its vertexes a different colour, any/all connecting partitions will have no problem colouring themselves. So long as you don’t repeat the same colour two vertexes in a row you are fine. Since the minimum number of colours is 3, you can just paint vertexes clockwise around a polygon by going through the colours in order, and if it happens you get 2 of the same colour in a row when you complete your walk, you just switch the last 2 vertexes you coloured.
The other tricky part is generating the partition graph fast enough from the input as given. This actually isn’t too hard, but it certainly is possible screw it up.