mraron's blog

By mraron, history, 4 years ago, In English

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

Problem A
Problem B
Problem C
  • Vote: I like it
  • +112
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can somebody explain what A asks for?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a working interval tree solution to problem A? Or is that bound to tle

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      Then when I select a slower language(c++17 64bits) it got TLE... When I switched to c++11 it got accepted...

»
4 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Time limit on A is basically insurmountable for Java :(

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Sorry to hear that :/ Yes the segtree one will TLE I'm pretty sure, but I think sqrt decomposition could manage in Java.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :(

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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..

»
4 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did I have the same approach as the solution, but I got TLE.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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]$$$.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it
    Combinatorial Argument for C?
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    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?

    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

»
4 years ago, # |
Rev. 8   Vote: I like it +62 Vote: I do not like it

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<C} u_n a_n = \sum_ n u_n\sum_j \binom n j [n-j\equiv c_1-k \pmod 2]\binom{n-j}{\frac{n-j+(c_1-k)}2} $$$

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.

»
4 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve 1403B - Spring cleaning by doing path queries with segment trees (without hld) like in this video?

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help explain why my submission to A times out- https://codeforces.me/contest/1403/submission/101917940 ?

I'm doing the "Save neighbour list by node, reduce storage space by constant factor" solution.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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)).