algorithms

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

commit e317d9ccf349cb499917e69bd5244c02f5ecfdc6
parent 9a317650c00a7199ee25f0059edec190f9a869ed
Author: Andrew Laack <andrew@laack.co>
Date:   Thu, 12 Nov 2026 09:48:44 -0600

div 4 contest

Diffstat:
Acomp/r1134/a.cpp | 56++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/r1134/aex1.in | 7+++++++
Acomp/r1134/b.cpp | 44++++++++++++++++++++++++++++++++++++++++++++
Acomp/r1134/bex1.in | 11+++++++++++
Acomp/r1134/c.cpp | 83+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/r1134/cex1.in | 11+++++++++++
Acomp/r1134/d.cpp | 119+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/r1134/dex1.in | 11+++++++++++
8 files changed, 342 insertions(+), 0 deletions(-)

diff --git a/comp/r1134/a.cpp b/comp/r1134/a.cpp @@ -0,0 +1,56 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + int testCases, current, a,b,c; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> a; + cin >> b; + cin >> c; + + bool valid = false; + + if(a == b && a == c) { + valid = false; + } + + if(a-1 == b+1 && a-1 == c) { + valid = true; + } + if(a+1 == b-1 && a+1 == c) { + valid = true; + } + if(a+1 == b && a+1 == c-1) { + valid = true; + } + if(a-1 == b && a-1 == c+1) { + valid = true; + } + + if(c+1 == b-1 && a == c+1) { + valid = true; + } + if(c-1 == b+1 && a == c-1) { + valid = true; + } + + + if(valid) { + cout << "YES" << endl; + } else { + cout << "NO" << endl; + } + + + } +} diff --git a/comp/r1134/aex1.in b/comp/r1134/aex1.in @@ -0,0 +1,7 @@ +6 +1 2 3 +2 2 2 +3 4 5 +1 1 4 +8 9 10 +3 5 7 diff --git a/comp/r1134/b.cpp b/comp/r1134/b.cpp @@ -0,0 +1,44 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + int testCases; + string current = ""; + cin >> testCases; + + // red and blue, start red + // color makes it switch so red := (index%2 == 0) + // can switch manually (including before start) + + // find min number of manual switches to write the string + + for(int z = 0; z < testCases; ++z) { + bool red = true; + int nu = 0; + + cin >> nu; + cin >> current; + + int switches = 0; + + for(int i = 0; i < current.size(); ++i) { + if(current[i] == 'B' && red) { + switches += 1; + red = false; + } else if(current[i] == 'R' && !red) { + switches += 1; + red = true; + } + red = !red; + } + cout << switches << endl; + } +} diff --git a/comp/r1134/bex1.in b/comp/r1134/bex1.in @@ -0,0 +1,11 @@ +5 +5 +BRRBR +1 +R +4 +RBRB +3 +BBB +6 +RRBBRB diff --git a/comp/r1134/c.cpp b/comp/r1134/c.cpp @@ -0,0 +1,83 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + int testCases, current, eles; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + // n books with height arr + // put books in any order I want + // visible from the right if strictly taller than all elements on othe right of it + + // find max number of visible books at a given time + // sum left visible + right visible + + // this has be be ~ linear time (possible sorting) + // can we just sort then alternate? + + // 1 2 2 3 3 3 + // 1 2 3 3 3 2 + // sum = 5 + // print any output that's valid + + cin >> eles; + + vector<int> ls {}; + for(int i = 0; i < eles; ++i) { + cin >> current; + ls.push_back(current); + } + + + sort(ls.begin(), ls.end()); + + vector<int> fin (ls.size(), 0); + + int left = 0; + int right = ls.size() - 1; + int visible = 0; + + for(int i = 0; i < ls.size(); ++i) { + if(i % 2 == 0) { + fin[left] = ls[i]; + + if(left != 0) { + if(fin[left] > fin[left-1]) { + visible += 1; + } + } else { + visible += 1; + } + + left += 1; + } else { + fin[right] = ls[i]; + if(right != ls.size() - 1) { + if(fin[right] > fin[right+1]) { + visible += 1; + } + } else { + visible += 1; + } + right -= 1; + } + } + + cout << visible << endl; + for(int i = 0; i < ls.size(); ++i) { + cout << fin[i] << " "; + } + cout << endl; + + + } +} diff --git a/comp/r1134/cex1.in b/comp/r1134/cex1.in @@ -0,0 +1,11 @@ +5 +6 +1 2 2 3 3 3 +1 +5 +3 +7 7 7 +4 +4 1 3 2 +11 +3 1 4 1 5 9 2 6 5 3 5 diff --git a/comp/r1134/d.cpp b/comp/r1134/d.cpp @@ -0,0 +1,119 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + + // s of length n + // operation: + // select a lowercase letter x != 'a' (no looping) + // replace all x in s with the prior letter in alphabet + // find min ops to make s a palindrome + + + // 5 + // 4 + // abca + + // abca + // x = c + // abba + // return 1 + + // idea: start decreasing the largest number in the list + // where the number doesn't match it's palndromic friend on the other side + + // 4 + // abdc + // 0 1 3 2 + // 0 1 2 2 + // 0 1 1 1 + // 0 0 0 0 + // 3 + + + // 7 + // racecar + // all chars match + + // 4 + // cbad + // 2 1 0 1 + // 1 1 0 1 + // 0 0 0 0 + + // 4 + // zaza + + // idea: start decreasing the largest number in the list + // where the number doesn't match it's palndromic friend on the other side + + int testCases, n; + string current; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cin >> current; + vector<int> characters (n,0); + + for(int i = 0; i < current.size(); ++i) { + characters[i] = (current[i]-'a'); + } + + // this algo can't be O(n^2) + + int res = 0; + + // already matched: + // changes don't matter so whatever on them + // not matched yet: + // bring larger down to the other + // we want to target the largest value that differs first + + // perhaps we just sub to get to the other and add an interval change to a list + // we'd then do lookups in there for non-matching to bring them down + + // vector<pair<int,int>> unmatched + + vector<pair<int,int>> unmatched {}; + + // unmatched, first is always smaller + const size_t n = current.size(); + for (int i = 0; i < n / 2; ++i) { + int a = characters[i]; + int b = characters[n - 1 - i]; + if (a != b) { + auto [lo, hi] = minmax(a, b); + unmatched.push_back({lo, hi}); + } + } + + vector<bool> canMoveFree (26,false); + + + for(int i = 0; i < unmatched.size(); ++i) { + int hi = unmatched[i].second; + int lo = unmatched[i].first; + while(hi > lo) { + if(!canMoveFree[hi]) { + canMoveFree[hi] = true; + res += 1; + } + hi -= 1; + } + } + + cout << res << endl; + + + + } +} diff --git a/comp/r1134/dex1.in b/comp/r1134/dex1.in @@ -0,0 +1,11 @@ +5 +4 +abca +4 +abdc +7 +racecar +4 +cbad +4 +zaza