Official

D - Repeated Sequence Editorial by en_translator

We prove that there exists a subarray \((A _ L,A _ {L+1},\dotsc,A _ R)\) of \(A\) that sums to \(S\) if and only if there exists a subarray \((A _ L,A _ {L+1},\dotsc,A _ R)\) of \(A\) that sums to \(s\), which is the remainder when \(S\) is divided by \(X\), where \(\displaystyle\sum _ {i=1} ^ NA _ i=X\).

Proof

\([\Rightarrow]\) it is sufficient to say that if \(S\geq X\), then \(S-X\) exists. If \(S\geq X\), then \(R-L+1\geq N\). (Otherwise, it violates the constraints that \(A _ i\) are positive.) Then, the sum of \((A _ L,A _ {L+1},\dotsc,A _ {R-N})\) equals \(S-X\). \(\square\)

\([\Leftarrow]\) \((A _ l,A _ {l+1},\dotsc,A _ {r+\lfloor S/X\rfloor N})\) sums to \(S\). \(\square\)

Thus, the problem is boiled down to \(0\leq S\lt X\). Especially, if there exists a conforming subarray, then its length is less than \(N\).

Therefore, it is sufficient to solve the following problem.

Is there a contiguous subraray of \((A _ 1,A _ 2,\dotsc,A _ {2N})\) that sums to \(S\)?

Considering the cumulative sums \(\displaystyle S _ i=\sum _ {1\leq j\leq i}A _ j\quad(0\leq i\leq 2N)\), we can even rephrase to:

Does the sequence \((S _ 0,S _ 1,\dotsc,S _ {2N})\) have elements \(S _ i,S _ j\) with \(S _ j-S _ i=S\)?

This can be solved by managing all the integers that appear in the sequence \((S _ 0,S _ 1,\dotsc,S _ {2N})\) with a balanced binary search tree or a hash table, or using the sliding window technique, in a total of \(O(N\log N)\) or \(O(N)\) time.

The following is sample code.

Since we use std::set in this sample code, the time complexity is \(O(N\log N)\).

#include <iostream>
#include <numeric>
#include <set>
#include <vector>

int main() {
    using namespace std;
    unsigned N;
    unsigned long S;
    cin >> N >> S;

    vector<unsigned long> A(N);
    for (auto& a : A)
        cin >> a;

    // Boil down to 0 <= S < X
    const auto sum{reduce(begin(A), end(A))};
    S %= sum;

    // Repeat A twice
    A.reserve(2 * N);
    for (unsigned i{}; i < N; ++i)
        A.emplace_back(A[i]);

    // Find the cumulative sum
    set<unsigned long> prefix_sum{};
    prefix_sum.emplace();
    for (unsigned long p{}; const auto a : A) {
        p += a;
        prefix_sum.insert(p);
    }

    // For each element p of the cumulative sums, check if (p + S) is contianed
    for (const auto p : prefix_sum)
        if (prefix_sum.contains(p + S)) {
            cout << "Yes" << endl;
            return 0;
        }

    cout << "No" << endl;
    return 0;
}

posted:
last update: