In the Prefix Sum tutorial, we presented a solution for Mansion that used precomputation to solve the problem in \(O(N)\) time. Here, we will present a different solution that also runs in \(O(N)\) time.
This solution has roughly the same structure: we will consider each interval one at a time, and store the maximum interval sum that we find. We begin by summing up the first interval (that goes from index 0 to index \(K-1\)), and this takes \(O(K)\) time. Then, we want to find the sum of the second interval (that goes from index 1 to index \(K\)). Notice that these intervals are very similar: the only differences occur at index 0 and index \(K\). In particular, we want to subtract the value at index 0, because this is no longer included in the range, and add the value at index \(K\). Doing this gives us the sum of the second interval, but only takes \(O(1)\) time!
This technique is often called sliding window or two pointers.
The video below shows this solution being applied to the sample input.
Overall, this solution has a time complexity of \(O(K+N) = O(N)\), which is the same time complexity as the prefix sum solution. Both solutions are equally good and will earn all 100 points!
Let's look at Wet Chairs from AIO 2015. Spend a few minutes trying the problem for yourself before reading my solution.
We are trying to minimise the distance between our leftmost and rightmost friend. When seating our friends, only three things matter:
read input
# The variable least_chairs_needed will eventually store the answer
# The maximum possible answer is C, because the problem guarantees us it will always be possible to seat everyone
least_chairs_needed = C
# Try each leftmost chair individually
for leftmost_chair = 1 to C:
num_chairs = 0
num_dry_chairs = 0
# loop over the chairs, starting with our chosen leftmost chair
for i = leftmost_chair to C:
num_chairs += 1
if chair i is dry:
num_dry_chairs += 1
if num_chairs >= N and num_dry_chairs >= N-K:
# We can seat everyone!
if num_chairs < least_chairs_needed:
# Update our answer each time we find a better solution
least_chairs_needed = num_chairs
# this will exit out of the inner-most loop but not the outer loop,
# so that we can try the next option for the leftmost chair
break
output least_chairs_needed
This solution has a worst-case time complexity of \(O(C^2)\), because in the worst case it will spend \(O(C)\) time considering each leftmost chair, and there are \(C\) options for the leftmost chair. This will earn 40 marks (subtask 1 and subtask 2).
Our goal is to solve wet chairs in \(O(C)\) time. Before we do this, let's think carefully about our previous solution.
Notice that as we go through possibilities for the leftmost chair, the corresponding closest rightmost chair can only move rightwards (or stay still). For example if we try chair number 3 as the leftmost chair and find that the closest rightmost chair that can seat everyone is chair 7, then for leftmost chair number 4, the closest rightmost chair that can seat everyone must be chair 7 or larger, it couldn't possibly be chair 6 or earlier (think about why this is the case).
Now, can you use this to solve the problem in a way that is similar (but not necessarily exactly the same) as the way we solved Mansion? Spend some time thinking about this, and only look at my solution if you get stuck!
\(O(C)\) Solution to Wet Chairs
Our approach will be very similar to the previous solution: We will try every possible leftmost chair, and find the earliest possible rightmost chair that allows us to fit everyone. Previously, we calculated the rightmost chair independently for each leftmost chair in \(O(C)\) time. We will use the two pointers technique to improve this.
Before I explain my solution, watch the below video that shows it being applied to an example input with \(C = 10\), \(N = 5\), and \(K = 2\) (\(N-K = 3\)).
We first assume that the leftmost chair is chair 1, and run the same procedure as before that counts the total number of chairs and the total number of dry chairs, stopping once there are enough chairs for everyone. We then assume that the leftmost chair is chair 2. To improve the time complexity, we don't start again from stratch. Instead, we start from the previous rightmost chair:
num_chairs variable, because chair 1 is no longer included.num_dry_chairs variable.What is the time complexity of this solution? It might not seem like it, but it's \(O(C)\). Specifically, notice that our leftmost and rightmost chairs only ever move towards the right. This means that we only consider \(2C\) intervals at most. We do \(O(1)\) work for each interval, so the overall time complexity time complexity is \(O(C)\). This is fast enough to score 100 for this problem.