algorithms

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

commit 7a9f283c717a78eafb449424dba25dbfdee0fb39
parent 15d7caf7886b9e3707979569ba89d8120355c9b9
Author: Andrew Laack <andrew@laack.co>
Date:   Sun,  1 Nov 2026 12:37:24 -0600

updated solution, working throuhg book

Diffstat:
Mcomp/r1131/a/main.cpp | 82++++++++++++++++++-------------------------------------------------------------
Acomp/r1131/a/submission-wa.cpp | 112+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/todo.txt | 53+++++++++++++++++++++++++++++++++++++++++++++++++++++
Acp3-book/ch1/pre-read-problems.txt | 29+++++++++++++++++++++++++++++
4 files changed, 212 insertions(+), 64 deletions(-)

diff --git a/comp/r1131/a/main.cpp b/comp/r1131/a/main.cpp @@ -16,6 +16,8 @@ using namespace std; //- can we mutate this such that the numerator simplified to "six" and denominator is cleared? // - return YES / NO +// NOTE: Char order doesn't matter because multiplication is associative. + int main() { int testCases, current, pSize, qSize; @@ -31,81 +33,33 @@ int main() { cin >> qSize; cin >> p; cin >> q; - - unordered_map<char,int> pCounts {}; + + vector<int> pCharCounts (26,0); for(int i = 0; i < pSize; ++i) { - pCounts[p[i]] += 1; + pCharCounts[p[i] - 'a'] += 1; } - unordered_map<char,int> qCounts {}; - bool ctn = false; - for(int i = 0; i < qSize; ++i) { - if(!pCounts.contains(q[i])) { - cout << "NO" << endl; - ctn = true; - break; - } - qCounts[q[i]] += 1; + pCharCounts[q[i] - 'a'] -= 1; } - if(ctn) { - continue; + int sum = 0; + for(int i = 0; i < 26; ++i) { + sum += pCharCounts[i]; } - - - bool fs = false; - bool fi = false; - bool fx = false; - bool bad = false; - - for(auto& ele : pCounts) { - - if(ele.second > qCounts[ele.first]) { - int delta = ele.second - qCounts[ele.first]; - - if(delta >= 2) { - bad = true; - break; - } - - if(ele.first == 's') { - if(fs) { - bad = true; - break; - } - fs = true; - } - else if(ele.first == 'i') { - if(fi) { - bad = true; - break; - } - fi = true; - } - else if(ele.first == 'x') { - if(fx) { - bad = true; - break; - } - fx = true; - } - else { - bad = true; - break; - } - } + + if(sum != 3) { + cout << "NO" << endl; + } + else if(pCharCounts['s' - 'a'] == 1 && pCharCounts['i' - 'a'] == 1 && pCharCounts['x' - 'a'] == 1) { + cout << "YES" << endl; } - if(fs && fi && fx) { - if(!bad) { - cout << "YES" << endl; - } else { - cout << "NO" << endl; - } - } else { + else { cout << "NO" << endl; } + + } } diff --git a/comp/r1131/a/submission-wa.cpp b/comp/r1131/a/submission-wa.cpp @@ -0,0 +1,112 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// NOTE: This got a contest WA on held out set. I think this is just excessively complex. + +//- p, q strings +//- p as product of variables written in the numerator of a fraction +//- q as product of variables written in the denominator of a fraction +//- can we mutate this such that the numerator simplified to "six" and denominator is cleared? +// - return YES / NO + +int main() { + + int testCases, current, pSize, qSize; + string p, q = ""; + + cin >> testCases; + + // idea: + // put into hashmap, count numbers, ensure sDelta = 1, iDelta = 1, xDelta = 1, all rest = 0 + + for(int z = 0; z < testCases; ++z) { + cin >> pSize; + cin >> qSize; + cin >> p; + cin >> q; + + unordered_map<char,int> pCounts {}; + + for(int i = 0; i < pSize; ++i) { + pCounts[p[i]] += 1; + } + + unordered_map<char,int> qCounts {}; + bool ctn = false; + + for(int i = 0; i < qSize; ++i) { + if(!pCounts.contains(q[i])) { + cout << "NO" << endl; + ctn = true; + break; + } + qCounts[q[i]] += 1; + } + + if(ctn) { + continue; + } + + + bool fs = false; + bool fi = false; + bool fx = false; + bool bad = false; + + for(auto& ele : pCounts) { + + if(ele.second > qCounts[ele.first]) { + int delta = ele.second - qCounts[ele.first]; + + if(delta >= 2) { + bad = true; + break; + } + + if(ele.first == 's') { + if(fs) { + bad = true; + break; + } + fs = true; + } + else if(ele.first == 'i') { + if(fi) { + bad = true; + break; + } + fi = true; + } + else if(ele.first == 'x') { + if(fx) { + bad = true; + break; + } + fx = true; + } + else { + bad = true; + break; + } + } + } + if(fs && fi && fx) { + if(!bad) { + cout << "YES" << endl; + } else { + cout << "NO" << endl; + } + } else { + cout << "NO" << endl; + } + } + +} diff --git a/comp/todo.txt b/comp/todo.txt @@ -0,0 +1,53 @@ +swap-and-negate: + +E. Swap and Negate +time limit per test 2 seconds +memory limit per test 256 megabytes + +You are given an array a of length n. + +You are allowed to perform the following operation on the array a any number of times (including zero): + + Choose an index i such that 1≤i<n; + Set a_i:=−a_{i+1} and a_{i+1}:=−a_i simultaneously. + +Determine the maximum possible sum of all elements in the array that can be achieved by performing the operations optimally. +Input + +The first line of the input contains a single integer t (1≤t≤10^4) — the number of test cases. The description of each test case follows. + +The first line of each test case contains a single integer n (1≤n≤2⋅10^5) — the length of the array a. + +The second line of each test case contains n integers a1,a2,…,an (−10^9≤ai≤10^9) — the elements of the array a. + +It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5. +Output + +For each test case, print a single integer — the maximum possible sum of the array elements after performing the operations any number of times. +Example +Input +Copy + +4 +1 +-3 +4 +1 -2 -3 4 +5 +-10 1 0 1 -10 +2 +6 -7 + +Output +Copy + +-3 +10 +18 +1 + +Note + +For the first test case, no operation can be performed. Hence, the maximum sum will be equal to −3. + +For the second test case, choosing i=2 makes the array a=[1,3,2,4]. Now, the sum of all the elements is equal to 10. It can be shown that this is the maximum possible. diff --git a/cp3-book/ch1/pre-read-problems.txt b/cp3-book/ch1/pre-read-problems.txt @@ -0,0 +1,29 @@ +2. Given an M × N integer matrix Q (1 ≤ M, N ≤ 30), determine if there exists a +sub-matrix of Q of size A × B (1 ≤ A ≤ M, 1 ≤ B ≤ N) where mean(Q) = 7. +(a) Try all possible sub-matrices and check if the mean of each sub-matrix is 7. +This algorithm runs in O(M 3 × N 3 ). + +this would use 2 for loops to iterate over all possible upper left locations + +we would then have two more for loops, iterating from A -> M and B -> N, taking the mean at each step to check each possible submatrix of correct sizes from the given position. + +(b) Try all possible sub-matrices, but in O(M 2 × N 2 ) with this technique: + +memoize solution for sub-matrices that will be fully enclosed, reusing such computations? uncertain + +(this is a see what you know before starting type question) + +--- + +7. You want to test if the factorial of n, i.e. n! is divisible by an integer m. 1 ≤ n ≤ 10000. +What should you do? +(a) Test if n! % m == 0. +(b) The naı̈ve approach above will not work, use: +(Section 5.5.1). + +better approach: + +if m <= n -> true +else compute prime factorization of n, iff any of the numbers <= n then true else false? + +(this seems wrong in the case of factorial matching, but not totally confident; seems like there's some sort of trick like that)