algorithms

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

commit 6b82bda0d15204fd7682cb63f8f238bd05b7e5e5
parent d3eae706c7d8b5bc97a024b5ec14ae8741b0bd46
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 16 Nov 2026 19:45:14 -0600

Two 1100's and one 1000

Diffstat:
Acomp/and-or-sort/ex1.in | 13+++++++++++++
Acomp/and-or-sort/ex2.in | 0
Acomp/and-or-sort/main.cpp | 144+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/and-or-sort/thoughts.txt | 0
Acomp/illya-and-queries/ex1.in | 6++++++
Acomp/illya-and-queries/ex2.in | 7+++++++
Acomp/illya-and-queries/main.cpp | 95+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/illya-and-queries/thoughts.txt | 0
Acomp/monsters-attack/ex1.in | 16++++++++++++++++
Acomp/monsters-attack/ex2.in | 0
Acomp/monsters-attack/main.cpp | 100+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/monsters-attack/thoughts.txt | 0
12 files changed, 381 insertions(+), 0 deletions(-)

diff --git a/comp/and-or-sort/ex1.in b/comp/and-or-sort/ex1.in @@ -0,0 +1,13 @@ +6 +4 +0011 +4 +1000 +5 +01000 +8 +01001101 +7 +0101010 +7 +0111101 diff --git a/comp/and-or-sort/ex2.in b/comp/and-or-sort/ex2.in diff --git a/comp/and-or-sort/main.cpp b/comp/and-or-sort/main.cpp @@ -0,0 +1,144 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// binary string s of length n +// can do this any number of times (including zero): + // choose an integer 1 <= i <= n and replace s_i with & or | of s_1, s_2, ..., s_i +// find minimum number of operations to sort s in ascending order + +// 4 +// 0011 +// already sorted, 0 + +// 4 +// 1000 +// 1 +// 1001 +// 1011 +// 1111 +// 3 ops + +// idea: for each zero that follows leading ones, they must be flipped one by one. + // is the question just how many zeroes follow the first one? + // not quite. in cases where there's a one after some zeroes, that one can be flipped + // is the answer then min(zeroesAfterFirstOne, onesAfterFirstZero)? + +// stepwise, do we just flip every one until the final sequence of zeroes? + + +// 5 +// 01000 +// 00000 + + +// 8 +// 01001101 +// 00001101 +// 00000101 +// 00000001 +// sum = 3 + + +// 7 +// 0101010 +// 0001010 +// 0000010 +// 0000000 + + +// 7 +// 0111101 +// 0111111 +// steps: 1 + + +// feels like some sort of inequality exists here +// is there something about the number of remaining zeroes and ones? + // like how many ones are there? If there are more ones then zeroes, only flip zeroes as needed? + +// how many more ones are there after the current positions? + // if there are more ones than zeroes, then we skip over the remaining runs of +// should we start from the end instead? + // if we start from the end: + +// the question here is this: + // where do we draw the boundary between ones and zeroes + // this position is the spot where there are more + // can we compute this incrementally? + // like we say what if we drew the line here and then everything on the left must be zeroes and right ones. + // this seems to be on the right track, but we also want to remove all leading zeroes. + // leading ones can't be flipped so if first position is a one then we just count zeroes + +int countZeroes(string& st) { + int res = 0; + for(int i = 0; i < st.size(); ++i) { + if(st[i] == '0') { + res += 1; + } + } + return res; +} + + +int stripLeadingZeroes(string& st) { + int leadingZeroes = 0; + for(int i = 0; i < st.size(); ++i) { + if(st[i] == '1') { + leadingZeroes = i; + break; + } + } + st = st.substr(leadingZeroes); + return leadingZeroes; +} + +int main() { + + int testCases, n; + string st; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + + cin >> n; + cin >> st; + + // we just count zeroes because everything must become one in such cases. + if(st[0] == '1') { + cout << countZeroes(st) << endl; + continue; + } + + int stripped = stripLeadingZeroes(st); + + int trailingZeroes = countZeroes(st); + int leadingOnes = 0; + + int best = trailingZeroes; + + for(int i = 0; i < st.size(); ++i) { + // what would happen if everyting before, and including the current, index had to be zeroes + // and everything after had to be ones? + if(st[i] == '1') { + leadingOnes += 1; + } else { + trailingZeroes -= 1; + } + int currentCost = leadingOnes + trailingZeroes; + if(currentCost < best || best == -1) { + best = currentCost; + } + } + + cout << best << endl; + + } +} diff --git a/comp/and-or-sort/thoughts.txt b/comp/and-or-sort/thoughts.txt diff --git a/comp/illya-and-queries/ex1.in b/comp/illya-and-queries/ex1.in @@ -0,0 +1,6 @@ +...... +4 +3 4 +2 3 +1 6 +2 6 diff --git a/comp/illya-and-queries/ex2.in b/comp/illya-and-queries/ex2.in @@ -0,0 +1,7 @@ +#..### +5 +1 3 +5 6 +1 5 +3 6 +3 4 diff --git a/comp/illya-and-queries/main.cpp b/comp/illya-and-queries/main.cpp @@ -0,0 +1,95 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +// s = s_1, s_2, ..., s_n consisting of only .'s and #'s +// m queries +// query := l_i, r_i + // answer is number of integers l_i <= i <= r_i that s_i = s_{i+1} + +// hmm, can't we just compute a prefix array and then subtract left and right? + +// ...... +// m = 4 +// l_i = 3, r_i = 4 +// l_i = 2, r_i = 3 +// l_i = 1, r_i = 6 +// l_i = 2, r_i = 6 + +// ...... + +// inclusive prefix sum: +// [1,2,3,4,5,5] + +// l_i = 3, r_i = 4 +// l_i = 2, r_i = 3 +// l_i = 1, r_i = 6 +// l_i = 2, r_i = 6 + +// 3,4 +// p_3 = 3 +// p_4 = 4 +// 1 + + +// #..### + +// 011233 + +// 1 3 + +// 1 - 0 = 1 + +// 5 6 + +// 1 + +// 1 5 + +// p_4 - p_1 = 3 - 0 = 2 + +// 3 6 +// 3 4 + +// strict inequality on the right so we are interested in the delta between: + // where the prefix sum is inclusive + // p_{r-1} - p_l + +using namespace std; + +int main() { + + string input; + cin >> input; + + vector<int> prefixSumsInc (input.size()+1, 0); + + for(int i = 0; i < input.size()-1; ++i) { + if(input[i] == input[i+1]) { + if(i > 0) { + prefixSumsInc[i+1] = prefixSumsInc[i] + 1; + } else { + prefixSumsInc[1] = 1; + } + } else { + if(i > 0) { + prefixSumsInc[i+1] = prefixSumsInc[i]; + } + } + } + prefixSumsInc[(input.size()-1) +1] = prefixSumsInc[input.size()-1]; + + int queryCount; + cin >> queryCount; + for(int z = 0; z < queryCount; ++z) { + int l,r; + cin >> l; + cin >> r; + cout << prefixSumsInc[r-1] - prefixSumsInc[l-1] << endl; + } +} diff --git a/comp/illya-and-queries/thoughts.txt b/comp/illya-and-queries/thoughts.txt diff --git a/comp/monsters-attack/ex1.in b/comp/monsters-attack/ex1.in @@ -0,0 +1,16 @@ +5 +3 2 +1 2 3 +-1 2 3 +2 1 +1 1 +-1 1 +4 10 +3 4 2 5 +-3 -2 1 3 +5 3 +2 1 3 2 5 +-3 -2 3 4 5 +2 1 +1 2 +1 2 diff --git a/comp/monsters-attack/ex2.in b/comp/monsters-attack/ex2.in diff --git a/comp/monsters-attack/main.cpp b/comp/monsters-attack/main.cpp @@ -0,0 +1,100 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +// computer game +// current game can be modeled as a straight line +// start at point 0 +// n monsters trying to kill you +// ith monster has a_i health starts at point x_i + +// every second: + // fire up to k bullets at monsters each hits one monster for 1 damage + // 0 or less health monsters die + // alive move one point closer + // if monster reaches you die +// can you survive? + // we will always want to target nearest and if at all possible not waste bullets + // + +// n = 3, k = 2 +// healths = [1 2 3] +// positions = [-1 2 3] + +// since we are at 0 we can normalize by distance + +// healths = [1 2 3] +// distances = [1 2 3] + +// we shoot nearest once, second once +// they move, we shoot second once and third once +// they move, we kill final, return "YES" + +// the issue here is that we can get fucked by large numbers, computationally +// instead we'll want to consider how many shots to kill nearest, take that many steps with a remainder +// and then move all of them. + +using namespace std; + +int main() { + ll testCases, n, k, current; + cin >> testCases; + + for(ll z = 0; z < testCases; ++z) { + cin >> n; + cin >> k; + + vector<ll> health {}; + vector<ll> distance {}; + + vector<pair<ll,ll>> distHealth {}; + + for(ll i = 0; i < n; ++i) { + cin >> current; + health.push_back(current); + } + + for(ll i = 0; i < n; ++i) { + cin >> current; + + if (current < 0) { + distance.push_back(current * -1); + } + else { + distance.push_back(current); + } + } + + for(ll i = 0; i < n; ++i) { + pair<ll,ll> current {distance[i], health[i]}; + distHealth.push_back(current); + } + + sort(distHealth.begin(), distHealth.end()); + bool ck = true; + long long shot = 0; + + for(ll i = 0; i < distHealth.size(); ++i) { + ll targetDistance = distHealth[i].first; + ll targetHealth = distHealth[i].second; + if((k*targetDistance) - shot < targetHealth) { + ck = false; + break; + } else { + shot += targetHealth; + } + } + + + if(!ck) { + cout << "NO" << endl; + } else { + cout << "YES" << endl; + } + } +} diff --git a/comp/monsters-attack/thoughts.txt b/comp/monsters-attack/thoughts.txt