algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit a7193be38bcbdb7c5aecc00a97217120260bbf9b
parent ba0f42996af843faf912ed82c46a3708092e69e5
Author: Andrew Laack <andrew@laack.co>
Date:   Fri, 16 Oct 2026 13:27:10 -0500

Zero sum prefixes cf problem (div2 1600)

Diffstat:
Acomp/zero-sum-prefix/ex1.in | 11+++++++++++
Acomp/zero-sum-prefix/main.cpp | 108+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/zero-sum-prefix/problem.txt | 99+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 218 insertions(+), 0 deletions(-)

diff --git a/comp/zero-sum-prefix/ex1.in b/comp/zero-sum-prefix/ex1.in @@ -0,0 +1,11 @@ +5 +5 +2 0 1 -1 0 +3 +1000000000 1000000000 0 +4 +0 0 0 0 +8 +3 0 2 -10 10 -30 30 0 +9 +1 0 0 1 -1 0 1 0 -1 diff --git a/comp/zero-sum-prefix/main.cpp b/comp/zero-sum-prefix/main.cpp @@ -0,0 +1,108 @@ +#include <iostream> +#include <unordered_map> +#include <vector> + +long long score(std::vector<long long>& eles) { + long long currentSum = 0; + long long res = 0; + for(int i = 0; i < eles.size(); ++i) { + currentSum += eles[i]; + if(currentSum == 0) { + res += 1; + } + } + return res; +} + +int main() { + int tc = 0; + std::cin >> tc; + for(int i = 0; i < tc; ++i) { + long long len = 0; + std::cin >> len; + std::vector<long long> eles {}; + + for(int x = 0; x < len; ++x) { + int cur = 0; + std::cin >> cur; + eles.push_back(cur); + } + + // compute prefix sum from start -> first zero + // this is always done + + std::vector<long long> workingPrefixes {}; + long long currentSum = 0; + int idx = 0; + int lastKnownZeroIdx = eles.size(); + + while (idx < eles.size() && eles[idx] != 0) { + currentSum += eles[idx]; + workingPrefixes.push_back(currentSum); + idx += 1; + } + + if (idx < eles.size() && eles[idx] == 0) { + lastKnownZeroIdx = idx; + } + + + // if a zero was found, we then go from there to the next zero + // computing prefix sums, find the most common element, and set the + // first zero to the aditive inverse + + + while(idx < eles.size()) { + + if(idx == lastKnownZeroIdx) { + idx += 1; + workingPrefixes.push_back(currentSum); + continue; + } + if(eles[idx] == 0) { + + + std::unordered_map<long long,long long> frequencies {}; + long long mostCommon = 0; + long long count = 0; + for(int m = lastKnownZeroIdx; m < idx; ++m) { + frequencies[workingPrefixes[m]] += 1; + long long freq = frequencies[workingPrefixes[m]]; + if(freq > count) { + count = freq; + mostCommon = workingPrefixes[m]; + } + } + eles[lastKnownZeroIdx] = mostCommon * -1; + + currentSum += eles[lastKnownZeroIdx]; + workingPrefixes.push_back(currentSum); + + lastKnownZeroIdx = idx; + idx += 1; + continue; + } + + currentSum += eles[idx]; + workingPrefixes.push_back(currentSum); + idx += 1; + } + if (lastKnownZeroIdx < (int)eles.size()) { + std::unordered_map<long long, long long> frequencies{}; + long long mostCommon = 0; + long long count = 0; + for (int m = lastKnownZeroIdx; m < (int)eles.size(); ++m) { + frequencies[workingPrefixes[m]] += 1; + long long freq = frequencies[workingPrefixes[m]]; + if (freq > count) { + count = freq; + mostCommon = workingPrefixes[m]; + } + } + eles[lastKnownZeroIdx] = mostCommon * -1; + } + + std::cout << score(eles) << std::endl; + } + +} diff --git a/comp/zero-sum-prefix/problem.txt b/comp/zero-sum-prefix/problem.txt @@ -0,0 +1,99 @@ +C. Zero-Sum Prefixes +time limit per test +1 second +memory limit per test +256 megabytes + +The score of an array v1,v2,…,vn is defined as the number of indices i (1≤i≤n) such that v1+v2+…+vi=0. + +You are given an array a1,a2,…,an of length n. You can perform the following operation multiple times: + + select an index i (1≤i≤n) such that ai=0; + then replace ai by an arbitrary integer. + +What is the maximum possible score of a that can be obtained by performing a sequence of such operations? +Input + +Each test contains multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. + +The first line of each test case contains one integer n (1≤n≤2⋅105) — the length of the array a. + +The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — array a. + +It is guaranteed that the sum of n over all test cases does not exceed 2⋅105. +Output + +For each test case, print the maximum possible score of the array a after performing a sequence of operations. + +--- + +problem: + +- sum := number of indices where all prior values + current == 0 +- operation + - select an index s.t. a[i] == 0 and replace it with any number + - we can do this as many times as we want + - don't have to though +- return max score where we can perform the ops + +--- + +ex1: + +2 0 1 -1 0 + +2 2 3 2 2 + +2 -2 1 -1 0 + +2 0 1 0 0 + +heuristic here was to compute the prefix sums, check sums to the right and +if number of zeroes < most popular other number, substitute the zero with the +inversion of the most popular number. + +ex2: + +1000000000 1000000000 0 + +1000000000 2000000000 2000000000 + +1000000000 1000000000 -2000000000 + +1000000000 2000000000 0 + +The heuristic should be inclusive of the a_i index + +ex3: + +0 0 0 0 + +0 0 0 0 + +4 + +ex4: + +3 0 2 -10 10 -30 30 0 + +3 3 5 -5 5 -25 5 5 + +3 -5 2 -10 10 -30 30 0 + +3 -2 0 -10 0 -30 0 0 + +We only care about the sums between zeroes + +ex5: + +1 0 0 1 -1 0 1 0 -1 + +1 1 1 2 1 1 2 2 1 + +1 -1 0 1 -1 0 1 0 -1 + +1 0 0 1 0 0 1 1 0 + +1 -1 0 1 -1 -1 1 0 -1 + +1 0 0 1 0 -1 0 0 -1