Editorial for An Animal Contest 3 P4 - Monkey Mayhem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ThingExplainer

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 i (call this monkey a) and the monkey on the topmost column is at row j (call this monkey b), the point of collision will be at cell (i, j).

If monkey a leaves at time x, monkey b will need to leave at time x+j-i. If we represent monkey b's departure time as y then we get the equation y = x+j-i \Rightarrow y+i = x+j. Swap i and j and we get y-j = x-i. Now these values y-j and x-i 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 y-j, we add to our answer the minimum between the number of occurrences of y-j and the number of occurrences of x-i such that y-j = x-i. This is because each y-j must be paired with an x-i 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.

Time Complexity: \mathcal{O}((N + M) \cdot \log (N + M))

Additional Notes

Big thanks to 4fecta for suggesting this problem.


Comments

There are no comments at the moment.