USACO Silver "Subsequences Summing to Sevens"

Problems and Contests
#1

I’m having trouble understanding USACO “Subsequences Summing to Sevens”'s solution.

Firstly, why is this true?

Note furthermore that if you take the sums of the two prefixes, they have the same remainder when divided by 7.

If I have the array [1, 2, 4], the sums of prefix [1, 2] (3) and [1, 2, 4] (7) do not have the same remainder when divided by 7.

I’m also not understanding the rest of the solution in general.

Therefore, for every prefix, we can compute the sum of the numbers in the prefix modulo 7, and keep track of the shortest and longest prefixes that when summed are equivalent to x modulo 7 for 0<x<7. The answer is then the maximum difference between the lengths of the shortest and longest prefixes over all x.

What does “compute sum of the numbers in the prefix modulo 7” mean? And why is the answer the “maximum difference between the lengths of the shortest and longest prefixes”?

#2

This condition holds if and only if the sum of the sublist is divisible by 7.

For example, if you have the array [6,5,1,2,4,3], then [1,2,4] has sum divisible by 7 because the sums of the prefixes [6,5] and [6,5,1,2,4] have the same remainder when divided by 7.

modulo 7 = remainder when divided by 7, see here for info about modular arithmetic.

Say we have the array [1,7,7,7,7,3]. Then the answer is the difference between the lengths of the longest prefix with remainder 1 when divided by 7 ([1,7,7,7,7]) and the shortest ([1]).

5 Likes
#3

How can I apply O(n) instead of O(n^2), i tried this to solve the problem and I got 9/10

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef uint64_t u64;
typedef vector vl;
typedef vector bgraf;
typedef vector vi;
typedef vector graf;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector vpi;
typedef vector wgraf;

#define F first
#define S second
#define PB push_back
#define POPB pop_back
#define MP make_pair
#define boost ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
#define INFL 1000000000000000000
#define INFI 1000000000
#define pqb priority_queue
#define pqs priority_queue<int, vi greater>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define leastbit(x) __builtin_ffs(x)
#define pi atan(1)*4
#define all© ©.begin(), ©.end()
#define rall© ©.rbegin(), ©.rend()
#define sz(x) (int)(x).size()
#define DBG(x) cerr << #x << " = " << x << endl;
#define salto “\n”
#define msz(a) memset(a, 0, sizeof a);

void setIO(string name = “”) {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(name)){
freopen((name+".in").c_str(), “r”, stdin);
freopen((name+".out").c_str(), “w”, stdout);
}
}

void solve(){

int n;

cin >> n;

vl a(n), pref;

ll sum = 0;

pref.PB(sum);

for(int i = 0; i < n; i++){
	cin >> a[i];
	sum += a[i];
	pref.PB(sum);
}

int res = 0;

for(int i = 1; i <= n; i++){
	
	for(int j = 0; j < i; j++){
		
		if((i - j) <= res) break;
		
		if((pref[i] - pref[j]) % 7 == 0){
			res = max(res, i - j);
		}
		
	}
}

cout << res << "\n";

}

int main(){
setIO(“div7”);

int t = 1;

// cin >> t;

while(t--)
	solve();
	
return 0;

}

#4
  1. Please properly format your code. Right now it’s a bunch of scattered code blocks, and that makes it really hard to read.
  2. Comment your code so we know what it’s supposed to actually do.
#5

Right now you are doing a complete search over the prefix sums. However, this is not necessary. We know that the only way to get a multiple of 7 is if both prefix sums have the same remainder \pmod{ 7}. Then, what happens if there are a lot of these prefix sums with the same remainder. If they’re located at indexes a_1,a_2,a_3,... ,a_n, your O(n^2) solution is finding the maximum of all of the differences.

But we don’t need to check a_2-a_1, for example, since we know a_n-a_1 is divisible by 7, and it must be larger. Thus, we only have to find a_1 and a_n, because all the other differences must be smaller. This means that for each remainder from 0 to 6, we can calculate a_1 and a_n, and find the maximum of their difference, which will be an O(n) solution.