### Qingyu's blog

By Qingyu, history, 6 days ago,

Let's discuss problems here.

• +90

 » 6 days ago, # |   +34 Is there an official editorial? If not, then how to solve J?
•  » » 6 days ago, # ^ |   +61
 » 6 days ago, # |   +19 How to solve problem D? MO algorithms gives TLE. I have an idea with Merge Sort Tree(as segment tree,but we store elements) . Will it pass ?
•  » » 6 days ago, # ^ |   +37 We solved D with Mo's Algorithm in under 2s. The idea is to have purely $O(Q \sqrt N)$ complexity (no log factor). You can do that with linked lists and undo (change inserions to erase and adapt Mo's Algo accordingly). Solution#include using namespace std; const int BS = 128; struct List { int n; vector ops; vector val2pos; vector nxt, prv; long long ans = 0; List(const vector& p) : n(p.size()), val2pos(n, -1), nxt(n, -1), prv(n, -1) { for (int i = 0; i < n; ++i) { val2pos[p[i]] = i; } for (int i = 0; i < n; ++i) { if (i > 0) prv[i] = i - 1; if (i + 1 < n) nxt[i] = i + 1; ans += get(i, nxt[i]); } } int get(int a, int b) { if (a == -1 || b == -1) return 0; return abs(val2pos[a] - val2pos[b]); } long long Get() { return ans; } void Erase(int x) { ops.push_back(x); int nx = nxt[x], pr = prv[x]; if (pr != -1) nxt[pr] = nx; if (nx != -1) prv[nx] = pr; ans += get(pr, nx) - get(pr, x) - get(x, nx); } void Undo() { int x = ops.back(); ops.pop_back(); int nx = nxt[x], pr = prv[x]; if (pr != -1) nxt[pr] = x; if (nx != -1) prv[nx] = x; ans -= get(pr, nx) - get(pr, x) - get(x, nx); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector p(n); for (int i = 0; i < n; ++i) { cin >> p[i]; --p[i]; } vector>> qrs(n); vector ans(q); for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; --l; --r; qrs[l / BS].emplace_back(r, l, i); } for (int i = 0; i < n; i += BS) { auto& qs = qrs[i / BS]; sort(qs.rbegin(), qs.rend()); List L(p); for (int j = 0; j < i; ++j) L.Erase(p[j]); int now_r = n - 1, now_l = i; for (auto [r, l, j] : qs) { while (now_r > r) L.Erase(p[now_r--]); while (now_l < l) L.Erase(p[now_l++]); ans[j] = L.Get(); while (now_l > i) L.Undo(), now_l--; } } for (int i = 0; i < q; ++i) { cout << ans[i] << '\n'; } return 0; } 
•  » » » 6 days ago, # ^ |   +11 Thank you bicsi !
•  » » » 6 days ago, # ^ |   +19 better coded than ours :). An observation: the final complexity is $O(n \sqrt q)$.
•  » » 6 days ago, # ^ | ← Rev. 3 →   +37 We used Mo algorithm with linked list over sorted segment. Deletion from linked list is $\mathcal{O}(1)$ and you use rollbacks to insert elements. To make this work with Mo algorithm sort queries by $(r/B, l, r)$. Then for each block you have $l \in [0, r)$ and $r \in [B * block, (B+1)*block)$, so insert all items from range $[0, (B+1)*block)$ into linked list, then to handle each query in sorted order you: Permanently remove some elements from left side Temporarily remove some elements from right side Retrieve answer Rollback all deletions from right side
•  » » » 6 days ago, # ^ |   +8 Thank you ATSTNG ! Obviously, linked list is better than set.
 » 6 days ago, # |   +39 How to solve problems G from Div1 and M from Div2 ? Our team thought may be random will work for M.
•  » » 6 days ago, # ^ |   +35 My Solution for Div.2 M: Let's shuffle the given permutation. The interactor is not adaptive, so we can assume that each location has an equal probability of containing a treasure, assuming it is $p$. Suppose we examine the first 20 locations in turn, then the probability that the first 20 positions do not contain any treasure is $(1-p)^{20}$. If this happens, then we can assume that $p$ is sufficiently small, so that among the remaining positions, we can assume that the probability of picking any two positions, both of which contain the treasure is small ($p^2$). Then, we perform about 20 more queries, choosing 2 adjacent positions for each queries. There is a $p^2$ probability of missing the answer. But since $p$ is small enough, $p^2$ is also small enough. If we still do not find an answer, then we consider the distribution of the treasure to be more sparse, and continue to increase the number of locations per query. The limit on the number of queries does not appear to be strict, and can be passed by taking a random reasonable set of strategies. Code
•  » » » 6 days ago, # ^ |   +26 Thank you Qingyu ! Very interesting observation.
 » 6 days ago, # |   +31 Is there any div.2 editorial available?
•  » » 6 days ago, # ^ | ← Rev. 2 →   +37 Problem A~K are the same as Div.1 problemsDiv.2 L: The Euler characteristic shows that $V-E+F-C=1$ on any planar graph $G$. So we have $C=V-E$ and the answer is simply $\max(n-m,0)$Div.2 M: hereDiv.2 N: After convert each portkey to intervals, the problem is essentially the same as CF786B. There will be up to $5n+m$ endpoints of the interval, but only $n+m$ of them will be useful. CodeDiv.2 O: The distance of the two points is just $d=|x_1-y_1|+|x_2-y_2|$, and note that the given graph is a bipartite graph, so the given condition is equivalent to $d \geq w$ and $d\equiv w \pmod 2$.
•  » » » 6 days ago, # ^ |   +18 for N, it is possible to use BFS also.
 » 6 days ago, # |   +38 For problem K, we had the following algorithm (which gave WA, but we apparently had a proof of):Root the tree at any vertex which is not a leaf ($n = 2$ is handled manually), and order leaves in pre-order. Then we will try to pair up leaves such that all paths go through one common vertex (not necessarily that root). This can be done by, say, pairing up the leaves $0, \lfloor m/2 \rfloor$, $1, 1 + \lfloor m/2 \rfloor$ and so on, and pair the last leaf with the first leaf.Our proof was based on the fact that the vertices that are in a path but not in the previous path form at most two chains, and if we root the tree at the common vertex of all such paths, then the chains are no longer candidates for the thief's position.Could someone point out a counterexample to this algorithm if the proof sounds wrong?
•  » » 6 days ago, # ^ |   +26 The problem is that leaf $\lfloor m/2 \rfloor$ can be in the middle of a subtree. If you first scan half of the subtree, then later the other half, the bad guy could move between the two parts of the subtree.
 » 6 days ago, # |   +23 Is there somewhere better explanation of problem I? It seems that a lot of important details skipped in the Editorial's explanation.
•  » » 6 days ago, # ^ |   +38 Assume that the drunkard is at position $x$, and let $\mathrm{dp}_{i,j}$ denote the probability of being at moment $i$ and passing through position $x+j$ at least once. Obviously $x$ does not affect the answer, so we only need to focus on the relative distance we are from the end point at each moment. We have $dp_{i,0}=1$, and $\mathrm{dp}_{i,j}=p \cdot \mathrm{dp}_{i+1,j}+(1-p) \cdot \mathrm{dp}_{i+1,j-a_{i+1}}$, so we can calculate all $\mathrm{dp}_{*,*}$ in $O(n^2)$. It's easy to observe that if the relative distance(signed) between the end point and the start point is $x$, then the probability of passing through $x$ at least once is just $\mathrm{dp}_{0,x}$, and the answer is $\frac{1}{2n+1} \sum_{i} \mathrm{dp}_{0,i}$. Code
 » 5 days ago, # |   +33 how to get an account?
•  » » 5 days ago, # ^ |   +8 You should probably ask one of closest sector's admin or register new sector. All information is here.
•  » » » 5 days ago, # ^ |   +5 How to find one of closest sector's admin?
•  » » » » 5 days ago, # ^ | ← Rev. 2 →   0 I don't know, maybe it would be a good solution to ask in site-register@opencup.org.
•  » » » » » 4 days ago, # ^ |   0 OK thankyou
 » 4 days ago, # |   +9 In problem G, it is not clear how to build the convex hull as for the set of points from example, it will be the monotonous ascending function. Is there any other explanations for problem G ? Endagorion Qingyu
•  » » 4 days ago, # ^ |   +13 My teammates just checked 50 points around)) I don't know why it works.
•  » » » 4 days ago, # ^ |   +18 AmDer Can you send your solution ?
•  » » » » 4 days ago, # ^ |   +18 Wow, it's 32 in the last send! Solution#include using namespace std; #define flush cout.flush using ll = long long; using ull = unsigned long long; using ld = long double; using pl = pair; const ll INF = 1e9 + 7; const ll mod = 1e9 + 7; const ll mod2 = 998244353; const ld eps = 1e-9; const ld PI = acos(-1); const ll MAGIC = 32; int main() { ios::sync_with_stdio(false); cin.tie(NULL); ll n; cin >> n; vector a(n), b(n), x(n); for (ll i = 0; i < n; ++i)cin >> a[i] >> b[i] >> x[i]; vector z; for (ll i = 0; i < n; ++i) { z.push_back({a[i], i}); z.push_back({b[i], i}); } z.push_back({1, -1}); sort(z.begin(), z.end()); ll m = z.size(); vector pref(m, 0.0); ld bad = 0.0; for (ll i = 1; i < m; ++i) { pref[i] = pref[i - 1] + (ld) x[z[i].second] * 0.5; bad += (ld) x[z[i].second] * 0.5; } ld res = -1e18; for (ll i = 0; i < m; ++i) { for (ll j = max(0ll, i - MAGIC); j <= i; ++j) { ld E = pref[i] + pref[j] - bad; E -= (ld) (z[i].first * z[j].first); res = max(res, E); } for (ll j = 0; j <= min(i, MAGIC); ++j) { ld E = pref[i] + pref[j] - bad; E -= (ld) (z[i].first * z[j].first); res = max(res, E); } } cout << fixed << setprecision(20); cout << res << "\n"; return 0; } 
•  » » » » » 4 days ago, # ^ |   +18 Thank you AmDer !
•  » » 4 days ago, # ^ |   0 Maybe someone from Div.1 will be able to explain this problem ?
•  » » » 3 days ago, # ^ |   +34 When we iterate $c$ over $X$ in ascending order, the slope of some lines increases. All we need to do is add a new line to the corresponding position. This can be done by using Li Chao Tree or convex hull trick.
•  » » » 3 days ago, # ^ |   0 Thank you Qingyu,senyaa! It is clear now.
•  » » 4 days ago, # ^ |   +44 google convex hull trick
 » 23 hours ago, # | ← Rev. 2 →   +1 Can anyone share the code for Problem B? I don't understand the last part of the editorial