Subsequences Summing to Sevens — Solution

Ref

Original problem: https://usaco.org/index.php?page=viewproblem2&cpid=595

Problem Explanation

The problem statement is straightforward: given an array of positive integers of a certain length, find the longest subsequence (contiguous) whose sum is a multiple of 7.

This problem requires quite a few fundamental techniques. Although it's classified as easy, the patterns you learn here can be reused in many other places.

First, notice that this is a subsequence-sum problem, which naturally suggests using prefix sums. After building the prefix sum array in a single O(n) pass, computing the sum of any subsequence range takes only O(1):

S(i, j) = P[j] - P[i - 1]

So we first preprocess the input directly into a prefix sum array — we no longer need to care about the original array at all.

The problem then transforms into finding all pairs of j and i such that:

P[j] - P[i - 1] mod 7 == 0

Recall the concept of congruence that we covered before (and that you've also learned in discrete math):

// equivalent to
P[j] = P[i - 1] (mod 7)

From this we can deduce: to find such a pair of j and i, we only need to look for two positions whose remainders modulo 7 are the same.

To solve this, we could use the brute-force approach — scanning forward from every position — which is O(n^2) and basically a non-starter.

So we apply another hashing trick: we do just a single scan. For each position, compute its remainder modulo 7 and look up that remainder in a hash map.

If the remainder exists, we've found a matching pair — compute the sequence length j - i + 1 and compare it against the current best.

If the remainder doesn't exist, store the remainder and the index as a key-value pair in the hash map.

There's also a greedy idea at play here: since we know longer sequences are always better, when we hit the same remainder again, there's no need to update the stored position — because as long as the remainders match, the older, smaller position remains valid, and it naturally yields a greater length.

Implementation Details

For any summation problem involving prefix sums, whenever you store a sum, just use long long without thinking twice — otherwise overflow will wreck you.

In the C++ implementation, you could use the try_emplace + pair-binding technique that's very common in real-world work, but since it's only supported from C++17 onward, it's rarely seen in competitive programming.

Original C++ Implementation

Accepted (AC)

#include <algorithm>
#include <climits>
#include <fstream>
#include <unordered_map>
#include <vector>
int main() {
  std::ifstream fin("div7.in");
  std::ofstream fout("div7.out");

  int N;
  fin >> N;

  std::vector<long long> psum(N + 1, 0);
  for (int i = 0; i < N; ++i) {
    int n;
    fin >> n;

    psum[i + 1] = psum[i] + n;
  }

  std::unordered_map<long long, long long> map;

  // * (S[j] - S[i]) mod 7 == 0
  // * -> S[j] mod 7 == S[i] mod 7
  long long ans = LLONG_MIN;
  for (int i = 0; i <= N; ++i) {
    auto it = map.find(psum[i] % 7);
    if (it != map.end()) {
      long long len = i - it->second;
      ans = std::max(ans, len);
    } else {
      // * Greedy update the index
      map[psum[i] % 7] = i;
    }
  }

  fout << ans << "\n";
  return 0;
}