algorithms

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

commit aef65fb3246112afc7f8d650a5fb28655e59c1a2
parent aa9836e493b47a23f983d1473d0336d265e34d42
Author: Andrew Laack <andrew@laack.co>
Date:   Thu, 22 Oct 2026 08:52:48 -0500

TLE on largest subsequence problem from cf

Diffstat:
Acomp/largest-subsequence/ex1.in | 13+++++++++++++
Acomp/largest-subsequence/main.cpp | 91+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/largest-subsequence/problem.txt | 116+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 220 insertions(+), 0 deletions(-)

diff --git a/comp/largest-subsequence/ex1.in b/comp/largest-subsequence/ex1.in @@ -0,0 +1,13 @@ +6 +5 +aaabc +3 +acb +3 +bac +4 +zbca +15 +czddeneeeemigec +13 +cdefmopqsvxzz diff --git a/comp/largest-subsequence/main.cpp b/comp/largest-subsequence/main.cpp @@ -0,0 +1,91 @@ +#include <vector> +#include <unordered_set> +#include <iostream> +#include <algorithm> + +void rotateLargest(std::vector<char>& chars) { + + char largest = 'a'; + + std::vector<char> result {}; + std::vector<int> resultIndex {}; + + + for(int i = chars.size()-1; i >= 0; --i) { + if(chars[i] >= largest) { + largest = chars[i]; + result.push_back(largest); + resultIndex.push_back(i); + } + } + + std::reverse(result.begin(), result.end()); + std::reverse(resultIndex.begin(), resultIndex.end()); + + for(int i = 0; i < resultIndex.size(); ++i) { + int nextIdx = resultIndex[(i+1) % resultIndex.size()]; + chars[nextIdx] = result[i]; + } + + return; +} + +bool isSorted(std::vector<char>& st) { + for(int i = 1; i < st.size(); ++i) { + if(st[i] < st[i-1]) { + return false; + } + } + return true; +} + +std::string asString(std::vector<char>& chars) { + std::string result = ""; + for(auto& ch : chars) { + result += ch; + } + return result; +} + +long long solve(std::vector<char>& chars) { + + std::unordered_set<std::string> seen {}; + seen.insert(asString(chars)); + long long rotations = 0; + + while(!isSorted(chars)) { + rotateLargest(chars); + rotations += 1; + + std::string current = asString(chars); + + if(seen.contains(current)) { + rotations = -1; + break; + } + seen.insert(current); + } + + return rotations; +} + +int main() { + int testCases; + std::string current; + + std::cin >> testCases; + for(int i = 0; i < testCases; ++i) { + std::vector<char> chars {}; + + std::cin >> current; + current = ""; + + std::cin >> current; + + for(int x = 0; x < current.size(); ++x) { + chars.push_back(current[x]); + } + + std::cout << solve(chars) << std::endl; + } +} diff --git a/comp/largest-subsequence/problem.txt b/comp/largest-subsequence/problem.txt @@ -0,0 +1,116 @@ +C. Largest Subsequence +time limit per test1 second +memory limit per test256 megabytes +Given is a string s + of length n +. In one operation you can select the lexicographically largest† + subsequence of string s + and cyclic shift it to the right‡ +. + +Your task is to calculate the minimum number of operations it would take for s + to become sorted, or report that it never reaches a sorted state. + +† +A string a + is lexicographically smaller than a string b + if and only if one of the following holds: + +a + is a prefix of b +, but a≠b +; +In the first position where a + and b + differ, the string a + has a letter that appears earlier in the alphabet than the corresponding letter in b +. +‡ +By cyclic shifting the string t1t2…tm + to the right, we get the string tmt1…tm−1 +. + +Input +Each test consists of multiple test cases. The first line contains a single integer t + (1≤t≤104 +) — the number of test cases. The description of the test cases follows. + +The first line of each test case contains a single integer n + (1≤n≤2⋅105 +) — the length of the string s +. + +The second line of each test case contains a single string s + of length n +, consisting of lowercase English letters. + +It is guaranteed that sum of n + over all test cases does not exceed 2⋅105 +. + +--- + +thoughts: + +- string s of length n +- one op: + - select largest subsequence + - lexographically + - cyclic shift one right +- find min number of shifts to sort s + - or state it doesn't ever get sorted + +--- + +aaabc + +(already sorted) += 0 + +--- + +acb + +largest := cb + +abc + += 1 + +--- + +bac + +largest = c + +can't rotate that. + += -1 + +--- + +zbca + +largest = zca + +1. find largest character +2. all subsequent characters are part of the largest subsequence unless there's a character to the right that's larger (suffix max) + - rotate that + - if in same state as seen before, return -1 + - keep going until that's not true ig + +abzc + +abcz + += 2 + + +--- + +czddeneeeemigec + +--- + +cdefmopqsvxzz +