algorithms

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

commit 2b132a8cb6f57031563cb5c021ffa29763013bd8
parent 35b3ddc0210eb54074926d261d5e1f2af0006d64
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 10 Nov 2026 15:13:23 -0600

Old div 4

Diffstat:
Acomp/r993/easy-problem/a.cpp | 36++++++++++++++++++++++++++++++++++++
Acomp/r993/easy-problem/a.in | 4++++
Acomp/r993/hard-problem/c.cpp | 35+++++++++++++++++++++++++++++++++++
Acomp/r993/hard-problem/c.in | 6++++++
Acomp/r993/harder-problem/d.cpp | 66++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/r993/harder-problem/d.in | 9+++++++++
Acomp/r993/normal-problem/b.cpp | 32++++++++++++++++++++++++++++++++
Acomp/r993/normal-problem/b.in | 6++++++
Acomp/wip/looking-for-order/ex3.in | 26++++++++++++++++++++++++++
Mcomp/wip/looking-for-order/main.cpp | 18++++++++++++++----
10 files changed, 234 insertions(+), 4 deletions(-)

diff --git a/comp/r993/easy-problem/a.cpp b/comp/r993/easy-problem/a.cpp @@ -0,0 +1,36 @@ +#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, n; + cin >> testCases; + + // a = n - b + // n = a - b + // how many (a,b) + // b = n-a + + // 2 + // ans 1 + + // 4 + // ans 3 + + // 6 + // ans 5 + + // is this just n - 1? + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cout << n - 1 << endl; + } +} diff --git a/comp/r993/easy-problem/a.in b/comp/r993/easy-problem/a.in @@ -0,0 +1,4 @@ +3 +2 +4 +6 diff --git a/comp/r993/hard-problem/c.cpp b/comp/r993/hard-problem/c.cpp @@ -0,0 +1,35 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// 2 rows +// m seats each +// a + b + c monkeys in class +// a only want to sit in row 1 +// b in row 2 +// c don't give a fuck + +int main() { + int testCases, m,a,b,c; + cin >> testCases; + + + for(int z = 0; z < testCases; ++z) { + cin >> m; + cin >> a; + cin >> b; + cin >> c; + + int firstRowSeated = min(m,a); + int secondRowSeated = min(m,b); + int rem = min((m - firstRowSeated) + (m - secondRowSeated), c); + cout << rem + firstRowSeated + secondRowSeated << endl; + } +} diff --git a/comp/r993/hard-problem/c.in b/comp/r993/hard-problem/c.in @@ -0,0 +1,6 @@ +5 +10 5 5 10 +3 6 1 1 +15 14 12 4 +1 1 1 1 +420 6 9 69 diff --git a/comp/r993/harder-problem/d.cpp b/comp/r993/harder-problem/d.cpp @@ -0,0 +1,66 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// ufo has array a of length n +// ufo makes b of length n s.t. + // a_i is a mode of [b_1,b_2,...,b_i] for all 1 <= i <= n + +int main() { + int testCases, ln, current; + + cin >> testCases; + + + for(int z = 0; z < testCases; ++z) { + + cin >> ln; + vector<int> ls {}; + + for(int i = 0; i < ln; ++i) { + cin >> current; + ls.push_back(current); + } + + unordered_set<int> bContains {}; + unordered_set<int> aContains {}; + vector<int> b (ls.size()); + + vector<int> nextMissing {}; + + for(int i = 0; i < ls.size(); ++i) { + aContains.insert(ls[i]); + } + + for(int i = 0; i < ls.size(); ++i) { + if(aContains.contains(i+1)) { + continue; + } + nextMissing.push_back(i+1); + } + + int nx = 0; + + // iff the ls[i] is not in b, then add it. otherwise, add a number <= n that isn't in the array a. + for(int i = 0; i < ls.size(); ++i) { + if(bContains.contains(ls[i])) { + b[i] = nextMissing[nx]; + nx += 1; + } else { + b[i] = ls[i]; + bContains.insert(ls[i]); + } + } + for(int i = 0; i < ls.size(); ++i) { + cout << b[i] << " "; + } + cout << endl; + } +} diff --git a/comp/r993/harder-problem/d.in b/comp/r993/harder-problem/d.in @@ -0,0 +1,9 @@ +4 +2 +1 2 +4 +1 1 1 2 +8 +4 5 5 5 1 1 2 1 +10 +1 1 2 2 1 1 3 3 1 1 diff --git a/comp/r993/normal-problem/b.cpp b/comp/r993/normal-problem/b.cpp @@ -0,0 +1,32 @@ +#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; + cin >> testCases; + + // charset = {p,q,w} + // find inversion + // go from start to end, replacing p's with q's and vice-versa (no change on w's) + + for(int z = 0; z < testCases; ++z) { + string current = ""; + cin >> current; + reverse(current.begin(), current.end()); + for(int i = 0; i < current.size(); ++i) { + if(current[i] == 'q') + current[i] = 'p'; + else if(current[i] == 'p') + current[i] = 'q'; + } + cout << current << endl; + } +} diff --git a/comp/r993/normal-problem/b.in b/comp/r993/normal-problem/b.in @@ -0,0 +1,6 @@ +5 +qwq +ppppp +pppwwwqqq +wqpqwpqwwqp +pqpqpqpq diff --git a/comp/wip/looking-for-order/ex3.in b/comp/wip/looking-for-order/ex3.in @@ -0,0 +1,26 @@ +1 1 +24 +3 4 +0 0 +4 3 +3 4 +0 0 +4 3 +3 4 +0 0 +4 3 +3 4 +0 0 +0 0 +4 3 +3 4 +0 0 +4 3 +3 4 +0 0 +4 3 +3 4 +0 0 +4 3 +3 4 +0 0 diff --git a/comp/wip/looking-for-order/main.cpp b/comp/wip/looking-for-order/main.cpp @@ -26,7 +26,11 @@ int distance(int x1,int y1,int x2,int y2) { return ((x2-x1) * (x2-x1)) + ((y2-y1) * (y2-y1)); } -int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holding, int x, int y, int cx, int cy) { +int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holding, int x, int y, int cx, int cy, vector<int>& memo) { + + if(holding == 0 && memo[current.to_ulong()] != -1) { + return memo[current.to_ulong()]; + } int shortest = INT_MAX; bool found = false; @@ -37,7 +41,7 @@ int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holdin bitset<24> updated = current; updated[i] = 1; int dist = distance(x,y,xVals[i], yVals[i]); - int cv = solve(xVals,yVals,updated, holding+1, xVals[i],yVals[i], cx, cy); + int cv = solve(xVals,yVals,updated, holding+1, xVals[i],yVals[i], cx, cy, memo); shortest = min(cv+dist,shortest); found = true; } @@ -46,7 +50,7 @@ int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holdin if(holding > 0) { int dist = distance(x,y,cx,cy); - int cv = solve(xVals,yVals,current, 0, cx,cy, cx, cy); + int cv = solve(xVals,yVals,current, 0, cx,cy, cx, cy, memo); shortest = min(cv+dist,shortest); found = true; } @@ -55,6 +59,10 @@ int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holdin return 0; // done } + if(holding == 0) { + memo[current.to_ulong()] = shortest; + } + return shortest; } @@ -78,5 +86,7 @@ int main() { bitset<24> current {}; - cout << solve(xVals,yVals,current, 0, hx,hy, hx, hy) << endl; + vector<int> memo(1 << n, -1); + + cout << solve(xVals,yVals,current, 0, hx,hy, hx, hy, memo) << endl; }