algorithms

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

commit 519ca1294599819069e45a36d3ec783be8107548
parent dee056aea94eeede5712febcffc46f6202b9067d
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  9 Nov 2026 15:42:01 -0600

Wow factor

Diffstat:
Acomp/wip/remove-the-ends/incorrect-greedy.cpp | 53+++++++++++++++++++++++++++++++++++++++++++++++++++++
Mcomp/wip/remove-the-ends/main.cpp | 7+++++++
Acomp/wow-factor/ex1.in | 1+
Acomp/wow-factor/ex2.in | 1+
Acomp/wow-factor/main.cpp | 85+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/wow-factor/problem.txt | 95+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 242 insertions(+), 0 deletions(-)

diff --git a/comp/wip/remove-the-ends/incorrect-greedy.cpp b/comp/wip/remove-the-ends/incorrect-greedy.cpp @@ -0,0 +1,53 @@ +#include <vector> +#include <iostream> + +using namespace std; + +long long solve(vector<int>& ls) { + long long res = 0; + int lc = 0; + for(int i = 0; i < ls.size(); ++i) { + if(ls[i] < 0) { + break; + } + res += ls[i]; + lc += 1; + } + + int rc = 0; + for(int i = ls.size() - 1; i >= 0; --i) { + if(!(ls[i] < 0)) { + break; + } + res += ls[i] * -1; + rc += 1; + } + + // that's not right because some of the innermost elements should be taken in certain cases + int left = 0; + int right = 0; + + if(lc + rc != ls.size()) { + left = abs(ls[lc]); + right = abs(ls[(ls.size() - 1) - lc]); + } + + return res + max(left,right); +} + +int main() { + int testCases, len, current = 0; + cin >> testCases; + for(int z = 0; z < testCases; ++z) { + + cin >> len; + vector<int> ls {}; + + for(int i = 0; i < len; ++i) { + cin >> current; + ls.push_back(current); + } + + cout << solve(ls) << endl; + } +} diff --git a/comp/wip/remove-the-ends/main.cpp b/comp/wip/remove-the-ends/main.cpp @@ -31,6 +31,13 @@ using namespace std; // hmm, actually maybe not // we'd've likely already been in this current state by that point +// alt framing: + // left, size + // do comparison for sizes and see if better approach exists for a larger size? + // this comparison array would be one per left value and have a size of n + // 200_000 * 200_000 = 40_000_000_000 + // that's too big. + long long solve(vector<int>& ls, int left, int right, unordered_map<long long, long long>& memo) { long long current = (((long long)left) << 32) | right; diff --git a/comp/wow-factor/ex1.in b/comp/wow-factor/ex1.in @@ -0,0 +1 @@ +vvvovvv diff --git a/comp/wow-factor/ex2.in b/comp/wow-factor/ex2.in @@ -0,0 +1 @@ +vvovooovovvovoovoovvvvovovvvov diff --git a/comp/wow-factor/main.cpp b/comp/wow-factor/main.cpp @@ -0,0 +1,85 @@ +#include <vector> +#include <iostream> + +// the state is as follows: +// +// - s(fvc,oc,svc) +// - fvc == first v count (0->2) +// - oc == o count (0->1) +// - svc == second v count (0->2) +// - s(ct) +// - ct ranges from 0->5 +// - vv o vv +// - when ct == 5, we have found one +// - when ct == 4 or 3, we can take a 4 +// - ... +// +// this gives us an upper bound of 5 * size which is at worst 500_000, a reasonable number of stated assuming limited computation per state + +using namespace std; + +long long solve(string& input, char found, int idx, vector<vector<long long>>& memo) { + + if(found == 5) { + return 1; + } + + if(idx == input.size()) { + return 0; + } + + if(memo[found][idx] != -1) { + return memo[found][idx]; + } + + + long long res = 0; + + // we may only use v's that are adjacent + // if the prior was a v, but current isn't, we skip + if(found != 1 && found != 4) { + res += solve(input, found, idx+1, memo); + } + + char current = input[idx]; + + switch (found) { + case 0: + if(current == 'v') { + res += solve(input,found+1, idx+1, memo); + } + break; + case 1: + if(current == 'v') { + res += solve(input,found+1, idx+1, memo); + } + break; + case 2: + if(current == 'o') { + res += solve(input,found+1, idx+1, memo); + } + break; + case 3: + if(current == 'v') { + res += solve(input,found+1, idx+1,memo); + } + break; + case 4: + if(current == 'v') { + res += solve(input,found+1, idx+1,memo); + } + break; + } + + memo[found][idx] = res; + return res; +} + +int main() { + string input; + cin >> input; + + vector<vector<long long>> memo (5, vector<long long> (input.size(), -1)); + + cout << solve(input,0,0, memo) << endl; +} diff --git a/comp/wow-factor/problem.txt b/comp/wow-factor/problem.txt @@ -0,0 +1,95 @@ +B. WOW Factor +time limit per test1 second +memory limit per test256 megabytes +Recall that string a + is a subsequence of a string b + if a + can be obtained from b + by deletion of several (possibly zero or all) characters. For example, for the string a +="wowwo", the following strings are subsequences: "wowwo", "wowo", "oo", "wow", "", and others, but the following are not subsequences: "owoo", "owwwo", "ooo". + +The wow factor of a string is the number of its subsequences equal to the word "wow". Bob wants to write a string that has a large wow factor. However, the "w" key on his keyboard is broken, so he types two "v"s instead. + +Little did he realise that he may have introduced more "w"s than he thought. Consider for instance the string "ww". Bob would type it as "vvvv", but this string actually contains three occurrences of "w": + +"vvvv" +"vvvv" +"vvvv" +For example, the wow factor of the word "vvvovvv" equals to four because there are four wows: + +"vvvovvv" +"vvvovvv" +"vvvovvv" +"vvvovvv" +Note that the subsequence "vvvovvv" does not count towards the wow factor, as the "v"s have to be consecutive. + +For a given string s +, compute and output its wow factor. Note that it is not guaranteed that it is possible to get s + from another string replacing "w" with "vv". For example, s + can be equal to "vov". + +Input +The input contains a single non-empty string s +, consisting only of characters "v" and "o". The length of s + is at most 106 +. + +Output +Output a single integer, the wow factor of s +. + +Examples +InputCopy +vvvovvv +OutputCopy +4 +InputCopy +vvovooovovvovoovoovvvvovovvvov +OutputCopy +100 +Note +The first example is explained in the legend. + +--- + +- a is a subsequence of b iff a can be created by removing elements from b +- wow factor := number of subsequences == "wow" +- we use vv as a stand in for w +- vvvv gives us three ways to make w's (always # of v's - 1) +- each string is made of only v's and o's + +--- + +examples: + +vvvovvv + +vv_ovv_ +vv_ov_v +vv_ovv_ +vv_ov_v + +in each example, we may take a v (or skip it), take another v (or skip it), and if we already have 2 v's then we may take the next o, ..., and after we've taken a o, we may take up to two more v's. + +string size is at most 10**6 = 100_000 + +a naive approach would be evaluating, basically, 2**n selections if all elements are v's + +the state is as follows: + +- s(fvc,oc,svc) + - fvc == first v count (0->2) + - oc == o count (0->1) + - svc == second v count (0->2) +- s(ct) + - ct ranges from 0->5 + - vv o vv + - when ct == 5, we have found one + - when ct == 4 or 3, we can take a 4 + - ... + +this gives us an upper bound of 5 * size which is at worst 500_000, a reasonable number of stated assuming limited computation per state + +--- + +vvovooovovvovoovoovvvvovovvvov