Editorial for An Animal Contest 4 P6 - Cozy Cottages
Submitting an official solution before solving the problem yourself is a bannable offence.
First, observe that there are two possibilities for the long term behaviour of the elves:
- All the houses have elf in them and the number of elves in each house stays constant.
- All the houses have exactly or elves and each elf continues cycling around the houses forever.
The first case is eventually reached iff and the second case is reached otherwise. It can be shown that it takes at most iterations to reach one of the cases. If we can calculate the number of elves at each house after hours directly. Otherwise, we will calculate the number of elves at each house after hours. In the first case, this will be the same as after hours. In the second, we will need to rotate the result by to get the number of elves in each house after hours.
Let . We are interested in the number of elves at each house after hours. To calculate this, we will iterate over all houses, , and maintain a data structure that stores for each whether there was an elf arriving at house at time . A simple but inefficient way of implementing such a data structure would be to have a boolean array, , of length where corresponds to an elf arriving at time . We initialize this data structure with values corresponding to house , which can be found relatively easily by iterating through the original array backwards. To update this data structure when moving from house to house , we shift every value in to the right by and replace the first 0s with 1s. The number of elves at the current house at time can be calculated by . This already yields an solution.
We can optimize this by replacing the boolean array with a stack of integers where each value corresponds to the index of a value in our old array. More specifically, if we are currently at house , a value in the stack represents that there will be no elves arriving at house at time . This representation allows us to avoid having to shift every value by when transitioning between houses. To find the number of elves at each house at time , we use the same strategy as we did with the boolean array, except now we binary search on our stack to find the number of time points in which no elf arrived at house . This binary search can be replaced with a pointer that always points to the smallest element smaller than and gets updated at every transition, which removes a log factor from the complexity.
Time Complexity: or