commit d3eae706c7d8b5bc97a024b5ec14ae8741b0bd46 parent e4ffd3c573b9d27009003dfb513a5e16200dd43a Author: Andrew Laack <andrew@laack.co> Date: Mon, 16 Nov 2026 12:37:37 -0600 4 1K rated problems on codeforces in c++ Diffstat:
| A | comp/deck-of-cards/acc.cpp | | | 137 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | comp/deck-of-cards/ex1.in | | | 9 | +++++++++ |
| A | comp/deck-of-cards/ex2.in | | | 0 | |
| A | comp/deck-of-cards/main.cpp | | | 73 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | comp/deck-of-cards/thoughts.txt | | | 0 | |
| A | comp/good-prefixes/ex1.in | | | 15 | +++++++++++++++ |
| A | comp/good-prefixes/ex2.in | | | 0 | |
| A | comp/good-prefixes/main.cpp | | | 69 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | comp/good-prefixes/thoughts.txt | | | 0 | |
| A | comp/string-construction/ex1.in | | | 9 | +++++++++ |
| A | comp/string-construction/ex2.in | | | 0 | |
| A | comp/string-construction/main.cpp | | | 100 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | comp/string-construction/thoughts.txt | | | 105 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | comp/swap-and-delete/ex1.in | | | 5 | +++++ |
| A | comp/swap-and-delete/ex2.in | | | 0 | |
| A | comp/swap-and-delete/main.cpp | | | 52 | ++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | comp/swap-and-delete/thoughts.txt | | | 0 |
17 files changed, 574 insertions(+), 0 deletions(-)
diff --git a/comp/deck-of-cards/acc.cpp b/comp/deck-of-cards/acc.cpp @@ -0,0 +1,137 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; +// cards from 1 -> n +// smallest to largest arrangement +// 1 on top, n at bottom +// k actions on the deck + // 0. remove top card + // 1. remove bottom card + // 2. remove either top or bottom card +// determine the fate of each card + // remains in deck + // removed from deck + // can be both + + +// n = 4 k = 2 + +// 01 + +// cards: 1,2,3,4 +// remove top +// remove bottom +// 2,3 +// -,+,+,- + + +// n = 3, k = 2 +// 22 +// 1 2 3 +// ? + ? +// ? ? ? + +// NTS: Worth doing the +-? encoding from the start then considering cases +// case: the second option will result in a card being removed, so if only one option remains, that card will be drawn + // ugghhhh.... if I do 2 for every character they are all removed + // if I do all -1 then we only know one or two of the centermost haven't been removed, depending on the parity of the size + // actually it's not that complicated, if we have all ?'s then they have all been taken + // otherwise, we don't know if they've been taken because there could be alternative selections that just so happen to have not taken our current one + +// n = 1, k = 1 +// 2 +// + +// - + + +// 7 5 +// 01201 + +// +++++++ +// -++++++ +// -+++++- +// -?+++?- +// --?++?- +// --?+?-- + +void printLs(vector<char>& ls) { + for(int i = 0; i < ls.size(); ++i) { + cout << ls[i]; + } + cout << endl; +} + +int main() { + + int testCases, n,k; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cin >> k; + vector<char> ls {}; + for(int i = 0; i < n; ++i) { + ls.push_back('+'); + } + + string instructions = ""; + cin >> instructions; + + int leftPtr = 0; + int rightPtr = ls.size() - 1; + int questionCount = 0; + + for(int i = 0; i < instructions.size(); ++i) { + + char inst = instructions[i]; + bool handleQuestion = false; + bool incCount = false; + + if(inst == '2') { + handleQuestion = true; + incCount = true; + } + if(inst == '0') { + if(ls[leftPtr] == '?') { + handleQuestion = true; + } + ls[leftPtr] = '-'; // todo: shift questions + leftPtr += 1; + } + else if(inst == '1') { + if(ls[rightPtr] == '?') { + handleQuestion = true; + } + ls[rightPtr] = '-'; // todo: shift questions + rightPtr -= 1; + } + + if(handleQuestion) { + if (leftPtr + questionCount + incCount > rightPtr) { + for(int m = 0; m < ls.size(); ++m) { + ls[m] = '-'; + } + break; + } + if(incCount) { + ls[leftPtr + questionCount] = '?'; + ls[rightPtr - questionCount] = '?'; + questionCount += 1; + } else if(inst == '0') { + ls[leftPtr + questionCount - 1] = '?'; + } else { + ls[rightPtr - questionCount + 1] = '?'; + } + } + } + + printLs(ls); + } +} diff --git a/comp/deck-of-cards/ex1.in b/comp/deck-of-cards/ex1.in @@ -0,0 +1,9 @@ +4 +4 2 +01 +3 2 +22 +1 1 +2 +7 5 +01201 diff --git a/comp/deck-of-cards/ex2.in b/comp/deck-of-cards/ex2.in diff --git a/comp/deck-of-cards/main.cpp b/comp/deck-of-cards/main.cpp @@ -0,0 +1,73 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +void printLs(vector<char>& ls) { + for(int i = 0; i < ls.size(); ++i) { + cout << ls[i]; + } + cout << endl; +} + + + +int main() { + + int testCases, n,k; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cin >> k; + vector<char> ls {}; + for(int i = 0; i < n; ++i) { + ls.push_back('+'); + } + + string instructions = ""; + cin >> instructions; + + // this is a second attempt, following the editorial, prior worked correctly, just complicated + int countTopRemove = 0; + int countBottomRemove = 0; + int countUnknown = 0; + for(int i = 0; i < instructions.size(); ++i) { + // i got top and bottom mixed up in my removal logic so I swapped these, but it all works like this. + if(instructions[i] == '0') { + countBottomRemove += 1; + } + else if(instructions[i] == '1') { + countTopRemove += 1; + } else { + countUnknown += 1; + } + } + for(int i = 0; i < countBottomRemove && i < ls.size(); ++i) { + ls[i] = '-'; + } + for(int i = ls.size() - 1; i > ((ls.size() - 1) - countTopRemove) && i >= 0; --i) { + ls[i] = '-'; + } + for(int i = 0; i < countUnknown; ++i) { + ls[i+countBottomRemove] = '?'; + int idx = ((ls.size()-1) - countTopRemove) - i; + if(idx >= 0 && idx < ls.size()) { + ls[((ls.size()-1) - countTopRemove) - i] = '?'; + } + } + if(countUnknown+countTopRemove+countBottomRemove >= ls.size()) { + for(int i = 0; i < ls.size(); ++i) { + ls[i] = '-'; + } + } + + printLs(ls); + } +} diff --git a/comp/deck-of-cards/thoughts.txt b/comp/deck-of-cards/thoughts.txt diff --git a/comp/good-prefixes/ex1.in b/comp/good-prefixes/ex1.in @@ -0,0 +1,15 @@ +7 +1 +0 +1 +1 +4 +1 1 2 0 +5 +0 1 2 1 4 +7 +1 1 0 3 5 2 12 +7 +1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296 +10 +0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592 diff --git a/comp/good-prefixes/ex2.in b/comp/good-prefixes/ex2.in diff --git a/comp/good-prefixes/main.cpp b/comp/good-prefixes/main.cpp @@ -0,0 +1,69 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// good := array such that some element can be represented as the sum of all other elements + // sum of all other elements is 0 if there are no other elements +// a_1,a_2,...,a_n +// count number of good non-empty prefixes of a + +// the question here is this: + // does the largest thus far = the sum of all other numbers + // since sum of others is what matters, doesn't have to be most recent + +// at each step: + // if current > largest + // sum += former largest + // largest = current + // else + // sum += current + // always + // compare sum with largest + + +int main() { + + int testCases, n; + ll current; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + vector<ll> ls {}; + for(int i = 0; i < n; ++i) { + cin >> current; + ls.push_back(current); + } + + // stop at this point bc no individual number can be that big + ll upperBound = 1000000000; + ll largest = -1; + ll sum = 0; + int res = 0; + + for(int i = 0; i < ls.size(); ++i) { + if(ls[i] > largest) { + if(largest != -1) { + sum += largest; + } + largest = ls[i]; + } else { + sum += ls[i]; + } + if(sum == largest) { + res += 1; + } + if(sum > upperBound) { + break; + } + } + cout << res << endl; + } +} diff --git a/comp/good-prefixes/thoughts.txt b/comp/good-prefixes/thoughts.txt diff --git a/comp/string-construction/ex1.in b/comp/string-construction/ex1.in @@ -0,0 +1,9 @@ +8 +5 2 +4 3 +6 1 +5 0 +7 3 +4 2 +3 2 +7 4 diff --git a/comp/string-construction/ex2.in b/comp/string-construction/ex2.in diff --git a/comp/string-construction/main.cpp b/comp/string-construction/main.cpp @@ -0,0 +1,100 @@ +#include <iostream> +#include <cmath> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// start from the beginning, fill with 1's until we reach ceil(k / 2), fill with 0's until we reach k total pairs, alternating on the rest + +bool isValid(string st, int n, int k) { + int numZ = 0; + int numO = 0; + int numPairs = 0; + + for(int i = 0; i < st.size(); ++i) { + if(i > 0) { + if(st[i] == st[i-1]) { + numPairs += 1; + } + } + if(st[i] == '1') { + numO += 1; + } else { + numZ += 1; + } + } + + if(numPairs == k && abs(numZ-numO) <= 1 && st.size() == n) { + return true; + } + return false; + +} + + +// THIS IS BAD: 110101 +// THIS IS BAD: 6 +// THIS IS BAD: 1 +// this case has an issue. + +// we want a prefix of a singular zero before our 1's otherwise we have too many 1's +// 011010 +// can we just try both approaches? +// like just try prefixing with a zero if we fail once? + + +string generate(string bs, int n,int k) { + + // we do +1 here because 11 is two characters but only one pair + int tgOne = (ceil((double)k / (double)2)) + 1; + int tgZero = (floor((double)k / (double)2)) + 1; + + bool lastIsOne = false; + + for(int i = 0; i < tgOne; ++i) { + bs += '1'; + } + for(int i = 0; i < tgZero; ++i) { + bs += '0'; + } + while(bs.size() < n) { + char last = bs[bs.size() - 1]; + if (last == '1') { + bs += '0'; + } else { + bs += '1'; + } + } + return bs; +} + + +int main() { + + int testCases, n, k; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cin >> k; + + string bs = generate("",n,k); + + if(isValid(bs, n, k)) { + cout << bs << endl; + } else { + string bsT = generate("0",n,k); + if(isValid(bsT, n, k)) { + cout << bsT << endl; + } else { + cout << "-1" << endl; + } + } + } +} diff --git a/comp/string-construction/thoughts.txt b/comp/string-construction/thoughts.txt @@ -0,0 +1,105 @@ +- given integers n and k +- construct binary string s of length n such that + - the difference between the number of 0's and 1's is at most 1 + - there are k pairs of adjacent equal characters in s + - k indices such that s_i = s_{i+1} + +--- + +- sum of n over testcases <= 200_000 + +--- + +n = 5, k = 2 + +11001 + +approach: wrote out long string of 1's to make all of the matches then backtracked to satisfy the property that +we may only have k matching adjacent pairs, along with the count constraint. + +this doesn't seem like a sensible approach as we're solving two constraints in the backtrack + +--- + +n = 4, k = 3 + +not possible, -1 + +--- + +n = 6, k = 1 + +100101 + +- 1's and 0's are interchangeable in isomorphic sense + +--- + +5 0 + +10101 + +--- + +7 3 + +1110010 + +--- + +4 2 + +1100 + +--- + +3 2 + +-1 + + +--- + +7 4 + +1110001 + +--- + +start from the beginning, fill with 1's until we reach ceil(k / 2), fill with 0's until we reach k total pairs, alternating on the rest + +--- + + +5 2 + +11001 good + + +4 3 + +11100 (-1) + +6 1 + +110101 + +5 0 + +10101 + +7 3 + +1110010 + +4 2 + +1100 + +3 2 + +110 (-1) + +7 4 + +1110001 diff --git a/comp/swap-and-delete/ex1.in b/comp/swap-and-delete/ex1.in @@ -0,0 +1,5 @@ +4 +0 +011 +0101110001 +111100 diff --git a/comp/swap-and-delete/ex2.in b/comp/swap-and-delete/ex2.in diff --git a/comp/swap-and-delete/main.cpp b/comp/swap-and-delete/main.cpp @@ -0,0 +1,52 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <cmath> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + + int testCases; + string s; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> s; + int zeroes = 0; + for(int i = 0; i < s.size(); ++i) { + if(s[i] == '0') { + zeroes += 1; + } + } + + int ones = (int)(s.size() - zeroes); + + ll sum = 0; + + for(int i = 0; i < s.size(); ++i) { + if(s[i] == '1') { + if(zeroes >= 1) { + zeroes -= 1; + sum += 1; + } else { + break; + } + } else { + if(ones >= 1) { + ones -= 1; + sum += 1; + } else { + break; + } + } + } + + cout << s.size() - sum << endl; + } +} diff --git a/comp/swap-and-delete/thoughts.txt b/comp/swap-and-delete/thoughts.txt