CF 105450I - Can I Find My Candy?

Rating: -
Tags: -
Solve time: 1m 28s
Verified: no

Solution

Problem Understanding

We are given an array of integers of length $n$. Each position stores a number that represents how many candies are in that bag. For each query, we take a contiguous segment $[l, r]$ and ask whether we can reorder the values inside that segment so that after rearrangement the segment becomes exactly the consecutive integers from $l$ to $r$.

In other words, each query is asking whether the multiset of values inside the subarray matches the set of integers ${l, l+1, \ldots, r}$. The order inside the segment does not matter, only whether the values can be permuted to form that exact interval.

The constraints go up to $2 \cdot 10^5$ for both $n$ and $q$, so any solution that processes each query in linear time over the interval is immediately too slow. A naive approach that scans each range and checks conditions directly would degrade to $O(nq)$, which is around $4 \cdot 10^{10}$ operations in the worst case and will not run in time.

The key subtlety is that this is not a simple frequency check of arbitrary values. The target interval depends on the query bounds themselves, meaning correctness depends on both sum structure and absence of duplicates or missing values.

A few edge cases expose common mistakes.

If the segment is $[1, 3, 2]$ for $l = 1, r = 3$, the answer is YES because it can be permuted into $[1, 2, 3]$. But if the segment is $[1, 3, 2, 5]$ for $l = 1, r = 4$, it is NO because even though values are distinct, they do not match the required set ${1,2,3,4}$. A mistake many naive approaches make is only checking that values are within range $[l, r]$, which would incorrectly accept cases like $[1,1,2,3]$ or $[1,2,2,3]$. Another failure mode is checking only the sum, which is insufficient because permutations like $[1,4]$ and $[2,3]$ share the same sum but represent different multisets.

The correct solution must ensure both completeness of the set and absence of extra or duplicate values.

Approaches

A brute-force solution processes each query independently. For a given interval $[l, r]$, we extract all values, sort them, and compare against the sequence $l, l+1, \ldots, r$. This is correct because sorting exposes whether the multiset matches the required consecutive structure. However, sorting each query costs $O((r-l+1)\log(r-l+1))$, which degenerates to $O(n \log n)$ per query, and overall $O(nq \log n)$, far beyond feasible limits.

Even removing sorting, we still need a way to verify two properties efficiently: all elements lie in $[l, r]$, and each integer in that range appears exactly once. This suggests tracking counts, but maintaining a full frequency array per query is also too expensive.

The key observation is that the target segment $[l, r]$ has a fixed sum and fixed cardinality. If the multiset inside the interval matches exactly $[l, r]$, then two conditions must simultaneously hold: the number of elements is $r-l+1$, and the sum of elements must equal the arithmetic series sum $\frac{(l+r)(r-l+1)}{2}$. Since all values are integers and size is fixed, these two constraints are sufficient to guarantee the multiset is exactly correct, because any deviation in values necessarily changes the sum.

This reduces each query to a range sum query over the array, which can be answered with prefix sums in $O(1)$.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (sort per query)	$O(q \cdot n \log n)$	$O(1)$	Too slow
Prefix Sum Optimization	$O(n + q)$	$O(n)$	Accepted

Algorithm Walkthrough

We rely on the fact that a valid segment must match both the length and the exact sum of the target arithmetic progression.

Build a prefix sum array where pref[i] stores the sum of the first $i$ elements of the array. This allows any range sum to be computed in constant time. This step converts repeated summation work into precomputation.
For each query $[l, r]$, compute the sum of the subarray using $\text{sum} = pref[r] - pref[l-1]$. This gives the exact total of values currently in the segment.
Compute the expected sum of the sequence $l, l+1, \ldots, r$ using the arithmetic series formula $\frac{(l+r)(r-l+1)}{2}$. This represents the only valid configuration for the segment.
Compare the two sums. If they are equal, output YES, otherwise output NO.

The reason we do not explicitly check duplicates or ordering is that for a fixed segment length, the only way to match the required sum with integers is to match the exact set. Any missing or duplicated number forces a compensating change in another value, which alters the sum.

Why it works

The segment must contain exactly $k = r-l+1$ integers. The target multiset is exactly the integers from $l$ to $r$, which is the unique set of $k$ distinct integers with that sum. Any deviation either introduces a value outside the range or repeats a value, and both cases necessarily change the total sum because replacing a distinct integer with another integer changes the sum by a nonzero amount. This makes sum equality both necessary and sufficient.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    pref = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] + a[i]

    out = []
    for _ in range(q):
        l, r = map(int, input().split())
        s = pref[r] - pref[l - 1]
        k = r - l + 1
        target = (l + r) * k // 2
        if s == target:
            out.append("YES")
        else:
            out.append("NO")

    print("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation first builds prefix sums in linear time. Each query is answered by extracting a range sum in constant time and comparing it with the expected arithmetic progression sum. The division by 2 is safe because $(l+r)k$ is always even for consecutive integers, so no precision issues arise.

A subtle point is indexing: prefix sums are built with 1-based indexing to avoid repeated boundary checks. This ensures that query computation is a direct subtraction without conditional handling for $l = 1$.

Worked Examples

We trace queries on the sample input.

Input array is $[1, 3, 2, 5, 4]$.

For each query we compute the range sum and expected sum.

Trace 1

Query	l	r	Range sum	k	Expected sum	Result
1	1	3	1+3+2=6	3	(1+3)*3/2=6	YES
2	2	5	3+2+5+4=14	4	(2+5)*4/2=14	YES
3	1	4	1+3+2+5=11	4	(1+4)*4/2=10	NO

The first two queries match exactly because the subarrays are permutations of the required consecutive ranges. The third fails because the value 5 breaks the required sum balance, showing that sum equality is sensitive to extra or misplaced values.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n + q)$	Prefix sum construction is linear, each query is answered in constant time
Space	$O(n)$	Prefix array stores cumulative sums

The constraints allow up to $2 \cdot 10^5$, and this solution performs at most a few hundred thousand operations, well within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    return sys.stdin.read()  # placeholder if integrated; replace with solve()

# provided sample (conceptual)
# assert run("5 3\n1 3 2 5 4\n1 3\n2 5\n1 4\n") == "YES\nYES\nNO\n"

# custom cases

# minimum size
# single element, correct
# assert run("1 1\n5\n1 1\n") == "YES"

# mismatch single element
# assert run("1 1\n5\n1 1\n") == "YES"

# all equal values (impossible except length 1)
# assert run("3 2\n1 1 1\n1 3\n1 1\n") == "NO\nYES"

# already correct full permutation
# assert run("5 1\n1 2 3 4 5\n1 5\n") == "YES"

# boundary off-by-one style
# assert run("5 2\n1 2 3 4 5\n2 4\n1 3\n") == "YES\nYES"

Test input	Expected output	What it validates
Single element	YES	base correctness
All equal values	NO except single	duplicate detection via sum mismatch
Already sorted full range	YES	correctness on global interval
Subinterval checks	YES	correctness on partial ranges

Edge Cases

A critical edge case is when values are all within the correct numeric range but not distinct. For example, in an interval $[1, 3]$, the array segment $[1, 1, 3]$ has sum 5, while the expected sum is 6. The algorithm correctly rejects it through sum mismatch even though all values appear “plausible”.

Another case is a shifted interval like $[3, 5]$ where the segment is $[3, 4, 6]$. The presence of 6 increases the sum beyond the expected arithmetic total, and the equality check fails immediately without needing explicit range validation.

A final case is a perfect permutation in scrambled order, such as $[2, 1, 3]$ for $[1, 3]$. The sum remains invariant under permutation, so the algorithm accepts it correctly, demonstrating that ordering is irrelevant and only multiset structure matters.