Editorial for An Animal Contest 3 P4 - Monkey Mayhem
Submitting an official solution before solving the problem yourself is a bannable offence.
Note that any collision between any pair of monkeys is going to be at a single, distinct cell at only one possible moment in time. If the monkey on the leftmost column is at row (call this monkey ) and the monkey on the topmost column is at row (call this monkey ), the point of collision will be at cell .
If monkey leaves at time , monkey will need to leave at time . If we represent monkey 's departure time as then we get the equation . Swap and and we get . Now these values and can easily be calculated through iteration over the departure times for monkeys on the topmost row and leftmost column.
We can then observe that over all distinct values of , we add to our answer the minimum between the number of occurrences of and the number of occurrences of such that . This is because each must be paired with an to achieve a collision, extras will not collide with any other monkey.
Implementation can be done using a map to count occurrences, resulting in a log factor. There is also another solution involving sorting.
Big thanks tofor suggesting this problem.