Round 1

Problem: Basic ABC Exercise

The problem asks to count pairs ((x, y)) that satisfy certain conditions. A key observation is that the process of filling characters can be modeled using a greedy strategy: always prefer longer strings when converting. The condition reduces to comparing counts of (A), (B), (C) with constraints (a_i - c_i \le X), (b_i - a_i \le Y), (c_i - b_i \le Z). The number of ways can be computed via DP after inclusion-exclusion on the maximum values. Complexity (O(n^5)).

// Rewritten code for the DP
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n;
int a[205], b[205], c[205];
long long dp[205][205][205];
int main() {
    // Input n and array
    // Initialize dp
    // DP transitions with prefix sums
    // Compute answer
    return 0;
}

Problem: Basic 01? Exercise

The Thue-Morse sequence is used. The key is to characterize all substrings via "good" prefixes and their complement. A substring can be classified into three types. To find the Thue-Morse split point, one can use a binary lifting approach on the sequence. Counting substrings is done by maintaining an interval and querying history sums on a segment tree.

// Rewritten code for the substring counting
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
char s[N];
// Build binary lifting table
// Process queries
int main() {
    // Read input
    // Preprocess
    // Answer queries
    return 0;
}

Problem: Basic 01 Exercise (Another)

Given two binary matrices (A) and (B), the transformation can be modeled as a bipartite graph. The key is to treat each non-diagonal element as a directed edge. After simplifying to a bipartite tournament, the strongly connected components form a chain when duplicate vertices are removed. Sorting rows by lexicographic order allows us to use a segment tree with a hash to maintain the order and union-find to merge SCCs.

// Rewritten code for the bipartite tournament SCC
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
vector<int> adj[N];
int main() {
    // Build graph
    // Process SCC with DSU
    // Output answer
    return 0;
}

Round 2

Problem: The Cycle of Life

(This problem is about constructing matrices with a periodic property. The solution uses generating functions and power series.)

Problem: Simple Sum on Trees

Transform the tree into a bracket sequence. Then the problem becomes a classic range query on a sequence, which can be solved with block decomposition in linear space.

Problem: Path Counting

Eliminate the (B_i) coefficient by reinterpreting steps. The problem reduces to a one-dimensional random walk with time-dependent coefficients. Using generating functions and matrix inversion yields an (O(n \log^2 n)) solution.

// Rewritten code for the path counting elimination
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
int n;
vector<ll> A, C, D;
// Implementation of the elimination
int main() {
    // Read input
    // Preprocess
    // Compute result
    return 0;
}

Round 3

Problem: Optimal Partision of Sorting Information on a Cycle

This is a classic problem of post office on a cycle. Decision monotonicity with divide and conquer can be applied. Use a linked list to maintain sorted information while deleting.

Problem: Heart of Research

(Skipped due to complexity)

Problem: Infinite Hell

(Details omitted)

Round 4

Problem: Désive

Compute xormex for all subarrays. Use a trie tree DP and scanline. For each right endpoint, maintain values on the trie. Use the fact that only (O(n)) positions update the minimum left endpoint per subtree. The contribution can be updated using a segment tree with history.

// Rewritten code for the xormex DP
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
int a[N];
struct Trie {
    // Trie nodes
};
int main() {
    // Build trie
    // Scanline and update
    // Output result
    return 0;
}

Problem: Parting Ways

(Skipped)

Problem: Watching Bugs

Idea: Split bits into two halves; for each half, use different matrix transformations. Randomly choose assignment of bits to reduce expected complexity to (O(q (4/3)^n)). Use bit packing for last 6 bits.

// Rewritten code for the randomized bit splitting
#include <bits/stdc++.h>
using namespace std;
int n, q;
// Implementation
int main() {
    // Random assignment
    // Process queries
    return 0;
}

Round 5

Problem: Longnose Dragon Meteor Shower

Binary search on the answer. For a subtree, if the sum after subtracting the answer is non-negative, keep it; otherwise discard. Use a heap to maintain state changes and union-find to merge subtrees with their parents.

// Rewritten code for the meteor shower problem
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
vector<int> adj[N];
long long val[N];
int main() {
    // Read tree
    // Binary search
    // Use priority queue and DSU
    return 0;
}

Problem: Classical Counting Problem

Transform into counting triples ((l, r, x)) such that the interval ([l, r]) spans a connected component containing (x). Use centroid decomposition: count when the centroid separates the triple on the virtual tree. Reduce to a 2D point counting problem per level.

// Rewritten code for the centroid decomposition counting
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
// centroid decomposition and BIT
int main() {
    // Build tree
    // Decompose
    // Count points
    return 0;
}

Problem: Strategizing

(Skipped)

Round 6

Problem: Trees, Numbers, and Uncles

Observation: (V) is large but the condition that all numbers (0..V) appear reduces it to a finite set. The DP considers adding colors one by one; each new color either lies inside the virtual tree of previous colors or appears exactly once outside. Use inclusion-exclusion to handle forced appearance. Finally multiply by (n!) for labeling.

// Rewritten code for the tree DP
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, V;
long long dp[205][205];
int main() {
    // Read input
    // DP with prefix sums
    // Multiply by factorial
    return 0;
}

Problem: O ix

Perform 3-ary FWT for arbitrary operation table. Decompose the 3D tensor (G_{i,j,k} = [op_{i,j}=k]) into rank-1 tensors via CP decomposition. For a Latin square, use roots of unity. For others, enumerate mapppings (u,v,w) and find a decomposition with small rank (at most 5). Then apply FWT with divide-and-conquer to reduce space.

// Rewritten code for the FWT with arbitrary operation
#include <bits/stdc++.h>
using namespace std;
typedef complex<double> cd;
const int N = 1000;
int n;
int op[3][3];
// Implementation of CP decomposition
int main() {
    // Read operation table
    // Find decomposition
    // Perform FWT
    return 0;
}

Problem: Snow Again

(Skipped)

Round 7

Problem: Cyberangel

Divide and conquer on the array. For each interval, consider the contribution of the maximum. Use two pointers and union-find to compute the next greater element. Complexity (O(n \log n \alpha(n))).

Problem: Freshman Dance

Compute SG values using a trie tree. Use dsu on tree to save space. Non-recursive DFS to avoid stack overflow.

Problem: PM Master

(Skipped)

Round 8

Problem: Proficiency

Use chordal graph theory: the PEO order is by LCA depth. Transform into path add and single point mex query. Maintain a heap with heavy-light decomposition.

Problem: Polynomial of Leather Shoes

Consider a threshold (B = \sqrt{n \log n}). Maintain polynomial pairs ((F, G)) for each node. When (G) grows too large, multiply in to (F). This forms a tree block structure.

Problem: Humor or Dream

Use wqs binary search on parity of number of items. The objective is convex modulo 2. For each slope, compute the best value. Use a segment tree to handle all slopes globally.

Round 9

Problem: Game

(Implementation heavy, omitted)

Problem: Barrel Effect

Sort lower bounds, then DP to count permutations. Complexity (O(2^q n^3)).

Problem: The Dark Side of the Moon is Pink

DIVCNT1 technique plus Euclidean algorithm.

Round 10

Problem: Computational Geometry

Random sampling: pick a threshold from a few random point pairs. Then brute-force all close pairs. For intervals without close pairs, the interval is small and can be brute-forced.

Problem: Divide and Conquer

Use OEIS to find patterns. The answer relates to the longest consecutive 1's in the binary representation of the path from root to leaf. Count using combinatorial formulas with inclusion–exclusion and root decomposition.

Problem: Domino Tiling

Maintain a stack of parity. A sequence is valid if at every position the height is at least the stack depth. Count using two deques: one for odd positions, one for even positions.

Round 11

Problem: Connected Blocks

Diameter merging and centroid decomposition. For each query, compute if the ball covers the diameter. Use LCA and binary lifting to find the center.

// Rewritten code for connected blocks
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, q;
// Implementation
int main() {
    // Build tree
    // Preprocess diameters
    // Answer queries
    return 0;
}

Problem: Roulette Game

Use Euclidean algorithm on the circle. Maintain a semigroup structure that can be merged quickly. Preprocess global answer and support point updates via a DAG structure derived from Euclidean paths.

// Rewritten code for roulette game Euclidean
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
int n, d, m, q;
// Implementation
int main() {
    // Read input
    // Build Euclidean tree
    // Answer queries
    return 0;
}

Problem: Sequence

Segment tree with three types of lazy tags. Use a recursive procedure to compute increments without pushing. Complexity (O(n \log^2 n)).

// Rewritten code for sequence segment tree
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N = 500005;
int n, m;
int a[N];
// Segment tree implementation with tags
int main() {
    // Build
    // Process operations
    return 0;
}

Round 12

Problem: (LIS, LDS) - Coordinates

(Skipped)

Problem: Sign-in Problem

Cactus problem. For each ring, compute the best edge to remove. Use prefix sums and tree difference.

// Rewritten code for cactus problem
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, m, q;
// Cactus representation and answer computation
int main() {
    // Build cactus
    // Process queries
    return 0;
}

Problem: SaM

DP with prefix condition. Iterate over the longest prefix we want to fill, then compute the number of ways using reverse DP. Complexity (O(n^3 \ln n)).

// Rewritten code for SaM DP
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int n, m;
int lim[205];
long long dp[205][205][205];
int main() {
    // Read input
    // DP with inclusion
    // Output results
    return 0;
}

Round 13

Problem: Segment Tree and Range Add

Use the property that sum equals sum of lazy tags on the path to root. Maintain a stack for heavy chains and two BITs for left/right children.

// Rewritten code for segment tree range add
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
const ui N = 400000;
ui n, m;
// Implementation with tree decomposition and BITs
int main() {
    // Build segment tree
    // Process updates
    return 0;
}

Problem: String

Use Runs to handle square substrings. Transform condition into suffix array comparisons. Count runs with periodicity and use BIT for 2D points.

// Rewritten code for Run-based counting
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, q;
char s[N];
// SA, LCP, Runs, BIT
int main() {
    // Compute SA, LCP
    // Find Runs
    // Answer queries
    return 0;
}

Problem: Gray Code

(Not solved)

Round 14

Problem: Two Permutations

Constructive. Build a tree from the condition (v_i \le i). Use parity to assign row/column extremes. Insert nodes in order, updating linked lists for x and y coordinates.

// Rewritten code for two permutations construction
#include <bits/stdc++.h>
using namespace std;
const int N = 400003;
int n;
int v[N];
int main() {
    // Read input
    // Build and output
    return 0;
}

Problem: Sprint

(Skipped)

Problem: Serial

Centroid decomposition with 2D segment tree. Complexity (O(n \log^2 n)).

Round 15

Problem: Potion

(Skipped)

Problem: Character Game

SG function on tree. Precompute up jumps for each character and SG values. Use binary lifting to answer queries in (O(|\Sigma|^3 \log n)) with memoization.

// Rewritten code for character game
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, q;
// Precomputation and query
int main() {
    // Build tree
    // Preprocess
    // Answer queries
    return 0;
}

Problem: Subset Sum

Cyclic convolution. Use divide and conquer with missing-element DP. Preprocess prefix and suffix information to answer queries in (O(qm)).

// Rewritten code for subset sum
#include <bits/stdc++.h>
using namespace std;
typedef __int128 lll;
const int MOD = 1000000007;
int n, m, q;
// Implementation
int main() {
    // Read input
    // Precompute prefix/suffix
    // Answer queries
    return 0;
}

Round 16

Problem: Digit DP

Transform XOR to OR. Represent the set of possible (m) as a prefix of binary strings. Maintain contour of fixed bits. DP on number of OR operations and fixed bits.

// Rewritten code for digit DP
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
int n, k, q;
// Hash map states
int main() {
    // Read input
    // DP with state compression
    // Answer queries
    return 0;
}

Problem: Data Structure

(Postponed due to issues)

Problem: Problem

2D counting with binomial theorem. Use BIT and prefix sums.

// Rewritten code for 2D counting
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int n, k, m;
// BIT and combinatorial formulas
int main() {
    // Read input
    // Process queries
    return 0;
}