Блог пользователя mraron

Автор mraron, история, 4 года назад, По-английски

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

Problem A
Problem B
Problem C
  • Проголосовать: нравится
  • +112
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can somebody explain what A asks for?

  • »
    »
    4 года назад, # ^ |
    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -20 Проголосовать: не нравится

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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Time limit on A is basically insurmountable for Java :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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 :(

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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..

»
4 года назад, # |
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.

»
4 года назад, # |
  Проголосовать: нравится +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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
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]$$$.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +47 Проголосовать: не нравится
    Combinatorial Argument for C?
  • »
    »
    4 года назад, # ^ |
    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?

    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 года назад, # |
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<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 года назад, # |
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)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
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)).