We hope you enjoyed the whole problemset even though there were some technical difficulties.
Problem A
Problem B
Problem C
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
Can somebody explain what A asks for?
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.
Does anyone have a working interval tree solution to problem A? Or is that bound to tle
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:
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.
Then when I select a slower language(c++17 64bits) it got TLE... When I switched to c++11 it got accepted...
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.
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.
Time limit on A is basically insurmountable for Java :(
Sorry to hear that :/ Yes the segtree one will TLE I'm pretty sure, but I think sqrt decomposition could manage in Java.
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 :(
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)
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..
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.
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
Why did I have the same approach as the solution, but I got TLE.
For C, the relation should be
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]$$$.
Index the columns from $$$0\ldots C-1$$$ rather than $$$1\ldots C$$$ and fix $$$R$$$. As mentioned above, for all $$$(i,j)$$$ satisfying $$$0<i,0<j,i+j\le C-1$$$, we want to show that
or
A king path can be described by a sequence
such that $$$p_x\in [0,C-1]$$$, and $$$|p_x-p_{x+1}|\le 1$$$.
Define
We can rewrite the condition we want to show as
(Note: You should first convince yourself that this holds for $$$C>R$$$. 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
First we transform each path $$$p$$$ on the LHS as follows:
$$$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:
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
We claim that this corresponds uniquely to an element of $$$zero[C-i][C-j]$$$, since
The transformations we mentioned are all reversible, so the bijections hold and we're done.
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:
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
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)
etc up to $$$a_{2,n}$$$, then advance to the second row/column pair
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
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.
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
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
It's obvious that $$$b_t = [t\equiv c_1 - k \pmod2]\binom{t}{\frac{t+(c_1-k)}2}$$$ could be calculated in $$$\Theta(C)$$$. And $$$\sum_{t\le n < C} \binom n t u_n$$$ can also be precalculated in $$$\Theta(C\log C)$$$ through one convolution. So we just need $$$\Theta(C)$$$ per query.
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)
Is it possible to solve 1403B - Spring cleaning by doing path queries with segment trees (without hld) like in this video?
Can anyone help explain why my submission to A times out- https://codeforces.net/contest/1403/submission/101917940 ?
I'm doing the "Save neighbour list by node, reduce storage space by constant factor" solution.
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)).