algorithms

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

commit 27a64f668eb6f3fbb8ee80a6ebefa6b539fefbe8
parent d16bd7b283e5131a75c87cc9b57534b4a4716c98
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 20 Oct 2026 11:52:45 -0500

Attempted max score

Diffstat:
Acomp/maximimze-the-score/ex1.in | 13+++++++++++++
Acomp/maximimze-the-score/main.cpp | 72++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/maximimze-the-score/problem.txt | 145+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/maximimze-the-score/t1.cpp | 63+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dcomp/trouble-sort/.main.cpp.swp | 0
5 files changed, 293 insertions(+), 0 deletions(-)

diff --git a/comp/maximimze-the-score/ex1.in b/comp/maximimze-the-score/ex1.in @@ -0,0 +1,13 @@ +6 +1 +1 1 +2 +1 2 1 2 +2 +1 2 2 1 +3 +1 1 2 3 3 2 +3 +1 2 3 3 2 1 +4 +1 2 3 4 1 2 3 4 diff --git a/comp/maximimze-the-score/main.cpp b/comp/maximimze-the-score/main.cpp @@ -0,0 +1,72 @@ +#include <iostream> +#include <vector> +#include <string> +#include <unordered_map> + +int square(int x) { + return x * x; +} + +std::string vecToString(std::vector<int>& nums) { + std::string res = ""; + for(int i = 0; i < nums.size(); ++i) { + res += std::to_string(nums[i]) + ", "; + } + return res; +} + +int solve(std::vector<int>& nums, std::unordered_map<std::string, int>& memo) { + + if(memo.find(nm) != memo.end()) { + return memo[nm]; + } + + int bestScore = 0; + + std::unordered_map<int,int> priors {}; + for(int i = 0; i < nums.size(); ++i) { + if(priors.find(nums[i]) == priors.end()) { + priors[nums[i]] = i; + } + + int firstIdx = priors[nums[i]]; + int score = square((i - firstIdx) + 1); + + std::vector<int> removedNums {}; + + for(int x = 0; x < nums.size(); ++x) { + if(x >= firstIdx && x <= i) { + continue; + } else { + removedNums.push_back(nums[x]); + } + } + + score += solve(removedNums, memo); + + if(score > bestScore) { + bestScore = score; + } + } + + memo[nm] = bestScore; + return bestScore; + +} + +int main() { + // greedily select the highest score first, in any order for ties + int caseCount, numCount, current; + std::cin >> caseCount; + for(int i = 0; i < caseCount; ++i) { + std::cin >> numCount; + numCount *= 2; + std::vector<int> nums {}; + for(int x = 0; x < numCount; ++x) { + std::cin >> current; + nums.push_back(current); + } + std::unordered_map<std::string, int> mem {}; + std::cout << solve(nums, mem) << std::endl; + } +} diff --git a/comp/maximimze-the-score/problem.txt b/comp/maximimze-the-score/problem.txt @@ -0,0 +1,145 @@ +C. Maximize the Score +time limit per test2 seconds +memory limit per test256 megabytes +You are given an array a + of length 2n +. Each integer from 1 + to n + occurs exactly twice in a +. + +Initially, your score is 0 +. + +You can repeatedly perform the following operation while a + is non-empty: + +Choose an integer x + that is present in a +. +Let l + and r + be the indices of the leftmost and rightmost occurrences of x + in the current array, respectively. If x + occurs only once, then l=r +. +Add (r−l+1)2 + to your score. +Delete the elements al,al+1,…,ar + from a +. The remaining elements are concatenated without changing their order and re-indexed starting from 1 +. +Find the maximum possible score after making the array empty. + +Input +Each test contains multiple test cases. The first line contains the number of test cases t + (1≤t≤104 +). The description of the test cases follows. + +The first line of each test case contains a single integer n + (1≤n≤2⋅105 +). + +The second line contains 2n + integers a1,a2,…,a2n + (1≤ai≤n +). + +It is guaranteed that each integer from 1 + to n + occurs exactly twice in a +. + +It is guaranteed that the sum of n + over all test cases does not exceed 2⋅105 +. + +--- + +- array a, size 2n + - include each number from 1->n twice +- score := 0 +- while a isn't empty you can do these steps if you want: + - choose an int x in a + - l = leftmost index of int x, r = rightmost index of int x + - iff only one x then l == r + - add (r - l + 1) ^ 2 to score + - delete a_l, a_l+1, ... a_r from array + +--- + +examples: + +--- + +ex1 + +1 1 + +drop 1, (r - l+1) ^ 2 = 4 +score = 4 + +--- + +ex2 + +1 2 1 2 + +3-1 + 1 = 3 + +3**2 = 9 + +(0 - 0+1) ** 2 = 1 + +res=10 + +this could also be considered the spread with the largest score. + +--- + +1 2 2 1 + +(3 - 0 + 1) ^ 2 = 16 + +differ from inner first: + +(2 - 1 + 1) ^ 2 = 4 +(1 - 0 + 1) ^ 2 = 4 + += 8 + +--- + +1 1 2 3 3 2 + +(5 - 2 + 1) ^ 2 = 16 + +1 1 + +(1 - 0 + 1) ^ 2 = 4 + += 20 + + +--- + +1 2 3 3 2 1 + +(5 - 0 + 1) ^ 2 = 36 + + +--- + +1 2 3 4 1 2 3 4 + +(4 - 0 + 1) ^ 2 = 25 + +2 3 4 + +(0 - 0 + 1) ^ 2 = 1 +(0 - 0 + 1) ^ 2 = 1 +(0 - 0 + 1) ^ 2 = 1 + +25 + 3 = 28 + +it'd be equivalent to remove in either order so just remove first I guess diff --git a/comp/maximimze-the-score/t1.cpp b/comp/maximimze-the-score/t1.cpp @@ -0,0 +1,63 @@ +#include <iostream> +#include <vector> +#include <unordered_map> + +int square(int x) { + return x * x; +} + +int solve(std::vector<int> nums) { + + int sum = 0; + + while(nums.size() > 0) { + + std::unordered_map<int,int> priors {}; + std::pair<int,int> bestIndexPair; + int bestScore = 0; + + for(int i = 0; i < nums.size(); ++i) { + if(priors.find(nums[i]) == priors.end()) { + priors[nums[i]] = i; + } + int firstIdx = priors[nums[i]]; + int score = square((i - firstIdx) + 1); + if(score > bestScore) { + bestScore = score; + bestIndexPair = {firstIdx,i}; + } + } + + std::vector<int> next {}; + + for(int i = 0; i < nums.size(); ++i) { + if(i >= bestIndexPair.first && i <= bestIndexPair.second) { + continue; + } else { + next.push_back(nums[i]); + } + } + + sum += bestScore; + nums = next; + } + + return sum; + +} + +int main() { + // greedily select the highest score first, in any order for ties + int caseCount, numCount, current; + std::cin >> caseCount; + for(int i = 0; i < caseCount; ++i) { + std::cin >> numCount; + numCount *= 2; + std::vector<int> nums {}; + for(int x = 0; x < numCount; ++x) { + std::cin >> current; + nums.push_back(current); + } + std::cout << solve(nums) << std::endl; + } +} diff --git a/comp/trouble-sort/.main.cpp.swp b/comp/trouble-sort/.main.cpp.swp Binary files differ.