A - Three Pairwise Maximums
Given three pairwise maximum values, determine if they can be derived from three positive integers. The solutoin involves sorting the input values and verifying consistency conditions.
#include <iostream>
#include <algorithm>
using namespace std;
void solve() {
int nums[3];
cin >> nums[0] >> nums[1] >> nums[2];
sort(nums, nums + 3);
if (nums[1] != nums[2]) {
cout << "NO\n";
return;
}
cout << "YES\n";
cout << 1 << " " << nums[0] << " " << nums[1] << "\n";
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}
B - Restore Permutation from Merger
Reconstruct a permutation from its merged sequence by selecting the first occurrence of each unique element.
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 50;
bool seen[MAX_N + 1];
void solve() {
int n;
cin >> n;
memset(seen, false, sizeof(seen));
for (int i = 0; i < 2 * n; i++) {
int num;
cin >> num;
if (!seen[num]) {
seen[num] = true;
cout << num << " ";
}
}
cout << "\n";
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}
C - Array Quality Validation
Determine the shortest prefix to remove so the remaining array is non-strictly unimodal. Traverse from right to find the peak, then left to find the starting point.
#include <iostream>
using namespace std;
const int MAX_N = 200000;
int arr[MAX_N + 1];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
int peak = n;
for (int i = n; i >= 1; i--) {
if (i < n && arr[i] < arr[i + 1]) break;
peak = i;
}
int start = peak;
for (int i = peak; i >= 1; i--) {
if (i < peak && arr[i] > arr[i + 1]) break;
start = i;
}
cout << start - 1 << "\n";
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}
D - Constructing Good Strings
Compute the minimum character changes needed to transform a string into an 'a'-good string using divide-and-conquer with memoization.
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 200000;
const int LETTERS = 20;
char str[MAX_N + 5];
int memo[MAX_N * 4][LETTERS];
int compute(int left, int right, int charIdx, int node = 1) {
if (left == right) return str[left] != 'a' + charIdx;
if (memo[node][charIdx] != -1) return memo[node][charIdx];
int mid = (left + right) / 2;
int leftCost = 0, rightCost = 0;
for (int i = left; i <= mid; i++) leftCost += (str[i] != 'a' + charIdx);
for (int i = mid + 1; i <= right; i++) rightCost += (str[i] != 'a' + charIdx);
int res = min(leftCost + compute(mid + 1, right, charIdx + 1, node * 2 + 1),
rightCost + compute(left, mid, charIdx + 1, node * 2));
return memo[node][charIdx] = res;
}
void solve() {
int n;
cin >> n >> (str + 1);
memset(memo, -1, sizeof(memo));
cout << compute(1, n, 0) << "\n";
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}
E - Directed Graph Acyclicity
Orient undirected edges in a mixed graph to avoid cycles using topological ordering of the directed subgraph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int>> graph[200001];
int inDegree[200001];
vector<int> topoOrder;
int orderIdx[200001];
void topologicalSort(int n) {
queue<int> q;
for (int i = 1; i <= n; i++)
if (!inDegree[i]) q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
topoOrder.push_back(cur);
for (auto edge : graph[cur]) {
int neighbor = edge.first;
int type = edge.second;
if (type && --inDegree[neighbor] == 0)
q.push(neighbor);
}
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
graph[i].clear();
inDegree[i] = 0;
}
while (m--) {
int type, u, v;
cin >> type >> u >> v;
if (type) {
graph[u].push_back({v, 1});
inDegree[v]++;
} else {
graph[u].push_back({v, 0});
graph[v].push_back({u, 0});
}
}
topoOrder.clear();
topologicalSort(n);
if (topoOrder.size() != n) {
cout << "NO\n";
return;
}
cout << "YES\n";
for (int i = 0; i < n; i++)
orderIdx[topoOrder[i]] = i;
for (int i = 1; i <= n; i++) {
for (auto edge : graph[i]) {
int neighbor = edge.first;
int type = edge.second;
if (type || (!type && orderIdx[i] < orderIdx[neighbor]))
cout << i << " " << neighbor << "\n";
}
}
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}
F - Leaf Removal Operations
Calculate the maximum operations to remove leaf sets in a tree using dynamic programming and re-rooting techniques.
#include <iostream>
#include <vector>
using namespace std;
vector<int> tree[200001];
int leafCount[200001];
bool validRoot[200001];
int operations[200001];
int maxOperations;
void dfs(int node, int parent) {
leafCount[node] = 0;
validRoot[node] = true;
operations[node] = 0;
for (int neighbor : tree[node]) {
if (neighbor == parent) continue;
dfs(neighbor, node);
leafCount[node] += validRoot[neighbor];
validRoot[node] &= validRoot[neighbor];
operations[node] += operations[neighbor];
}
operations[node] += leafCount[node] / m;
validRoot[node] &= (leafCount[node] % m == 0);
}
void reRoot(int node, int parent) {
maxOperations = max(maxOperations, operations[node]);
for (int neighbor : tree[node]) {
if (neighbor == parent) continue;
int saveNodeLC = leafCount[node];
bool saveNodeVR = validRoot[node];
int saveNodeOP = operations[node];
int saveNeighborLC = leafCount[neighbor];
bool saveNeighborVR = validRoot[neighbor];
int saveNeighborOP = operations[neighbor];
leafCount[node] -= validRoot[neighbor];
validRoot[node] = (leafCount[node] == tree[node].size() - 1) && (leafCount[node] % m == 0);
operations[node] = operations[node] - operations[neighbor] - (leafCount[node] + validRoot[neighbor]) / m + leafCount[node] / m;
leafCount[neighbor] += validRoot[node];
validRoot[neighbor] = (leafCount[neighbor] == tree[neighbor].size()) && (leafCount[neighbor] % m == 0);
operations[neighbor] = operations[neighbor] + operations[node] - (leafCount[neighbor] - validRoot[node]) / m + leafCount[neighbor] / m;
reRoot(neighbor, node);
leafCount[node] = saveNodeLC;
validRoot[node] = saveNodeVR;
operations[node] = saveNodeOP;
leafCount[neighbor] = saveNeighborLC;
validRoot[neighbor] = saveNeighborVR;
operations[neighbor] = saveNeighborOP;
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) tree[i].clear();
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1, 0);
maxOperations = 0;
reRoot(1, 0);
cout << maxOperations << "\n";
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}
G - Column Swap for Permutation
Determine column swaps to transform a matrix into row permutations using graph cycles and orientation selection.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_N = 200000;
vector<pair<int, pair<int, int>>> graph[MAX_N + 1];
int frequency[MAX_N + 1];
bool visited[MAX_N + 1];
vector<int> swapsA, swapsB;
void traverse(int node) {
visited[node] = true;
for (auto edge : graph[node]) {
int neighbor = edge.first;
int colIndex = edge.second.first;
int swapType = edge.second.second;
if (!visited[neighbor]) {
if (swapType) swapsA.push_back(colIndex);
else swapsB.push_back(colIndex);
traverse(neighbor);
}
}
}
void solve() {
int n;
cin >> n;
memset(frequency, 0, sizeof(frequency));
for (int i = 1; i <= n; i++) graph[i].clear(), visited[i] = false;
for (int col = 1; col <= n; col++) {
int a, b;
cin >> a >> b;
frequency[a]++;
frequency[b]++;
graph[a].push_back({b, {col, 1}});
graph[b].push_back({a, {col, 0}});
}
for (int i = 1; i <= n; i++)
if (frequency[i] != 2) {
cout << "-1\n";
return;
}
vector<int> result;
for (int i = 1; i <= n; i++) {
if (visited[i]) continue;
swapsA.clear();
swapsB.clear();
traverse(i);
if (swapsA.size() < swapsB.size())
result.insert(result.end(), swapsA.begin(), swapsA.end());
else
result.insert(result.end(), swapsB.begin(), swapsB.end());
}
cout << result.size() << "\n";
for (int swapIdx : result) cout << swapIdx << " ";
cout << "\n";
}
int main() {
int tests;
cin >> tests;
while (tests--) solve();
return 0;
}