fmota's blog

GP of Ural
By fmota, history, 7 years ago, In English

Let's discuss the problems
How to solve A and C ?

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

Comments Comments (30)
| Write comment?
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

What is the procedure to register for them??

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

A: Divide and Conquer in the direction of the value + Convex Hull Trick. If you D&C in normal wrong direction, you need dynamic CHT.

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

    Can you please elaborate?

    My solution was segment tree on values (a[i]) and in each segment dynmic convex hull tree. Although I could avoid dynamic cht because the slopes were always increasing and so we could just binary search for queries.

    Do you mean segment tree when you said divide and conquer?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it +8 Vote: I do not like it

      Maybe you did in wrong direction. I mean that,

      • let C be (max(a) - min(a)) / 2.
      • split a1~an into two groups Lower and Upper such that ai < C in Lower and ai ≥ C in Upper.
      • first, calculate DP table of Lower recursively.
      • second, propagate DP table of Lower to DP table of Upper. this can do by Convex Hull Trick.
      • third, calculate DP table of Upper recursively.

      Use a' such that pair(ai, i) is a'i -th smallest in n elements, instead of a.

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

How to solve F?

As I understand, we need to find such x that p(x) = 1. But how to find x using  ≤ 7500 queries?

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

    • The answer to query "a b c" is c if and only if p(a) = 0 or p(b) = 0. Using this, find p - 1(0) in n / 2 + const queries.

    • Now you know s, t such that p(s) ≠ 0 and p(t) = 0. The answer to query "a s t" is s if and only if p(a) = 1. Using this, find p - 1(1) in n + const queries.

    • The remaining part is easy to do in n + const queries.

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

      You said: The answer to query "a b c" is c if and only if p(a) = 0 or p(b) = 0.

      But, p(a)p(b)+p(c)=p(c) means p(a)p(b)= multiple of n, not necessarily one of them has to be 0 right? For example one is 2 and the other is n/2. Probably I am misunderstanding you?

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

        Yes, I missed that.

        Still, in n / 2 queries, we can limit the candidates of p - 1(0), and with a few hundreds of extra random queries we should be able to determine p - 1(0). The same works for p - 1(1) — I wrote n but actually it's n / 2 again. So, we have 2512 queries in total for extra random queries.

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

          I also used random queries, but are there no way to solve without randomized algorithm? The statement said that there is a deterministic solution which works for every possible permutation.

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

How to solve D, E, I and G?

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

    G : Calculate the area of ((initial polygon) U (final polygon) U (N fan shapes)) (fan shapes : rotating segments between origin and vertices)

    -> sort by angle about origin. For each angle range, we can calculate the maximum radius of fan shape. Also, there would be exactly one segment from initial polygon and final polygon. Then we can calculate the union of fan shape and two triangles.

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

    D: if n is even, it is just 10n / 2. Otherwise, the real fun begins. What we need is the number of palindromes such that sum of even digits equals to the sum of odd digits.

    Let's iterate over the central digit: if it is fixed, we need to find the number of pairs (n1-digit number, n2-digit number) such that the difference between their sum of digits is equal to a fixed δ. Let's take a look at a generating function of the counts of n-digit numbers with a given sum of digits s: fn(x) = cn, 0x0 + cn, 1x1 + ... cn, sxs + .... One can notice that fn(x) = (1 + x + ... + x9)n = ((x10 - 1) / (x - 1))n. What we need is the coefficient for xδ in fn1(x)·fn2(1 / x) = fn1 + n2(x) / xn2. So in the end we just need to be able to compute a given coefficient of some fk(x). One can derive it from the closed formula for f, or just use an existing formula, e.g.

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

      I don't get how you are calculating fn(x) faster than O(n2). My approach is to differentiate this polynom by x and get a recursive formula for its coefficients from the following equality: nfn(x)(1 + 2x + ... + 9x8) = f'n(x)(1 + x + x2 + ... + x9).

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

        I don't need to calculate fn(x) altogether: I just need to calculate a single coefficient of it 10 times, so it's just 10 O(n) computations.

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

          Ah, I see, you are exploiting the fact that polynom is symmetric.

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

        We tried following nlogn but resulted tle.

        Basically f^n = ifft(n*fft(f)).

        And since the mod was not a friendly one so we took two different primes. Is this approach wrong?

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

        How is nfn(x)(1 + 2x + ... + 9x8) = f'n(x)(1 + x + x2 + ... + x9) helpful to compute the coefficients of f?

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

          Suppose fn(x) = a0 + a1x + a2x2 + ... What is coefficient for xi in this equality? On the left we have nai + 2nai − 1 + ... + 8nai − 8. On the right we have (i + 1)ai + 1 + (i)ai + ... + (i − 8)ai − 8. Subtract one from the other and you have (i + 1)ai + 1 equal to linear combination of 9 previous coefficients. You only need a0 = 1 to start recurrent calculations (assume all negative coefficients are zero).

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

How to solve C and K?

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

    C: If there are consecutive same color cells, just keep one of them. Now divide the colors into two groups. If a color have more than sqrt(n) cells, call them big color, otherwise small. For each big color, keep: (how many color adjacent to this big color are on, how many are of, what are the adjacent colors). For each small color, keep: (what are the small colors adjacent to this small color).

    Now you can update in sqrt(n) in every query. Suppose you are altering a big color. So go to that color's list and update. Also visit all other big colors, if your updated big color is in them update them accordingly.

    If some small color gets changed, go to all the big colors and check if your altered small color is adjacent to them. Also process the list in small color side.

    Please note, there are not more than sqrt(n) big color. And the adjacency list size in small color side is sqrt(n).

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

      Could you explain please how you calculate the answer after update? I'm still not understand what do you do with the values you keep

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

    K: If you can precompute [r1][c1][r2][c2] = can you go from r1,c1 to r2,c2 using a palindromic string, then rest is easy, just a dijkstra/dp.

    How to compute this matrix? Think in reverse, initially all [i][j][i][j] is visited, also [i][j][i1][j1] where (i1,j1) is adjacent to (i,j). Next try to apply same move to both (i,j) and (i1,j1). That is, try to expand palindromic string. It can be done in O(50^4) bfs.

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

How to solve J?

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it -23 Vote: I do not like it

Bad post. Ignore it.

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

anyone willing to post solution for H?

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

    I have an O(N*sqrt(N)*log(N) ) solution but i don't know how to improve time complexity. I got TLE. My idea is to mix Mo's algorithm with palindromic tree, but i needed to use LCA on palindromic tree to speed up the jumps over the structure links. If somebody have an idea please share it.

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

      Why not LCA in O(1) with Sparse Table?

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

        because i need to perform some other operations on each jump, i need to find the longest palindrome that start at a position i with lenght less or equal to some x. The x is variable among the queries, so i can't precompute the hole sparse table.

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

    wrong, ignore

    → Reply