Made Up
Problem Statement Given three sequences A, B, C, count the number of pairs (i, j) such that A[i] = B[C[j]].
Solution Approach Since all values are bounded between 1 and N, we can use frequency counting. For each value v, count how many times it appears in array A (stored in cntA) and how many times it appears as B[C[j]] (stored in cntB). The answer is the sum of cntA[i] multiplied by cntB[i] for all i from 1 to N.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
vector<int64> freqA(n + 1, 0), freqB(n + 1, 0);
for (int i = 0; i < n; i++) {
cin >> a[i];
freqA[a[i]]++;
}
for (int i = 0; i < n; i++)
cin >> b[i];
for (int i = 0; i < n; i++) {
cin >> c[i];
int idx = b[c[i] - 1];
freqB[idx]++;
}
int64 result = 0;
for (int i = 1; i <= n; i++)
result += freqA[i] * freqB[i];
cout << result << '\n';
return 0;
}
H and V
Problem Statement You are given an H × W grid containing only '.' and '#'. You may choose any subset of rows and any subset of columns to change to '.' (clearing them). How many ways result in exactly k '#' characters remaining?
Solution Approach Given the small constraints (H, W ≤ 6), we can enumerate all possibilities. For each subset of rows (2^H choices) and each subset of columns (2^W choices), we simulate the clearing operation and count '#' characters. If the count equals k, we increment the answer.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w, k;
cin >> h >> w >> k;
vector<string> grid(h);
for (auto& row : grid)
cin >> row;
auto countHash = [](const vector<string>& g) {
int total = 0;
for (const auto& row : g)
for (char cell : row)
if (cell == '#')
total++;
return total;
};
int64 answer = 0;
for (int rowMask = 0; rowMask < (1 << h); rowMask++) {
for (int colMask = 0; colMask < (1 << w); colMask++) {
vector<string> working = grid;
for (int r = 0; r < h; r++)
if (rowMask & (1 << r))
working[r] = string(w, '.');
for (int c = 0; c < w; c++)
if (colMask & (1 << c))
for (int r = 0; r < h; r++)
working[r][c] = '.';
if (countHash(working) == k)
answer++;
}
}
cout << answer << '\n';
return 0;
}
Moving Piece
Problem Statement You have n points where each point i can jump to point P[i] and earns C[P[i]] score. Starting from any point for exactly K steps (starting point score not counted), find the maximum achievable score.
Solution Approach The directed graph consists of multiple disjoint cycles. For each cycle, we simulate traversing K steps. When K exceeds the cycle length, we calculate how many complete cycles are traversed and multiply the cycle sum accordingly. We track cumulative sums along the path and evaluate all possible staritng positions within the cycle.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> nxt(n + 1);
for (int i = 1; i <= n; i++)
cin >> nxt[i];
vector<int> val(n + 1);
for (int i = 1; i <= n; i++)
cin >> val[i];
int64 best = LLONG_MIN;
for (int start = 1; start <= n; start++) {
int cur = start;
int64 cycleSum = 0;
vector<int64> prefix;
while (true) {
cur = nxt[cur];
cycleSum += val[cur];
prefix.push_back(cycleSum);
if (cur == start) break;
}
int cycleLen = prefix.size();
for (int offset = 0; offset < cycleLen && offset < k; offset++) {
int completeCycles = (k - 1 - offset) / cycleLen;
best = max(best, prefix[offset]);
if (completeCycles > 0)
best = max(best, prefix[offset] + completeCycles * cycleSum);
}
}
cout << best << '\n';
return 0;
}
Sum of Divisors
Problem Statement Define f(X) as the number of divisors of X. Calculate Σ(K=1 to N) K × f(K).
Solution Approach Consider the contribution of each integer i. The value i appears as a divisor in all multiples of i up to N (specifically, in floor(N/i) numbers). The contribution of i as a divisor to each multiple j×i equals j×i. Summing over all multiples: i + 2i + 3i + ... + floor(N/i)×i, which is an arithmetic series with first term i, common difference i, and floor(N/i) terms. The sum of this series for all i from 1 to N gives the answer.
Implemantation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int64 answer = 0;
for (int i = 1; i <= n; i++) {
int64 first = i;
int64 last = i * (n / i);
int64 count = n / i;
answer += count * (first + last) / 2;
}
cout << answer << '\n';
return 0;
}
Red and Green Apples
Problem Statement You have three sequences A, B, C. Elements from C can replace any elements in A or B. Select exactly X elements from A and Y elements from B to maximize the total sum.
Solution Approach First, sort A and B in descending order and extract the top X and Y elements respectively. Add these elements to sequence C. Sort the combined C in descending order and take the top (X + Y) elements. This guarantees the maximum sum since we always pick the largest available elements.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x, y, szA, szB, szC;
cin >> x >> y >> szA >> szB >> szC;
vector<int> A(szA), B(szB), C(szC);
for (auto& v : A) cin >> v;
for (auto& v : B) cin >> v;
for (auto& v : C) cin >> v;
sort(A.begin(), A.end(), greater<int>());
sort(B.begin(), B.end(), greater<int>());
for (int i = 0; i < x; i++)
C.push_back(A[i]);
for (int i = 0; i < y; i++)
C.push_back(B[i]);
sort(C.begin(), C.end(), greater<int>());
int64 result = 0;
for (int i = 0; i < x + y; i++)
result += C[i];
cout << result << '\n';
return 0;
}
Rem of Sum is Num
Problem Statement Given sequence A, count the number of contiguous subarrays where (sum of subarray) mod K equals the (length of subaray).
Solution Approach Transform the condition. Let prefix sum be S. The condition (S[r] - S[l-1]) mod K = r - (l-1) is equivalent to (S[r] - r) mod K = (S[l-1] - (l-1)) mod K. This means we need to count pairs where these transformed values match. We use a sliding window with a hash map to track frequencies. Initialize with position 0 having count 1. The window length is at most K since lengths exceeding K cannot satisfy the condition.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 n, k;
cin >> n >> k;
vector<int64> arr(n + 1), pref(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
pref[i] = pref[i - 1] + arr[i];
}
for (int i = 1; i <= n; i++)
pref[i] = (pref[i] - i) % k;
int64 answer = 0;
int windowSize = min<int>(k - 1, n);
unordered_map<int64, int64> freq;
freq[0] = 1;
for (int i = 1; i <= n; i++) {
if (i > windowSize) {
int64 key = pref[i - windowSize - 1];
freq[key]--;
}
answer += freq[pref[i]];
freq[pref[i]]++;
}
cout << answer << '\n';
return 0;
}
Keep Connect
Problem Statement Given a 2 × n grid graph with 2n vertices and 3n-2 edges, count the number of ways to delete exactly i edges (for i from 1 to n-1) while keeping the graph connected, modulo p.
Solution Approach Use dynamic programming where each column (pair of vertices) is processed sequentially. Let dp[i][j][s] represent the number of ways to handle the first i columns, having deleted j edges, with connectivity state s (1 for connected, 0 for disconnected). We transition based on how columns i and i+1 connect, considering vertical and horizontal edges within and between columns.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 3005;
int64 dp[MAXN][MAXN][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 n, mod;
cin >> n >> mod;
dp[1][0][1] = 1;
dp[1][1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n; j++) {
dp[i + 1][j + 1][1] = (dp[i + 1][j + 1][1] + dp[i][j][1] * 3) % mod;
dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % mod;
dp[i + 1][j + 2][0] = (dp[i + 1][j + 2][0] + dp[i][j][1] * 2) % mod;
dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][0]) % mod;
dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][0]) % mod;
}
}
for (int i = 1; i < n; i++)
cout << dp[n][i][1] << " \n"[i == n - 1];
return 0;
}