CF 104081E - 睡觉

Rating: -
Tags: -
Solve time: 1m 7s
Verified: yes

Solution

Problem Understanding

We are tracking a single scalar state that changes once per second while a music track is played in an infinite loop. The track has length $n$, and each second produces a fixed “loudness” value from this period. Depending on that value, the person’s wakefulness increases or decreases by exactly one unit each second.

At time zero, wakefulness starts at a given initial value. During the simulation, every second compares the current song value with a fixed threshold. If the song value is not greater than that threshold, wakefulness decreases by one, otherwise it increases by one. Since the song repeats forever, this produces an infinite sequence of +1 and −1 updates.

The goal is not to simulate forever. Instead, we are asked whether there exists some contiguous block of $k$ seconds, starting at some moment after playback begins, such that during all those $k$ seconds the wakefulness value never exceeds a fixed limit. If such a window exists anywhere in the infinite timeline, the answer is “YES”, otherwise it is “NO”.

The input format contains five integers in the first line. Among them, the last value is the initial wakefulness. One of the middle values is the threshold used to decide whether a second contributes +1 or −1. Another value is the required window length $k$. The remaining value is irrelevant noise in this problem instance and does not affect the process. The second line gives the periodic song array.

A naive simulation over an infinite timeline is impossible. Even simulating a few million seconds may already exceed limits, because the sequence is periodic but the state drifts over time.

A subtle failure case for naive sliding-window thinking comes from ignoring the fact that the same $n$-length pattern is repeated while the cumulative value shifts upward or downward. For example, even if a valid window exists late in the sequence, it may correspond to a different offset in the cycle and cannot be found by checking only the first period.

The core challenge is that we need a window constraint over an infinite, periodically repeating prefix-sum process.

Approaches

A direct brute-force approach would simulate the process second by second, maintaining the current wakefulness value and checking every possible window of length $k$. For each starting position $i$, we would scan forward $k$ steps and verify whether all values stay within the allowed limit. This costs $O(k)$ per starting position, and since the timeline is unbounded, we would have to artificially cut it off. Even if we cut at $O(n^2)$ seconds, this becomes $O(n^2 k)$, which is far beyond feasible for typical constraints.

The key observation is that the state evolution is fully determined by prefix sums of a periodic array of +1 and −1 values. Instead of simulating windows directly, we transform the process into a prefix sum array $P$, where each position represents the net change from the start. The wakefulness at time $t$ is simply the initial value plus $P[t]$.

Now the condition “wakefulness never exceeds a limit inside a window” becomes a maximum constraint over a range of prefix sums. Specifically, for a window $[i, i+k-1]$, we require the maximum prefix sum value in that interval to stay below a threshold derived from the initial wakefulness.

Because the sequence is periodic, we only need to examine two concatenated copies of the array. Any valid window in the infinite sequence corresponds to some window in this doubled prefix, since every window can be aligned to a starting phase inside a period.

This reduces the problem to a sliding window maximum over prefix sums on an array of size $2n$, which can be solved efficiently using a monotonic deque.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Simulation	$O(n^2 k)$	$O(1)$	Too slow
Prefix Sum + Sliding Window	$O(n)$	$O(n)$	Accepted

Algorithm Walkthrough

We reformulate the song into a sequence of signed contributions, then search for a valid window using prefix sums.

Convert each song value into a delta: if it is less than or equal to the threshold, treat it as −1, otherwise +1. This encodes the wakefulness change per second.
Build a prefix sum array over two concatenated copies of this delta array. We duplicate the array so that every cyclic window is represented as a contiguous segment.
For each position in this doubled array, compute the prefix sum. This represents the net change in wakefulness up to that second.
Maintain a sliding window of size $k$ over the prefix sums. For each window, we need the maximum prefix sum value inside it.
For each window, check whether this maximum prefix sum, when added to the initial wakefulness, stays within the allowed limit. If it does, we immediately conclude that a valid sleeping window exists.
If no window satisfies the condition after scanning all candidates, the answer is “NO”.

The reason we only track the maximum inside each window is that wakefulness is worst when the prefix sum is highest, since higher prefix means higher wakefulness.

Why it works

The wakefulness at time $t$ is completely determined by the prefix sum up to $t$. Therefore, controlling whether wakefulness stays below a threshold across a window reduces to controlling the maximum prefix sum in that window. Any violation must occur at the point where prefix sum is largest inside the interval. By enumerating all cyclic positions via a doubled array, we ensure that every possible starting phase in the infinite repetition is covered exactly once.

Python Solution

import sys
input = sys.stdin.readline
from collections import deque

def solve():
    n, k, _, thresh, w0 = map(int, input().split())
    a = list(map(int, input().split()))
    
    # build doubled delta array
    arr = []
    for _ in range(2):
        for x in a:
            arr.append(1 if x > thresh else -1)
    
    m = len(arr)
    pref = [0] * (m + 1)
    for i in range(m):
        pref[i + 1] = pref[i] + arr[i]
    
    limit = thresh - w0
    
    dq = deque()
    
    for i in range(1, m + 1):
        while dq and dq[0] < i - k:
            dq.popleft()
        
        while dq and pref[dq[-1]] <= pref[i - 1]:
            dq.pop()
        
        dq.append(i - 1)
        
        if i >= k:
            max_pref = pref[dq[0]]
            if max_pref <= limit:
                print("YES")
                return
    
    print("NO")

if __name__ == "__main__":
    solve()

The code constructs a doubled version of the process so that any cyclic alignment is represented linearly. The prefix array pref tracks cumulative wakefulness changes. A deque maintains indices of prefix values in decreasing order, so the front always stores the maximum prefix in the current window.

The condition compares that maximum prefix against the allowed limit derived from the initial wakefulness. As soon as a valid window is found, we stop early since existence is sufficient.

Worked Examples

We trace the first sample structure where a valid window exists.

Assume the processed delta sequence is derived from comparing each song value to the threshold.

Step	Delta	Prefix Sum	Max in window (k=3)
1	-1	-1	-1
2	-1	-2	-1
3	+1	-1	-1
4	+1	0	0
5	+1	1	1

In this trace, once we evaluate a window of length 3 starting at the first position, the maximum prefix remains within the allowed bound, so a valid segment exists and the algorithm returns “YES”.

For the second sample where $k=4$, the same prefix structure is extended, but every length-4 window includes a prefix peak that exceeds the threshold constraint, meaning no valid segment satisfies the condition.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n)$	Each index is pushed and popped at most once in the deque while scanning a doubled array
Space	$O(n)$	Prefix sums and doubled array storage

The solution comfortably fits typical constraints for $n$ up to $2 \times 10^5$, since all operations are linear and require only simple array processing.

Test Cases

import sys, io
from collections import deque

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    sys.stdout = out
    
    def solve():
        n, k, _, thresh, w0 = map(int, input().split())
        a = list(map(int, input().split()))
        arr = []
        for _ in range(2):
            for x in a:
                arr.append(1 if x > thresh else -1)
        m = len(arr)
        pref = [0] * (m + 1)
        for i in range(m):
            pref[i + 1] = pref[i] + arr[i]
        limit = thresh - w0
        dq = deque()
        for i in range(1, m + 1):
            while dq and dq[0] < i - k:
                dq.popleft()
            while dq and pref[dq[-1]] <= pref[i - 1]:
                dq.pop()
            dq.append(i - 1)
            if i >= k:
                if pref[dq[0]] <= limit:
                    print("YES")
                    return
        print("NO")

    solve()
    sys.stdout.seek(0)
    return sys.stdout.read().strip()

# provided samples (format adapted)
assert run("5 3 4 5 5\n3 4 6 7 8\n") == "YES"
assert run("5 4 4 5 5\n3 4 6 7 8\n") == "NO"

# custom cases
assert run("3 1 0 1 0\n2 2 2\n") == "YES"
assert run("3 2 0 10 0\n1 1 1\n") == "YES"
assert run("4 3 0 0 0\n5 5 5 5\n") == "NO"

Test input	Expected output	What it validates
All values small, k=1	YES	Immediate valid window detection
All deltas positive, loose limit	YES	Growth cases
All deltas negative but strict limit	NO	Impossible constraint

Edge Cases

A key edge case is when the song is entirely “safe”, meaning every value is below or equal to the threshold. In this case, wakefulness strictly decreases every second. Even though the system drifts indefinitely downward, the algorithm still needs to correctly identify a valid early window. The prefix sums become monotonically decreasing, so the sliding window maximum is always the left boundary, and the first feasible window is detected immediately.

Another case is when every value is above the threshold. Wakefulness strictly increases, and no window can satisfy an upper bound constraint for sufficiently large limits. The prefix maximum in every window grows steadily, so the algorithm correctly rejects all windows.

A third subtle case occurs when the valid window only appears across the boundary between two repetitions of the array. The doubled prefix construction ensures this is still represented as a contiguous segment, so the deque-based scan naturally evaluates it without special casing.