algorithms

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

commit e3d4e9653dcdfda8b60a40a3e624c726deacf2bd
parent aef65fb3246112afc7f8d650a5fb28655e59c1a2
Author: Andrew Laack <andrew@laack.co>
Date:   Sat, 24 Oct 2026 19:54:12 -0500

Two contest problems from cf

Diffstat:
Acomp/sequence-decreasing/ex1.in | 9+++++++++
Acomp/sequence-decreasing/main.cpp | 44++++++++++++++++++++++++++++++++++++++++++++
Acomp/sequence-decreasing/problem.txt | 110+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/subset-selecting/ex1.in | 13+++++++++++++
Acomp/subset-selecting/main.cpp | 45+++++++++++++++++++++++++++++++++++++++++++++
Acomp/subset-selecting/problem.txt | 84+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 305 insertions(+), 0 deletions(-)

diff --git a/comp/sequence-decreasing/ex1.in b/comp/sequence-decreasing/ex1.in @@ -0,0 +1,9 @@ +4 +1 +0 +1 +1 +3 +5 3 4 +5 +2 1 1 0 3 diff --git a/comp/sequence-decreasing/main.cpp b/comp/sequence-decreasing/main.cpp @@ -0,0 +1,44 @@ +#include <iostream> +#include <vector> + +//- can we make zeroes? +// - yes +// - iteratively select smallest element, matched with one other element and decrement +// - specifically, yes is true iff the number of non-zero elements >= lowestValue +// - no +// - under this case, we know the above conditional is not true +// - removing elements won't help us so we return 0 + +int main () { + int testCases, current, sz = 0; + std::cin >> testCases; + + for(int i = 0; i < testCases; ++i) { + std::cin >> sz; + + std::vector<int> nums {}; + + for(int x = 0; x < sz; ++x) { + std::cin >> current; + nums.push_back(current); + } + + int smallest = nums[0]; + int nonZero = 0; + + for(int z = 0; z < nums.size(); ++z) { + if(nums[z] < smallest) { + smallest = nums[z]; + } + if(nums[z] > 0) { + nonZero += 1; + } + } + + if(smallest < nonZero || smallest == 0) { + std::cout << nums.size() << std::endl; + } else { + std::cout << 0 << std::endl; + } + } +} diff --git a/comp/sequence-decreasing/problem.txt b/comp/sequence-decreasing/problem.txt @@ -0,0 +1,110 @@ +B. Sequence Decreasing +time limit per test1 second +memory limit per test256 megabytes + +Gracie Abrams - That's So True +An array b + of non-negative integers is called good if it can be turned into a non-empty array consisting only of zeros by performing the following operation any number of times (possibly zero): + +choose a non-empty subarray∗ + of b + in which all elements are positive; +decrease each element of this subarray by 1 +; +choose one element of this subarray and remove it from b +, without changing the order of the remaining elements. +You are given an array a + of n + non-negative integers. Find the maximum length of a good subsequence† + of a +, or report that a + has no good subsequence. + +∗ +An array c + is a subarray of an array b + if c + can be obtained from b + by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. + +† +A sequence c + is a subsequence of a sequence a + if c + can be obtained from a + by the deletion of several (possibly, zero or all) elements from arbitrary positions. + +Input +Each test contains multiple test cases. The first line contains the number of test cases t + (1≤t≤104 +). The description of the test cases follows. + +The first line of each test case contains a single 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 + (0≤ai≤109 +) — the elements of the array a +. + +It is guaranteed that the sum of n + over all test cases does not exceed 2⋅105 +. +--- + +- thoughts: + - good if b -> an array of all zeroes + - operation + - choose non-empty subarray in which all elements are positive + - decrease each element by 1 + - remove one of these elements from the subarray + +--- + +1 +0 + +return 1 + +1 +1 + +return 0 + +--- + +3 +5 3 4 + +5,3 -> 2 + +2,4 -> 1 + +1 -> + +0 + +--- + +5 +2 1 1 0 3 + +2 1 1 3 -> 1 0 0 0 + +--- + +- so basically can we get to zeroes? + - how the fuck does that work? + +--- + +- can we make zeroes? + - yes + - iteratively select smallest element, matched with one other element and decrement + - specifically, yes is true iff the number of non-zero elements >= lowestValue + - no + - under this case, we know the above conditional is not true + - removing elements won't help us so we return 0 diff --git a/comp/subset-selecting/ex1.in b/comp/subset-selecting/ex1.in @@ -0,0 +1,13 @@ +6 +3 1 +0 2 1 +4 2 +1 2 3 4 +5 2 +0 1 0 1 0 +5 4 +0 0 1 0 0 +5 1 +4 0 0 0 2 +6 2 +0 0 2 1 0 0 diff --git a/comp/subset-selecting/main.cpp b/comp/subset-selecting/main.cpp @@ -0,0 +1,45 @@ +#include <iostream> +#include <algorithm> +#include <vector> + +int main() { + + int testCount, current, k, numsToLoad; + std::cin >> testCount; + + for(int r = 0; r < testCount; ++r) { + std::cin >> numsToLoad; + std::cin >> k; + std::vector<int> nums {}; + + for(int i = 0; i < numsToLoad; ++i) { + std::cin >> current; + nums.push_back(current); + } + + std::sort(nums.begin(), nums.end()); + + int res = -1; + int i = 0; + + while(true) { + int v = res + 1; + bool found = false; + + while(i < nums.size() && nums[i] <= v) { + if(nums[i] == v) { + found = true; + } + i += 1; + } + + if(!found || i < (v + 1) * k) { + break; + } + + res = v; + } + + std::cout << res + 1 << std::endl; + } +} diff --git a/comp/subset-selecting/problem.txt b/comp/subset-selecting/problem.txt @@ -0,0 +1,84 @@ +A. Subset Selecting +time limit per test1 second +memory limit per test256 megabytes +Olivia Rodrigo - the cure +You are given an array a + of n + integers and a positive integer k +. + +You want to split some of the elements of a + into groups S1,S2,…,Sm + (m≥0 +) such that: + +each group contains at least k + elements; +each element of a + belongs to at most one group (an element may also belong to no group at all). +Find the maximum possible value of mex({max(S1),max(S2),…,max(Sm)}) + over all valid ways to form the groups, where mex(c) + denotes the smallest non-negative integer that does not appear in the collection c +. If m=0 +, the collection is empty and mex({})=0 +. + +Input +Each test contains multiple test cases. The first line contains the number of test cases t + (1≤t≤500 +). The description of the test cases follows. + +The first line of each test case contains two integers n + and k + (1≤k≤n≤100 +) — the length of the array a + and the minimum allowed size of each group. + +The second line of each test case contains n + integers a1,a2,…,an + (0≤ai≤n +) — the elements of the array a +. + +Output +For each test case, output a single integer — the maximum possible value of mex({max(S1),max(S2),…,max(Sm)}) + over all valid ways to form the groups. + +--- + +- a of n int +- postiive k +- S_1, ... S_n + - groups such that + - each group has at least k elements + - each element belongs to at most one group +- find mex(max(S_1) + ... ) + - where mex is the smallest non-zero integer that doesn't appear in the collection c + +--- + +3 1 +0 2 1 + +n = 3 +k = 1 + + + +--- + +4 2 +1 2 3 4 + +5 2 +0 1 0 1 0 + +5 4 +0 0 1 0 0 + +5 1 +4 0 0 0 2 + +6 2 +0 0 2 1 0 0 +