Mock Contest Problem 1
Problem Overview
Converting the constraints reveals two key requirements for any valid set:
- Must include the maximum power of each prime factor of n
- Must contain at least one pair of distinct prime factors
Since the number of prime factors is much smaller than log(n), brute force search works effectively.
Approach: Inclusion-Exclusion
Direct counting proves diffciult. Instead, compute all possible combinations first, then subtract invalid ones.
Implemantation
void dfs(int idx, long long prod, long long sign) {
if (idx > primeCnt) {
add(answer, qm(2, prod) - 1, sign);
return;
}
dfs(idx + 1, prod * p[idx] % MOD, sign);
dfs(idx + 1, prod * (p[idx] - 1) % MOD, (MOD + MOD - sign - sign) % MOD);
if (p[idx] > 2) dfs(idx + 1, prod * (p[idx] - 2) % MOD, sign);
}
void solve() {
freopen("set.in", "r", stdin);
freopen("set.out", "w", stdout);
cin >> n;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
p[++primeCnt] = 1;
while (n % i == 0) {
n /= i;
p[primeCnt]++;
}
}
}
if (n > 1) p[++primeCnt] = 2;
dfs(1, 1, 1);
printf("%lld", answer % MOD);
}
Time complexity depends on the number of prime factors.
CF1916E: Tree Color Query Problem
Core Insight
Enumerate each node as a potential LCA. For each node, we need the number of distinct colors on paths from nodes in subtrees to the current node.
For a single node, the answer equals the product of the maximum and second maximum values among its children.
Maintaining Path Color Counts
First consider the linear case. When moving upward, adding 1 to all nodes below seems logical, but double-counting occurs when encountering a node with the same color.
The solution: maintain the nearest node with the same color for each position. During updates, subtract 1 from all nodes below that nearest same-color node.
Extending to trees: for the current node, each child subtree needs its own nearest same-color point tracked.
Use a segment tree for range updates and queries on the tree's Euler tour.
Implementation
void collect(int u) {
euler[u] = ++timer;
int prev = colorPos[col[u]];
if (col[u]) sameColor[col[u]].push_back(u);
colorPos[col[u]] = u;
for (int v : tree[u]) {
colorPos[col[u]] = u;
collect(v);
}
subtreeEnd[u] = timer;
colorPos[col[u]] = prev;
}
void solveNode(int u) {
for (int v : tree[u]) solveNode(v);
seg.update(1, euler[u], subtreeEnd[u], 1, n, 1);
for (int v : sameColor[u]) seg.update(1, euler[v], subtreeEnd[v], 1, n, -1);
long long max1 = 1, max2 = 1;
for (int v : tree[u]) {
int val = seg.query(1, euler[v], subtreeEnd[v], 1, n);
if (val > max1) {
max2 = max(max2, max1);
max1 = val;
} else if (val > max2) {
max2 = val;
}
}
result = max(result, max1 * max2);
}
ARC119D: Graph Modeling Problem
Problem Transformation
For each red cell, connect its row to its column. A cell becomes uncolorable when its corresponding row or column is deleted.
This bipartite graph perfectly preserves the problem's properties.
Key Observation
After deletions, each connected component must retain exactly one vertex. This can be verified through manual testing.
Solution Strategy
- Build the bipartite graph from red cells
- Enumerate the number of remaining rows after processing all components
- For each enumeration, compute maximum white cells using the formula
Implementation
void exploreComponent(int v) {
visited[v] = true;
components[currentComp].push_back(v);
if (v <= rowCount) rowInComp++;
else colInComp++;
for (int to : adj[v]) {
if (!visited[to]) exploreComponent(to);
}
}
void reconstruct(int v, int parent) {
visited[v] = true;
for (int to : adj[v]) {
if (!visited[to]) reconstruct(to, v);
}
if (parent) {
if (v > rowCount) printf("Y %d %d\n", parent, v - rowCount);
else printf("X %d %d\n", v, parent - rowCount);
}
}
void solve() {
cin >> rowCount >> colCount;
for (int i = 1; i <= rowCount; i++) {
for (int j = 1; j <= colCount; j++) {
char c; cin >> c;
if (c == 'R') addEdge(i, j + rowCount);
}
}
for (int i = 1; i <= rowCount + colCount; i++) {
if (adj[i].size() && !visited[i]) {
currentComp++;
exploreComponent(i);
}
}
int bestRows = 0;
for (int i = 1; i <= currentComp; i++) {
if ((rowCount - rowInComp + bestRows) * (colCount - colInComp + currentComp - bestRows) >
(rowCount - rowInComp + i) * (colCount - colInComp + currentComp - i))
bestRows = i;
}
printf("%d\n", rowInComp + colInComp - currentComp);
fill(visited, visited + rowCount + colCount + 1, false);
for (int i = 1; i <= bestRows; i++)
for (int v : components[i]) if (v <= rowCount) reconstruct(v, 0);
for (int i = bestRows + 1; i <= currentComp; i++)
for (int v : components[i]) if (v > rowCount) reconstruct(v, 0);
}
ABC197F: Palindrome Paths in a Labeled Graph
Observation
Given the constraints, this problem becomes straightforward with bidirectional search.
Simultaneously search from nodes 1 and n. Track the current position pair (i, j) and the resulting palindrome length. When exploring neighbors, only traverse edges where the labels match.
Answer Computation
- When the search reaches (i, i), the palindrome length equals 2 × distance + 1
- For even-length palindromes, add 1 to any valid state (i, j) where edge (i, j) exists
Implementation
void bidirectionalSearch() {
queue<pair<int, int>> q;
q.push({1, n});
visited[1][n] = true;
while (!q.empty()) {
auto [u, v] = q.front(); q.pop();
for (int i = 0; i < graph[u].size(); i++) {
for (int j = 0; j < graph[v].size(); j++) {
int nu = graph[u][i].first;
int nv = graph[v][j].first;
if (graph[u][i].second != graph[v][j].second) continue;
if (visited[nu][nv]) continue;
visited[nu][nv] = true;
distance[nu][nv] = distance[u][v] + 2;
q.push({nu, nv});
}
}
}
}
int solve() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y; char c;
cin >> x >> y >> c;
addEdge(x, y, c);
}
bidirectionalSearch();
int answer = INF;
for (int i = 1; i <= n; i++) {
if (visited[i][i]) answer = min(answer, distance[i][i]);
}
for (int i = 1; i <= n; i++) {
for (auto [v, _] : graph[i]) {
if (visited[i][v]) answer = min(answer, distance[i][v] + 1);
}
}
return answer == INF ? -1 : answer;
}
ABC242F: Combinatorial Counting on a Grid
Problem Setup
Count valid placements of black and white pieces on an n×m grid under specific constraints.
Initial Formula
The answer involves summing over all possible row and column selections:
$$\text{ans} = \sum_{i=1}^{n} \sum_{j=1}^{n-i} \sum_{k=1}^{m} \sum_{l=1}^{m-k} \binom{n}{i}\binom{n-i}{j}\binom{m}{k}\binom{m-k}{l} \cdot a_{i,k} \cdot b_{j,l}$$
Where $a_{i,k}$ represents the number of ways to place black pieces in exactly i rows and k columns, and $b_{j,l}$ represents the same for white pieces.
Computing a and b
Direct computation fails because configurations where some selected rows or columns remain empty get counted.
Apply inclusion-exclusion:
$$a_{i,j} = \binom{i \cdot j}{S} - \sum_{k=1}^{i} \sum_{l=1}^{j} \binom{i}{k}\binom{j}{l} \cdot a_{k,l}$$
where $(k,l) \neq (i,j)$ in the subtraction.
Implementation
void precompute(int pieces, int type) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[type][i][j] = C[i * j][pieces];
for (int k = 1; k <= i; k++) {
for (int l = 1; l <= j; l++) {
if (k == i && l == j) continue;
subtract(dp[type][i][j], C[i][k] * C[j][l] % MOD * dp[type][k][l] % MOD);
}
}
}
}
}
long long solve() {
initialize();
long long answer = 0;
cin >> n >> m >> blackPieces >> whitePieces;
precompute(blackPieces, 0);
precompute(whitePieces, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n - i; j++) {
for (int k = 1; k <= m; k++) {
for (int l = 1; l <= m - k; l++) {
add(answer, C[n][i] * C[n - i][j] % MOD * C[m][k] % MOD * C[m - k][l] % MOD
* dp[0][i][k] % MOD * dp[1][j][l] % MOD);
}
}
}
}
return answer;
}
Additional Notes
- CF2068J: Simple implementation problem
- JOI 2017 Final: Semi-High-Speed Train - Implementation-heavy solution
- JOI 2016 Final: Railway Pricing - Refer to separate analysis
- Mock Contest 10.8 T1: Brute force enumeration problem; ensure adequate range when selecting values