rsFalse's blog

opencup.ru: GP of Two Capitals
By rsFalse, history, 8 years ago, In English

Problem B was very interesting, but haven't overcome tc #7.

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

»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Do you really mean B? After seeing the dirty sample input I didn't want to even read the statement...

There were some nice problems, I enjoyed A/F/H, but overall I feel there were too many tedious tasks (especially in harder part).

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

    Yes, B, because I like dirty string problems xD . Moreover you should have not read the whole dirty sample, only edges of text chunks!

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

    Guys, how to solve task H and J? It's interesting tasks, but very hard for me. I think, J is very strange

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

      J: For a given query, BFS from both vertices simultaneously.

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

      J: For a query (x, y) first check if x and y are in different connected component (by dsu). If in the same component, run two way bfs. AFAIR shortest distance between two nodes in a random graph will be like sqrt(n) [not sure though].

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

        We implemented local generator/checker while working on this problem, and it turned out that query results are mostly in range 5..10. Now checking some papers (like this) it seems that it is O(log(n)).

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

    So which other tasks did you find tedious?

    Here's our approach to B: for each length-10 substring of text, we remember the list of lines where it appears, but only until we find 10 appearances — if we find more, we discard that string. Now we find all length-10 substrings of pages, and find which offset has the most matches. Only a few lines of code.

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

      The impression mostly comes from 3 of the 4 hardest tasks (B/E/G). B — the input contains lots of leading/trailing spaces and punctuations, E — this is indeed a traditional geometry implementation problem where you just need to generate all candidates and check them, and G — very complicated statement. But I have to admit that I didn't read the details of B/G carefully and they may be good against their appearances.

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

        Yeah, I think here you got deceived by the statements — I find both B and G very nice, G might be the most beautiful from the contest. I'll post my solution for it below.

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

      What was your approach for G by the way?

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

        First of all, thanks a lot for setting this amazing problem and for the contest in general! Might I ask how did you come up with this problem?

        My approach goes like this. Let's ask about the sum modulo 2 in each column. First, consider the case where all answers are 0 (it's not a special case in the solution, but it helps understand the general case). Then we can do the following: let's pick any row, and ask about its cells one by one. In case all of those come back as 0 as well, we have found a row of zeroes so we're done. In case one of those comes back as 1, we know there's another 1 in its column, since the sum of each column is 0 modulo 2, so we can just ask about other cells in that column one by one to find the second 1, and we're done.

        Now, let's solve the general case: when some columns have an odd number of ones. Let's split all rows into two almost equal halves A and B arbitrarily, and let's ask about sum mod 2 in rows from A in each column with total sum 1 (we also learn the sum in each such column in rows from B, by subtraction). Since the total sum in each "interesting" column is 1, exactly one of its sums in A and in B will be 0, and exactly one will be 1. Now we want to pick either A or B, and continue recursively with this set of rows and only with columns that have sum 1 in it, until at some point we have no columns with sum 1 anymore. Which one to pick between A and B? Well, in order for the recursive calls to converge, we need to maintain the invariant: the number of rows in our set is strictly greater than the number of interesting columns. Initially it's true (n+1>n), and since we split the rows into two parts and columns into two parts, it's not hard to see that it will still be true either for A, or for B — and that's what we should pick.

        What do we have after the dust settles? We have used at most n (initial column queries) + n (column queries on first split) + n/2 (column queries on second split, since we split the rows in two and the number of interesting columns keeps being less than the number of remaining rows) +n/4+... <= 3n queries. And we have the following artifact: we have a row such that for each column there's a segment of cells in that column that has sum 0 modulo 2 and contains the given row (whenever a column becomes "not interesting", we find such a segment for this column).

        Now we can just do the same thing we did for the case where all columns had sum 0: we iterate over our row, find any 1, and then find the second 1 in its column (it exists, since we have a segment with sum 0 there), spending at most 2n more queries, so overall we fit exactly in 5n as needed.

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

          Thank you! My solution is literally the same. This problem appeared in my research practice, the system described in the statement is called linear-splitting trees and the whole tree can be used as a proof of unsatisfiability of a boolean formula. This formula (for pigeonhole principle) is a good example of hard formula for many proof systems and it was natural to find upper bounds for depth of a proof for this formula.

          And it turned out that optimal approach for the prover here is that natural, I was amased myself when I found the solution. I'm so glad that you and two other teams solved it! I don't think many participants made it through the statement but I don't think it's possible to make it significantly clearer.

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

How to solve the problem I?

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

    The main idea is to generate grey table with white rectangle [i, n] × [1, i]. Given table satisfies this condition for i = 1. Then you can increase i by one in the following way. Using black pair you can generate tables which look like follows

    ...B
WWW.
WWW.
WWW.

    Then using column swapper you can get

    .B..
W.WW
W.WW.
W.WW

    Add initial rectangle 

    WWW.
WWW.
WWW.
WWW.

    to all these shifts and you got

    ....
WWWW
WWWW
WWWW

    Eventually you will get 1 × (n) white rectangle and applying this approach to it you will obtain grey table.

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

    The following picture represents our algorithm:

    Numbers under tables aren't actual numbers which were used to produce output since somewhere we added a table which is got from the 0th table by swapping rows and columns and contains two black squares sharing a vertical side, hence creating such tables changed the numeration. These numbers under tables are only for better explanation of some additions.

    UPD: here is the link to the picture if someone needs a better quality.

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

      That's very clear, thank you all!

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

How to solve K?

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

    Посчитаем cnt[i] — количество i-ых единичных битов в числаx Ai.
    Посчитаем sb[i] — i бит в S.

    Сумма всех чисел это сумма по cnt[i]*(1<<i).

    Заметим что мы можем заменить в сумме cnt[i]*(1<<i) на (n-cnt[i])*(1<<i) поставив в ответе на i позицию 1.

    Пусть dp[i][j][q] — миним. бит в ответе на i-2 позиции что на i-1 позиции стоит q и сколько перенеслось из меньших разрядов единичек(остаток)

    перехода всего 2:
    1. Ставим0наiпозицию.Если (j+cnt[i])%2=bs[i] то перейдём в dp[i+1][(j+cnt[i])/2][0]
    2. Ставим1наiпозицию.Если (j+(n-cnt[i]))%2=bs[i] то перейдём в dp[i+1][(j+n-cnt[i])/2][0]

    размеры дп: первый параметр это максимум 60. второй параметр может максимум быть n+n/2+n/4+n/8... < n+n

    не очень красивый и не оптимальный по памяти код

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

My solution of H is 3^m with cutting and it is passed(455ms). Is there faster solution of H?

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

    I think ours was O(2^m * n).

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

      and what was the idea?

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

        If you know the 3^m solution, you can notice that when considering submasks, there are only O(n) nonzero entries to consider, so that helps you get O(2^m * n) instead.

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

        Our idea: use inclusion-exclusion, now we need to quickly count the number of pairs that are separated by all sets from a given subset of our sets. We need to do bitwise-and of the mask of sets for each element and the subset, and now we need to pick k items from one mask, and k from its complement.

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

          So our (wrong) approach was something like:

          1. Pickup a subset of the given m sets, which would separate X and Y such that, "X < Ai" and "Y ^ Ai = empty" for all Ai in the chosen subset.

          2. So, compute: "^ Ai" and "^ ", which are candidates for X and Y.

          3. Take ncr(Size1, K)*ncr(Size2, k).

          4. If chosen subset size (in 1) was odd/event add/subtract the (3). And 2*(4) to include such pairs that "Y < Ai" and "X ^ Ai = empty".

          This is wrong because this overcounts something like: -> If Ai and Aj are two of the sets, then we double count those which has: "X < Ai and Y ^ Ai = empty" and "X ^ Aj = empty and Y < Aj". which we could not subtract.

          If I am not wrong 3^m solution is like: 3 types of sets:

          1. Do not consider for IE purpose

          2. These Ai's are like: "X < Ai and Y ^ Ai = empty"

          3. These Bi's are like: "Y < Bi and X ^ Bi = empty" Once we know all these sets, we can do like: candidate for X: "^ Ai ^ ", candidate for Y: "^ Bj ^ ", and then ncr(size1, k) * ncr(size2, k).

          Is that right? If so I was wondering how to reduce it to 2^m*n?

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

            So here's how the approach I propose is different (at the contest we submitted something more complex, so it hasn't been tested :))

            We have a subset of given m sets, let's call it B1, B2, ..., Bt. Now, instead of counting the number of X and Y such that X&Bi=Bi and Y&Bi=empty and then multiplying by 2, we compute directly what's needed: number of X and Y such that for each Bi, X&Bi=Bi and Y&Bi=empty or X&Bi=empty and Y&Bi=Bi.

            In order to do that, for each element we find a bitmask: bit 0 means "is it in B1", bit 1 means "is it in B2", and so on. Now sets X and Y need to be formed like this: for X we take k elements with the same bitmask, and for Y we need to take k elements with the complementary bitmask to X.

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

    Mine 2^m n * const got TL at onsite competition. I needed to precalc everything. :(

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

My solution of E is binary search about radius and check all the tangent line of two circles, but it didn't pass tc #21. Is there a counterexample of this algorithm? Then, what is the right approach to E?

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

    I don't know what's wrong with your solution, so I'll just describe our approach here.

    There're two major cases:

    1. There are at least two points on one of the four lines. In this case, we can fix these two points and binary search over the answer. For a fixed width, we can ignore all points that are inside the strip formed by the fixed line and the line parallel to it. We need to check that all other points are in some orthogonal strip. It's the case iff the difference between the smallest and the largest projection is no more than the width of the strip.

    2. Otherwise there should be at least one point on each line. Let's iterate over all ordered tuples of 4 different points and build a cross going through them (the cross is uniquely defined by these 4 points: we can write down a linear equation in the sine of the angle between one line of the cross and the x-axis. It's not the case if there're collinear or form a square, but these cases can be ignored).

    There are no other cases as we can rotate/squeeze any configuration without increasing the width of the strips until it becomes one of the two described above.

    This solution is O(n^5), which might seem a little bit too much, but it gets accepted with a couple of hacks.

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

    I think your solution is identical to ours but we had EPS issues, with 10 - 7 we got WA but with 10 - 8 we got AC.

    Just to confirm that your solution is identical to ours — we binary search on the size of the cross (call this s). We iterate over every pair of points. We find the two pairs of lines that have distance s from each other going through these lines (otherwise we just use the lines perpendicular to the segment), then we project all points onto these line and check if we could form a cross of size s.

    Our solution is therefore O(N3).

    → Reply