DAY0 (2024.11.15)
Finally arriving at the camp.
T2 GYM104787M
First, we define a replica connected component as a connected component formed by traversing only nodes with index greater than n. It's not hard to observe that a replica connected component (green nodes) connects to several leaves with index less than n, and together with the original graph, it forms a symmetric connected component. See the diagram below:
Then, if there are lf leaves (blue nodes), we need to cut lf - 1 edges such that the graph remains connected after removal. If we project all removed edges back onto the original tree, a solution is valid if and only if every connected component in the original tree contains a leaf. We can then solve this with dynamic programming.
On Valid Solution VerificationIn this problem, a solution is invalid if and only if two leaves form a cycle or a node is disconnected from both trees. This corresponds to two leaves existing in the same connected component in the original tree. Conversely, the solution is valid. - This enspires us to consider necessary and sufficient conditions from the opposite perspective.
Implementation DetailsThe DP design: Let f_u/g_u be the number of valid configurations where the connected component containing node u has one/no leaf(s) respectively, assuming all connected components in the subtree are valid.
Initial state: For leaves: f_u = 1, g_u = 0. When u processes a new child:
[f_u \gets f_u \times (g_v + f_v) + g_u \times f_v ][g_u \gets g_u \times (g_v + f_v) ] Implementation``` #include<bits/stdc++.h> #define ll long long #define pb emplace_back using namespace std;
const int MAXN = 5000 + 10; const ll MOD = 998244353;
struct Edge { int to, next; } edges[MAXN << 1];
int head[MAXN], edgeCnt; int N; bool selected[MAXN], visited[MAXN]; ll dpA[MAXN], dpB[MAXN], pow2[MAXN];
void addEdge(int u, int v) { edges[++edgeCnt] = {v, head[u]}; head[u] = edgeCnt; }
int leafCount;
void traverse(int u, int parent) { if (!selected[u]) { leafCount++; dpA[u] = 1; dpB[u] = 0; return; } dpA[u] = 0; dpB[u] = 1; visited[u] = 1; for (int i = head[u]; i; i = edges[i].next) { int v = edges[i].to; if (v == parent) continue; traverse(v, u); dpA[u] = (dpA[u] * (dpB[v] + dpA[v]) % MOD + dpA[v] * dpB[u] % MOD) % MOD; dpB[u] = (dpB[u] * (dpB[v] + dpA[v])) % MOD; } }
int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; pow2[0] = 1; for (int i = 1; i <= N; i++) pow2[i] = 2LL * pow2[i - 1] % MOD; for (int i = 1; i < N; i++) { int x, y; cin >> x >> y; addEdge(x, y); addEdge(y, x); } for (int i = 1; i < N; i++) { int x; cin >> x; selected[x] = 1; for (int u = 1; u <= N; u++) visited[u] = 0, dpA[u] = dpB[u] = 0; ll result = 1; for (int u = 1; u <= N; u++) if (!visited[u] && selected[u]) { leafCount = 0; traverse(u, 0); result = result * dpA[u] % MOD * pow2[leafCount - 1] % MOD; } cout << result % MOD << "\n"; } return 0; }
### T3 Mod
- **Problem Statement**
Given a sequence a of n positive integers, consider the following function:
void mod(int x){ for(int i=1;i<=n;i++)a[i]=a[i]%x; }
You can execute this function an arbitrary number of times, and each call can have any positive integer parameter x. How many different final sequences a can be obtained? Output the answer modulo 998244353.
For 50% of the test cases, we have a_i = i.
- **Solution**
First, consider the special case. By manual exploration, one can discover that the resulting sequence must have the form: 1, 2, 3, ..., x_1, 0, 1, 2, ..., x_2, 0, 1, 2, ..., x_3, ..., with all values less than x_1 + 1.
It's not hard to verify this is also a sufficient condition, since we can insert all positions of 0 into the modular value set (not necessarily in ascending order). We can enumerate x_1 and apply an O(n²) DP internally. For general data, we extend this approach.
On DP Design and Avoiding Double CountingFirst, the DP formulation: Let f_{i,j} be the number of different original arrays that end up with value j after operations, given the original value was i.
We enumerate the position x of the first 0 and run DP with initial state f_{x,0} = 1.
Transitions:
- f_{i+1,j+1} += f_{i,j}
- if exists a_w = i: f_{i,j} = sum_{k=0}^{x-1} f_{lst,k} (for all 0 ≤ j ≤ min(x-1, i-lst-1))
Implementation```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 500 + 10;
const int MOD = 998244353;
int N, arr[MAXN], maxVal, present[MAXN];
ll dp[MAXN][MAXN];
void addMod(ll &x, ll y) {
x = (x + y) % MOD;
}
ll compute(int startPos) {
memset(dp, 0, sizeof(dp));
dp[startPos][0] = 1;
int last = 0;
for (int i = 1; i <= maxVal; i++) {
if (present[i]) {
ll sum = 0;
for (int j = 0; j < startPos; j++) addMod(sum, dp[last][j]);
for (int j = 0; j <= i - last - 1; j++) addMod(dp[i][j], sum);
last = i;
}
for (int j = 0; j < startPos; j++) addMod(dp[i + 1][j + 1], dp[i][j]);
}
ll ret = 0;
for (int i = 0; i < startPos; i++) addMod(ret, dp[maxVal][i]);
return ret;
}
int main() {
freopen("mod.in", "r", stdin);
freopen("mod.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
ll answer = 0;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
maxVal = max(maxVal, arr[i]);
present[arr[i]] = 1;
}
for (int i = 1; i <= maxVal + 1; i++) addMod(answer, compute(i));
cout << (answer + 1) % MOD;
return 0;
}
DAY1
Morning contest went well, achieved AK.
Afternoon: solved T3 from day0.
DAY2
Evening attempt at UNR with larsr. Spent an hour on the first problem, could only devise an O(n³) solution, which turned out to be flawed (though easily fixable to pass). After checking others' progress, found that nobody solved T1, so gave up. Later wrote some blog posts and adjusted the environment before heading back.
DAY3
Morning: solved two problems, then tackled a data structure problem by yyc, gaining deeper insights into segment tree divide-and-conquer. Learned about parallel binary search in the afternoon, though spent the whole afternoon debugging due to insufficient array size and long long issues.
Feeling quite unproductive today.
Evening: wrote blog posts. Later participated in a mock contest: T1 was straightforward, T2 involved subset inclusion-exclusion, T3 was a linear basis template problem but I couldn't solve it, T4 was mysterious. Final score: 100 + 80 + 80 + 20 = 280.
DAY4
Morning: studied linear basis.
Afternoon: worked on practice problems from the study materials. Evening mock contest: spent 2 hours on T1, implemented a greedy approach that passed all large samples. Strange how nobody else finished T1? T2 didn't make sense at all, with the ability to change objectives? T3 seemed doable after 30 minutes of thought, so I went for it. With 40 minutes remaining, passed all large samples on T3. Created two hack cases, but the solution failed. Fixed and fixed, then realized I needed inclusion-exclusion. Wrote 100 lines but couldn't finish on time. Final score: how come I got points? Wait, maybe I did? How did I get rank 7? Oh right, everyone was watching the Chinese national football team.
T2 String
- Problem Statement:
Given n distinct binary strings of length m, a binary string S of length nm is considered good if and only if S[1:m], S[m+1:2m], ..., S[(n-1)m+1:nm] are pairwise distinct, and each substring appears in {S_1, S_2, ..., S_n}. You have a typewriter with probability p of typing an error (1 becomes 0, 0 becomes 1). You are intelligent enough to produce a good string and can adjust your strategy based on current output. What is the probability of successfully typing a good string? n, m ≤ 10³.
- Solution:
Consider performing all operations on a Trie tree. It's not hard to see that a valid string corresponds to traversing the tree n times, picking one string from the set each time. In other words, each edge on the Trie is traversed exactly as many times as it appears in the paths.
Since we can change the target during traversal, considering strings directly is infeasible; we must process character by character.
Assume we've reached node u, with the left subtree edge traversed c_1 times and the right subtree edge c_2 times. This reduces to: with c_1 zeros and c_2 ones, produce exactly c_1 + c_2 characters. We can solve this with DP. Then multiply the results from both child nodes. Time complexity: O(nm).
Implementation``` #include<bits/stdc++.h> #define ll long long #define db double using namespace std;
const int MAXNODES = 2e6 + 10; const int MAXLEN = 1e3 + 10;
db result = 1; db prob[MAXLEN][MAXLEN];
struct Trie { int child[MAXNODES][2]; int cnt[MAXNODES]; int nodeCnt = 1;
void insert(const string& str) {
int p = 1;
for (int i = 0; i < str.size(); i++) {
int bit = str[i] - '0';
if (!child[p][bit]) child[p][bit] = ++nodeCnt;
p = child[p][bit];
cnt[p]++;
}
}
void solve(int u) {
if (!u) return;
result *= prob[cnt[child[u][0]]][cnt[child[u][1]]];
solve(child[u][0]);
solve(child[u][1]);
}
} tr;
int n, m;
int main() { freopen("string.in", "r", stdin); freopen("string.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); db tb; cin >> n >> m >> tb; tb = max(tb, 1.0 - tb); const db p = tb; const db q = 1.0 - tb;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
tr.insert(str);
}
prob[0][0] = 1.0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 && j == 0) continue;
if (i > j) {
prob[i][j] = prob[i - 1][j] * p;
if (j > 0) prob[i][j] += prob[i][j - 1] * q;
} else {
if (j > 0) prob[i][j] += prob[i][j - 1] * p;
if (i > 0) prob[i][j] += prob[i - 1][j] * q;
}
}
}
tr.solve(1);
cout << fixed << setprecision(12) << result;
return 0;
}
DAY5
----
Solved some linear basis problems and two DP problems. Evening water-drinking contest.
DAY6
----
Became the brute-force expert: 100 + 0 + 72 + 40 = 212. However, after the contest I understood both T3 and T2 with just one hint. Is this a plateau? QAQ
DAY7
----
### T3 Match
- **Problem Statement:**
Floating Island is hosting an annual magic tournament with n participants and three different venues. Each contestant has a different ranking at each venue. As the referee, Little One can choose any two non-eliminated contestants to compete and specify a venue. The weaker contestant at that venue gets eliminated.
The magical world keeps changing: there are queries and modifications where each modification swaps the rankings of two contestants at one venue.
For each query, Little One asks whether contestant x can possibly win the tournament. Help answer these questions.
n, q ≤ 10⁵
- **Solution:**
First, for each sequence a_i, draw a directed edge to a_{i+1}. It can be observed that only nodes in the strongly connected component formed by the heads of the three chains can defeat all others. Further observation reveals that this SCC S satisfies: it consists of the first len positions from each of the three chains, with |S| = len. In other words, we need to find the minimum len such that S_0 = {a_{0,1}, a_{0,2}, ..., a_{0,len}}, S_1 = {a_{1,1}, a_{1,2}, ..., a_{1,len}}, S_2 = {a_{2,1}, ..., a_{2,len}} are all identical.
Thus, we maintain for contestant i the minimum position L_i and maximum position R_i across the three rankings. We add 1 to the range [L_i, R_i - 1]. The answer is the first position with value 0. This is maintained with a segment tree. Time complexity: O((n + q) log n).
> During the contest, I got 72 points using brute-force tarjan. This teaches us that for graph problems, we don't necessarily need to analyze the entire graph structure—only the portion relevant to the answer, then transform accordingly.
Implementation```
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int minimum(int x, int y) { return (x < y) ? x : y; }
int maximum(int x, int y) { return (x > y) ? x : y; }
void updateMin(int &x, int y) { if (x > y) x = y; }
void updateMax(int &x, int y) { if (x < y) x = y; }
const int MAXN = 1e5 + 10;
int n;
int arr[3][MAXN];
int rankPos[3][MAXN];
int leftBound[MAXN], rightBound[MAXN];
int answer;
namespace SegTree {
#define leftChild (o << 1)
#define rightChild (o << 1 | 1)
#define mid ((l + r) >> 1)
int lazy[MAXN << 2];
int minVal[MAXN << 2];
void pull(int o) { minVal[o] = minimum(minVal[leftChild], minVal[rightChild]); }
void applyTag(int o, int v) {
minVal[o] += v;
lazy[o] += v;
}
void pushDown(int o) {
if (!lazy[o]) return;
applyTag(leftChild, lazy[o]);
applyTag(rightChild, lazy[o]);
lazy[o] = 0;
}
void rangeAdd(int o, int l, int r, int ql, int qr, int v) {
if (ql > qr) return;
if (ql <= l && r <= qr) {
applyTag(o, v);
return;
}
pushDown(o);
if (ql <= mid) rangeAdd(leftChild, l, mid, ql, qr, v);
if (mid < qr) rangeAdd(rightChild, mid + 1, r, ql, qr, v);
pull(o);
}
int findFirst(int o, int l, int r) {
if (l == r) return l;
pushDown(o);
if (minVal[leftChild] == 0) return findFirst(leftChild, l, mid);
return findFirst(rightChild, mid + 1, r);
}
}
using namespace SegTree;
void modify(int player, int newRank, int venueId) {
rangeAdd(1, 1, n, leftBound[player], rightBound[player] - 1, -1);
rankPos[venueId][player] = newRank;
leftBound[player] = rightBound[player] = rankPos[0][player];
for (int i = 1; i < 3; i++) {
updateMin(leftBound[player], rankPos[i][player]);
updateMax(rightBound[player], rankPos[i][player]);
}
rangeAdd(1, 1, n, leftBound[player], rightBound[player] - 1, 1);
}
signed main() {
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> n >> T;
for (int venueId = 0; venueId < 3; venueId++) {
for (int j = 1; j <= n; j++) {
cin >> arr[venueId][j];
rankPos[venueId][arr[venueId][j]] = j;
}
}
for (int i = 1; i <= n; i++) {
leftBound[i] = rightBound[i] = rankPos[0][i];
for (int venueId = 1; venueId < 3; venueId++) {
updateMin(leftBound[i], rankPos[venueId][i]);
updateMax(rightBound[i], rankPos[venueId][i]);
}
rangeAdd(1, 1, n, leftBound[i], rightBound[i] - 1, 1);
}
answer = findFirst(1, 1, n);
while (T--) {
int opt;
cin >> opt;
if (opt == 2) {
int venueId, x, y;
cin >> venueId >> x >> y;
venueId--;
int rankX = rankPos[venueId][x];
int rankY = rankPos[venueId][y];
modify(x, rankY, venueId);
modify(y, rankX, venueId);
answer = findFirst(1, 1, n);
} else {
int x;
cin >> x;
cout << (rankPos[0][x] <= answer ? "Yes" : "No") << "\n";
}
}
return 0;
}
T2 Wolf
- Problem Statement:
There are n wolves in a pack on Floating Island, numbered 1 to n. Wolf i starts at grid vertex (x_i, y_i). In each round, each wolf moves to one of the four adjacent vertices: (x-1, y), (x+1, y), (x, y-1), or (x, y+1). After m rounds, all n wolves have moved to the same grid vertex. Count the number of valid movement sequences, modulo 10⁹ + 7.
Two movement sequences are different if there exists a round where some wolf's direction differs.
n ≤ 50, x_i, y_i ≤ 10⁵
- Solution:
Consider which vertices a single point can reach. It clearly forms a tilted square. Rotate the board by 45 degrees: a point's coordinates become (x + y, x - y). A move now corresponds to (±1, ±1), so the two coordinates can be handled independently. Enumerate the final x + y or x - y coordinate and derive the formula.
When encountering large x, y values, consider separating the two dimensions through coordinate transformation.
DAY8
Forgot to record.
11.26
T4
First, it's not hard to see that after adding a character, all borders of S can contribute to the answer. Specifically, for a border of length k, it contributes 1 to queries for k. An O(n²) solution follows naturally. (True, but in contest I wrote brute-force jumping wich passed.) This is equivalent to building the failure tree of the string, then for each new position, adding 1 to the path from its failure tree parent to the root. Offline queries can use heavy-light decomposition, but online queries are not possible.
Consider using heavy-light decomposition ideas. By designating heavy children, we can efficiently maintain chain information. Considering operations on borders, the following property is useful:
- All borders of a string can be partitioned into O(log n) arithmetic progressions.
For a node u with failure tree parenet fa, when u has a child v, we set v as the heavy child of u. Then apply a Fenwick tree. The time complexity is O(n log² n). However, the editorial claims O(n log n) and I'm not sure how to prove it.
Notes
- For XOR on a Trie tree, you can apply lazy propagation with bitwise operations. For global +1 operations, greedy from LSB to MSB works.