chenjb's blog

By chenjb, history, 4 years ago, In English

Hello! Happy New Year! I'm happy to announce XXI Open Cup: Grand Prix of Nanjing, which will be held on Jan 10th, 2021.

This contest is mainly prepared by SUA Programming Contest Problem Setter Team, which has already been served as the 2020 ICPC Asia Nanjing Regional Contest.

Authors: chenjb, zimpha, shb123, TsReaper, oipotato, jiangshibiao, MudCoal

Testers: 300iq, Um_nik, Merkurev, KAN, jqdai0815, Suika_predator, lwn_16, lxlxl, Sugar_fan, liguanglin, lyk248289469. Thank you!

Contest link: http://official.contest.yandex.ru/opencupXXI/contest/24046/enter (Only visible for users with OpenCup login)

I will publish this contest to gym and please feel free to discuss afterwards.

UPD: An editorial written in Chinese Zhihu and I will make an english version later (hopefully).

UPD2: Now it is in the gym.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Your URL is wrong; it should have "opencupXXI" instead of "opencupXX"

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

    Thanks, I will update it immediately.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Div 2 link doesn't work

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

How to solve A and D?

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

    In A got AC by building very long path (diagonal zigzag)

    Funnily I've have had another solution which locally had better (33%) success rate but it couldn't get AC which is very weird

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

      Could you share that 33% one with me? I thought there should be some problems with that.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        20 20
        01111011111001111101
        11001010001011000101
        10011010111010111101
        10110110100110100011
        10101101101101101110
        10111011011011011000
        11000110110110110111
        01011101100101101101
        11010011010111011011
        10110110111010110101
        10101101101101101111
        10111011010111011000
        11000110111000110111
        01011101101011101101
        11010011011010011001
        10110110110110010111
        10101101100101110100
        11101011010111000111
        00011010111000111001
        11110111101111101111
        
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I run 10 stress tests under different seeds, the result is below:

          95 times hack
          103 times hack
          104 times hack
          97 times hack
          102 times hack
          116 times hack
          130 times hack
          98 times hack
          116 times hack
          112 times hack
          
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks, must be some kind of error in local checker

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

            Turns out the basic rand() that local C++ compiler has gives 33% but after switching to proper random it dropped to just 20%. One more proof that C++ rand() is garbage.

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

              In the regional, some teams asked me to justify whether the checker is correct because of this issue. Then we found that using rand() under windows will somehow give a much higher hack ratio.

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

              Wow, I have heard a few times that C++ rand is not great from the cryptographic perspective, but I never imagined it can actually be distinguished from better randomness in "real life scenarios" o0

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

      I also did diagonal zigzag but first got WA. Then I only changed cout << grid.at(i).at(j); to cout << grid.at(19-i).at(j); and go AC...

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

        This is possible. A diagonal zigzag without any adjustment may got failed in some tests if unlucky. 125/500 is a little bit tricky. While if you make few adjustments to make full use of grids and build some traps, you construct will be more stable...You see I was going to set 5*125/500 tests but soon I realize this is too mean...

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

    Strategy in D: call vertex bad if its degree is more than $$$n/2$$$. While there is an edge between bad vertices, delete such edges. It will not break graph connectivity. After that while there is an edge with one bad end which is not a bridge, delete it. After that if there is still a bad vertex, answer is "No", otherwise find any spanning tree.

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

      How do you incrementally figure out whether an edge is a bridge or not? You can delete an edge and then some edge that didn't use to be a bridge now becomes one and figuring that online seems quite difficult

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

        Find any spanning tree and delete only edges outside of it. After that there will be at most one bad vertex. If you delete it and find connected components of the remaining graph, then you need one edge going to each component, so you can delete all the other edges.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

EZ win xDDDDD

We: 1353min

Past Glory: 1354min

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my brain exploded after trying to hack A 69 times))))))) you have no idea what tests I tried...

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

    plz someone write a map from A. i really tired very much because of this shit(

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Spoiler
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

complicated enriched segment tree beats: 28 AC

trivial geo where you just need to check whether two segments intersect: 17 AC

People really need to stop being so afraid of geometry xd

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

    I didn't even know there was geometry. Reading all the statements is too hard.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +29 Vote: I do not like it

      Just go through statements and search for "x_i y_i" in input section =] (and make sure statement doesn't mention rectangles so that it is not some stinking sweeping instead of real geometry). I do that in first 5 minutes of every contest :D

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

    Both Yuhao and I are very curious about this issue too. In the regional, only 1 team solved I while 14 teams solved J. And testers solved I in the early period of 5 hours.

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

    At first read, we thought you'd have to do the plane-sweep interval expanding/merging thing, before we realized that there are easier solutions because of small bounds. Perhaps other teams had this mistake too?

»
4 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it
Problem I
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Will be the editorial published?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    We had already made a Chinese version and I may make an english version and publish the contest onto gym as soon as I got out of hospital~

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve problem B?

»
4 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

How to solve C and J?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it

    J: if the bitwise xor of all pile sizes is $$$X$$$, you want to compute number of values $$$v$$$ in range satisfying $$$v\oplus X < v$$$. This happens precisely when $$$v$$$ has a $$$1$$$ at the most significant bit position of $$$X$$$. So maintain bitwise xor and count of values with a $$$1$$$ for each bit position, handle the update with segment tree beats (you need to additionally maintain minimum, count of minimum, and second minimum).

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

      I managed to squueze $$$O((n+q)\sqrt{n} \log {A})$$$ in 2.052s in upsolving.

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

    C:

    Let's assume you first move in the following order exhausting moves of each type: Right, Left, Up, Down.

    Suppose you move initially $$$x_r$$$ units to the right. Let $$$y^r_{hi}$$$, $$$y^r_{lo}$$$ be the maximum/minimum $$$y$$$ coordinate of the points to the right of $$$x_r$$$. Then go to left up to $$$x_l$$$, and let $$$y^l_{hi}$$$, $$$y^l_{lo}$$$ be the highest/lowest $$$y$$$ coordinate of the points to the left of $$$x_l$$$.

    The answer to the problem is: $$$2 \cdot x_r + |x_l| + 2 \cdot \max(y^r_{hi}, y^l_{hi}) + \max(|y^r_{lo}|, |y^l_{lo}|)$$$ [1]

    To compute this efficiently, we should store for all coordinates $$$x_l \le 0$$$ the four values: $$$x_l + a \cdot 2 \cdot y^l_{hi} + b \cdot y^l_{lo}$$$ where $$$(a, b) \in (0, 1)^2$$$ in a data structure such as a segment tree to query for minimums.

    Fix each $$$x_r$$$ and, and depending on the values of $$$y^r_{hi}$$$, $$$y^r_{lo}$$$ you can determine using binary search some intervals to the left where you know in the equation [1] which terms of the $$$max(\cdot, \cdot)$$$ will dominate, and query for minimum in that intervals on relevant segment tree.

    Finally, since the order of the moves (LRDU) affects the answer, you should try the four of them, flipping $$$x$$$ and $$$y$$$ axis, and solving the problem multiple times.

    Code

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Did other people get B accepted with some sensible solutions? We just got shameless $$$O(n^2)$$$ because who gives 10 seconds TL (which was 14 seconds in statements >:[) with $$$n \le 50000$$$

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

    The intended solution goes with O(nlog^2n) or even O(nlogn) from zimpha. I got no idea with the TL on Yandex and all work are done by snark since I stayed in hospital for about a week :(

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

      Why was the time limit so high then? It looked like the intended was O(n sqrt(n) log(n)) or something. My O(n log^2(n)) takes only 231ms to run. The time totally could've been way tighter if that was intended.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Strange. I check both mashup and polygon, the TL is supposed to be 5000ms... The runtime of std takes 2600ms...I don’t know what happened when it is moved to Yandex.

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

          The reason could be that the std runs extremely slowly on Yandex (which happened before) and the. Snark have to set it to 10s.

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

            Std runs 3.6s.... So I got no idea why TL is 10 or 14s...Sorry for this issue, should be tighter though.

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

              Is std model solution? What does it stand for? If it runs 3.6s on Yandex then 5s would be really cruel... And we needed just 5.9s xd

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

                I think std stands for "standard", as in "gold standard"/model solution? Not too sure.

                If std took 3.6s, then 10s time limit is reasonable. Why does std take more than 1 second for $$$O(n log^2(n))$$$ when $$$n \le 50000$$$ though? That constant seems really bad.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Yes, it behaves badly on Yandex, but it is O(nlog^2n) after all. If 3.6s on Yandex, a better idea is to ask the author provide one with smaller constraints, or this seems a little bit ridiculous. I think sqrt solutions (sqrt*log or sth else) can be allowed to pass, but personally I don’t want n^2 to get passed. But never mind LOL

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    My solution was a pretty standard "merge smaller into bigger on suffix tree" idea.

    The hard part of this problem is counting the number of $$$i$$$ so that $$$s[k \ldots n]<s[i \ldots n]$$$ but $$$r-k+1 > lcp(s[k\ldots n], s[i \ldots n]) \ge r-i+1 \ge 1$$$ (note in particular that this condition implies $$$k < i \le r$$$). (The other cases are simple rectangle queries on the set of points $$$(i,rank(s[i\ldots n]))$$$ from the suffix array of the whole string, though you could do smaller into bigger too if you wanted.)

    To solve this case, we run merge-smaller-into-bigger on the suffix tree. For each node, we store a set of queries with $$$k$$$ in this subtree satisfying $$$r-k+1 > height$$$ sorted by $$$r$$$, and a sorted set of indices $$$i$$$ in this subtree. You can maintain these with smaller into bigger.

    Then, we just need to handle all valid query/index pairs from 2 siblings being merged (queries from the left sibling and indices from the right). Once again, we use smaller into bigger. If there are fewer queries than indices, loop over the queries $$$r$$$ and count the number of indices with $$$r\ge i > r-height$$$ (so we should store the indices in an order statistic tree, I used PBDS). If there are fewer indices than queries, then for each index $$$i$$$, add one to all queries $$$i \le r < i+height$$$ (so we should store the queries in a BBST or compressed seg tree with lazy propagation, I used treap).

    All of this is trivial to analyze as merge-smaller-into-bigger with O(log(n))-time data structures, so it naturally achieves O(n log^2(n)). In fact, splay trees and treaps and some other BBSTs can perform union of sets of size $$$m<n$$$ in $$$O(m \log(n/m))$$$, so if we use those for everything, we can get $$$O(n\log(n))$$$ runtime.

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

      That's exactly what we hoped for — that you guys will go for a fair solution instead of gaming the system like us haha. Maybe that's what we need to win anything xD Radewoosh was hiding from the rest of us what he is trying to do because me and Marek would try to convince him to solve it in a typical way, but he turned out to be right :p

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

        In fairness, this solution only took ~40 or ~50 minutes to implement, and I got it without any dirt, so I'm not sure squeezing would've worked out better. We were considering it, but decided not to try.

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

      Just to confirm, "The other cases are simple rectangle queries" what are these cases? Or in other words, are you missing "k < i" condition from what you wanted to count in second paragraph?

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

        Yes, here are the other 2 cases:

        • Case 1: $$$k < i \le r$$$ and $$$lcp(s[k \ldots n], s[i \ldots n]) \ge r-k+1$$$.
        • Case 2: $$$l \le i \le r$$$, $$$s[i \ldots n] < s[k \ldots n]$$$, and $$$lcp(s[k \ldots n], s[i \ldots n]) < r-k+1$$$.

        Note that the LCP/string conditions just correspond to a range of the suffix array, so these are rectangle queries.

        In the second paragraph, $$$k < i \le r$$$ is implicit because $$$r-k+1 > r-i+1 \ge 1$$$ (sorry about that confusion).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

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

    Solution of E: Contestants may solve it with a bunch of case analysis. But the intended solution is that there must be a permutation that doing all U,D,L,R together. So enumerate all 4! and check whether it is legal.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    F (fixed point approach): As we want the minimum making optimal decisions, we can build a recursion:

    $$$E_i = \min (m + (1 - \frac{p}{10000})^i E_0, n + E_{i+1})$$$

    note. $E_i$ is the expected time to rest with i unused fireworks.

    Our main problem is that we need $$$E_0$$$ to solve the problem. If we take a closer look at the recursion, we can realize that:

    $$$E_0 = \min\limits_{i \ge 0}(m + n i + (1 - \frac{p}{10000})^i E_0)$$$

    We can notice that if the $E_0$ on the right is fixed, the function with respect to $$$i$$$ in the positive reals is convex. now we can solve the problem by noting that the resulting value minus the set value gives us the direction of our optimal value in the binary search (if I set a lower value, the minimum takes a higher value and closer to our solution, if I give it a higher value, the minimum takes a lower value.).

    double lo = 0, hi = 1e12;
    for (int i = 0; i <= 65; ++i) {
      double mid = (lo + hi) / 2;
      if (f(mid) - mid >= 0) lo = mid;
      else hi = mid;
    }
    

    To solve each subproblem in good time, note that the minimum value takes it in:

    $$$i = \max(0, \log_{\beta}(\frac{-n}{x \ \log \beta})))$$$

    note. where $x$ is the fixed value and $$$\beta = (1 - \frac{p}{10000})$$$

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I have a faster solution for I.

Using a binary search for the answer, it's possible to reduce the problem to checking if there is a path satisfying a certain horizontal speed limit.

Let a point be reachable if it is the end of a correct path. It's possible to bypass all obstacles iff there is a reachable point above all of them.

Let's use scanline to find reachable points. Initially, the scanline is located below the obstacles and reachable points form a segment $$$[-m, m]$$$. I claim that at any height reachable points lie in a union of segments. Consider a range $$$[y_1, y_2]$$$ of heights where no obstacles start or finish. To recalculate a segment of reachable points while moving the scanline through this range, one can do the following steps:

  1. Expand the segment by $$$\frac{v_x}{v_y} \cdot (y_2 - y_1)$$$ from both sides

  2. Find obstacles that are the nearest to the right and the left.

  3. Intersect it with the segment formed by the upper points of the obstacles.

Picture

The only case when the number of segments increases is when a segment is split by a starting point of a new obstacle. Therefore, the number of segments is $$$O(n)$$$ and the overall complexity of this solution is $$$O\left(n^2 \log \left( \frac{C}{\varepsilon} \right)\right)$$$.

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

    This is the idea we initially had as well. I think you should be able to do this in $$$\tilde{O}(n \log(n))$$$ by maintaining events and whatnot, but I haven't worked out the details.

    Regardless, this solution is faster by asymptotic runtime, but not by time to AC!

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

      Isn't tilde over $$$O$$$ supposed to ignore logarithmic factors?

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

        Yeah, I was going to ignore them, but $$$\tilde{O}(n)$$$ just looks too small, you know? I am ignoring factors of $$$\log(1/\varepsilon)$$$ though.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used Google Translate to translate the editorial of problem B from Chinese. And I struggle with understanding it.

"For this tree, the points with only one son can be removed, so that $$$O(n)$$$ points are obtained."

Why $$$O(n)$$$ points are obtained?

"Then, for those who have $$$k$$$ sons, a binary tree of size $$$2k-1$$$ can be constructed."

Which binary tree?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be really helpful if there is an english editorial, the chinese one with google translate is sometimes a bit difficult to understand. Please look into this if possible, and thanks for great problems.