rsFalse's blog

Opencup GP of Europe div. 2
By rsFalse, history, 6 years ago, In English

Good morning. Does anyone knows if the 2nd division of GP of Europe will be held today? It's 40 minutes after the contest should have started.
11.11.2018 12:00 Grand Prix of Europe

Upd. div. 2 system appeared and is planning to start at 13:00

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rsFalse (previous revision, new revision, compare).

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

What's the idea for D/G/L/M?

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

    G: Every number can be represented as 2^x*3^y*z, group them by z and let (x,y) be its coordinate, then it is a standard mask-DP problem on the grid(you can't choose a shape like 'L').

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

      which one needs to squeeze hard into TL (we couldn't)

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

        AC in 0.766

        You can sort all existing cells, then all interesting cells are in a segment, you can do something like two-pointers, each movement of a border of this segment correlate to DP transition.

        Max length of this segment is 19, and it is decreasing with x and z quite fast.

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

        I used many methods to decrease the running time, such as:

        1. only consider connected grids.

        2. for all points: y -= min(y).

        3. iterate states carefully, not all states.

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

      But, x, y <= 30 right? So how do you do the mask dp?

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

        y<=18, and larger x has smaller y.

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

    D: first for each query calculate minimum of "when this segment started to accumulate snow after clearing last time" using segment tree or other data strycture. Next, you need to answer queries of type "how much snow was there from moment x to t (current moment)". It will have several full blizzards (use prefix sums for that) and 2 partial blizzards (it's 2 quadratic functions)

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

      "when this segment started to accumulate snow after clearing last time" -> but they might be cleaned partially no?

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

        I mean, i-th kilometer segment has 1 number lasti -- "when this segment started to accumulate snow after clearing last time". For each query of type '?' you'll get minmum of lasta, ..., lastb

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

    L: Use inclusion-exlusion formula. We choose some subset of rows, columns and diagonals such that all cells there are equal and add  ± 2number of cells not covered by subset + number of connected components in subset to the answer. Without diagonals it is easy to do in O(n2). With diagonals when we choose rows and columns we need to keep track of cells on diagonals that are covered by some row and some column. We can do it with dp.

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

    M: First kick out all points that can't reach (1,1) or (n,m). What we need to do is to count the number of points each point can reach in the graph. Note that it is a planar graph, so for a point, lets track the wall by our left hand and right hand, we will get a polygon. The answer is equal to the number of points inside the polygon. We can use DP to calculate this. The complexity is linear.

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

Ternary search passed problem A, is there a solution without ternary search?

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

    I got WA18 by nested ternary search. I got AC after eliminating one TS and did some reflection trick.

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

    I solved it only with reflection trick, but costed me lots of time. Ternary search sounds better.

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

      Isn't there quite a lot case work, if we solve just by reflection?

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

    Three cases: if shortest path to one line passes through other line, that's the answer. (times 2)

    Otherwise, if segment between reflection of O over two lines intersects both lines and in the correct order, answer is tbat distance.

    If none of these work, answer is path to intersection and back.

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

    Any idea what is WA 115 in A?

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

      It's the case of parallel lines. Try something like -1 0 -1 and 1 0 2

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

How can one parse the statement for J in a way that Maggy can rest in some moments??

Like no sentence of these imply that! I like the word "exactly" the most from it. Such a nice touch to a already misleading legend!

He announced that he would return shortly, after exactly k moments. Maggy knows the current lengths of all scarves and both stitching and unravelling a row takes her one moment. Help Maggy – compute how many scarves of equal length she can produce.

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

Is it necessary to set input upto 5 MiB for TL = 1 sec in O ('Sysadmin')? (Can't even read so much with slower language :( )

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

Upsolving page isn't working. It would be nice to have ability to upsolve problems which are div. 2 only (O, P or others).

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

How to solve E , I ?

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

    I: Let (p,t) be points on 2D-plane, rotate the plane by 45 degree. According to Dilworth's theorem, the answer is equal to the length of LDS.

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

    E is an extension of the 2018 USACO US Open problem Disruption. As mentioned, for edges off the MST, you do an LCA query to find the maximum path on the MST between those vertices, and the edges in the MST part can be handled in the way described in the reference solution.

    I has probably appeared more than once in other contests, see for example the 2009 BOI problem Candy Machine, except you don't need to produce a proof of the answer. The reference solution here also passes once you omit the extra output.

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

What about J?

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

    J: Sort all numbers, the optimal way is to select consecutive numbers a[l],a[l+1],...,a[r] and change them to a[(l+r)/2]. So two-pointer iterate l and r to find the longest one.

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

How to solve B?

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

    How to write an integer as the sum of Fibonacci numbers using minimum number of terms? It's called Zeckendorf representation and can be obtained greedily.

    Let f(X, K) be the number of integers up to X, whose Zeckendorf representation contains at most K terms. If Fi is the largest Fibonacci number less than or equal to X, f(X, K) = f(Fi - 1, K) + f(X - Fi, K - 1) holds. Write memoized recursion using this.

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

      I transformed the statement into "counting how many 01 strings with at most k ones, and there are no two adjacent ones in the string", it can be easily solved using DP.

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

rsFalse uses Perl for every problem :O

→ Reply