Subsequences Summing to Sevens

Solución

Explicación

Podemos calcular el arreglo de sumas de prefijos de nuestros IDs para computar rápidamente si un rango de vacas tiene IDs que suman un múltiplo de $7$ .

Dado un arreglo de sumas de prefijos $p$ , la suma sobre el rango $[l, r]$ es $p[r] - p[l-1]$ . También debemos asegurarnos de que esta suma sea un múltiplo de $7$ para que sea un grupo válido. Estas dos condiciones nos dan lo siguiente:

(p[r] - p[l - 1]) \equiv 0 \pmod{7} \Longleftrightarrow p[r] \equiv p[l - 1] \pmod{7}

Así, podemos simplificar la solución a hallar la mayor diferencia entre dos índices donde sus sumas de prefijos son equivalentes módulo $7$ .

Además, como la suma de prefijos en $i$ está definida por

p[i]\%7 = \left(a[i]+p[i-1]\right)\%7,

podemos hallar el prefijo módulo $7$ al precomputar para evitar números grandes.

Para hallar el grupo consecutivo más grande, intentamos hallar la mayor distancia entre dos prefijos iguales. Podemos tener una lista que guarda la primera ocurrencia de cada resto. Cada vez que volvemos a ver un resto, calculamos la distancia entre el índice actual y la primera ocurrencia del resto.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
const int MOD = 7;
 
int main() {
	freopen("div7.in", "r", stdin);
	freopen("div7.out", "w", stdout);
	int cow_num;
	cin >> cow_num;
 
	int longest_photo = 0;
	// first[i] guarda el índice de la primera vez que una suma de prefijos % 7 == i
	vector<int> first(MOD, -1);
	first[0] = 0;
 
	int curr_remainder = 0;
	for (int i = 1; i <= cow_num; i++) {
		int cow;
		cin >> cow;
 
		curr_remainder = (curr_remainder + cow) % MOD;
		if (first[curr_remainder] == -1) {
			first[curr_remainder] = i;
		} else {
			longest_photo = max(longest_photo, i - first[curr_remainder]);
		}
	}
	cout << longest_photo << endl;
}


import java.io.*;
import java.util.*;
 
public final class Div7 {
	private static final int MOD = 7;
	public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();
		BufferedReader read = new BufferedReader(new FileReader("div7.in"));
		int cowNum = Integer.parseInt(read.readLine());
 
		int maxLen = 0;
		// first[i] guarda el índice de la primera vez que una suma de prefijos % 7 == i
		int[] first = new int[MOD];
		Arrays.fill(first, -1);
		first[0] = 0;
 
		int runningMod = 0;
		for (int c = 1; c <= cowNum; c++) {
			int cow = Integer.parseInt(read.readLine());
			runningMod = (runningMod + cow) % MOD;
			if (first[runningMod] == -1) {
				first[runningMod] = c;
			} else {
				maxLen = Math.max(maxLen, c - first[runningMod]);
			}
		}
 
		PrintWriter written = new PrintWriter("div7.out");
		written.println(maxLen);
		written.close();
	}
}


MOD = 7
 
with open("div7.in") as read:
	cows = [int(read.readline()) for _ in range(int(read.readline()))]
 
best_photo = 0
# first_occ[i] guarda el índice de la primera vez que una suma de prefijos % 7 == i
first_occ = [-1 for _ in range(MOD)]
first_occ[0] = 0
 
running_mod = 0
for v, c in enumerate(cows):
	running_mod = (running_mod + c) % MOD
 
	if first_occ[running_mod] == -1:
		first_occ[running_mod] = v + 1
	else:
		best_photo = max(best_photo, v + 1 - first_occ[running_mod])
 
print(best_photo)
print(best_photo, file=open("div7.out", "w"))

Solución en video

Por Project Starcoder

Video de YouTube (wXNhLjiuTgw)

Código de la solución en video

C++


#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main() {
	ifstream cin("div7.in");
	ofstream cout("div7.out");
 
	ll N;
	cin >> N;
 
	vector<ll> cows(N);
	vector<ll> prefix(N + 1);
 
	for (int i = 0; i < N; i++) {
		cin >> cows[i];
		prefix[i + 1] = (prefix[i] + cows[i]) % 7;
	}
 
	vector<int> lastFound(7);
	for (int i = 0; i < 7; i++) { lastFound[i] = -1; }
	int maximum = 0;
 
	for (int i = 0; i < prefix.size(); i++) {
		if (lastFound[prefix[i]] == -1) {
			lastFound[prefix[i]] = i;
		} else {
			maximum = max(i - lastFound[prefix[i]], maximum);
		}
	}
 
	cout << maximum;
}