MikeMirzayanov's blog

By MikeMirzayanov, 2 months ago, In English

Hello!

On December 13th, the ICPC Northern Eurasia Finals (previously known as NEERC) will take place. The competition will be held at several venues: St. Petersburg, Novosibirsk, Kutaisi, and Astana. Almost 300 teams will participate in it.

Onsite Contest Current Standings →
Don't look in it if you take part in the online mirror contest

We invite you to join the online mirror of the competition: 2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred). It will start at Dec/13/2023 10:35 (Moscow time). We recommend participating in teams, but experienced individual participants will also have fun.

The duration of the competition will be 5 hours. Of course, the round is unrated.

Good luck!

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

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

the link of the contest seems to be wrong

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

It is not Almaty, it is Astana

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

why so less contests in this december month....especially the rated ones....i hope atleast 5-6 contests will be added in this month in coming time....

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

omg how F

1vs3 is so tiring.

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +25 Vote: I do not like it

    Upd: I have made a proof here

    I upsolved this problem with iteration method 237083785, but I can't prove why its convergence speed is fast enough. Nevertheless, following is my solution.

    First, we have the game procedure:

    1. Thief moves to a leaf, cause staying at a non-leaf vertex won't be better than any leaf in it's subtree

    2. Thief stays at the leaf until police reaches a leaf. If thief moves to another leaf during the police move, he could have move there in 1.

    3. Police chooses another leaf and go directly to it, because he knows that thief's best move is waiting on a leaf

    4. After police reaches the leaf, if not caught, all other leaves are accessible to thief. Thief select a vertex based on the leaf police is at and move there, then return to 1.

    We can see from the above procedure that non-leaf vertices are irrelevant after the first step, so for the following discussion, vertices are all leaf.

    We denote the expected moves that police catches thief starting from leaf $$$u$$$ by $$$E(u)$$$, denote the probability that thief moves to $$$v$$$ if police is at $$$u$$$ by $$$p(u,v)$$$. Then, thief must distribute $$$p(u,v)$$$ in a way that no matter how police changes his strategy, $$$E(u)$$$ will not be larger. In this case, no matter how police chooses, $$$E(u)$$$ stay the same. Thus for $$$u$$$ and every other leaf $$$v_i$$$, we have

    $$$E(u)=dis(u,v_1)+(1-p(u,v_1))E(v_1)=dis(u,v_2)+(1-p(u,v_2))E(v_2) = \dots$$$

    We try to solve it by iteration method, which means calculate new $$$E'(u)$$$ by $$$E(u)$$$ in the last round, i.e.

    $$$ E'(u)=dis(u,v_1)+(1-p(u,v_1))E(v_1)=dis(u,v_2)+(1-p(u,v_2))E(v_2) = \dots$$$

    Then, $$$dis(u,v_i)$$$ and $$$E(v_i)$$$ are all constants, the only variable is $$$p(u,v_i)$$$. Hence, we denote $$$x_i$$$ by $$$p(u,v_i)$$$, and the above equation can be rewritten as

    $$$\begin{cases} a_i=E(v_i) \\ b_i=dis(u,v_i)+E(v_i) \\ E'(u)=-a_ix_i+b_i=-a_jx_j+b_j=\dots \\ \sum x_i = 1 \end{cases}$$$

    Then we have

    $$$\begin{align*} x_i=\frac{b_i}{a_i}-\frac{E'(u)}{a_i} \\ \sum \frac{b_i}{a_i}- \sum \frac{1}{a_i} \cdot E'(u)=1 \\ E'(u) = \frac{\sum \frac{b_i}{a_i}-1}{\sum \frac{1}{a_i}} \end{align*}$$$

    For the first step where police starts from $$$s$$$, we have the same conclusion that $$$E(s)$$$ stays the same no matter how police moves. Hence, we can calculate $$$E(s)$$$ by the same equation above.

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

when would we be able to see other's solution or would there be any editorial?

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

why did the submit button vanish after the contest?

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

    I try to submit and it says contest is over maybe we have to wait for a while.

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

How to solve G / H?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    G
    H
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

J is matrix exponentiation?

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +21 Vote: I do not like it

    No. You are required to find the number of solutions to $$$a_1x_1+a_2x_2+a_3x_3=t$$$ where $$$x_i$$$ are given and $$$a_i$$$ are variables. So the key idea is to fix $$$X=a_1 mod x_3$$$ and $$$Y=a_2 mod x_3$$$ and find the number of solutions for this $$$(X,Y)$$$. Suppose $$$Z=(t-Xx_1-Yx_2)/x_3$$$. Then any solution for this $$$(X,Y)$$$ is of the form $$$(X+t_1x_3,Y+t_2x_3,Z-(t_1x_1+t_2x_2))$$$ where $$$t_1,t_2 \geq 0$$$. Now the number of such pairs $$$(t_1,t_2)$$$ for which $$$t_1x_1+t_2x_2 \leq Z$$$ can be found in $$$O(x_2)$$$ by fixing $$$t_1 mod x_2$$$ using some math giving a total complexity of $$$O(x_2x_3^2)$$$.

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

    Yes. Basically we want to find [x^n](1 / ((1 — x^a1) * (1 — x^a2) * (1 — x^a3))) which is f[N] for f[0] = 1, f[x < 0] = 0 and f[N] = sum of -f[N-i] * [x^i]P(x) for i > 0, P(x) being (1 — x^a1) * (1 — x^a2) * (1 — x^a3). This is due to the ties between linear recurrences and generating functions, for functions of this type the denominator being the reverse of the characteristic polynomial of the recurrence.

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

      Will the following approach be correct? Choose some parameter P then compute matrix for every different triple and every power divisible by P. Then for each query solve it with trivial dp for $$$O(t / P)$$$ complexity and you start with precomputed matrix.

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

        I don't see why not simply doing binary exponentiation.

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

          Sorry I didn't understand your approach well. I mean solution where you optimize 3 x t dp with 48 × 48 matrix which seems to be TL

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

            Oh I didn't think about it possibly being TL. Then yeah you possibly could precompute powers of 2 for sums that are too high. By doing that we can simply multiply the matrices by the column matrix, reducing the O(SUM^3) multiplication to O(SUM^2). I solved it by using the "How to calculate k-th term of a linear recurrence?" part from this https://codeforces.com/blog/entry/61306

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

            Actually my first attempt was TL as you said, but I printed the matrix out and find out there is at most 100 non-zero positions in the matrix, so I added break 237013217 and passed.

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

        I forgot to notice that you should pick $$$P$$$ in optimal way(something close to the square root)

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

how J and when tutorial

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

    ax + by + cz = N as we know, case for K = 1 and K = 2 pretty standard so I won't explain

    u can calculate L = LCM(a, b, c)

    now I say that I iterate on m = min(x, y, z)

    now still m doesn't have very good bounds, but what I can observe is

    if u have answer for m, u can calculate answer for m + L, m + 2L, it will come out to be arithmetic progression of a kind, still it will be some casework but this is the outline

    so u have to iterate from m = 0 to L — 1 and calculate everything using formulaes

    I just handled cases, when x = m, y, z > m, x = m, y = m, z > m and so on

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

In Problem D if type can be 1 or 3 (when k is equal i.e. mod==2) then print 3 will get WA on test 3. Rank1 faced exactly the same issue in contest. I wonder if the problem writer of D even didn't write an spj. It is a total mistake.

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

How to solve C or I or F? qwq

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

    I is simply a matter of doing the math and coding as far as I can see. Do a rotating 2-pointers thing that keeps the edges that will define the height of the water surface while rotating the polygon, then it's a matter of doing whatever integration thing that results from that. There's a part that's integrating cos(x) * a and I hope that the other part isn't that much harder, my intuition says that it might simply be P(x) * cos(x) for a polynomial of low degree P(x).

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

Open for upsolving please!

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

how can i subit my code after the contest?

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

We came up with strange matrix exponentiation solution for problem J.

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

how A? I have no idea with it.

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

Tutorial, if anyone is looking for it

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

Does anyone have any formal proof or intuition for problem D's solution?

Spoiler
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Powers of b modulo n work in one of 3 ways:

    1. There's some positive k such that b^k = 1 modulo n. This happens when gcd(b, n) == 1

    2. There's some positive k such that b^k = 0 modulo n. This happens when b is divisible by all primes that divide n.

    3. All other cases, which means that b is divisible by some prime that divides n but not all of them.

    For case 2 it's simply what happens when we use a "divisibility test" for 2, 5, 10 and so on in base 10.

    For case 1, we must divide the digits of the number in such a way that the coefficient of the digits are the congruent to their own coefficient without the division. What I mean is that a number can be written as sum d[i] * b^i and we must choose the division according to the problem in such a way that c[i] * d[i] = b^i * d[i] modulo n, c[i] being what we end up multiplying the i-th digit with after dividing the number under some rule of the problem. From here I think it'd be good for you to think about how to explain it splitting into two cases: the alternating one and the non-alternating one. But I think it's not hard to see how it works from here. The reason why "we must divide the digits[...]" is because it's trivial to create a counter-example if that doesn't happen and if it does happen it's easy to see that it works.

    For case 3, if we divide the number under some rule of the problem then there's an arbitrarily large number x such that c[x] = 1, but that can't happen since c[x] * d[x] = b^x * d[x] modulo n must be true and the only non-negative x that makes b^x = 1 modulo n is 0. So this case is impossible to solve.

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

I hope everyone get positive rating after this contest

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

when the contest rating

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

Radewoosh could you explain why your code (237099844) is not a random 20 lines, but a solution to the problem please?)

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

    If the problem is to solve $$$a_1 x_1 + a_2 x_2 + ... = b$$$ then you just iterate over parity of $$$x_1, x_2, ...$$$ and then reduce the problem to one where each $$$a_i$$$ is doubled.

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

    We’re looking for a few values (how many Pokémon of each species there is). So let me guess the parity of each of these numbers ($$$2^n$$$ options). Knowing the parity of some $$$x$$$ means writing it as either $$$2x’+0$$$ or $$$2x’+1$$$. I subtract what these 0s and 1s give me and from now I need to set each number of species even. But it’s the same as without parity restriction but with the sum two times smaller. Add memorization cause the number of different sums will be small.

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

Can anyone explain the solution to problem K?