Editorial for MALD Contest 1 P3 - Scratch Cat and Infestation

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.

Simulating all days is too slow because there's a maximum of $10^9$ ~10^9~ days.

We can cut down the days to simulate if we skip to the day when there are $K$ ~K~ Yubocats. If there are at least $K$ ~K~ Yubocats, there will be at least one infection a day. The simulation days are now bounded by $N$ ~N~.

Sort the natural infection times in ascending order. The $K^\text{th}$ ~K^\text{th}~ index will be the first day where there are $K$ ~K~ Yubocats. Now you can simulate the remaining days.

While simulating, it is always optimal for Yubocats to manually infect cats naturally infected latest. If one cat is naturally infected tomorrow and another in a million days, it is always optimal to infect the latter cat. Keep in mind that manually infected cats become Yubocats the next day. You can simplify your implementation by using a pending variable to store the number of cats that will become a Yubocat the next day.

Complexity: $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

Comments

There are no comments at the moment.