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

GP of Baltic Sea
Автор TripleM5da, история, 6 лет назад, По-английски

How to solve A and L?

Also what is D's judge solution, I am not sure if mine was the intended one.

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

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

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

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

B or K anyone?

We solved both but B included precalc for values from 80 to 100 and K was accepted by changing EPS value from $$$10^{-9}$$$ to $$$10^{-12}$$$, I don't think these were the intended solutions. :D

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

    My B was: dp of order: i * n * 2^15 where we are to find i-interesting permutation of length n. And I assumed the coprime-prefix won't be more than ~30 [number of prime within 100].

    K: I kept a list of objects and then I went from left to right. With a new object, I pushed it into the list. Next, I checked (in a loop) if I can merge the last two objects of the list. If so I merged it (and then I kept checking the last two objects). Merging means, summation of the mass and summation of velocity (+1, -1s). Note, the real velocity of the object is: (sum of velocity)/(sum of mass). Two objects can be merged if they can ever be merged (it does not matter in which order they merge).

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

      We thought of doing this mitm but all we've come up with is $$$3^{number~of~primes}$$$. Can you elaborate a bit more on your solution?

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

      B: The key is to use 2^15 instead of 2^25 (we can ignore all primes above 50).

      K: Suppose that the velocities are $$$v_1, \ldots, v_n$$$ from left to right. Plot points $$$(i, v_1 + \ldots + v_i)$$$. The solution corresponds to lower convex hull of these points.

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

        Oh, true, 2^15 sounds much better, thanks.

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

        Actually you only need to store mask for primes less than $$$\sqrt{n}$$$. For all bigger primes we can group numbers by that biggest prime divisor and make all transitions at once (thus we can take only one of them) and then forget about this prime because we can never encounter it afterwards.

        So actually this problem can be solved for much larger $$$n$$$ (up to 500 easily).

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

          Could you please elaborate more about why we can store mask for primes less than $$$\sqrt{n}$$$?

          I understand why we can store mask for primes less than 50, but what about $$$\sqrt{n}$$$?

          Thank you!

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

            Each number have a set of small (smaller than $$$\sqrt{n}$$$) and maybe one big prime. Let's look at all numbers with given big prime. We can take one of them (or none). So we can do all transitions using numbers from this group at once and forget about this prime.

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

    For $$$K$$$ we sorted all $$$X$$$ values and than use one stack for simulation whole process. We didn't use any double values, just save pairs $$$(a,b)$$$ — current element has speed $$$\frac {a}{b}$$$. code

    For $$$B$$$ we had around $$$2^{14} \cdot 11 * n^2$$$ operations. But the thing is that for all values $$$i>25$$$ answer is zero ( have $$$1$$$ + $$$24$$$ different primes). Even it can be reduced from $$$n^2$$$ to $$$n \cdot log(n)$$$.

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

    And another solution for K is just straightforward simulation — maintain priority queue of all neighbour meeting times

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

    Hmm, how did you use precalc for different modules?

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

      We calculated without the modulo, the lengths of numbers are not that huge. It got to about 70kb for all answers from 80 to 100.

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

My solution to D: Let's call following shape: revU

....
.xx.

The count for: revU = 6, count for two revU separated by a column of x is: = 2*(2 + 6) = 16, appending another revU separated by column of x = 2*(2 + 16) = 36. And so on.

So I greedily take the largest number from this sequence. You will see that, 20 revU is the largest number less than 1e7. revU takes 4 columns and one separator, so total 5 column for single revU. 20 revU requires 20*5 = 100 columns.

You can also put I shapes side by side separated by a column of x, to add some small number (base case).

There is some minor details I am omitting.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    My output looks like this
    → Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    my solution was a little different

    I used :

    ...

    .xx

    and appended this shape to itself i times it turned out that it gets $$$Fibo_{i+4}-1$$$ each time so every I just searched for the most repetitions I can make such that they are less than $$$K$$$.

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

    Yeah, this is exactly the building block used in the jury solution as well (code). Sure, various other building blocks can also help.

    For both problems C (Blocking Crosses) and D (Exact Number of Calls), I started developing them with randomized solutions in mind, but ended up with constructive approaches. However, if anyone solved them with non-constructive algorithms, I'd love to hear about that in the comments!

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

      More about problem D.

      Note that the checker is essentially written in the statement, and it's not at all hard to implement. Once you have the checker, you can actually try it on several small boards if you look for building blocks and ways to merge them. Or you can try constructing a large board with a large answer, and then remove its lower pieces to get a good approximation for the desired number of steps.

      The important thing is, all this stuff is way easier once you accept the thought of dedicating computer time to find the solution to the problem, as opposed to solving completely on paper or in your head, and start implementing only then. Just a few minutes are required to write a checker and run it on some inputs. Solving it on paper, and doing the simulation in your head, must generally consume more wall-clock time.

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

        Actually that got me thinking that can not be the problem's actual checker, so i am interested how did you write the actual checker for the solution?

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

          The checker should react properly to wrong input, yeah. There is also a polynomial speedup: maintaining a doubly-linked list of empty squares. Other than that, it's the same recursive function.

          The constraints were only up to $$$10^{7}$$$, both to make the checker simple and to allow using the checker in the solution.

          I believe there is actually a polynomial solution to this checking problem, based on some math involving Aztec diamonds, but it's a wholly different story.

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

      The following randomized solution for C passed.

      Let's start with some random placement. While there's at least one movable piece, repeat the following:

      • Choose a movable piece at random. Let $$$(x, y)$$$ be its center.
      • Remove all pieces whose centers are within the rectangle $$$[x-2, x+2] \times [y-2, y+2]$$$.
      • Let $$$S$$$ be the collection of all cells in the rectangle $$$[x-4, x+4] \times [y-4, y+4]$$$
      • Shuffle $$$S$$$.
      • For each cell in $$$S$$$, check if we can put a new piece such that the cell becomes the center of the piece, and put it if we can.

      code

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

        Yay, that's amazing! I'm glad it actually passed.

        Thanks for sharing!

        → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится
Problem A
→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +74 Проголосовать: не нравится

    This problem can be solved using duality in linear programming (or, equivalently, Minimax theorem). Basic idea is the following: fix $$$\alpha, \beta, \gamma \geq 0$$$, $$$\alpha + \beta + \gamma = 1$$$, then minimize $$$\alpha \cdot (\text{time of the first}) + \beta \cdot (\text{time of the second}) + \gamma \cdot (\text{time of the third})$$$. It's clear that if the answer to the original problem was $$$A$$$, then the answer to this new problem is $$$\leq A$$$. The converse is also true: one can find $$$\alpha$$$, $$$\beta$$$, $$$\gamma$$$ so that the answer to the new problem is equal to $$$A$$$. So it suffices to do ternary search for $$$\alpha$$$, $$$\beta$$$, $$$\gamma$$$.

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

Problem L: To partition a subtree, assume that its parent, its leftmost leaf and its rightmost leaf are already assigned to the same set. Now assign the 'left path' and the 'right path' to a new set, together with the lefmost and rightmost leafs of subtrees hanging of these paths. Now we can partition those subtrees recursively, since the assumption is satisfied for them.

Below is a picture to make it more clear. The red nodes are already assigned to some set (the same set for all three). The green nodes are assigned to a new set. The purple subtrees are assigned recursively.

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

    We can actually improve this construction so that each set has size $$$\leq 12$$$. To do this, subdivide the set above as follows:

                1
            |
            2
           / \
          3   3
         / \ / \
        4(3) (3)4
       / \     / \
     ... (4) (4) ...
     /             \
    3               3
   / \             / \
  2  (3)         (3)  2
 / \                 / \
1   2               2   1

    Here 1 is the initial color, 2, 3, 4, ... are new colors. (k) is a subtree with leftmost and rightmost leaves colored k; (k) is then colored recursively with new colors. One can see that the resulting compressed graph is a tree since the new edges are (1, 2), (2, 3), (3, 4), ...

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

How to solve C?

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

    Here is a constructive solution with a low number of cases.

    There is an obvious structure for sizes $$$(3 a) \times (3 b)$$$:

    Spoiler

    Now, suppose the height is not divisible by $$$3$$$; if it's width instead, rotate the board. First we get solutions for odd width, that is, for $$$(2 k + 1) \times (3 t + 1)$$$ and for $$$(2 k + 1) \times (3 t + 2)$$$:

    Spoiler

    Finally, to get solutions for even width, that is, for $$$(2 k) \times (3 t + 1)$$$ and for $$$(2 k) \times (3 t + 2)$$$, we can repeat the second step of the pattern once, just to increase width by an odd number:

    Spoiler

    Here it is in code.

    → Ответить