Djok216's blog

Grand Prix of Peterhof
By Djok216, history, 6 years ago, In English

Let's discuss problems.

How to solve A, D, G, J?

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

»
6 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

J: check on a lot of random modules <= 5000.

UPD: oops, my solution is wrong

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    If the given number is divisible by every number up to 5000, this will fail. To make it pass, we have to increase the upper limit.

    Different tests (33-52) contain integers divisible by every prime up to 107, and tests 33-34 are divisible by all primes from 2 to 833 947 simultaneously.

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

      Seems that there were no tests with given number divisible by every number up to 5000 because i have an OK

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Yeah, taking larger powers of very small primes as witnesses can pass these tests.

        Anyway, as with hashing, there sure are tests against every possible small collection of witnesses known in advance, but there is no known test against every possible witness, so it's normal for such solution to pass, except if it chooses only few small and fixed primes.

        → Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

J:

We solve it by Euler's criterion. Pick about K primes, module the given integer and test it with Euler's criterion. The probability of failure will be about 2 - K.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thank you. Finally got AC with first 50 prime numbers bigger than 109 + 7.

    → Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +5 Vote: I do not like it

G (div.2: up to 4*N moves):

Spoiler 1
Spoiler 2
Spoiler 3
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Is that all that you do? It seems that I can last for more then N turns this way

    Suppose N = 2K — big enough
    Queen=(1, 1);Knight = (K, N)
    Turn1: Queen=(K, 1), Knight = (K+2, N — 1)
    Turn2: Queen=(K, N — 1). Knight = (K + 1, N — 3)

    Now I think you need 2N — 1 more turns to win And it will be even a bit more, if we move knight starting point to the left to (2,N) or so

    (column first in all coordinates)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      For N it is not enough. Div.2 problem statement is: to not exceed 4*N moves ("Your task is to capture the Knight in at most 4N moves"). No access to Div.1 statement. My solution works in 2*N I think.

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

        For Div1 it is at most N moves.

        I think your solution is 2N+1 moves

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We used basically the same idea(go to the same row, then win in O(2 * halfwidth), but we needed additional bruteforce for first few turns because otherwise sometimes we needed N + 1 turns

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve B, H?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    H is the computation of a resultant (case t = xy in https://en.wikipedia.org/wiki/Resultant#Number_theory ), but general algorithms for computing resultants are not fast enough. It seems that an efficient algorithm is given in http://algo.inria.fr/flajolet/Publications/BoFlSaSc02.pdf (Corollary 4).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    H:

    Using this one can easily find the k-th coefficient of and then calculate .

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 5   Vote: I like it +18 Vote: I do not like it

      I am not sure if I understand how to use this equation

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        So we calculate all logarithms (), calculate from the logarithms of f and g and calculate the exponent.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    B is similar to Jigsaw Puzzle from Moscow Subregional 2013.

    We can solve it with dp by profile. State is:

    1. column id

    2. mask of colors in last column

    3. list of possible masks (each mask: has 1 on position i if there is a horizontal pile from last column to next one in row i)

    Yes, it looks like m * 2^n * 2^(2^n) states. But most of states are unreachable. And for n=6 there are about 1600 reachable states per column.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    B. Checking if coloring is good can be done by dynamic programming on set of border points which are already colored. Dynamic programming of set of states reachable states of dynamic programming above on one layer works fast enough to pass or precalc (~1.2s in yandex context for me).

    See code for more details. I think it's quite easy.

    Spoiler
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Can you please explain meaning of a few things: mask, x.first, the for loop inside go (what does the i stand for)?

      Edit: I think I understood the gist.

      Mask: colors of previous column (not exactly previous column, if you are at r,c then they represent colors of cells i,c for i<r and I,c-1 for i>=r)

      x.first: every bit represents status of the previous column (not exactly, defined as above). 0 means not yet covered and 1 means already covered.

      Loop I: for each of the covered/uncovered status we try to figure out if we want to color current cell bit then what are the possible next statuses.

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

        Yes, you are correct. Probably naming could be a bit more understandable :)

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +73 Vote: I do not like it

    It took me 140 minutes to solve 7 tasks and more than 3 hours to solve H, I feel this is an overkill, but anyway...

    We use Newton's identities. Check the definitions of ei and pi there.

    Let A = {ai}, B = {bi}, C = {aibj}. We are given the values of ei(A) and ei(B), and we want to get ei(C).

    1. From ei(A), compute pi(A).
    2. From ei(B), compute pi(B).
    3. Compute pi(C). This is quite easy because pi(C) = pi(A)pi(B).
    4. From pi(C), compute ei(C).

    Thus, the main challenge is the conversion between pi and ei.

    Now, let's use Newton's identities. It says that the convolution of (0, p1,  - p2, p3,  - p4, p5,  - p6, ...) and (e0, e1, e2, ...) is (0, e1, 2e2, 3e3, 4e4, ...). Let P(X) = 0 + p1X - p2X2 + p3X3 - p4X4 + ... and E(X) = e0 + e1X + e2X2 + e3X3 + .... We have P(X)E(X) = E'(X)X (Don't miss derivative sign).

    The conversions between P and E can be done as follows:

    • P(X) = E'(X)X × inverse(E(X)).
    • P(X) / X = E'(X) / E(X) = (log(E(X)))', thus .

    Computation of inverses: Link (Check problem E)

    Computation of exponentiation: Link (Left part of Fig.1 is enough)

    (I'm not quite sure why these computations with integrations/differentiations are valid.)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      Yes, it's exactly the author's solution. When I was preparing this problem, I first came up with the idea to use Newton's identities to convert between ei and pi. After a while, I realized, that this could be done efficiently using and .

      So I decided to use this big constraints in the problem statement, so that more obvious solutions don't pass. If the constraints were smaller, one could use Berlekamp's algorithm or Cantor–Zassenhaus algorithm to factorize the polynomials, and after that just multiply a lot of linear polynomials.

      Your solution and Golovanov399's solution are the same, by the way.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        You can calculate log and exp efficiently using Newton's method.

        Also, you should notice, that log and exp are not well-defined when we are working modulo 998 244 353, because we sometimes divide by zero. But we don't need that. We are only interested in the first 105 coefficients of polynomials, so log and exp are well-defined.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Conversion between pi and ei could be done by divide-and-conquer FFT.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    We solved H by Newton-Girard formulas and divide-and-conquer FFT.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

D: first bring the outter point to the inner layer in the shortest possible way. Then continue descending in the same manner, checking whether it’s optimal to traverse the current layer to connect the two points :)

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

For problem A, first consider the same problem on a square grid. It can be easily shown that, if we fix the perimeter, a polyline with the largest area is the polyline most closely resembling a square: the sides are either all equal or differ by 1.

On a hexagonal grid, the reasoning is similar, although there happen to be more cases. Sure, our wall will be a convex hexagon. We can show that two consecutive sides differ by at most two: otherwise, we can get a larger area with the same perimeter. In Figure 1 below, we change the part ABC of the wall with lengths 2 and 5 to part DEF, increasing the total enclosed area by 1 (the difference is that we get XEFC instead of DABX).

Figure 1

Thus we can take a rough guess of what will be the length of one side s, then try all values from s - 2 to s + 2 for the two neighboring sides, and so on.

If we investigate further a bit, we can find the optimal solution for each possible perimeter. The six cases are shown on Figure 2 below.

Figure 2

Here is a short solution summarizing the six cases.

A piece of hexagonal paper was provided in the statement to help solve the problem.

→ Reply