Official Analysis (Java)

Solution

Explanation

We can calculate the prefix sum array of our IDs to quickly compute whether or not a range of cows has IDs summing to a multiple of $7$.

Given a prefix sum array $p$, the sum over the range $[l, r]$ is $p[r] - p[l-1]$. We must also make sure this sum is a multiple of $7$ to be a valid group. These two conditions give us the following:

Thus, we can simplify the solution to finding the largest difference between two indices where their prefix sums are equivalent mod $7$.

Additionally, because the prefix sum at $i$ is defined by

we can find the prefix mod $7$ when precomputing to avoid large numbers.

In order to find the largest consecutive group, we try to find the largest distance between two equal prefixes. We can have a list that stores the first occurrence of each remainder. Everytime we see a remainder again, we calculate the distance between the current index and the first occurrence of the remainder.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 7;

int main() {
	freopen("div7.in", "r", stdin);

Copy
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());

Copy
MOD = 7

with open("div7.in") as read:
	cows = [int(read.readline()) for _ in range(int(read.readline()))]

best_photo = 0
# first_occ[i] stores the index of the first time a prefix sum % 7 == i
first_occ = [-1 for _ in range(MOD)]
first_occ[0] = 0

Video Solution

By Project Starcoder

Video Solution Code

Copy
#include <bits/stdc++.h>
using namespace std;

#define ll long long

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

	ll N;