Qingyu's blog

By Qingyu, history, 2 months 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

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve Nanoassembly from div2?

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

    Just google a formula for flipping a point over a line

»
2 months 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

  • »
    »
    2 months 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)

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

»
2 months 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.

  • »
    »
    2 months 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.

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

      How to use only two 2000x2000 arrays?

      • »
        »
        »
        »
        2 months 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.

»
2 months 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?

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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

»
2 months 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.

»
2 months 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.

»
2 months ago, # |
  Vote: I like it +56 Vote: I do not like it

How to solve 2: Orienteering?

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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.

»
2 months 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.

  • »
    »
    2 months 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)

»
2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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.

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

      Is Q equal $$$r\frac{\sqrt{2}}{2}$$$?

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Any hints for problem 11?

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

Is there testdatas or .pdf tutorial for the contest?