Editorial for UTS Open '18 P3 - Restaurants


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: PlasmaVortex

Subtask 1:

For each subarray of size T (in order from left to right), count how many restaurants are in that subarray, and find where the empty locations are. If there are less than K restaurants in the subarray, greedily add more in the rightmost empty locations until there are exactly K restaurants.

Time Complexity: \mathcal{O}(NT)

Subtask 2:

Instead of recalculating the number of restaurants and the empty locations in each subarray, you can maintain a deque of the empty locations, as well as the number of restaurants in the sliding window. Both of these can be updated in \mathcal{O}(1) time as the subarray shifts to the right. Perform the same greedy algorithm as described above.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.