algorithms

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

commit 0d8be52f906a5538ca81c377621955cf7e57edcb
parent bf939056b88bd7e6403b9ed8b5a731b21a136aa5
Author: Andrew Laack <andrew@laack.co>
Date:   Fri,  6 Nov 2026 22:19:21 -0600

sort

Diffstat:
Acomp/sort/ex1.in | 18++++++++++++++++++
Acomp/sort/main.cpp | 90+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/sort/problem.txt | 116+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/sort/tle-oracle.cpp | 48++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 272 insertions(+), 0 deletions(-)

diff --git a/comp/sort/ex1.in b/comp/sort/ex1.in @@ -0,0 +1,18 @@ +3 +5 3 +abcde +edcba +1 5 +1 4 +3 3 +4 2 +zzde +azbe +1 3 +1 4 +6 3 +uwuwuw +wuwuwu +2 4 +1 3 +1 6 diff --git a/comp/sort/main.cpp b/comp/sort/main.cpp @@ -0,0 +1,90 @@ +#include <vector> +#include <iostream> +#include <unordered_map> + +using namespace std; + +int main() { + + int l, r, n, q, testCases = 0; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + + cin >> n; + cin >> q; + + string a,b = ""; + + cin >> a; + cin >> b; + + // create prefix sum arrays per character + // then use these to solve problems in O(1) time instead of O(r-l) time + + unordered_map<int, vector<int>> sumsA {}; + unordered_map<int, vector<int>> sumsB {}; + for(int ch = 0; ch < 26; ++ch) { + sumsA[ch] = {}; + sumsB[ch] = {}; + } + + for(int i = 0; i < a.size(); ++i) { + for(int ch = 0; ch < 26; ++ch) { + auto& currentCS = sumsA[ch]; + if(i != 0) { + currentCS.push_back(currentCS[currentCS.size() - 1]); + } else { + currentCS.push_back(0); + } + } + auto ch = a[i] - 'a'; + sumsA[ch][sumsA[ch].size() -1] += 1; + } + + for(int i = 0; i < a.size(); ++i) { + for(int ch = 0; ch < 26; ++ch) { + auto& currentCS = sumsB[ch]; + if(i != 0) { + currentCS.push_back(currentCS[currentCS.size() - 1]); + } else { + currentCS.push_back(0); + } + } + auto ch = b[i] - 'a'; + sumsB[ch][sumsB[ch].size() -1] += 1; + } + + for(int qn = 0; qn < q; ++qn) { + cin >> l; + cin >> r; + + l -= 1; + r -= 1; + + int intersection = 0; + + for(int ch = 0; ch < 26; ++ch) { + + int av = 0; + int bv = 0; + + if(l != 0) { + av = sumsA[ch][r] - sumsA[ch][l-1]; + } else { + av = sumsA[ch][r] - 0; + } + + if(l != 0) { + bv = sumsB[ch][r] - sumsB[ch][l-1]; + } else { + bv = sumsB[ch][r] - 0; + } + + intersection += std::min(av,bv); + } + + cout << ((r-l) + 1) - intersection << endl; + } + } +} diff --git a/comp/sort/problem.txt b/comp/sort/problem.txt @@ -0,0 +1,116 @@ +C. Sort +time limit per test +5 seconds +memory limit per test +256 megabytes + +You are given two strings a and b of length n. Then, you are (forced against your will) to answer q queries. + +For each query, you are given a range bounded by l and r. In one operation, you can choose an integer i (l≤i≤r) and set ai=x where x is any character you desire. Output the minimum number of operations you must perform such that sorted(a[l..r])=sorted(b[l..r]). The operations you perform on one query does not affect other queries. + +For an arbitrary string c, sorted(c[l..r]) denotes the substring consisting of characters cl,cl+1,...,cr sorted in lexicographical order. +Input + +The first line contains t (1≤t≤1000) – the number of test cases. + +The first line of each test case contains two integers n and q (1≤n,q≤2⋅105) – the length of both strings and the number of queries. + +The following line contains a of length n. It is guaranteed a only contains lowercase latin letters. + +The following line contains b of length n. It is guaranteed b only contains lowercase latin letters. + +The following q lines contain two integers l and r (1≤l≤r≤n) – the range of the query. + +It is guaranteed the sum of n and q over all test cases does not exceed 2⋅105. +Output + +For each query, output an integer, the minimum number of operations you need to perform in a new line. + +--- + +- strings a and b of length n +- answer q queries +- given a range bounded by l and r +- in one operation you can select one i s.t. l <= i <= r and set a_i = x + - where x is any character you desire +- output min number of ops you must perform such that: + - sorted(a[l...r]) = sorted(b[l...r]) +- operations don't persist across queries + +--- + +examples + + +5 3 +abcde +edcba +1 5 +1 4 +3 3 + +n = 5 +q = 3 + + +a = abcde +b = edcba +both of the strings have length of n + +(latin letters only) + +following q lines (q = 3) + +1 5 +1 4 +3 3 + +l = 1, r = 5 +l = 1, r = 4 +l = 3, r = 3 + +q1 = 1,5 + +a = abcde +b = edcba + +sorted(abcde) = abcde +sorted(edcba) = abcde + +ops = 0 +print(0) + +l = 1, r = 4 + +sorted(abcd) = abcd +sorted(edcb) = bcde + +b->e in first + +we then have: + +sorted(ebcd) = bcde +sorted(edcb) = bcde + +we may also do e->a within b to find: + +sorted(abcd) = abcd +sorted(adcb) = abcd + +idea: + - compute the elements that aren't in both...? + - how do we know which one should get the change in this context they're undistinguished... + - count the numbers of each character per word then: + - for each of the characters in a that aren't in b: + - flip them to a character not in a that is in b + + +l = 3, r = 3 + +sorted(c) = c +sorted(c) = c + +sum intersection = 1 +return sum_intersection - size = 0 + +--- diff --git a/comp/sort/tle-oracle.cpp b/comp/sort/tle-oracle.cpp @@ -0,0 +1,48 @@ +#include <vector> +#include <iostream> + +using namespace std; + +int main() { + + int l, r, n, q, testCases = 0; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cin >> q; + + string a,b = ""; + + cin >> a; + cin >> b; + + for(int qn = 0; qn < q; ++qn) { + cin >> l; + cin >> r; + + vector<int> countA (26,0); + vector<int> countB (26,0); + + for(int i = l-1; i < r; ++i) { + countA[a[i] - 'a'] += 1; + countB[b[i] - 'a'] += 1; + } + + int intersection = 0; + + for(int i = 0; i < countA.size(); ++i) { + int ca = countA[i]; + int cb = countB[i]; + intersection += std::min(ca,cb); + } + + cout << ((r - l) + 1) - intersection << endl; + } + + + } + + + +}