Qingyu's blog

By Qingyu, history, 3 years ago, In English

How to solve Problem 7, 10? Is there any tutorial available?

  • Vote: I like it
  • +73
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve Nanoassembly from div2?

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

    Just google a formula for flipping a point over a line

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

In problem 7 there's a simple dp in O(C*B). You run it for C<=1e4 and see that you only need small number of B (200ish). IIRC For C <= 2e5 ans <= 301

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

    I did that + realize that the pattern depends on the parity of N, so just make a program to print all ranges of answers and then submit a hardcoded solution (because of troubles with ML)

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

    I also got this fact. Also I noticed that we can use ternary search to get the answer. However, for C = 2e5 my solution worked for about 5 — 6 seconds.

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

      Well, if you managed to let it finish in 5 sec you could send all the answers in static array. Our solution works 0.8s

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

For problem 10, use FFT to find, for each cell, how many # are there if the rectangle starts in this cell that should be . and vice versa(it's a match if both are 0). Due to the tight memory limit, you'll probably need to use NTT instead of FFT.

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

    I would also mention that 1) we need only two 2000x2000 arrays instead of 4000x4000 (therefore my custom complex<double> was perfectly fine in terms of memory), and 2) we can do only one multiplication, if we assign $$$1$$$, $$$i$$$, and $$$1+i$$$ to cells ., # and _ of the board, and $$$1$$$, $$$-i$$$, and $$$0$$$ to these cells of the vault.

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

      How to use only two 2000x2000 arrays?

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

        Just multiply them as you always do. In res[i][j] you will have the sum of all coefficients of $$$x^{2048k+i}y^{2048l+j}$$$ of the result. It is because 1) you got this result only looking at the values in $$$2048$$$-th roots of unity, or 2) because in when you use fft to multiply two 1d polynomials, you basically do this in the ring modulo $$$x^n-1$$$.

        After this you can manually exclude all candidates who correspond to vault being placed on the torus instead of the normal board.

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

Task 6 is the worst thing that I have met. 5 hours just to have 19 test. Can anyone explain how to write robust Gauss method?

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

    What do you mean by robust? We are working in $$$\mathbb{Z}_7$$$, so there are no precision problems

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

      I mean something mystical like solve all existing problems. Do you mean that it is enough to use Gauss by module?

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

        Well, yes, because you are only interested in the rank of the matrix over $$$\mathbb{Z}_7$$$. Calculating the rank over $$$\mathbb{R}$$$ does not work, since, for example, (it is not a valid example, but you can construct a valid one similarly) one button that switches the day in the first universe 7 times does not work, but the rank over $$$\mathbb{R}$$$ is 1

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve A from div. 2. I tried two pointeres but got WA12.

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

how to solve problem 1 and problem 6? i tried to debug for 2 hours but still didn't understand what's wrong.

»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

How to solve 2: Orienteering?

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

    I was iteratively adjusting the points, each adjustment of a single point was some binary search. However, it costed me +20 to find proper number of iterations of each and I do not think it was intended.

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

    What we did was the following:

    First, choose MAGIC points on each circle and choose the best route in O(n * MAGIC^2). Now near each of the points on the optimal path choose MAGIC points again and find the optimal path again.

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

    We did gradient descent to find the optimal route. Each point was parametrised with the angle. However, this solution was very prone to converge to local optimum instead of global optimum if angles were not initialised properly.

    The last initialisation that worked for us was finding the optimal point in the circle if only the previous and next circles were relevants. Circles in the endpoints were initialised pointing the adjacent circle.

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

    The "official" solution is to take $$$K$$$ samples on each circle, and compute minimum distance through them using $$$O(N K^2)$$$ dynamic programming. Quite importantly, the case of $$$N = 2$$$ must be considered analytically. For $$$N >= 3$$$ it can be proved that relative error of sampling solution does not exceed $$$\Theta(1 / K)$$$ with some constant. Taking $$$K = 2500$$$ should provably suffice, although even something as low as $$$K = 200$$$ passes due to smooth nature of the distance function.

    Also, circular shape is too nice to stop various local searches from getting ACCEPTED. I personally implemented one with randomly perturbing polar angle on random circle many times.

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Can anyone tell me what is worth paying attention to in Hockey? I debugged for 2 hours and got 5 WAs.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve problem 9? I thought a solution using trie but got WAs.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    You replace each a[i] with a[i]*i! and do the trie solution. The answer is len(poly1) + len(poly2) — 2 * len(common suffix)

»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Here is tutorial (in Russian) by problem authors: https://www.youtube.com/watch?v=NFS6_6m6c4g

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

Can anyone please explain problem 1(Polesov and Work)?

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

    You have a vector $$$v = (a, b)$$$, so consider point $$$P = \frac{v}{||v||} \cdot r$$$ first. This is the point giving maximum dot product, but it is real-valued. Let's round both its coordinates down to integers, and you'll get some pretty good point $$$Q$$$, which gives initial estimate on the goal function.

    Which points can be better than $$$Q$$$? Draw a line passing through $$$Q$$$ normal to $$$v$$$, it will cut a thin segment from the circle. The integer points in this segment are better than the initial record. The thickness of the segment is $$$O(1)$$$, so it contains at most $$$O(\sqrt{R})$$$ integer points. Iterate through all of them and find the best one — that would be the answer.

    The remaining is technical details. Usually you find $$$X_{min}$$$ and $$$X_{max}$$$ bounding the segment (e.g. compute angle of the segment from thickness and radius, then find min/max points), then iterate through all $$$X \in [X_{min} \ldots X_{max}]$$$, and check $$$Y = \sqrt{R^2 - X^2}$$$ for each of them. Just note that double precision is not enough to compute such $$$Y$$$ precisely, so you might need plus/minor one adjustments.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Any hints for problem 11?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    Here are some hints.

    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Hint 5
    Hint 6
    Hint 7
    Hint 8
    Hint 9
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there testdatas or .pdf tutorial for the contest?