### ko_osaga's blog

By ko_osaga, history, 3 years ago,

Update (2021.10.28): Editorial, Division 1 Gym, Division 2 Gym are prepared.

Hello!

For external accounts, the contest is ready now.

List of relevant previous contests:

Enjoy!

• +188

 » 3 years ago, # |   +53 How to solve G, M?
•  » » 3 years ago, # ^ |   +47 G: The player with HP $X$ dies if and only if there exists a subsegment with sum at most $-X$. The case with ultimate is similar since the HP doesn't change.
 » 3 years ago, # |   +44 How to solve Beautiful Numbers from Div2, Or Machine, Periodic Ruler ?Or Machine looks like a grap. In Beautiful Numbers I tried greedy in multiset by finding the closest groups such 91, 82,73 and etc.. ,but it doesn't work.
•  » » 3 years ago, # ^ |   +50 Periodic Ruler: Let's first find which $d$ satisfy that there exists a $s$ such that $\forall t, s[t]=s[t+d]$. We take any two $i,j$ such that $a_i \ne a_j$, it is obvious that all divisors of $|x_i-x_j|$ cannot be the period. Let's take the distances of all the two different characters and their divisors, which are all the numbers that do not satisfy the condition. Then, we have to remove the values that are impossible as minimum periods. Note that if $d$ is a period of $S$, then $S$ must satisfy $S_i = S_j$ for all $i \equiv j \pmod d$. If for some $0\leq i const int N = 1e6 + 50; long long x[N], a[N]; int main() { long long n; std::cin >> n; for (int i = 1; i <= n; ++i) { std::cin >> x[i] >> a[i]; } std::vector divisors; auto divide = [&](long long x) { for (long long i = 1; i * i <= x; ++i) if (x % i == 0) { divisors.push_back(i); if (i != x / i) divisors.push_back(x / i); } }; for (int i = 1; i <= n; ++i) for (int j = 1; j < i; ++j) if (a[i] != a[j]) { long long t = std::abs(x[i] - x[j]); divide(t); } auto check = [&](int d) { std::vector s(d, -1); int filled = 0; for (int i = 1; i <= n; ++i) { int y = (x[i] % d + d) % d; if (s[y] == -1) { s[y] = a[i]; ++filled; } else if (s[y] != a[i]) return true; } if (filled != d) return false; for (int t = 1; t < d; ++t) { bool ok = true; for (int i = 0; i < d; ++i) if (s[i] != s[(i + t) % d]) { ok = false; break; } if (ok) return true; } return false; }; for (int d = 1; d <= 50; ++d) if (check(d)) { divisors.push_back(d); } std::sort(divisors.begin(), divisors.end()); divisors.erase(std::unique(divisors.begin(), divisors.end()), divisors.end()); long long sum = 0; for (long long x : divisors) sum += x; printf("%lld %lld\n", divisors.size(), sum); }  •  » » » 3 years ago, # ^ | +18 Wow, great solution. Thank you Qingyu !  » 3 years ago, # | +80 Thank you for the participation!Problems were prepared by .o. A Doju B tamref C spectaclehong D queued_q EJ kipa00 F ko_osaga GKL jh05013 H nong I mo_onrabbit2 M Editorials and Gym contest are not prepared as of now. I will work on it. •  » » 3 years ago, # ^ | +10 Could you please public the jury's solutions? Maybe it's helpful if there's no tutorial available yet. Thanks!  » 3 years ago, # | +22 How to solve A? •  » » 3 years ago, # ^ | +17 You realize that$E_{ij}$can be decomposed as$P_i+Q_j$, and then reduce the problem to having row and column sums and trying to find a construction that gives these sums •  » » » 3 years ago, # ^ | +1 How to find the sum of the first/last row/column? •  » » » » 3 years ago, # ^ | ← Rev. 2 → +18 Denote by$P_i$the sum of the$i$-th row and$Q_i$the sum of the$i$-th column. Since we know$P_{2}, ..., P_{n-1}$and$P_1 - P_2 - P_3 - ... - P_n$, we can get$P_1 - P_n$. Similarly we get$Q_1 - Q_n$. Now since$\sum_{i=1}^n P_i = \sum_{i=1}^n Q_i$, we can also get$(P_1+P_n) - (Q_1+Q_n)$. Thus, we can know$P_1, P_n, Q_1, Q_n$up to an unknown additive constant. Finally using an element in$E$(say$E_{11}$) to calculate the unknown additive constant.  » 3 years ago, # | +11 Was it the intention to prevent$O(n \log n)$from passing in B? Time limit is rather ambiguous, our solution barely fits locally but fails at test 10 in the system. •  » » 3 years ago, # ^ | ← Rev. 3 → +8 Due to unusual time limit I suppose it was intended. By the way there exists linear solution. •  » » 3 years ago, # ^ | +10 Yes. Model solution is$O(n)$, and it passes TL very leniently.  » 3 years ago, # | +10 Any hints for L and F? :) •  » » 3 years ago, # ^ | ← Rev. 2 → +20 L: Compute MCMF in$O(VE \log V)$by Dijkstra with potentials. The symmetric difference of matching from$G - {e}$and$G$constitutes a path from$s \rightarrow t$. If you add an edge from sink to source, you can compute the path with Dijkstra, using the same potentials. •  » » » 3 years ago, # ^ | +8 Well, you may need one more path, so you need two runs of Dijkstra algorithm. And I failed to squeeze time limit. •  » » » » 3 years ago, # ^ | +8 Sorry, the TL is tight to break SPFA approach. And I don't understand why we need one more path. •  » » » » » 3 years ago, # ^ | +8 Consider test 2 2 3 1 1 2 1 2 10 2 2 2 Best set is using only edge #2. But if you remove it, you can add both #1 and #3. But first path search can do only one of them. •  » » » » » » 3 years ago, # ^ | ← Rev. 2 → +8 L(2) -> R(2) -> L(1) -> R(1) is a single path?(Edit: Yes, the edge is not added from$t$to$s$. It is added from sink to source. My bad) •  » » » » » » 3 years ago, # ^ | +21 •  » » » » » » » 3 years ago, # ^ | +11 Okey, I didn't got capacity of T -> S edge correctly. But my solution gets TL anyway. •  » » 3 years ago, # ^ | +20 F: Random approach does not help. You would need to start with a deterministic solution which uses$2\sqrt{V}+\alpha \approx 2000+30$queries where$V=1\,000\,000$:$t = Query(1, 1\,000\,000)$gives a vertex which must be included in the cycle. Now$a_i = Query(t, i)$for i=1 to 999,$b_i = Query(t, i*1000)$for i=1 to 1000. Any positive integer$n \le 1\,000\,000$can be represented as$x*1000-y$, where$1 \le x \le 1000, 0 \le y \le 999$, so some results of the query(namely$b_x$and$a_y$) will be the same.$Query(t, c) = Query(t, d)$gives you the information that$c-d$is multiple of the cycle length$n$. Factorize$D=c-d$, and for each prime factor$p$, query$Query(t, D/p)$. If this equals to$t$, divide$D$by$p$and continue the process. Else, the answer$n$should be multiple of$p^e$($e=ord_p(D)$), and go on to the next prime factor. For$Q \le 900$, you should apply various tricks to optimize the second process. All you need is: for all$n \le 1\,000\,000$, one of$q_i - q_j$is a multiple of$n$. Note that you can query some large integers like$2\cdot 10^{18}$; this helps a lot. Intended solution uses$\sqrt{2V/3}+\alpha$queries. Some hints about various tricks 200000 divides 400000, 600000, 800000 and so on 3 divides$3\cdot 2^k$999999000000 is divisible by 999999 and 1000000  » 3 years ago, # | +26 How to solve K? •  » » 3 years ago, # ^ | +55 There is a well known problem about finding a Hamiltonian path in an implicit tournament graph in$O(n \log n)$(next to last GP of Gomel, I think). After you know the path, you are only interested in finding segments that are SCC. For that it's enough to find the leftmost outgoing edge from each vertex. Let's try all possibilities for 2 sports it should be better in, then we have queries "min on rectangle", solve them using scanline with segment tree. •  » » » 3 years ago, # ^ | +18 I see, thanks. •  » » 3 years ago, # ^ | +34 It can be proven that the SCC forms a total order. The SCC can be computed with Kosaraju's algorithm. To speed up, you can find an unvisited vertex with segment trees. •  » » » 3 years ago, # ^ | +18 Thanks. Cute transition to SCCs in tournament graphs. •  » » 3 years ago, # ^ | +44 For a tournament, node degrees determine connected components. Degrees can be found with inclusion exclusion (degree of person i = #people they beat in races 1, 2 + #people they beat in races 1, 3 + #people they beat in races 2, 3 — 2 * #people they beat in all races). To find these, use Fenwick trees for 2d cases, and your choice of 2d structure for 3d case.  » 3 years ago, # | +23 I swear that J feels harder than A, C, E. •  » » 3 years ago, # ^ | +3 Can you explain solution for E? •  » » » 3 years ago, # ^ | +8 The editorial is already published below and I found it hard to formulate solution in few words (I feel like there is a ton of indexing and variables and it would be total mess), so hopefully you can refer to the editorial.  » 3 years ago, # | +62 Some late advertisements:My favorite problem in this set was I (Organizing Colored Papers) by nong. He is not only a good problem setter but an indie game developer who created Teamfight Manager with his brother. If you want to see competitive programmers in great success, you may want to support their work. But they don't need your help: Their work is already appreciated by Steam users, tons of pro gamers and streamers including DWG KIA ShowMaker and this Russian streamer. Just become a part of the great game!  » 3 years ago, # | +23 How to solve C? •  » » 3 years ago, # ^ | +50 For a tree, we add the edges in the non-increasing order of weights. Let's denote the component where$u$is currently located is$A_u$. For an edge$(u,v,w)$, we have$v_T(u_0,v_0)=w (\forall u_0 \in A_u, v_0 \in A_v)$. Therefore, if two trees are in the same group, then for all weights$w$, there must be all components connected by edges with weight$w$that are equivalent. Note that as long as the previous merges are the same, then in this round of merging, it is only necessary to ensure that the minimum values of all components are the same. You can use std::map to get a deterministic solution, or just choose a proper hash function. Code (hash)#include template struct Z { int v; Z(long long _v = 0) : v((_v % mod + mod) % mod) {} int inc(int x, int y) const { x += y - mod; return x + (x >> 31 & mod); } int mul(int x, int y) const { return 1ll * x * y % mod; } Z operator+(const Z &rhs) const { return Z(inc(v, rhs.v)); } Z operator*(const Z &rhs) const { return Z(mul(v, rhs.v)); } bool operator<(const Z &rhs) const { return v < rhs.v; } bool operator==(const Z &rhs) const { return v == rhs.v; } bool operator!=(const Z &rhs) const { return v != rhs.v; } }; const int bases[] = { 2333, 19260817, 114514191 }; typedef Z<998244353> Z0; typedef Z<1000000007> Z1; typedef Z<1000000009> Z2; typedef Z<1000000021> Z3; const int N = 1e6 + 50; int n, d, f[N]; std::mt19937 s(std::chrono::steady_clock::now().time_since_epoch().count()); std::vector> edges; std::vector> ebuc[N]; struct number { Z0 _0; Z1 _1; Z2 _2; Z3 _3; number(int v = 0) : _0(v), _1(v), _2(v), _3(v) {} number(Z0 _0, Z1 _1, Z2 _2, Z3 _3) : _0(_0), _1(_1), _2(_2), _3(_3) {} } a[N], a2[N], a3[N], a4[N], a5[N], h[N]; number operator+(const number &x, const number &y) { return number(x._0 + y._0, x._1 + y._1, x._2 + y._2, x._3 + y._3); } number operator+=(number &x, const number &y) { return x = x + y; } number operator*(const number &x, const number &y) { return number(x._0 * y._0, x._1 * y._1, x._2 * y._2, x._3 * y._3); } bool operator<(const number &x, const number &y) { if (x._0 != y._0) return x._0 < y._0; if (x._1 != y._1) return x._1 < y._1; if (x._2 != y._2) return x._2 < y._2; return x._3 < y._3; } bool operator==(const number &x, const number &y) { return x._0 == y._0 && x._1 == y._1 && x._2 == y._2 && x._3 == y._3; } bool operator!=(const number &x, const number &y) { return x._0 != y._0 || x._1 != y._1 || x._2 != y._2 || x._3 != y._3; } int find(int x) { while (x != f[x]) x = f[x] = f[f[x]]; return x; } void merge(int x, int y) { x = find(x), y = find(y); if (x > y) std::swap(x, y); f[x] = y; } number getHash(std::vector &b, number *a) { number r(0); for (int i = 0; i < b.size(); ++i) r += a[i] * number(b[i]); return r; } number getHash(std::vector &b, number *a) { number r(0); for (int i = 0; i < b.size(); ++i) r += a[i] * b[i]; return r; } number pairHash(int u, int v) { return number(u) * number(1e6) + number(v); } std::map map; void load(number &h) { for (int i = 1; i <= n; ++i) f[i] = i; std::vector buc; for (int i = 1; i < n; ++i) { int u, v, w; std::cin >> u >> v >> w; edges.emplace_back(u, v, w); buc.push_back(w); } auto uni = [&](auto &x) { std::sort(x.begin(), x.end()); x.erase(std::unique(x.begin(), x.end()), x.end()); }; uni(buc); h = number(2333333) * getHash(buc, a); for (auto [u, v, w] : edges) { int t = std::lower_bound(buc.begin(), buc.end(), w) - buc.begin(); ebuc[t].emplace_back(u, v); } std::vector eigen; for (int i = n; i >= 0; --i) if (!ebuc[i].empty()) { std::vector set; std::vector vertecies; std::vector> vec; for (auto [u, v] : ebuc[i]) { vertecies.push_back(find(u)); vertecies.push_back(find(v)); } uni(vertecies); for (auto [u, v] : ebuc[i]) merge(u, v); for (int y : vertecies) vec.emplace_back(find(y), y); std::sort(vec.begin(), vec.end()); std::vector blocks; number old = vec[0].first; for (auto [fx, x] : vec) { if (fx != old) { uni(blocks); set.emplace_back(getHash(blocks, a2)); blocks.clear(); old = fx; } blocks.emplace_back(x); } uni(blocks); set.emplace_back(getHash(blocks, a3)); std::sort(set.begin(), set.end()); eigen.emplace_back(getHash(set, a4)); } h += getHash(eigen, a5); edges.clear(); for (int i = 0; i <= n; ++i) ebuc[i].clear(); } int ans[N]; int main() { for (int i = 0; i < N; ++i) { a[i] = number(s()), a2[i] = number(s()), a3[i] = number(s()); a4[i] = number(s()), a5[i] = number(s()); } std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::cin >> d >> n; std::vector> vec; for (int i = 1; i <= d; ++i) { load(h[i]); vec.emplace_back(h[i], i); } std::sort(vec.begin(), vec.end()); int lst = 0; for (int i = 0; i < vec.size(); ++i) { if (i == 0 || vec[i].first != vec[i - 1].first) { lst = ans[vec[i].second] = vec[i].second; } else { ans[vec[i].second] = lst; } } for (int i = 1; i <= d; ++i) std::cout << ans[i] << " "; return 0; }   » 3 years ago, # | +69 Editorials are now ready, enjoy!  » 3 years ago, # | 0 Hello, where is the XXII Open Cup Schedule, or the next open cup contest? •  » » 3 years ago, # ^ | +8 arthurconmy here . Next round is on 7 November.  » 3 years ago, # | +10 Apparently in problem B in every test the number of Y-s in strings$S$and$T\$ is equal, even though it is not mentioned in the statement
•  » » 3 years ago, # ^ |   0 It is translator's mistake (who is me). Sorry!
 » 3 years ago, # |   +8 Hyeong ko_osaga, can you share the test cases?
•  » » 3 years ago, # ^ |   0 You can find some of them (not all) in https://drive.google.com/drive/u/0/mobile/folders/1-BG9lmWvPeN4nayQ13YDHOpUvPWPdA7A?usp=sharing.
•  » » » 3 years ago, # ^ |   0 Thank you! 감사합니다
 » 2 years ago, # | ← Rev. 2 →   0 I'm misunderstanding K.1 12 2 3 3 4 45 56 6(Instead of this being the actual positions, let this be the physical orderings of the players, where the indices they are at are their actual places in the respective tournament)From what I'm understanding, it won't have the edge (2,4) in it (or 2,3 into 3,4). If you call dfs(1), it looks like it'll result in calling dfs(6). Dfs(2) then calls into dfs(5), etc. Then, when you do it backwards (with a min segtree this time), Dfs(6) calls dfs(1), etc. so you add the same edges.So the edges in the graph are now (1,6), (2,5), (3,4).This isn't right, so I know that there's a gap in my understanding, but I don't know what it is. It kinda makes more sense if you don't do a DFS and process it in a specific order to add edges each time, but in this case it still requires the specific ordering of processing like, 6 5 1 2 (from top down) which is a bit sus since you don't know the correct ordering from the get go.My approach was to use sets to process the highest value that the current index beats (and vice versa for the bottom up) but it fails in this test case:5 61 16 52 34 43 2where the edge (1,4) is missing even if you go both ways, so the editorial isn't talking about something like this either.So what is it talking about? Evidently the editorial is straight over my head. What did I miss?