Блог пользователя rsFalse

Автор rsFalse, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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').

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

        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
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Any idea what is WA 115 in A?

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :( )

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve E , I ?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится
    E
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about J?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

rsFalse uses Perl for every problem :O