USACO 2016 January Contest Silver Division - Subsequences Summing to Sevens

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be done in several ways, but the most simple method consists in keeping track of rolling sums and find the smallest and biggest position with a prefix sum which has a certain reminder when dividing by \(7\).

In order to do that, we will keep in \(mini[i]\) the position of the smallest prefix sum with remainder \(i\) when divided by \(7\) and then every time we found a sum that has occured previously, we subtract from the current position, the position of that minimum.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
using namespace std;

int main() {
    ifstream cin("div7.in");
    ofstream cout("div7.out");

    int n, k;
    cin >> n >> k;

    vector<long long> v(n+1), mini(7, -1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    mini[0] = 0;
    long long sum = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        sum += v[i];
        if (mini[sum % 7] == -1) {
            mini[sum % 7] = i;
        }
        else {
            ans = max(ans, i - mini[sum%7]);
        }
    }
    cout << ans;
    return 0;
}