algorithms

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

commit d16bd7b283e5131a75c87cc9b57534b4a4716c98
parent c214f59c572d6b6b00aefa40ef4a887d4e15108f
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 19 Oct 2026 19:17:24 -0500

Trouble sort cf

Diffstat:
Acomp/trouble-sort/.main.cpp.swp | 0
Acomp/trouble-sort/ex1.in | 16++++++++++++++++
Acomp/trouble-sort/main.cpp | 52++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/trouble-sort/problem.txt | 144+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 212 insertions(+), 0 deletions(-)

diff --git a/comp/trouble-sort/.main.cpp.swp b/comp/trouble-sort/.main.cpp.swp Binary files differ. diff --git a/comp/trouble-sort/ex1.in b/comp/trouble-sort/ex1.in @@ -0,0 +1,16 @@ +5 +4 +10 20 20 30 +0 1 0 1 +3 +3 1 2 +0 1 1 +4 +2 2 4 8 +1 1 1 1 +3 +5 15 4 +0 0 0 +4 +20 10 100 50 +1 0 0 1 diff --git a/comp/trouble-sort/main.cpp b/comp/trouble-sort/main.cpp @@ -0,0 +1,52 @@ +#include <iostream> +#include <vector> + +std::string solve(std::vector<int>& nums, std::vector<int>& bools) { + bool hasZero = 0; + bool hasOne = 0; + + for(int i = 0; i < bools.size(); ++i) { + if(bools[i] == 1) { + hasOne = 1; + } else { + hasZero = 1; + } + if(hasZero && hasOne) { + return "Yes"; + } + } + + for(int i = 1; i < nums.size(); ++i) { + if(nums[i] < nums[i-1]) { + return "No"; + } + } + + return "Yes"; +} + +int main() { + int problemCount = 0; + std::cin >> problemCount; + + for(int i = 0; i < problemCount; ++i) { + std::vector<int> nums {}; + std::vector<int> bools {}; + int numberCount = 0; + std::cin >> numberCount; + + for(int y = 0; y < numberCount; ++y) { + int current = 0; + std::cin >> current; + nums.push_back(current); + } + for(int y = 0; y < numberCount; ++y) { + int current = 0; + std::cin >> current; + bools.push_back(current); + } + std::cout << solve(nums,bools) << std::endl; + } + + +} diff --git a/comp/trouble-sort/problem.txt b/comp/trouble-sort/problem.txt @@ -0,0 +1,144 @@ +B. Trouble Sort +time limit per test1 second +memory limit per test256 megabytes +Ashish has n + elements arranged in a line. + +These elements are represented by two integers ai + — the value of the element and bi + — the type of the element (there are only two possible types: 0 + and 1 +). He wants to sort the elements in non-decreasing values of ai +. + +He can perform the following operation any number of times: + +Select any two elements i + and j + such that bi≠bj + and swap them. That is, he can only swap two elements of different types in one move. +Tell him if he can sort the elements in non-decreasing values of ai + after performing any number of operations. + +Input +The first line contains one integer t + (1≤t≤100) + — the number of test cases. The description of the test cases follows. + +The first line of each test case contains one integer n + (1≤n≤500) + — the size of the arrays. + +The second line contains n + integers ai + (1≤ai≤105) + — the value of the i +-th element. + +The third line containts n + integers bi + (bi∈{0,1}) + — the type of the i +-th element. + +Output +For each test case, print "Yes" or "No" (without quotes) depending on whether it is possible to sort elements in non-decreasing order of their value. + +You may print each letter in any case (upper or lower). + +--- + +Thoughts: + +- n elements in a line +- each element is [a_i,b_i] where b \in {0,1} and a_i is an int +- sort ascending a_i +- can only swap elements of different kinds (b_i != b_j) at each step +- return yes / no if he can/can't sort + +--- + +approach: +- sort a, see if a can be arranged like that with swaps + - min swap problem basically + - elements of same value exist though +- what are impossible cases + - since we can do 0->1->0 are there any? +- are we doing exhaustive search? + - seems unlikely even though only 500 elements at most +- could we do something like bubble sort? + - at each step we swap the current with a smaller if possible + - stop once can't do this anymore + - doesn't work for + - 4 3 2 1 + - 0 0 0 1 + - is this just always true if > 1 of each? + - + + +--- + + +Examples: + +10 20 20 30 +0 1 0 1 + +yes, already + + +3 1 2 +0 1 1 + +1 3 2 +1 0 1 + +1 2 3 +1 1 0 + +so in this one we just find the index that wants our position and we swap with it + +2 2 4 8 +1 1 1 1 + +done + +5 15 4 +0 0 0 + +done + +20 10 100 50 +1 0 0 1 + +target: 10 20 50 100 + +10 20 100 50 + 0 1 0 1 + +10 20 50 100 + + +--- + +so in this one we just find the index that wants our position and we swap with it + +this doesn't work because: + +10 20 40 15 +0 1 0 1 + +instead we must: + +- iterate over all elements, ask that question again + +--- + +duh, if there are elements of diff types we can use them to proxy swapping. + + +if count(0) >= 1 and count(1) >= 1: + - yes + +one doesn't have any: + - no swaps, is it good right now?