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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
For each subarray of size (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
restaurants in the subarray, greedily add more in the rightmost empty locations until there are exactly
restaurants.
Time Complexity:
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 time as the subarray shifts to the right. Perform the same greedy algorithm as described above.
Time Complexity:
Comments