chenjb's blog

By chenjb, history, 3 years ago, In English

Hello! I'm happy to announce XXII Open Cup: Grand Prix of Nanjing, which will be held on Dec 12th, 2021.

This contest is mainly prepared by SUA Programming Contest Problem Setter Team, which has already been used as the 2021 ICPC Asia Nanjing Regional Contest. There are around 700 teams participating in the Regional.

This is the fourth Nanjing Regional and the third Grand Prix of Nanjing in Open Cup, I feel very grateful and wish everyone enjoy this contest.

We also have an anonymous author this year. He provides a very interesting problem to this contest.

Authors: chenjb, TsReaper, jiangshibiao, shb123, quailty, Subconscious, oipotato

Testers: KAN, Um_nik, Merkurev, TLE, antontrygubO_o, Rewinding, J.T.J.L., tun, sfiction, cxt, pb0207, Eden_CY, Suika_predator, lwn_16, lxlxl, xpchf, liyang21, AkaiLemon, nothing100, UESTC_Nocturne, Orenji.Sora, Gromah, smax, arvindr9, RandomKami

Contest link: https://official.contest.yandex.ru/opencupXXII/contest/33444/enter (Only visible for users with OpenCup login)

Open Cup Scoreboard: http://opentrains.snarknews.info/~ejudge/res/res10559

Regional Scoreboard: https://board.xcpcio.com/icpc/46th/nanjing

UPD: The contest is in the gym now.

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

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

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I Love ChenJB. :)

»
3 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Thanks for the interesting problems!

How to solve problem L?

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

    Try to solve the problem assuming we may light/extinguish the central torch for each operation, then try to execute the same sequence by only lighting. While there are operations we can make, make them. In the end the remaining operations form consecutive groups, each of size 2. If there's an unlit torch next to such group, we can light it, do both operations in the group, then light it again, to the same effect. If all 2-groups are 1 apart, don't do anything as everything if fixed already.

»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

How to solve problem C? I tried dp on positions of x for every x that occures in the input but that approach gives WA7.

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

    Note that if you enumerate the mode x, you only care about x and x-k in the end. So enumerate all possible x and it becomes finding a maximum value for a prefix sum formula.

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

    I also got WA 7 at first because I mishandled the case k=0, you should check if your solution works in that case

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

      Yes, k = 0 was the problem. Got accepted after fixing that case. Thanks for your help!

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

      my code done right when k=0, but WA on test 5

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

        Write simple $$$O(n^3)$$$ bruteforce solution which tries all possible $$$(l, r)$$$ and applies operation for it. Find the answer by taking maximum over all such pairs. Also don't forget that you don't have to use the operation. After you have this solution write random test generator. Use bash/batch script to generate random tests, run both of your solutions on the generated input and compare output files. Do this while the output files doesn't differ. Most likely you will find some input where your fast solution fails while your correct but slow bruteforce solution doesn't. Then all you have to do is analyze the input and understand why your solution is wrong.

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

How to solve J?

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

    Apply the solution of ABC231 Problem E on the divisibility graph of the factors of b-a.

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

      Sorry I don't quite understand. How do you bring down a to 1?

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

        I think what you basically construct is the following. Let $$$p_1, p_2, \dots, p_k$$$ be the sequence of primes you use to divide by in the reverse order: $$$p_1$$$ is the last prime to be divided by. Let $$$x_0$$$ be the balance of minus-plus operations you perform after you divide by every prime, $$$x_1$$$ be the balance of minus-plus operations before dividing by $$$p_1$$$ and so on.

        Then you should choose $$$x_0, x_1, \dots, x_k$$$ in such a way that $$$x_0 + p_1 \cdot x_1 + p_1 \cdot p_2 \cdot x_2 + \dots = a$$$ and $$$\sum\limits_{i=0}^{k} |x_i|$$$ is minimum possible.

        So to reduce to the ABC problem, you make the sequence of coins the sequence $$$1, p_1, p_1 \cdot p_2, \dots$$$. The only difference is that you forbid the transition to $$$\left\lfloor \frac a x \right\rfloor$$$ if it's equal to $$$0$$$. I guess it's never optimal to go to $$$0$$$ instead of $$$1$$$.

»
3 years ago, # |
  Vote: I like it +62 Vote: I do not like it
pain
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    You will find the TL is even tighter in ECFinal 2020 G. We actually set a TL for those code which has no optimization in 4*4 matrix multiplication to pass while the std code runs within 500ms.

    It is trivial to halve the constant since you only need to compute the upper diagonal. And you may further find that you only need to compute C(4,2)=6 in the end.

    UPD: Not sure why it is 3s in gym for that problem now. When I was testing that one, it was set in 1s and you have to expand the multiplication to pass.

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

      That's interesting, we didn't manage to fit in the time limit even with an $$$n^3/6$$$ matrix multiplication without the following optimization: if the matrix is a unit one, we can skip push operation.

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

        Could you try submitting your TLE code in Gym again (with 64-bit compiler)?

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

          Now the optimized multiplication version without this push optimization passes in 1.2 (TLE 43 on the contest) (138919648), while an unoptimized one still gets TLE 23 (138920067)

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

            This is the one without any optimization: 138170891

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

              I guess my solution makes two modify operations for each operation, so maybe this matters. Or maybe my style of writing pushes whenever we enter a vertex is just too bad:)

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

                In my testing of seg tree codes, there are indeed ways of coding it that can be 70% slower with no apparent reason other than the way things are pushed. I'm sure it can get worse.

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

      No. I am just saying it is pain because I got AC 2 mins after contest ended.

      My TLE is not because of constant time... I used a sqrt solution and forgot to change bucket size to something that is not $$$2$$$ when I was submitting.

      I still dont actually know what the intended is...

      Code lol

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

        You simply use a segment tree to maintain everything you need: the length, the linear sum, the square sum and historical square sum. You can handle all pushdown and update by a 4*4 matrix.

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

    I use the sqrt decomposition also fit the time during the contest.

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

      A team from SJTU also wrote a sqrt decomposition in the Regional and passed it. I didn't generate data for this kind of solution. I am also wondering if there is any sqrt solution running in less than 1 second.

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

        After adding pragmas and tuning the bucket size, I have gotten my solution down to 436ms on the gym. I checked the status and this is actually the current fastest solution on the gym. 139039589

        Maybe it can be brought down even further if we made the code more friendly to be vectorized?

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I love statements taking INF time to load.

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

      Due to the Yandex system, Snark loads all opencup statements (for most rounds prepared in Polygon) by uploading an image directly. Meanwhile, you can always download a complete PDF by pushing a single button on the right.

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

How do solve D and H?

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

    H: Observe that if you enter a vertex $$$u$$$ for the first time, it can have at most two children from where you can collect the points. If it has some child $$$v$$$ with $$$t_v = 3$$$, you may go to some other child $$$w$$$, collect its points, come back to $$$u$$$ and then go to $$$v$$$. Alternatively, you may just go to some child and collect its points.

    Equivalently, we want to color the tree in three colors: white (did not collect points), black (did collect points) and red (did collect points but "in passing" like from $$$w$$$ above, without chance to collect points from its children). The coloring must satisfy the following constraints:

    • A red vertex may have only white children.
    • Any vertex must have at most one black and one red child.
    • A vertex can only have a red child if it also has a black child with $$$t_i = 3$$$

    and must maximize the sum of points in red and black vertices. This can now be solved using a classical tree dp, where $$$\mathrm{dp}[u][k]$$$ is the maximum number of points you can get from the subtree of $$$u$$$ given that $$$u$$$ has the color $$$k$$$.

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

      Hi there, I followed your guide, but maybe there's some bug that I cannot find, can you help me? Thx

      Implement
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        If you read the tree like this

         C[u].push_back(v); C[v].push_back(u); 

        Consider this testcase

        1
        5
        2 3 4 5 6
        1 1 1 1 1
        1 2
        2 3
        3 4
        4 5
        The answer for it is 20 but looks like your solution will output 2 because of this
        if (C[idx].size() <= 1 )
        {
        BLACK[idx] = VALUE[idx];
        RED[idx] = VALUE[idx];
        WHITE[idx] = 0;
        return;
        }
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Definitely, that's what I'm looking for. Thank you so much.

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

    D: This sorting algorithm can be reformulated as follows: construct an increasing subsequence greedily (start from the first element, each time take the next element strictly bigger then the current maximum), cycle shift it by one, then perform an insertion sort. And you need to print the length of the increasing subsequence + the number of swaps performed by an insertion sort. For one array this is easily done in $$$O(n\log n)$$$: find the increasing subsequence in $$$O(n)$$$, cycle shift it, then for each element add the number of distinct values on the prefix, that are bigger than this element.

    Now we need to recalculate the answer after adding an element to the array. If this element is not a maximal one, this is pretty easy, since it does not affect any of the previous steps. If this element is a new maximum, the length of the increasing subsequence increases by one, and also one more swap is needed for some iterations of the insertion sort. It is not hard to understand that this swap is needed for the elements that are positioned after the second occurrence of the previous maximum (hard to explain, but easy to understand from some examples). After that everything can be easily recalculated.

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

      Interestingly this sorting algorithm has been recently published as this

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

        LOL, I also wrote that kind of sort when I just began CP. I thought it was bubble sort.

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

          I thought it is the Bubble Sort for a long time when I began CP.

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

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

How to solve B, F, G, K?

Also, are there any solutions for E without any matrix multiplications?

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

    E: I'm pretty sure all solutions would be pretty much equivalent to matrix multiplications. The key here is that the operations (a += k and history += a^2) are linear operations on history, a^2, a, and 1, which lets us compose them succinctly. Matrices and matrix multiplication are just notations for linear operators, but I think all solutions probably rely on this linearity.

    F: There are 2 cases, either one polygon contains the other, or there's a separating line through the origin. In the first case, the outer polygon must exactly be the convex hull of all points, so we can check this solution. In the second case, we can sort the points by the angle to the origin, and then sweep the angle of the dividing line. Note that within each convex polygon, the points must be sorted by angle to the origin, so we can precompute whether each triple of neighboring points is actually convex. This lets us efficiently check the validity of any solution, so we can just take the max of all valid ones.

    K: This problem asks for the number of sets of 4 points which form and independent set, minus the number of sets which form a clique. Let's focus on counting the number of independent sets. We can count this using PIE: we want the number of sets of 4 points, minus the number of sets of 4 points and 1 edge among them, plus the number of sets of 4 points and 2 edges among them, etc. In particular, we need to add the number of sets of 4 points with 6 edges among them, i.e. cliques. Thus, we only need to count the number of each configuration of 4 points with up to 5 edges. These are:

    1. Four points with zero edges
    2. Single edge and 2 points
    3. Two edges with a common vertex and a point
    4. Two parallel edges
    5. Three edges sharing a common vertex (a claw)
    6. Three edges forming a triangle and a point
    7. Three edges forming a path
    8. Four edges forming a triangle with an extra edge attached
    9. Four edges forming a square
    10. Five edges forming two triangles glued together

    Of these values, numbers 1 through 5 are trivial, numbers 6, 7, 8, and 10 can be counted by enumerating all triangles, and number 9 requires counting 4-cycles. We do both of these in $$$O(E \sqrt{E})$$$ time. There are a few ways to do this, here's a pretty nice one.

    Sort all vertices of the graph by degree, and then direct each edge from the earlier (smaller) vertex to the later one. Then, we claim that each vertex has outdegree at most $$$\sqrt{2E}$$$. This is because all later vertices must have degree at least equal to your outdegree, but the total degree is $$$2E$$$, so there can be at most $$$\sqrt{2E}$$$ out-neighbors.

    Now, to enumerate triangles, we can casework on the edge between two smallest vertices; fixing this, there are at most $$$\sqrt{2E}$$$ choices for the outedge from the middle to the largest vertex, so we can enumerate all triangles in $$$O(E \sqrt{E})$$$ time.

    To enumerate 4-cycles, we will casework on the diagonal containing the largest vertex; let's denote that vertex by $$$z$$$ and the opposite vertex by $$$x$$$. Fix $$$x$$$, and consider every $$$y$$$ adjacent to $$$x$$$; then, $$$z$$$ must be an out-neighbor of $$$y$$$. Thus, we can enumerate them naively and count the number of times each $$$z$$$ is 2 away from $$$x$$$; taking those counts choose 2 gives the number of squares. The total runtime is also $$$O(E \sqrt{E})$$$, since each (undirected) edge is used twice as the edge between $$$x$$$ and $$$y$$$, and $$$y$$$ has at most $$$O(\sqrt{E})$$$ out-neighbors.

    We had this code in our ICPC book from before: https://github.com/ecnerwala/icpc-book/blob/master/content/graph/cycle-counting.cpp.

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

    G: Instead of diameter, we can maximize the length of some path instead (and don't care about any other paths). We can use $$$dp[p][x][y]$$$, meaning the maximum path length from node $$$x$$$ to node $$$y$$$, and that we are about to place $$$a_p$$$.

    For each path $$$(x,y)$$$, we additionally need to store the number of "free" edges we can use without extending $$$(x,y)$$$.

    For a fast transition, we add two more states: $$$dx$$$ is a boolean meaning we have not assigned some cost to the edge $$$(x', x)$$$ ($$$x'$$$ is the previous $$$x$$$), and $$$dy$$$ the same thing but for $$$y$$$. Then the transition depends on $$$dx$$$ and $$$dy$$$: in particular, if $$$dx=1$$$ we can either use a current "free" edge or iterate on vertices adjacent to $$$x$$$ for extending the path. If $$$dx=0$$$ we can either use a "free" edge or assign $$$a_p$$$ to the last edge of $$$x$$$ (so increase the value of $$$dp$$$ by $$$a_p$$$). Same for $$$dy$$$.

    Total complexity is $$$O(n^3)$$$.

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

    Can you explain, what is matrix idea to solve E?

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

      I'll skip the reduction to a single 1D segtree with "add on range" and "get a historic sum of squares on range".

      You can store a vector of $$$K$$$ values in each node of a segtree and represent your push (lazy update) operation as a $$$K \times K$$$ matrix that moves some of these values into others with different coefficients. Applying a lazy tag to a node is multiplying a vector by a matrix. Pushing a lazy tag into children is multiplying their matrices by yours.

      I believe, the sum of squares is a non-trivial part if you never encountered it. You want to transform $$$\sum \limits_{i=l}^{r} x_i^2$$$ into $$$\sum \limits_{i=l}^{r-1} (x_i + \mathit{push})^2$$$. Rewrite as $$$\sum \limits_{i=l}^{r-1}(x_i^2 + 2 \cdot x_i\cdot \mathit{push} + \mathit{push}^2)$$$ = $$$\sum \limits_{i=l}^{r-1} x_i^2 + 2 \cdot \mathit{push} \cdot \sum \limits_{i=l}^{r-1} x_i + (r - l) \cdot \mathit{push}^2$$$.

      Thus, this vector of values in a node responsible for the range $$$[l; r)$$$ can be $$$(\mathit{historic~sum~x^2}, \mathit{sum~x^2}, \mathit{sum~x}, r - l)$$$. So there are $$$4$$$ values and you need a $$$4 \times 4$$$ matrix to deal with them.

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

    B: we will try to reduce both graphs to canonical form. If canonical forms coincide, we perform the reduction for $$$A$$$, and undo the reduction for $$$B$$$ after that.

    If you make operations $$$(a, b, c, d, x)$$$ and $$$(b, a, c, d, x)$$$, weight of $$$ab$$$ edge will increase by $$$2x$$$, and weight of $$$cd$$$ will decrease by $$$2x$$$. This allows to change weights pretty much arbitrarily, preserving the total sum, as well as parity of each individual weight. We will "canonize" parity first, and then do some even steps.

    If $$$n$$$ is small (say, at most $$$5$$$), we can look for the lex. smallest reachable parity configuration with BFS. If $$$n = 4$$$, sum of opposite edge weights is always preserved, thus after parity fixing we can make all edges not adjacent to vertex $$$1$$$ to be $$$0$$$ or $$$1$$$, and that's canonical form. If $$$n = 5$$$, we can make all edges other than $$$(1, 2)$$$ to be $$$0$$$ or $$$1$$$ by transferring their weights to $$$(1, 2)$$$ with the $$$2x$$$ gadget above, possibly with an intermediate step.

    If $$$n \geq 6$$$, we can always make at most one edge have odd weight. If edges $$$ab$$$ and $$$cd$$$ are odd, and $$$e, f$$$ are any other two vertices, then applying operations to $$$acef, adef, bcef, bdef, abcd$$$ (all with $$$x = 1$$$) makes $$$ab$$$ and $$$cd$$$ even while preserving all other parities. Doing this repeatedly (possibly with intermediate steps, like above) we can make all edges, except possibly $$$(1, 2)$$$, have even weights. After that we can gather all even weights into $$$(1, 2)$$$ similar to the above.

    UPD: also I'm stupid and we just need to reduce the difference of $$$A$$$ and $$$B$$$ to all zeros lol.

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Is it right that scanf/printf are really slow on CodeForces?

During the Open Cup round, I used scanf and printf in problem H, it passed in less than 500ms. But when I submit the solution to gym after the contest, it got TLE (time limit is 2 seconds, so it's at least 4 times slower than Yandex.Contest).

Then, I replaced scanf with cin and fread, and they both got accepted quickly and in almost the same time as on Yandex.Contest.

Appendix
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Maybe you should try submitting with 32-bit compiler. I've seen this on others submission attempts to this problem.

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

      Thanks, you are correct. It got accepted.

      It's weird that the performance of scanf improves a lot when switching to a 32-bit compiler...

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

How to solve M?