TripleM5da's blog

GP of Baltic Sea
By TripleM5da, history, 6 years ago, In English

How to solve A and L?

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

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

Comments Comments (35)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

      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?

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

      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.

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

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

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

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

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

          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!

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

            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.

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

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

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

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

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

      Ye, that's what we did but somehow managed to face precision issues fixable by EPS.

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

        I managed to get with EPS = 1e-9, one should calculate impulses instead of velocities.

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

    Hmm, how did you use precalc for different modules?

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

      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.

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

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    My output looks like this
    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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$$$.

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

    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!

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

      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.

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

        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?

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

          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.

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

            oh I thought the constraints were up to $$$10^{11}$$$ my bad :"D.

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

      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

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

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

        Thanks for sharing!

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

    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$$$.

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

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.

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

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

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

      Oh, awesome! I knew that such decomposition exists but could not construct one explicitly!

      If anybody is interested, such decomposition is called tree-partition, it is connected with the standard treewidth: https://arxiv.org/abs/math/0602507.

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

        Bonjour tunyash, can you please share the problemset link? Thanks.

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

          I think it is not allowed in order to make the problemset reusable.

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

How to solve C?

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

    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.

    → Reply