mraron's blog

By mraron, history, 2 years ago,

We hope you enjoyed the whole problemset even though there were some technical difficulties.

Problem A
Problem B
Problem C

• +112

 » 2 years ago, # |   +5 Can somebody explain what A asks for?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +32 Well in simpler terms: you are given an a graph with $N$ nodes, initially without any edges and $U$ times you do the following: add an edge or remove an already present edge. This defines $U+1$ versions of this graph (first the "empty" one, then after the one with the first edge added etc.), then you are given queries of form $x,y,v$ in one query you should find some neighbour of $x$, $x'$ and some neighbour of $y$, $y'$ in the $v$th version so that the absolute value of $H_{ y' } - H_{ x' }$ is minimal (where the array $H$ is given initally). And the queries are online.
 » 2 years ago, # |   0 Does anyone have a working interval tree solution to problem A? Or is that bound to tle
•  » » 2 years ago, # ^ |   +17 Yes, the official one runs around 2.3s, we decided not to increase the limits too much as the sqrt decomposition idea runs much faster in practice. Here's the code: Multiple segtree official#include using namespace std; int n,d,u,*f; void init(int N, int D, int F[]) { n=N; d=D; f=&F[0]; } vector evs[100001]; vector> trs[100001]; void insert(int from, int ind, int L, int R, int i, int j, int to) { if(R& res) { while(1) { for(auto j:trs[from][ind]) { res.push_back(j); } if(L==R) { break ; } if(i<=(L+R)/2) { R=(L+R)/2; ind=2*ind; }else { L=(L+R)/2+1; ind=2*ind+1; } } } vector egyik, masik; void curseChanges(int U, int A[], int B[]) { u=U; for(int i=0;i,int> since; auto add=[&](int from, int L, int R, int to) { int pos1=lower_bound(evs[from].begin(), evs[from].end(), L)-evs[from].begin(); int pos2=prev(lower_bound(evs[from].begin(), evs[from].end(), R))-evs[from].begin(); insert(from, 1, 0, (int)evs[from].size()-1, pos1, pos2, to); }; for(int i=0;iB[i]) swap(A[i], B[i]); if(since.count(make_pair(A[i], B[i]))) { add(A[i], since[make_pair(A[i], B[i])], i+1, B[i]); add(B[i], since[make_pair(A[i], B[i])], i+1, A[i]); since.erase(make_pair(A[i], B[i])); }else { since[make_pair(A[i], B[i])]=i+1; } } for(auto i:since) { add(i.first.first, i.second, U+1, i.first.second); add(i.first.second, i.second, U+1, i.first.first); } egyik.reserve(500); masik.reserve(500); } void get_all(int x, int v, vector& to) { to.clear(); auto itx=upper_bound(evs[x].begin(), evs[x].end(), v); if(itx==evs[x].begin() || evs[x].empty()) return ; int posx=prev(itx)-evs[x].begin(); get(x, 1,0,(int)evs[x].size()-1, posx, to); } int question(int X, int Y, int V) { get_all(X,V,egyik); get_all(Y,V,masik); if(egyik.empty() || masik.empty()) return 1e9; sort(egyik.begin(), egyik.end()); sort(masik.begin(), masik.end()); int ans=1e9; int i=0, j=0; while(i<(int)egyik.size() && j<(int)masik.size()) { ans=min(ans, abs(egyik[i]-masik[j])); if(egyik[i]>n>>d>>u>>q; int *f=new int[n]; for(int i=0;i>f[i]; int *a=new int[u], *b=new int[u]; for(int i=0;i>a[i]>>b[i]; init(n,d,f); curseChanges(u,a,b); while(q--) { int x,y,v; cin>>x>>y>>v; cout<
•  » » » 2 years ago, # ^ |   +3 Can you share official implementation of "Save neighbor list by node, binary search by version" for A? I implemented something like this but was getting TLE.
•  » » » 23 months ago, # ^ |   -20 Then when I select a slower language(c++17 64bits) it got TLE... When I switched to c++11 it got accepted...
 » 2 years ago, # | ← Rev. 3 →   +14 I have a simpler idea for A, though I haven't implemented it. First, instead of storing the whole neighbor list each time, you just hold a size D array and for each index store whether there is a node there or not. Now for an update, just find any index without a node and put a node there or find index with that node take it away. Now you can hold each update for each index separately, so you don't store the list each time. If this still MLE's, don't make the array of size D, but if you can't find an index that currently does not have a node, just increase the array size and add the node there. There aren't enough updates to make all nodes have a size D list, so it should be good. For queries you can bsearch each index seperately. Should be O(U) memory I thonk. Sorry if this is what sol means and I just don't understand.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +19 Finally got around to coding it and got AC. The code is much simpler than the ideas presented in the editorial above. Here's the code: link.
 » 2 years ago, # |   0 Time limit on A is basically insurmountable for Java :(
•  » » 2 years ago, # ^ |   +14 Sorry to hear that :/ Yes the segtree one will TLE I'm pretty sure, but I think sqrt decomposition could manage in Java.
•  » » » 23 months ago, # ^ |   0 Actually even the second subtask is hard to pass with Java (even if you presort and have QD instead of QDlog(D) in the time complexity). Was it possibly easier to pass on the actual competition than here? I'll probably attend ceoi next year and want to use Java :(
•  » » » 23 months ago, # ^ |   0 Lol, that's kinda funny. I tried solving some other subtask, the second subtask with the same program now passed due to a lucky coincidence (the constraints are so tight that it can sometimes pass and sometimes not lol)
•  » » » 23 months ago, # ^ |   0 Any tips on how to pick a good $C$ value? I finally got 100/100 after sending many attempts to tune my $C$ value lol..
 » 2 years ago, # | ← Rev. 3 →   +15 In $A$, solution described for subtask $5$ is enough fast to pass all data. I have just one small optimization to avoid $O(M \sqrt U log M)$. You do not need any set, you can do all updates in $O(\sqrt U)$ with normal arrays and vectors. Also better value for block is $4000$ if you want to fit in memory limit.
 » 2 years ago, # |   +1 My approach for A was similar to "Save neighbour list by node, reduce storage space by constant factor" except I set $C=D$ and removed the $QC\log C$ factor.Code
 » 23 months ago, # |   0 Why did I have the same approach as the solution, but I got TLE.
 » 23 months ago, # | ← Rev. 3 →   0 For C, the relation should be $dp[i][j]=dp[i-1][j-1]+dp[1][i+j-1]$for all $i>1$, $j>1$, $i+j\le C+1$. For all $i+j>C+1$, $dp[i][j]=dp[C+1-i][C+1-j]$.
•  » » 23 months ago, # ^ |   +47 Combinatorial Argument for C?Index the columns from $0\ldots C-1$ rather than $1\ldots C$ and fix $R$. As mentioned above, for all $(i,j)$ satisfying $0R$. In this case, the rightmost term simply disappears.)It suffices to biject paths on the LHS to paths on the RHS. We can do this by splitting paths into pieces, rearranging them, flipping some of them horizontally or vertically, and finally concatenating them. Define horizontal flip — $flipx(p)=[(0,p_{R-1}), (1,p_{R-2}),\ldots,(R-1,p_0)]$ vertical flip — $flipy(p)=[(0,-p_0), (1,-p_1),\ldots,(R-1,-p_{R-1})]$ concatenating two paths — $p_1+p_2$. We'll need to translate the paths horizontally and vertically as necessary such that the right endpoint of $p_1$ matches up with the left endpoint of $p_2$. First we transform each path $p$ on the LHS as follows: Let $a$ be the maximum $x$ such that $p_x=0$. Set $p\leftarrow flipx(p_{[0,a]})+p_{[a,R-1]}$ $p_{[0,a]}$ originally was a path from $(0,i)\to (a,0)$; now $flipx(p_{[0,a]})$ is a path from $(0,0)\to (a,i)$ and $p_{[a,R-1]}$ is a path from $(a,i)\to (R-1,i+j)$. The LHS now consists of all $p$ that satisfy the following: Let $a$ be the maximum $x$ such that $p_x=i$. $p_x\in [0,C-1]$ when $x \in [0,a]$ $p_x\in [i+1,C-1+i]$ when $x\in [a+1,R-1]$. This includes all elements of $path[0][i+j]$. Each LHS path $p$ not contained within $path[0][i+j]$ satisfies $p_x=C$ for some $x$. Let $b$ be the maximum $x$ such that $p_x=C$, and set $p\leftarrow flipx(p_{[a,b]})+p_{[0,a]}+flipy(p_{[b,R-1]}).$We claim that this corresponds uniquely to an element of $zero[C-i][C-j]$, since $flipx(p_{[a,b]})$ is a path from $(0,C-i)\to (b-a,0)$. The $y$-coordinates are all in the range $[0,C-1]$, and $y$-coordinate $0$ appears only at the right end of the path. $p_{[0,a]}$ is a path from $(b-a,0)\to (b,i)$. Its $y$-coordinates are all in the range $[0,C-1]$ $flipy(p_{[b,R-1]})$ is a path from $(b,i)\to (R-1,C-j)$, Its $y$-coordinates are all in the range $[0,C-1]$ and $y$-coordinate $i$ appears only at the left end of the path The transformations we mentioned are all reversible, so the bijections hold and we're done.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +18 You are right, this is a more simple way of expressing the DP relation. In the editorial, there is a typo in the first formula as +1 should be -1 in the last term. The second formula seems correct.Let me remark some things to provide more background for this problem concerning the king. I was guessing there could be some simple relations between the numbers of ways for a given row, as it is relatively common for the integer powers of these so-called Toeplitz-type matrices (i.e. all diagonals are contant values; in our case we have a tridiagonal matrix $A$ with diagonals $(1,1,1)$ as the transition matrix for the king ways) to maintain certain invariance equations w.r.t. their entries.Indeed, I was able to figure them out quickly by applying a standard technique: An easy proof?Notate the number of ways when advancing $R-1$ rows, starting at column $i$ and arriving at column $j$, by $a_{i,j}$ (in terms of matrices, these $a_{i,j}$-s are the entries of $A^{R-1}$). We are proving the statement for these values.Now, imagine we are advancing one additional row forward. The corresponding numbers of ways starting at column $i$ and arriving at column $j$ (a.k.a. the entries of $A^R$) are then $A^R = \left[ \begin{matrix} a_{1,1}+a_{1,2} & a_{1,1}+a_{1,2}+a_{1,3} & a_{1,2}+a_{1,3}+a_{1,4} & \cdots & a_{1,n-1}+a_{1,n} \\ a_{2,1}+a_{2,2} & a_{2,1}+a_{2,2}+a_{2,3} & a_{2,2}+a_{2,3}+a_{2,4} & \cdots & a_{2,n-1}+a_{2,n} \\ a_{3,1}+a_{3,2} & a_{3,1}+a_{3,2}+a_{3,3} & \cdots & \cdots & a_{3,n-1}+a_{3,n} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_{n,1}+a_{n,2} & a_{n,1}+a_{n,2}+a_{n,3} & a_{n,2}+a_{n,3}+a_{n,4} & \cdots & a_{n,n-1}+a_{n,n} \end{matrix} \right]$Observe that the number of ways when going $i\to j$ columnwise is the same as the number of ways for $j\to i$ (there is a simple bijection defined as taking any path of the first type and reversing it), irrespective of the number of traversed rows. So on one hand, we have $a_{i,j} = a_{j,i}$ for any $1\leq i,j\leq C$ as $A^{R-1}$ is symmetric. On the other hand, $A^R$ is symmetric too, so starting from the first row/column pair, we derive (using the previous symmetry) $a_{2,1}+a_{2,2} = a_{1,1}+a_{1,2}+a_{1,3} \ \Rightarrow \ a_{2,2} = a_{1,1}+a_{1,3}; \\ a_{3,1}+a_{3,2} = a_{1,2}+a_{1,3}+a_{1,4} \ \Rightarrow \ a_{2,3} = a_{3,2} = a_{1,2}+a_{1,4};$etc up to $a_{2,n}$, then advance to the second row/column pair $a_{3,1}+a_{3,2}+a_{3,3} = a_{2,2}+a_{2,3}+\underline{a_{2,4}} \ \Rightarrow \ a_{3,3} = a_{2,2} + a_{1,5}; \\ a_{4,1}+a_{4,2}+a_{4,3} = a_{2,3}+a_{2,4}+\underline{a_{2,5}} \ \Rightarrow \ a_{3,4} = a_{4,3} = a_{2,3} + a_{1,6};$etc up to $a_{3,n}$. Here the relations from the first row/column were used for the underlined entries. Proceeding this way completes the proof.I was happy about this, as it was also indicating that the well-known approach for computing a high matrix power $A^{R-1}$ as a linear combination of low powers w.r.t. some modulus (i.e. compute charpoly, use Cayley--Hamilton and polynomial division to express $A^{R-1}$ as a linear combination of $I,A,A^2,\ldots, A^{C-1}$) won't really make the problem easier to solve as long as both the starting and finishing squares vary: we still need to find a way to compute arbitrary entries of the low matrix powers. Though on the other hand, starting this way we've gained the advantage that up until power $C$, the king can only touch at most one of the two sidewalls, making combinatorial summation formulas and generator functions much easier to work with. This is e.g. how the solution described by Elegia below works; we've found an equivalent one based on Catalan numbers before proposing this problem, but didn't want to exclude it by making $Q\leq 10^5$ or adding extra subtasks, both because it would complicate the implementation of the bishop, and also because this approach was not considered a "shortcut" compared to the other one.(In fact, the appearance of Catalan numbers made me realize a nice combinatorial proof, essentially the same as the one by Benq, utilizing the idea of mirroring path segments. Congrats that you've found it on your own!)Hope you guys enjoyed solving this problem! :D
 » 23 months ago, # | ← Rev. 8 →   +62 update: It can be solved in $\Theta(C\log C\log R)$ time for preparation and $\Theta(1)$ per query, you just need to calculate $\sum_k u_k (x^{-1} + x^0 + x^1)^k$, this could be done in $\Theta(C\log^2 C)$ with D&C. Actually King could be solved in $\Theta(C\log C\log R)$ (or $\Theta(C^2\log R)$ without FFT) time for preparation and $\Theta(C)$ per query.In preparation, we should calculate the characteristic polynomial of the transition matrix. $p_C(\lambda) =\left| \begin{matrix} \lambda - 1 & -1 \\ -1 & \lambda - 1 & -1 \\ & -1 & \lambda - 1 & \ddots \\ & & \ddots & \ddots \end{matrix}\right|$You can see that $p_C = (\lambda - 1)p_{C-1} - p_{C-2}$, so this could be calculated in $\Theta(C\log C)$ whatever you like, such as matrix exponentiation which its elements are polynomials. Then we can reduce $answer(R)$ into the linear combination of $answer(1), answer(2), \dots, answer(C)$. The coefficient can be calculated in $\Theta(C\log C\log R)$ through polynomial division. Then we have to calculate the ways to move from $(1,c_1)$ to $(i,c_R)$ for all $1\le i\le C$. We can use the inclusion-exclusion through a reflection. All paths which touched $y=0$ can be reflected to all paths from $(1,c_1)$ to $(i,-c_R)$. $y = C+1$ is similar.Now the problem is: How to calculate the ways to travel from $(1,c_1)$ to $(i,k)$ for all $1\le i\le C$? After some derivation actually I found out that the generating function is $\left( \frac{1-x-\sqrt{1-2x-3x^2}}{2x} \right)^{|c_1-k|} \frac{1}{\sqrt{1-2x-3x^2}}$, and it's sequence is a p-recursive sequence with constant terms in recurrence so it could be calculated in $\Theta(C)$. Here I will introduce 142857's solution to avoid calculating this sequence.After enumerating the times of going straight, the ways of using the rest of the moves can be represented with simply a binomial. So $\sum_{i\ge 0} a_ix^i =\sum_{i\ge 0} \#[(1,c_1) \rightarrow (i+1,k)] x^i = \sum_{n\equiv c_1-k \pmod 2} \binom{n}{\frac{n+(c_1-k)}2} \sum_j x^{n+j} \binom{n+j}j$But actually we just want to know one linear combination of $a_0, a_1, \dots, a_{C-1}$ because $answer(i+1)$ is represented by $a_i$. We let the coefficient be $u_0, u_1, \dots, u_{C-1}$, then \$ \sum_{0\le n
 » 23 months ago, # | ← Rev. 2 →   +19 For problem C, if T='Q', C=R && C1=1 && CR=C, Wouldn't the shortest path be 1?? (correct me If I'm wrong please)
 » 23 months ago, # |   0 Is it possible to solve 1403B - Spring cleaning by doing path queries with segment trees (without hld) like in this video?
 » 20 months ago, # | ← Rev. 2 →   0 Can anyone help explain why my submission to A times out- https://codeforces.com/contest/1403/submission/101917940 ?I'm doing the "Save neighbour list by node, reduce storage space by constant factor" solution.
 » 7 months ago, # | ← Rev. 3 →   0 For the "HLD approach" of problem B, if we maintain a separate segment tree for each chain (instead of putting all chains onto a single segment tree), then we can improve "(log(n))^2" to "log(n)" in the time complexity.The reason is that: Each time we add to a non-leaf node V, we flip the parity (odd or even) of all nodes on the path from V to the root. When we update the HLD chains (maintained by segment trees) covering this path, except the first chain and the last chain, all other chains are updated completely, which correspond to an O(1) operation on each segment tree. Since there are O(log(n)) chains, then the time complexity of adding to one non-leaf node is T(updating the first chain) + T(updating the last chain) + number_of_the_rest_chains * T(updating a chain completely) = O(log(n)) + O(log(n)) + O(log(n)) * O(1) = O(log(n)).