commit f935525f4143abb7b839c9391f071e5dba92495e
parent ed1e2177227b0b26ffe05f719953c8bc492d6fd2
Author: Andrew Laack <andrew@laack.co>
Date: Sat, 31 Oct 2026 16:14:49 -0500
Completed 4 problems in div 3 contest
Diffstat:
15 files changed, 625 insertions(+), 0 deletions(-)
diff --git a/comp/main.cpp b/comp/main.cpp
@@ -3,9 +3,21 @@
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
+#include <queue>
+
+#define ll long long
using namespace std;
int main() {
+ // boilerplate loading
+ int testCases, current, n, k;
+ cin >> testCases;
+
+ vector<int> ls {};
+ for(int z = 0; z < testCases; ++z) {
+ cin >> current;
+ ls.push_back(current);
+ }
}
diff --git a/comp/r1131/a/ex1.in b/comp/r1131/a/ex1.in
@@ -0,0 +1,16 @@
+5
+4 1
+sinx
+n
+6 7
+xixsms
+mixsxim
+8 5
+fixtures
+frute
+3 3
+abc
+def
+5 10
+sixty
+codeforces
diff --git a/comp/r1131/a/main.cpp b/comp/r1131/a/main.cpp
@@ -0,0 +1,111 @@
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+#include <unordered_map>
+#include <algorithm>
+#include <queue>
+
+#define ll long long
+
+using namespace std;
+
+
+//- p, q strings
+//- p as product of variables written in the numerator of a fraction
+//- q as product of variables written in the denominator of a fraction
+//- can we mutate this such that the numerator simplified to "six" and denominator is cleared?
+// - return YES / NO
+
+int main() {
+
+ int testCases, current, pSize, qSize;
+ string p, q = "";
+
+ cin >> testCases;
+
+ // idea:
+ // put into hashmap, count numbers, ensure sDelta = 1, iDelta = 1, xDelta = 1, all rest = 0
+
+ for(int z = 0; z < testCases; ++z) {
+ cin >> pSize;
+ cin >> qSize;
+ cin >> p;
+ cin >> q;
+
+ unordered_map<char,int> pCounts {};
+
+ for(int i = 0; i < pSize; ++i) {
+ pCounts[p[i]] += 1;
+ }
+
+ unordered_map<char,int> qCounts {};
+ bool ctn = false;
+
+ for(int i = 0; i < qSize; ++i) {
+ if(!pCounts.contains(q[i])) {
+ cout << "NO" << endl;
+ ctn = true;
+ break;
+ }
+ qCounts[q[i]] += 1;
+ }
+
+ if(ctn) {
+ continue;
+ }
+
+
+ bool fs = false;
+ bool fi = false;
+ bool fx = false;
+ bool bad = false;
+
+ for(auto& ele : pCounts) {
+
+ if(ele.second > qCounts[ele.first]) {
+ int delta = ele.second - qCounts[ele.first];
+
+ if(delta >= 2) {
+ bad = true;
+ break;
+ }
+
+ if(ele.first == 's') {
+ if(fs) {
+ bad = true;
+ break;
+ }
+ fs = true;
+ }
+ else if(ele.first == 'i') {
+ if(fi) {
+ bad = true;
+ break;
+ }
+ fi = true;
+ }
+ else if(ele.first == 'x') {
+ if(fx) {
+ bad = true;
+ break;
+ }
+ fx = true;
+ }
+ else {
+ bad = true;
+ break;
+ }
+ }
+ }
+ if(fs && fi && fx) {
+ if(!bad) {
+ cout << "YES" << endl;
+ } else {
+ cout << "NO" << endl;
+ }
+ } else {
+ cout << "NO" << endl;
+ }
+ }
+
+}
diff --git a/comp/r1131/a/problem.txt b/comp/r1131/a/problem.txt
@@ -0,0 +1,7 @@
+Constraints:
+
+- p, q strings
+- p as product of variables written in the numerator of a fraction
+- q as product of variables written in the denominator of a fraction
+- can we mutate this such that the numerator simplified to "six" and denominator is cleared?
+ - return YES / NO
diff --git a/comp/r1131/b/ex1.in b/comp/r1131/b/ex1.in
@@ -0,0 +1,3 @@
+2
+0 0 3
+1 1 2
diff --git a/comp/r1131/b/main.cpp b/comp/r1131/b/main.cpp
@@ -0,0 +1,47 @@
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+#include <unordered_map>
+#include <algorithm>
+
+#define ll long long
+
+using namespace std;
+
+int main() {
+ int testCases, x,y,z;
+ cin >> testCases;
+
+ for(int m = 0; m < testCases; ++m) {
+
+ cin >> x;
+ cin >> y;
+ cin >> z;
+
+ int sum = x + y + z;
+
+ if(x >= y && x >= z) {
+
+ for(int i = 0; i < sum; ++i) {
+ cout << 'P'; // most rocks
+ }
+ cout << endl;
+
+ }
+ else if(y >= x && y >=z) {
+ for(int i = 0; i < sum; ++i) {
+ cout << 'R'; // most scissors
+ }
+ cout << endl;
+
+ }
+ else if(z >= x && z >= y) {
+ for(int i = 0; i < sum; ++i) {
+ cout << 'S'; // most paper
+ }
+ cout << endl;
+ } else {
+ cout << "UNKNOWN" << endl;
+ }
+ }
+}
diff --git a/comp/r1131/b/problem.txt b/comp/r1131/b/problem.txt
@@ -0,0 +1,55 @@
+- Alice and Bob are playing the Rock, Scissors, Paper game.
+
+- It is given that the game consists of exactly x+y+z
+- rounds. Also, Bob knows that Alice will play Rock exactly x
+- times, Scissors exactly y
+- times, and Paper exactly z
+- times. However, Bob does not know the order of Alice's outcomes.
+-
+- Before the game starts, Bob must choose all of his outcomes in advance. Help him find an optimal sequence of x+y+z
+- outcomes such that, regardless of the order of Alice's outcomes, the number of rounds won by Bob is at least the number of rounds won by Alice.
+-
+- It is guaranteed that such a sequence always exists.
+
+---
+
+- given the distribution of plays x,y,z find the optimal approach
+
+0 0 3
+
+x,y,z
+r,p,s
+
+just play
+r,r,r
+
+1 1 2
+
+r,r,r,r
+
+because rock beats scisosrs twice (two wins)
+and then it ties and loses the others.
+
+1 1 1
+
+at most 300 steps
+at most 1000 test cases
+
+dp?
+
+we only care about the worst case. basically, we want to match their moves with ours
+as an example:
+
+if they have 1,1,1
+then we want to match their scissors with our paper, their rock with our scissors, etc.
+
+can we just increase our numbers?
+
+how?
+ - should we just match on their most common one then?
+ - like we fight against that?
+ - seem no because ties matter in some cases
+ - ?
+ - yes, that's it actually
+ - proof:
+ - contradition: assume they win by matching on their best. this means the antagonist of ours is larger than what we fought. that's not right.
diff --git a/comp/r1131/c/ex1.in b/comp/r1131/c/ex1.in
@@ -0,0 +1,9 @@
+4
+4
+1 2 3 4
+5
+1 1 1 1 1
+2
+6 7
+4
+1 1 1 2
diff --git a/comp/r1131/c/ex2.in b/comp/r1131/c/ex2.in
@@ -0,0 +1,7 @@
+3
+4
+1 2 3 4
+5
+1 1 1 1 1
+2
+6 7
diff --git a/comp/r1131/c/main.cpp b/comp/r1131/c/main.cpp
@@ -0,0 +1,65 @@
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+#include <unordered_map>
+#include <algorithm>
+
+#define ll long long
+
+using namespace std;
+
+// - can we just combine the central elements as much as possible?
+// - that seems right.
+// - combine central elements together until no more, than split largest into 1 and other
+
+int main() {
+ int testCases, sz, current;
+ cin >> testCases;
+ for(int m = 0; m < testCases; ++m) {
+ cin >> sz;
+
+ vector<int> ls {};
+
+ for(int i = 0; i < sz; ++i) {
+ cin >> current;
+ ls.push_back(current);
+ }
+
+ int innerSum = 0;
+
+ bool allOnes = true;
+
+ for(int i = 0; i < sz; ++i) {
+ if(ls[i] != 1) {
+ allOnes = false;
+ break;
+ }
+ }
+
+ if(allOnes) {
+ cout << -1 << endl;
+ continue;
+ }
+
+ bool ib = false;
+
+ for(int i = 1; i < sz-1; ++i) {
+ innerSum += ls[i];
+ if(ls[i] >= 2) {
+ ib = true;
+ }
+ }
+
+ if(!ib) {
+ innerSum = 0;
+ }
+
+ int left = ls[0];
+ int right = ls[ls.size() - 1];
+
+ left += innerSum;
+ right += left - 1;
+ cout << right << endl;
+
+ }
+}
diff --git a/comp/r1131/c/problem.txt b/comp/r1131/c/problem.txt
@@ -0,0 +1,80 @@
+- n cores
+- 1 -> n numbered
+- a_i is weight of ith core
+- operation
+ - choose one core
+ - s.t. mass a_i >= 2
+ - split a_i into x,y s.t. x >= 1, y >= 1, x + y = a_i
+ - after splitting, remove the element, decrementing the total size of a
+ - x is added to left neighbor (if exists)
+ - y is added to right neighbor (if exists)
+- Determine whether it is possible to end the process with exactly one core remaining. If it is possible, find the maximum possible mass of this single final core.
+
+
+---
+
+- so basically perform the ops to maximize the size of one core at the end.
+
+---
+
+4
+1 2 3 4
+
+remove 3
+
+1 3 6
+
+remove 3
+
+2 8
+
+remove 2
+
+9
+
+in this we added as much as possible to the larger element and the smallest amount to the smaller one. that doesn't seem quite right overall, but the idea that we only want to put 1 on the loss side when no left or right seems right.
+
+---
+
+5
+1 1 1 1 1
+
+can't make any choices.
+
+-1
+
+
+---
+
+2
+6 7
+
+either way.
+
+7 + 5 = 12
+
+---
+
+idea:
+ - can we just decide that the left or right is correct based on which is smaller than do combinations on the interior to minimize left and maximize right (or whicever)?
+
+- can we always just lose 1?
+
+1 1 3
+
+1 3
+
+3
+
+in this case we lose 2 overall
+
+---
+
+can we combine smallest / largest possible at each step?
+
+- can we combine smallest at each step? does order matter?
+
+- can we just combine the central elements as much as possible?
+ - that seems right.
+ - combine central elements together until no more, than split largest into 1 and other
+
diff --git a/comp/r1131/d/ex1.in b/comp/r1131/d/ex1.in
@@ -0,0 +1,11 @@
+5
+3
+1 2 3
+2
+-1 -1
+4
+18 -2 9 11
+9
+9 9 8 2 4 4 3 5 3
+3
+6 67 7
diff --git a/comp/r1131/d/main.cpp b/comp/r1131/d/main.cpp
@@ -0,0 +1,53 @@
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+#include <unordered_map>
+#include <algorithm>
+
+#define ll long long
+
+using namespace std;
+
+int main() {
+
+ int testCases, current, size;
+
+ cin >> testCases;
+ for(int z = 0; z < testCases; ++z) {
+
+ cin >> size;
+ vector<ll> ls{};
+
+ for(int i = 0; i < size; ++i) {
+ cin >> current;
+ ls.push_back(current);
+ }
+
+ sort(ls.begin(), ls.end());
+
+ int leftMatch = 1;
+ int rightMatch = 1;
+ ll changeBy = 0;
+
+ ll cost = 0;
+
+ while(leftMatch + rightMatch <= (int)ls.size()) {
+ if(leftMatch < rightMatch) {
+ // lock left
+
+ ll delta = ls[leftMatch] - ls[leftMatch-1];
+ changeBy -= delta;
+ cost += leftMatch * delta;
+ leftMatch += 1;
+
+ } else {
+ // lock right
+ ll delta = ls[ls.size() - rightMatch] - ls[ls.size() - rightMatch - 1];
+ changeBy -= delta;
+ cost += rightMatch * delta;
+ rightMatch += 1;
+ }
+ }
+ cout << cost << " " << ls.back() - ls[0] << endl;
+ }
+}
diff --git a/comp/r1131/d/problem.txt b/comp/r1131/d/problem.txt
@@ -0,0 +1,147 @@
+D. Lock and Unlock
+time limit per test2 seconds
+memory limit per test256 megabytes
+You are given an integer array [a1,a2,…,an]
+. Initially, all the elements are unlocked.
+
+You may perform the following operation on array a
+ any number of times (possibly zero):
+
+Choose an integer k
+ (1≤k≤n
+) and choose exactly k
+ distinct indices. The elements at these indices are locked for the current operation. This step incurs a cost equal to k
+.
+
+Choose one of the following two actions:
+
+Increase every unlocked element by 1
+;
+Decrease every unlocked element by 1
+.
+This step does not incur any additional cost.
+
+Unlock all the elements. This step does not incur any additional cost.
+The total cost is equal to the sum of the individual costs over all the operations performed.
+
+Determine the minimum possible total cost to make all the elements of the array a
+ equal. Furthermore, among all the ways to achieve this minimum possible total cost, find the minimum number of operations required.
+
+Input
+The first line of the input contains a single integer t
+ (1≤t≤2⋅104
+) — the number of test cases. The description of each test case follows.
+
+The first line of each test case contains a single integer n
+ (2≤n≤2⋅105
+) — the length of the array a
+.
+
+The second line of each test case contains n
+ integers a1,a2,…,an
+ (−109≤ai≤109
+) — the elements of the array a
+.
+
+It is guaranteed that the sum of n
+ over all the test cases does not exceed 2⋅105
+.
+
+Output
+For each test case, print two space-separated integers on a new line — the minimum possible total cost to make all the elements equal, and the minimum number of operations required to make all the elements equal with the minimum possible total cost.
+
+---
+
+[a_1,a_2,...,a_n] where all elements are locked
+
+can do this any number of times:
+ - choose a number k >= 1 k <= n and choose k distinct indices all of these elements are locked, with a cost of k
+ - choose one of the two actions
+ 1. increased every unlocked by 1
+ 2. decrease every unlocked by 1
+ - unlock all elements
+
+- find min cost to make all elements equal
+ - find the minimum number of operations required too, using min cost approach
+
+- constraints
+ - 2000 test cases
+ - 10_000 arr len max
+ - numbers between -10^9 and 10^9
+
+- so we must do this in nlogn / linear time
+
+
+3
+1 2 3
+
+1 2 3
+
+lock 1, decrement
+
+1 1 2
+
+lock final element, increment
+
+2 2 2
+
+cost: 2
+ops: 2
+
+idea: find highest and lowest. find number of high and low elements and then move towards whichever one has less elements.
+sort first(?) order doesn't matter in terms of positions.
+
+---
+2
+-1 -1
+
+cost: 0
+ops: 0
+
+---
+4
+18 -2 9 11
+
+can start on either end. lock low
+
+
+17 -2 8 10
+
+16 -2 7 9
+
+...
+
+7 -2 -2 0
+
+7 -1 -1 1
+
+7 0 0 2
+
+7 1 1 3
+
+7 2 2 4
+
+7 3 3 5
+
+7 4 4 6
+
+7 5 5 7 (cost 2)
+
+7 6 6 7 (cost 2)
+
+7 7 7 7
+
+cost: 22 (2 additional at the end)
+
+18 -- 2 = 20
+
+note: number of operations == max - min or smt like that
+note: we can then compute the stepwise deltas between elements, using this as a multiplier for our selections
+
+---
+9
+9 9 8 2 4 4 3 5 3
+---
+3
+6 67 7
+---
diff --git a/comp/r1131/run.sh b/comp/r1131/run.sh
@@ -0,0 +1,2 @@
+#!/bin/bash
+g++ main.cpp && cat ex1.in | ./a.out