Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

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

Автор ko_osaga, история, 9 месяцев назад, По-английски,

No threads, so I decided to make it.

Let's discuss!

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

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

Hard contest for our team.

What could be a reason for getting WA 44 on problem A?

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

    Overflow? You may need int128.

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

      Could you plase tell how to use int128? I can only do it with boost, otherwise sizeof(int128) shows 16 with g++/clang.

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

        I tested in my environment just now and sizeof(int128) showed 16. However, it seems operations with int128 are working for magical reasons. Looks quite strange.

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

        16 bytes = 128 bits, what's wrong?

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

how to solve F and G?

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

    G:

    tl;dr, compute how many 0 ≤ i < n, 0 ≤ j < m with or where g is gcd of 2(n - 1) and 2(m - 1) using inclusion-exclusion principle.

    First, let's get rid of grids and consider the point setting: a ray of direction (1, 1) shoots from the origin and reflects when hitting the boundary of [0, n - 1] × [0, m - 1] rectangle.

    For a point (i, j) in the rectangle, it is passed by the ray if and only if there are integers a, b satisfying one of the four conditions:  ± i + 2a(n - 1) =  ± j + 2b(m - 1). This condition comes from that we can pave rectangles all over the plane and ignore ray reflection.

    Above condition is equivalent to . Then by some elementary math skill and inclusion-exclusion principle we can calculate how many (i, j) satisfying the equation and get the answer.

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

    There's a 1 line formula... Let me see if I can remember it. Let Then the answer is

    You can find this by computing the number of times the bishop goes up and down the board (say $m < n$). This is going to be because the smallest integer k such that m - 1|k(n - 1) is . After that you count number of repeated squares, noting that a square can only be repeated twice or else you get a cycle.

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

    Got presentation error on TC#38... Any ideas of getting such a verdict?

    But I believe in my solution: 1) find how many times bishop needs to make a trip from one shortest side to opposite shortest side (it is: (min(N-1,M-1)) / gcd(N-1,M-1)), then multiply this count by length of this way (which is: max(N,M)), 2) subtract a number of intersections of ways, which is in a grid in a rectangle of ( max(N-1,M-1) + 1 ) x ( min(N-1,M-1) - 1 ), and a number of intersections is ( max(N-1,M-1) / gcd(N-1,M-1) + 1 ) x ( min(N-1,M-1) / gcd(N-1,M-1) - 1 ) / 2.

»
9 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Can we solve A without fighting with TL? log2 per query is not very easy to pass.

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

    We used N^2 dp for N <= 500 and logn * C (C <= 10, maybe smaller) otherwise, which passes pretty easily, although it's more boring to code

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

      Can you elaborate on how you calculated the k-th binomial of n choose c in O(log2)? We only managed to solve it by doing c binary searches (with increasing and decreasing step size), computing binomials at each step (O(log3) total).

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

        Oh you are right, it was C^2lgN indeed.

        Actually we had three cases : One for N <= 500, Other one for N <= 1000000, and N > 1000000. Second case is implemented with DP (as we know C < 10), so it’s ClgN per query.

        After the contest, we thought second case was overkill. But now I think we might got TL otherwise.

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

    Precalculate binomial coefficients bin[100][100] one time.

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

For problem D, we do dynamic programming on the state dp[odd][even][p], where odd, even is the number of connected components of odd/even size, p is the parity of the edges inside connected components that hasn't been added.

UPD: turns out to be a silly bug, the above dynamic programming should be correct.

»
9 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve I?

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

    Process intervals using a recursive function, starting with intervals containing a single 1, and discarding all intervals with duplicate elements. You can check if an interval of size s is a permutation by checking if its maximal element is s. After checking that, also process the two intervals obtained by extending the interval to the left or to the right to include its mex (smallest missing element).

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

    Let's find all intervals [L, R] such that

    • K = R - L + 1 is at least two.
    • AL, ..., AR is a permutation of 1, ..., K.
    • K is to the right of 1 in the interval.

    Try all N possibilities for R. For a fixed R, find the maximum i such that i ≤ R and ai = 1. Clearly, K is the maximum of ai, ..., aR. Now we can uniquely determine L because L = R - K + 1. Use hashes to check if aL, ..., aR is a valid permutation.

    It also proves that there are at most 3N good intervals.

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

      I guess, we have to perform this operation in both directions. If not, how do we find permutations starting from 7, 6 and 5 for input array 7 6 5 1 2 3 4 using this algorithm?

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

    Thanks. We also thought to make this "search" but didn't notice that there are not much good intervals.

»
9 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Any proof for I(that answer can't be bigger that 2*n)?

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

how to solve C?

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

    Just binary search over the coordinate of the line. Once you've fixed it, the problem becomes: find the convex hull and calculate its area. BTW, how to solve D?

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

      No binary search is needed. Just build convex hull iteratively (add points one by one) as a normal algorithm, but keep current area value as well. We compute that for each prefix and suffix so then we get an answer.

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

        Is building convex hull iteratively easy? Isn't this significantly nastier to code than a binary search (whereas normal convex hull is just copy / paste).

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

          I think he meant Andrew’s monotone chain. If you sort by pair of xcoord and ycoord, then this is a simple for loop just like normal convex hull, so not significantly nasty.

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

            Sorry, had to mentioned that. Convex hull with Graham-Andrew algorithm and sum of areas under every segment on top of that.

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

Why i couldn't enter the contest?

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

How to solve F?

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

    Assuming dpmask is the number of placing elements from n - k + 1 to n, where k is equal to the number of 1's in the mask and 1's in the mask correspond to the occupied places by numbers from n - k + 1 to n, such that after performing m given operations of swapping these elements will be in their positions (it means that n will stand at n-th position, ..., n - k + 1 will stand at (n - k + 1)-th position after performing all swappings).

    dp0 = 1.

    Then let's iterate over 0's bits in the mask and try to put there the value n - k (k is the number of 1's in the mask). It means we are processing (adding) elements from n to 1. Now we can check whether it's a correct mask or not. We know that the elements that are 1's in the mask are greater than n - k, and the elements that are 0's in the mask are less than n - k. Now we can construct sequence using number 0, 1, 2, where 0's stand on the positions, that are zero in the mask, 1 stands where we want to put n - k in the mask and 2's stand on the positions, where 1's in the mask. So we just sort this sequence applying given comparisons and if it's sorted in the end, we can do this transition.

    Spoiler
»
9 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Did anybody have problems with test 6 in D? Any ideas what test is it?

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

    We failed test 6 when we missed some initialization.

    No idea what the test is, though it should be a fairly simple test, IMO.

»
9 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

K?

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

    First, pick a lexicographically minimal length-k substring, and remove all strings which have such as substring.

    After that, you can append other length-k substring, possibly overlapping some. You should try to pick and append the substring to make it lexicographically minimal. (Note that length matters — in case of aabbbcc and aabbbccd, you should pick the former one, as it contains the latter one) After that, remove all strings which have such as substring.

    The limit is kinda small, but you should pick a reasonably fast DS or efficient code. I used std::set to maintain the strings.

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

      But what about test:

      2 1
      ad
      d
      

      I mean you choose substring 'a', then 'd' and we will obtain the answer 'ad', but we can delete 'a' from this answer and it still satisfies the statement about lying in each given string, but here is a contradiction with the second condition from the statement.