algorithms

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

commit 4a298c80aef4c6c89987a1454024d6e6a6830609
parent f58ad5212448b6566bce00c2a2f68df508271bb1
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 28 Oct 2026 20:22:17 -0500

Codeforces dp problem

Diffstat:
Acomp/non-descending-arrays/ex1.in | 10++++++++++
Acomp/non-descending-arrays/main.cpp | 82+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/non-descending-arrays/problem.txt | 89+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 181 insertions(+), 0 deletions(-)

diff --git a/comp/non-descending-arrays/ex1.in b/comp/non-descending-arrays/ex1.in @@ -0,0 +1,10 @@ +3 +3 +2 1 4 +1 3 2 +1 +4 +4 +5 +2 3 3 4 4 +1 1 3 5 6 diff --git a/comp/non-descending-arrays/main.cpp b/comp/non-descending-arrays/main.cpp @@ -0,0 +1,82 @@ +#include <vector> +#include <iostream> +#include <unordered_map> + +// idea: + // try flipping an element + // try not flipping an element + // if current is not non-decreasing and flip is also, return 0 + // propogate this up + // return sum + +long long subsets(std::vector<int>& a, std::vector<int>& b, int idx, std::unordered_map<int,long long>& memo) { + + if(memo.contains(idx)) { + return memo[idx]; + } + + if(idx >= b.size()) { +// for(int i = 0; i < a.size(); ++i) { +// std::cout << a[i] << " "; +// } +// std::cout << std::endl; +// for(int i = 0; i < a.size(); ++i) { +// std::cout << b[i] << " "; +// } +// std::cout << std::endl; + + + memo[idx] = 1; + return 1; // this means we safely went to the end and know of an ordering + } + + bool isFineNoSwap = true; + if(idx != 0) { + isFineNoSwap = a[idx] >= a[idx-1] && b[idx] >= b[idx-1]; + } + + bool isFineSwap = true; + if(idx != 0) { + isFineSwap = a[idx] >= b[idx-1] && b[idx] >= a[idx-1]; + } + + if(!isFineNoSwap && !isFineSwap) { + memo[idx] = 0; + return 0; + } + + long long sm = 0; + + // since this is symmetric, we notice there's either one correct option or both are correct, regardless of if we swapped at the prior step + + if(isFineNoSwap) { + sm += subsets(a,b,idx+1, memo); + } + if(isFineSwap) { + sm += subsets(a,b,idx+1, memo); + } + + + memo[idx] = sm % 998244353; + return sm % 998244353; +} + +int main() { + int current, lsSize, testCaseCount; + std::cin >> testCaseCount; + for(int z = 0; z < testCaseCount; ++z) { + std::cin >> lsSize; + std::vector<int> a {}; + std::vector<int> b {}; + for(int x = 0; x < lsSize; ++x) { + std::cin >> current; + a.push_back(current); + } + for(int x = 0; x < lsSize; ++x) { + std::cin >> current; + b.push_back(current); + } + std::unordered_map<int, long long> mp {}; + std::cout << subsets(a,b,0,mp) << std::endl; + } +} diff --git a/comp/non-descending-arrays/problem.txt b/comp/non-descending-arrays/problem.txt @@ -0,0 +1,89 @@ +C. Non-Descending Arrays +time limit per test2 seconds +memory limit per test256 megabytes +You are given two integer arrays a + and b + both of length n +. + +You can choose any subset of indices and swap the elements at those positions (i. e. make a swap(ai +, bi +) for each i + in the subset). A subset of indices is considered good if, after the swapping, both arrays are sorted in non-descending order. + +Your task is to calculate the number of good subsets. Since the answer can be large, print it modulo 998244353 +. + +Input +The first line contains a single integer t + (1≤t≤500 +) — the number of test cases. + +The first line of each test case contains a single integer n + (1≤n≤100 +). + +The second line contains n + integers a1,a2,…,an + (1≤ai≤1000 +). + +The third line contains n + integers b1,b2,…,bn + (1≤bi≤1000 +). + +Additional constraint on the input: there is at least one good subset. + +--- + +- thoughts + - a, b both length n + - select any subset of indices and swap a_b and b_i + - a subset is good if a and b are sorted non-descendingly + - return number of good subsets mod 998244353 + - big nums + +--- + +since big nums, use long, and we know the algo is efficient + +ex1: + +3 +2 1 4 +1 3 2 + +option1: + +2 3 4 + +1 1 2 + +option2: + +1 1 2 +2 3 4 + +--- + +1 +4 +4 + +we can keep same or swap so 2 + +--- + +5 +2 3 3 4 4 +1 1 3 5 6 + + + +// idea: + // try flipping an element + // try not flipping an element + // if current is not non-decreasing and flip is also, return 0 + // propogate this up + // return sum