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

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

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

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

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

How to solve Nanoassembly from div2?

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

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

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

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

      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 года назад, # |
Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

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

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

      How to use only two 2000x2000 arrays?

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

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

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

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

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

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

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

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

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

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

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

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

How to solve 2: Orienteering?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Any hints for problem 11?

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

    Here are some hints.

    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Hint 5
    Hint 6
    Hint 7
    Hint 8
    Hint 9
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is there testdatas or .pdf tutorial for the contest?