Editorial for SAC '22 Code Challenge 4 P4 - Obligatory Subarray Problem

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

Subtask 1

It suffices to iterate over all subarrays while maintaining the minimum and maximum value.

For each subarray, check if the difference between the minimum and maximum value is in [B, T].

Time Complexity: \mathcal{O}(N^2)

Subtask 2

Define a function long long count(int thres) that will count the number of subarrays with a difference less than or equal to thres.

Realize that the answer is count(T) - count(B - 1) through PIE since the answer should include all answers with a difference less than or equal to T, but then the answer should exclude all subarrays with a difference less than or equal to B-1.

One way to implement count is by using a monotonic queue where the left pointer is maintained while the right pointer is incremented. Then, a counter variable is incremented by all the potential lower bound indices with PIE at each index.

Time Complexity: \mathcal{O}(N)

Note that there are many solutions to this problem.

The bounds for N are theoretically high for any \mathcal{O}(N \log N) solution, but all of these solutions should pass.

They were set this high to prevent a heavily constant optimized \mathcal{O}(N^2) from passing.

Additionally, the author believes that distinguishing between a log factor (e.g., monotonic queue vs. sparse table) is unfair to competitors.


There are no comments at the moment.