Problem B: What, More Kangaroos?
Operations 1 and 2 nullify eachother, as do operations 3 and 4. The problem reduces to applying positive integer operations on two buttons only, yielding four enumeration cases.
With operations 1 and 3 chosen, let operation 1 execute x times and operation 3 execute y times (x, y > 0). The goal is maximizing indices where c_i + x·a_i + y·b_i < 0. Since c_i > 0, we need x·a_i + y·b_i < -c_i. Scaling both x and y by a common factor makes this equivalent to x·a_i + y·b_i < 0.
Classification:
- a_i × b_i = 0: One coefficient is zero. If the other is negative, the condition holds; otherwise it fails.
- a_i > 0, b_i > 0: Impossible to satisfy.
- a_i < 0, b_i < 0: Always satisfies.
- a_i < 0, b_i > 0: Rearranging yields -a_i/b_i > y/x.
- a_i > 0, b_i < 0: Rearranging yields -a_i/b_i < y/x.
Cases 1-3 admit direct counting. Cases 4-5 become interval coverage problems solvable via discretization and prefix sums.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T;
const int MAXN = 200005;
int coeffA[MAXN], coeffB[MAXN], constC[MAXN];
int neg[2] = {1, -1};
struct Entry {
int a, b;
int kind;
} records[MAXN];
int result = 0;
int recordCount = 0;
int bestResult = 0;
bool cmpEntries(Entry x, Entry y) {
return abs(x.a) * abs(y.b) < abs(x.b) * abs(y.a);
}
void process(int num1, int num2) {
if (num1 == 0 && num2 == 0) return;
if (num1 == 0) {
if (num2 < 0) result++;
return;
}
if (num2 == 0) {
if (num1 < 0) result++;
return;
}
if (num1 * num2 > 0) {
if (num1 < 0) result++;
return;
}
if (num2 > 0)
records[++recordCount] = {num1, num2, 0};
else
records[++recordCount] = {num1, num2, 1};
}
int prefix[MAXN];
void solve() {
int n;
cin >> n;
bestResult = 0;
for (int i = 1; i <= n; i++)
cin >> coeffA[i] >> coeffB[i] >> constC[i];
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
result = 0;
recordCount = 0;
fill(prefix, prefix + n + 15, 0);
for (int k = 1; k <= n; k++)
process(coeffA[k] * neg[i], coeffB[k] * neg[j]);
sort(records + 1, records + 1 + recordCount, cmpEntries);
int grpIdx = 0;
for (int k = 1; k <= recordCount; k++) {
if (k == 1) grpIdx++;
else if (records[k].a * records[k-1].b != records[k].b * records[k-1].a) grpIdx++;
if (records[k].kind == 1)
prefix[grpIdx]++;
else {
prefix[0]++;
prefix[grpIdx]--;
}
}
int curr = prefix[0];
for (int k = 1; k <= n + 10; k++) {
prefix[k] = prefix[k] + prefix[k-1];
curr = max(curr, prefix[k]);
}
bestResult = max(bestResult, curr + result);
}
}
cout << bestResult << endl;
}
signed main() {
cin >> T;
while (T--)
solve();
return 0;
}
Problem G: Bucket Bonanza
Two buckets draining optimally can merge profitably. Given v₁ > v₂ and l₁ > l₂, the merge yields profit when t·l₁ - v₂ > 0. This indicates small volumes paired with large flow rates are advantageous.
Sort volumes in ascending order and flow rates in descending order, producing arrays L_i and V_i. The expression t·L_i - V_i is monotonic, allowing binary search based on positivity.
When L_i volume matches V_u flow and V_i flow matches L_v volume, their union forms a new bucket with properties V_u and L_v. When L_i volume equals V_i flow, the bucket is already empty—conceptually equivalent to self-merging.
This sorting perspective transforms the problem into selecting one volume and one flow rate, where self-matching represents completion.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T;
const int MAXN = 200010;
struct Bucket {
int volume, flow, idx;
} volData[MAXN], flowData[MAXN];
struct Query {
int value, idx;
} queries[MAXN];
bool cmpVol(Bucket a, Bucket b) {
if (a.volume == b.volume) return a.flow < b.flow;
return a.volume < b.volume;
}
bool cmpFlow(Bucket a, Bucket b) {
if (a.flow == b.flow) return a.volume > b.volume;
return a.flow > b.flow;
}
bool cmpQuery(Query a, Query b) {
return a.value < b.value;
}
int answer[MAXN];
int active[MAXN];
void solve() {
int n;
priority_queue<Bucket> pq;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> volData[i].volume;
for (int i = 1; i <= n; i++)
cin >> volData[i].flow;
for (int i = 1; i <= n; i++)
active[i] = 1;
int totalVol1 = 0, totalFlow1 = 0;
int totalVol2 = 0, totalFlow2 = 0;
for (int i = 1; i <= n; i++) {
volData[i].idx = i;
totalVol1 += volData[i].volume;
totalFlow1 += volData[i].flow;
flowData[i] = volData[i];
}
sort(volData + 1, volData + 1 + n, cmpVol);
sort(flowData + 1, flowData + 1 + n, cmpFlow);
int q;
cin >> q;
for (int i = 1; i <= q; i++)
cin >> queries[i].value, queries[i].idx = i;
sort(queries + 1, queries + 1 + q, cmpQuery);
int ptrFlow = 1, ptrVol = 1;
for (int i = 1; i <= q; i++) {
int id = queries[i].idx;
int timeVal = queries[i].value;
while (true) {
if (ptrFlow > n || ptrVol > n) break;
else if (flowData[ptrFlow].flow * timeVal - volData[ptrVol].volume >= 0) {
int id1 = flowData[ptrFlow].idx;
int id2 = volData[ptrVol].idx;
active[id1] = 0;
active[id2] = 0;
totalVol2 += volData[ptrVol].volume;
totalFlow2 += flowData[ptrFlow].flow;
ptrFlow++;
ptrVol++;
} else break;
}
answer[id] = totalVol1 - totalFlow1 * timeVal - totalVol2 + totalFlow2 * timeVal;
}
for (int i = 1; i <= q; i++)
cout << answer[i] << ' ';
cout << endl;
}
signed main() {
cin >> T;
while (T--)
solve();
return 0;
}
Problem H: Pen Pineapple Apple Pen
Finding substrings matching pattern ABCCA where the two BC segments are identical.
Brute force yields O(n⁸). Constraining j₁ and j₄ to the same length reduces this to O(n⁶). Precomputing the number of valid BCC segmentations for each (i, j) pair further optimizes to O(n³).
Computing valid BCC positions
When matching positions (i₂, j₂) equals (i₃, j₃), they contribute 1 to BCC counts for all (i, j) where i < i₂ and i₃ ≤ j ≤ j₃. The bottleneck lies in finding matching substrings—enumerating i₂, i₃, then finding maximum matching length via binary search on the hash comparison.
For longest common prefix queries, polynomial hashing with prefix sums suffices. When finding maximum length L where substrings [i₂, i₂+L-1] and [i₃, i₃+L-1] match, use binary search. Each matching pair contributes 1 to all positions in the rectangle [1, i₂-1] × [i₃, i₃+L-1], handled via 2D prefix sums.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
const int MAXN = 5005;
const int BASE = 101;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string inputStr;
char s[MAXN];
int hashVal[MAXN];
int prefixHash[MAXN];
int matchLen[MAXN][MAXN];
int countMat[MAXN][MAXN];
int prefix1[MAXN][MAXN];
int prefix2[MAXN][MAXN];
int modAdd(int a, int b) {
int res = a + b;
if (res >= MOD) res -= MOD;
return res;
}
int modSub(int a, int b) {
int res = a - b;
if (res < 0) res += MOD;
return res;
}
int modMul(long long a, long long b) {
return (a * b) % MOD;
}
int modPow(int base, int exp) {
int res = 1;
while (exp > 0) {
if (exp & 1) res = modMul(res, base);
base = modMul(base, base);
exp >>= 1;
}
return res;
}
int getHash(int l, int r, int* powArr, int* invArr) {
int raw = modSub(prefixHash[r], prefixHash[l-1]);
return modMul(raw, invArr[l]);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int totalAns = 0;
for (int i = 0; i < 26; i++)
hashVal[i] = rng() % MOD;
prefixHash[0] = 0;
cin >> inputStr;
int n = inputStr.size();
for (int i = 0; i < n; i++)
s[i+1] = inputStr[i];
int powArr[MAXN], invArr[MAXN];
powArr[0] = 1;
for (int i = 1; i <= n; i++)
powArr[i] = modMul(powArr[i-1], BASE);
invArr[n] = modPow(powArr[n], MOD - 2);
for (int i = n; i >= 1; i--)
invArr[i-1] = modMul(invArr[i], BASE);
for (int i = 1; i <= n; i++)
prefixHash[i] = modAdd(prefixHash[i-1], modMul(hashVal[s[i]-'a'], powArr[i]));
for (int l = 1; l <= n; l++) {
for (int r = l + 1; r <= n; r++) {
if (s[l] != s[r]) continue;
int lo = 1, hi = min(r - l, n - r + 1);
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
int l1 = l, r1 = l + mid - 1;
int l2 = r, r2 = r + mid - 1;
if (getHash(l1, r1, powArr, invArr) == getHash(l2, r2, powArr, invArr))
lo = mid;
else
hi = mid - 1;
}
matchLen[l][r] = lo;
int l1 = l, r1 = l + lo - 1;
int l2 = r, r2 = r + lo - 1;
countMat[1][l2]++;
countMat[l1][l2]--;
countMat[1][r2+1]--;
countMat[l1][r2+1]++;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
countMat[i][j] = modAdd(countMat[i][j], countMat[i-1][j]);
countMat[i][j] = modAdd(countMat[i][j], countMat[i][j-1]);
countMat[i][j] = modSub(countMat[i][j], countMat[i-1][j-1]);
prefix1[i][j] = countMat[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
prefix1[i][j] = modAdd(prefix1[i][j], prefix1[i-1][j]);
prefix1[i][j] = modAdd(prefix1[i][j], prefix1[i][j-1]);
prefix1[i][j] = modSub(prefix1[i][j], prefix1[i-1][j-1]);
}
}
for (int j = 1; j <= n; j++)
for (int i = 1; i <= n; i++)
prefix2[i][j] = modAdd(prefix2[i-1][j], prefix1[i][j]);
for (int pos1 = 1; pos1 <= n; pos1++) {
for (int pos4 = pos1 + 4; pos4 <= n; pos4++) {
if (s[pos1] != s[pos4]) continue;
int maxLen = min(pos4 - 3 - pos1, n + 1 - pos4);
maxLen = min(maxLen, matchLen[pos1][pos4]);
int baseVal = prefix1[pos4-3][pos4-1];
int term1 = modMul(baseVal, maxLen);
int term2 = modSub(prefix2[pos1 + maxLen - 1][pos4 - 1], prefix2[pos1 - 1][pos4 - 1]);
totalAns = modAdd(totalAns, modSub(term1, term2));
}
}
cout << totalAns << endl;
return 0;
}
The final answer aggregates across all valid (i₁, i₄) pairs using 2D prefix sums, achieving O(n² log n) complexity with O(n²) preprocessing.