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

**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