algorithms

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

commit c214f59c572d6b6b00aefa40ef4a887d4e15108f
parent 546133362397332da5bb216d6cd40ab2d3ea275b
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 19 Oct 2026 16:42:05 -0500

Lose it, cf

Diffstat:
Acomp/lose-it/ex1.in | 2++
Acomp/lose-it/ex2.in | 2++
Acomp/lose-it/ex3.in | 2++
Acomp/lose-it/main.cpp | 60++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/lose-it/problem.txt | 74++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 140 insertions(+), 0 deletions(-)

diff --git a/comp/lose-it/ex1.in b/comp/lose-it/ex1.in @@ -0,0 +1,2 @@ +5 +4 8 15 16 23 diff --git a/comp/lose-it/ex2.in b/comp/lose-it/ex2.in @@ -0,0 +1,2 @@ +12 +4 8 4 15 16 8 23 15 16 42 23 42 diff --git a/comp/lose-it/ex3.in b/comp/lose-it/ex3.in @@ -0,0 +1,2 @@ +15 +4 8 4 8 15 16 8 16 23 15 16 4 42 23 42 diff --git a/comp/lose-it/main.cpp b/comp/lose-it/main.cpp @@ -0,0 +1,60 @@ +#include <vector> +#include <unordered_map> +#include <iostream> + +int main() { + + int eleCount; + std::cin >> eleCount; + std::vector<int> eles {}; + + for(int i = 0; i < eleCount; ++i) { + int current; + std::cin >> current; + eles.push_back(current); + } + + std::unordered_map<int,int> subsequences {}; + + std::unordered_map<int,int> nextMapping {}; + + int first = 4; + + nextMapping[first] = 8; + nextMapping[8] = 15; + nextMapping[15] = 16; + nextMapping[16] = 23; + nextMapping[23] = 42; + nextMapping[42] = -1; + + int missed = 0; + + for(int i = 0; i < eleCount; ++i) { + + int current = eles[i]; + + if(first == current) { + subsequences[nextMapping[current]] += 1; + continue; + } + + if(subsequences[current] == 0) { + missed += 1; + continue; + } + + subsequences[current] -= 1; + subsequences[nextMapping[current]] += 1; + } + + int inProgress = 0; + + inProgress += subsequences[8] * 1; + inProgress += subsequences[15] * 2; + inProgress += subsequences[16] * 3; + inProgress += subsequences[23] * 4; + inProgress += subsequences[42] * 5; + + std::cout << missed + inProgress << std::endl; + +} diff --git a/comp/lose-it/problem.txt b/comp/lose-it/problem.txt @@ -0,0 +1,74 @@ +- a consists of n integers +- a_i \in 4,8,15,16,23,42 +- remove the minimum number of elements to make good +- good: + - length is divisible by 6 + - can split into k/6 subsequences 4,8,15,16,23,42 +- return number of removals necessary. + +--- + +- how to: + - from left to right: + - mark number of elements not in the correct ordering + - return this number + - issue: + - sometimes we don't finish the sequence + - in such cases, deduct number of elements that have been found that aren't part of a full seq + - nope: + - subsequences can be dis-continuous + - instead of the prior: + - we basically iterate and create a vector for each of the 4 elements we find + - (don't allocate full vector in case there's an adverserial 4,4,4,4,4,.... example) + - as we go, we then try to append a given element to one of the arrays as the next element + - if this isn't possible increment removal counter + - if a vector is filled with the 42nd element, clear it from our list of lists + - return removalCounter + numberOfElementsInVectors +--- + +Examples: + +ex1: +4 8 15 16 23 + +marked = 0 +queue: 4 +queue: 4, 8 +queue: 4, 8, 15 +queue: 4, 8, 15, 16 +queue: 4, 8, 16, 16, 23 + +return marked + len(queue) + +-> 5 + +--- + +ex2: +4 8 4 15 16 8 23 15 16 42 23 42 + +target = 4,8,15,16,23,42 + +[4] + +[4,8] + +[4,8] +[4] + +[4,8,15,16,23,42] -> [] +[4,8,15,16,23,42] -> [] + + +--- + +ex3: + +4 8 4 8 15 16 8 16 23 15 16 4 42 23 42 + +bad = 2 +[4,8,15,16,23,42] -> [] +[4,8,15,16,23,42] -> [] +[4] + +return 3