rui_er's blog

Codeforces Round 864 (Div. 2) Editorial
By rui_er, history, 19 months ago, In English

1797A - Li Hua and Maze

Tutorial
Solution (rui_er)

1797B - Li Hua and Pattern

Tutorial
Solution (rui_er)

1797C - Li Hua and Chess

Tutorial
Solution (rui_er)

1797D - Li Hua and Tree

Tutorial
Solution (rui_er)

1797E - Li Hua and Array

Tutorial
Solution (rui_er)

1797F - Li Hua and Path

Tutorial
Solution (Celtic, centroid decomposition)
Solution (rui_er, reconstruction trees)
  • Vote: I like it
  • +214
  • Vote: I do not like it

Comments Comments (107)
| Write comment?
»
19 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Super Fast Editorial

→ Reply
»
19 months ago, # |
  Vote: I like it -266 Vote: I do not like it

problem descriptions were very bad. learn english.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

this contest is better than the previous one div2

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Fast Tutorial.

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

Thanks for very fast editorial!

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I believe the diagrams in the editorial solution for A could have been much simpler, just block the TOP, BOTTOM, LEFT or RIGHT block depending on the position of either (x1, y1) or (x2, y2).

→ Reply
»
19 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Very good contest!

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

$$$n log^3$$$ with unordered_map constant got TL in E(((

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    unordered_map can be "hacked" to be linear per operation

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

      I know, but in fact, the number of different elements added was very small, O(logw), so it should still work fast enough, in O(1)

      → Reply
»
19 months ago, # |
  Vote: I like it +18 Vote: I do not like it

orz contest. Problems are gold

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -90 Vote: I do not like it

    seriously, were you guys paid to write these comments? what's good about this round? just mention one good problem

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      E and F were Epic.

      Overall, the contest was well balanced and the statements were clear so yes it is a good contest

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
        ← Rev. 2   Vote: I like it -22 Vote: I do not like it

        E and F were very standard problems, idk what you found epic about them, moreover you didn't solve them.

        The statements weren't clear at all(the coloring in B wasn't specific at the beginning, I found D hard to understand too), and very confusing.

        and A, B, C, D are pretty much on the same level, so I don't know what your definition of balanced is.

        → Reply
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it +45 Vote: I do not like it

          Please, don't cry over each contest you don't do well in and start blaming authors, contest you find bad others find great, just try to learn from mistakes you make and you'll eventually improve.

          → Reply
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            ← Rev. 2   Vote: I like it -56 Vote: I do not like it

            who is crying? my rank was even better than yours. I am just saying that there was nothing spectacular about the round, as people claim.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              19 months ago, # ^ |
                Vote: I like it +24 Vote: I do not like it

              Ofc you are saying this from a fake account…

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

        I think E is interesting but F are too classical, but it's a good and educational round though.

        → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      Yes we are. Maybe you should contact the authors and start making money?

      → Reply
»
19 months ago, # |
  Vote: I like it -21 Vote: I do not like it

The idea in E is segment-tree-beats, isn't it? I guess it is a hard E for div 2.

→ Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it +93 Vote: I do not like it

Thanks for good problems and lightning-fast Editorial!

UPD: as well as fast rating-changing within less than 1 hour after the contest.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Great contest!

Even tho I only solved A -> D but I had lots of observations on E, F and I think they're absolutely worth upsolving.

Waiting for more more rounds from you in the future!

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

    ya E has a beautiful observation. i also try to upsolve

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

    Can you explain use of DSU according to tutorial in the solution?

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest and fast editorial!

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

going to expert possibly:))))

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the link for the solution of F using RT is broken it is showing "you are not allowed to view the requested page"

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

    Oops, it seems that you can't view the submission. How can I share the submissions correctly?

    I'll fix them soon.

    UPD: fixed.

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

      Could you elaborate on how to calculate C in problem F in the RT solution ? Thanks in advance.

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

        Oh sorry, I forgot about this message.

        You first calculate the dfs number ($$$\operatorname{dfn}$$$) and subtree size ($$$\operatorname{sz}$$$) of every vertex on the max-RT. Then $$$u$$$ is in subtree of $$$v$$$ on the max-RT if and only if $$$\operatorname{dfn}(v)\le\operatorname{dfn}(u)\le\operatorname{dfn}(v)+\operatorname{sz}(v)-1$$$.

        Then, you dfs on the min-RT. Entering a vertex $$$u$$$, you have all ancestors of $$$u$$$ marked in the fenwick tree. You can use the dfs number and size on max-RT to calculate how many ancestors of $$$u$$$ on min-RT is in the subtree of $$$u$$$ on max-RT.

        → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1797/submission/201352138 WHat is wrong in this for B

→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

editorial faster than my code's time complexity

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Beautiful Contest, I like all the questions. Especially the C and D questions although easy to get solution tricky to implement!!

→ Reply
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

i am newbie can anyone tell why solution of problem a fail my approach to a was first i check for x1 and x2 at corners if they are at corners means that they only move two steps so we block only two steps if they not at corners but at first row or first column or nyh row or mth col they move only three steps then we need to block only three steps if they not at corners and also not at 1 or nthrow or mthcol then they must in between something in between so we move 4 steps so i check both this conditions for (x1,x2) and (y1,y2) and tale min of both of them so my pretest was pass during contest but fail on system test can anyone pls tell where my codes fails here is my code 201316107

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

    1 100 1000 100 100 50 50

    //ans should be 3,but output is 4

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

    First of all, I am also a newbie, but you seem to forget the case where n,m equals 1,2,3. If either n and m equals 1, the answer must be 1

    → Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Today I wrote the forbidden complexity in E, O(N log(W) sqrt(N)) !!

I didn't thought such atrocity could pass System test but it did.

Now I know that with seg tree I can do in O(N log^2 N)

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Such a great contest, well done, authors

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems，fast Editorial and fast ranting update.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is another solution in C which is maybe easier. Consider (x, y) as the answer we need to find. If we query (a, b), we will get max(abs(x — a), abs(y — b)) as answer. We can ask (1, 1) (get k1) and (2, 1) (get k2) and we have 2 cases. If k1 = k2 then y — 1 must equal to k1 cause if it not then k1 = abs(x — 1), k2 = abs(x — 2) => k1 != k2. If k1 != k2 then abs(x — 1) = k1, abs(x — 2) = k2 and we can calculate x. The final query will be (1, y) if you can find y or (x, 1) if you can find x.

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

    three-point localization www

    the problem can be harder if the 3 points are given and u need to calc the position

    → Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think C can be done in 2 queries, by querying (1, 1) and (n, 1) and then solving a system of equations.

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

    Consider this:

    • Board size $$$9 \times 9$$$
    • Distance from $$$(1, 1)$$$ is $$$4$$$
    • Distance from $$$(9, 1)$$$ is $$$4$$$

    Where is the king?

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

      (5, 1) ? maybe im missing something

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

        It could also be $$$(5, 2)$$$, $$$(5, 3)$$$, $$$(5, 4)$$$ or $$$(5, 5)$$$

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

          I think im misunderstanding something about the problem. If distance from (1, 1) is 4 , how can you reach (5, 5) from (1, 1) in 4 steps?

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

    10 10

    ? 1 1

    1

    ? 10 1

    8

    ! 2 1 or ! 2 2 ?

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

      How can it be ! 2 2, if distance from (1, 1) is 1?

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

        King can move diagonally so 2,2 to 1,1 is 1

        → Reply
»
19 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Probably the stupidest mistake ever in C.

I printed the string "! n m" instead of "!" and the values of n and m...

Spoiler
→ Reply
»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Thank you rui_er for excellent problems and fast editorial. I enjoyed the problems very much.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1797/submission/201344789 Can someone please tell me my mistake for Problem C.

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

    flush the output ( cout.flush(); ) after printing anything

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

    in the first test case for n=3, m=4, r=2, c=2

    you will get a=1, b=2, c=1 in your code and y=1 and x=-1

    while printing x and y you are printing -1(x) so you are getting wrong output format

    just dry run your code you will get it.

    → Reply
»
19 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Can someone explain the idea behind the Centroid-Decomposition solution in task F?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    Consider the operation of adding vertices. If we know the initial answer and array $$$f_n$$$ meaning the number of paths in which one end is $$$i$$$ and the other is the minimum, we can easily calculate the increase of the answer because the adding vertex must be the maximum. And we have $$$f_{n+j}=f_{k_j}+1$$$ in the $$$j$$$-th operation.

    Then we consider how to calculate the initial answer and array $$$f_i$$$.

    We can use Centroid-Decomposition. Denote $$$u$$$ as the current centroid. We can calculate the paths passing the vertex $$$u$$$. If we calculate the maximum and minimum from each vertex to the root, each vertex can be represented as a triple $$$(i,max_i,min_i)$$$. Then the answer passing $$$u$$$ is a two-dimension counting points problem. It can be solved in $$$O(n\log n)$$$. We need to do it again for each subtree because two vertices in the same subtree can't contribute to the answer.

    Total time complexity $$$O(n\log^2 n)$$$.

    → Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My approach to Problem C:
Find the distance from $$$(1,1)$$$ (let it be $$$k$$$), now the king must be on the following two segments:

  • from $$$(1,k+1)$$$ to $$$(k+1,k+1)$$$
  • from $$$(k+1,1)$$$ to $$$(k+1,k+1)$$$

    • Now take the intersection point of the two segments, i.e., $$$(k+1,k+1)$$$. Find the distance from $$$(k+1,k+1)$$$ (let it be $$$d$$$).
    You will have two possible options only: $$$(k+1-d,k+1)$$$ (let it be point $$$p1$$$) or $$$(k+1,k+1-d)$$$ (let it be point $$$p2$$$).
    In the third query find the distance from $$$p1$$$, if it's $$$0$$$ then print $$$p1$$$ else the king was on $$$p2$$$.

    Note : When $$$k+1$$$ exceeds either $$$n$$$ or $$$m$$$, then make the $$$x$$$ or $$$y$$$ coordinate to $$$n$$$ or $$$m$$$ (in the $$$2nd$$$ step). The approach/idea will remain the same.
    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Nice problems

    → Reply
    »
    19 months ago, # |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Could someone tell why I'm getting "wrong output format illegal query (test case 1)" in this code?

    https://mirror.codeforces.com/contest/1797/submission/201367288

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

      because the board has size n*m (n rows and m columns). You ask the question "? m 1". But there may be no line m, for example if n = 3,n = 5. (You are asking the question "? 5 1" and there are only 3 lines.)

      → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Submission Can somebody check why this is giving idleness limit exceeded on test 2. I have used endl and cout.fflush to flush the output. Thanks!

    → Reply
    »
    19 months ago, # |
      Vote: I like it -16 Vote: I do not like it

    Test 3 of the D is the worst ivention of humanity. But the xontest was really fun and i enjoyed solving it. I especially liked D. Also E feels a bit unbalanced for a div2.

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    I tried submitting my solution for C but it's continuously prompting ""wrong output format illegal query (test case 2)" on the first test case
    Link to my submission -> 201341675

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

      Got it! was just exceeding the upper limit for query. Will take care next time.

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

        what does it means? I am having the same issue please help.

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

      When the field is, for example, 8 by 5, and the first response to the request is "? 1 1" this is 7. The next query according to your algorithm will be "? 8 8" although this cell is located outside the field, therefore the error

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

        Thanks mate got it and sorted it out!
        I dealt with it by making a case for
        "if $$$query + 1$$$ exceeds n or m we know $$$query + 1$$$ is definitely the other co-ordinate."
        and I will just make another query to find the other element.
        in the example of 8 5 we ask
        "? 1 1" --> 7
        then since 8>5 we know 1st co-ordinate is 8 then the next query
        "? 8 1" --> something
        and
        "! 8 (something + 1)"

        → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    for problem E, rather than using a segment tree to solve everything, you can just use a sparse table to get the LCA of the range, and then get the minimum depth (depth = how far away is the number from 1) and the sum of depth using a seg tree. This leads to an O(w log w + n log n log w + m log w) sol (w log w for the sieve, n log n log w for sparse table build + seg tree updates, and m log w sparse table query). This could technically be sped up to O(w log log w + n log n log w + m log log w) but doesn't really matter.

    Here's the code (its a bit messy but still most understandable then the tutorial's solution in my opinion): 201387841

    Hope this helps!

    → Reply
    • »
      »
      19 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      You are not recalculating the lca after type 1 queries, the lca can change for certain (l,r) after a type 1 query involving some part of (l,r), you have only calculated for the initial values. Can you explain, please

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

        Instead of calculating the lca, we can find the depth of the lca. If the depth of one of the nodes in a range is less than the initial lca depth of the range, we know that that is the new lca. This is because if the depth is higher then the initial lca of the range, the lca will not change because the lca is still one of the node's ancestors, but if the depth is lower than the initial lca, the lca is no longer on of the node's ancestors, but now the node is one of the lca's ancestors, meaning this node is the new lca. This basically means that the depth of the current lca will be the min of the depth of the original lca and the depth of the current numbers in the range of (l, r).

        → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Can anyone finds the runtime error in this code? Thank you!

    1797D

    → Reply
    »
    19 months ago, # |
    ← Rev. 2   Vote: I like it -38 Vote: I do not like it

    ****

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Can someone help me about prblm e.. here is my solution.. https://paste.ubuntu.com/p/w9TBJNmBp5/

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    First interactive that i could solve. The problem statements were very clear looking forward for more such rounds

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

    Implementation based round that only exists to confuse with tricks and shortcuts. A round befitting of Chinese authors. The problems were god awful that only wants people to think how to implement, not how to solve.

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    oh，I think my mind is we

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    I have a different solution to problem E, does not require any dsu, just some logic + vectors + segtree.

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Problem E can also be solved using just a segment tree(struct tournament in a code) with sum on an interval. For each query operation we know that the answer must be one of the numbers which the leftmost element in an interval can turn into using some number of operations. For each element we will store that set of numbers and maintain the number of operations for each number in a segment tree. Also for each number we will store the set of indexes that can become that number using some number of operations. We can answer each query by binary searching on the set of numbers which the leftmost element can turn into. If we are currently answering a query and need to know if each element in an interval can become a given number, we need to check if all numbers in a given interval can turn into it(can be done using lower_bound() on a set and a segment tree) and calculate the sum of operations with the before mentioned segment tree. When updating an interval, we can update the elements one by one as mentioned in the editorial, and decrease the number of operations for all numbers that the current element can turn into by one. The tricky part of understanding this idea is how this segment tree works(ordering of the leaves is somewhat similar to how we order nodes in HLD) and how to maintain it.

    Code: 201457307

    → Reply
    »
    19 months ago, # |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can Problem E be optimized to $$$\mathcal{O}(q \log n)$$$ by maintaining the max and min dfn?

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    I think the problem descriptions were clear!

    → Reply
    »
    19 months ago, # |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    rui_er is there really a solution for problem E without $$$\Omega(n\log w)$$$ ?

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Hi. Can someone please help me out by letting me know why my submission 202689621 for $$$E$$$ fails?

    My basic idea is to maintain a single segment tree where every node is a pair of integers. First entry is their LCA and second is the minimum number of operations. While merging segments in $$$build$$$ and $$$query$$$, I have just climbed up starting from LCAs of both the segments. This process wasn't required in $$$update$$$ because we are doing point updates in which the node takes value of its ancestor which is just one level above it (its parent). So LCA of every segment containing it either changes just by one level or doesn't change at all.

    Thank you.

    → Reply
    »
    19 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Can anyone tell me Why this gives the wrong output? 205025905 But when I change the insert process of set -ve it works? 205025843 . What stl problem is creating?

    → Reply
    »
    13 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    Problem D- Li Hua and Tree Can someone what's wrong in this implementation?

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

    why My solution on problem B fails on test case 5 Here is my solution please explain me why?? my solution link is : https://mirror.codeforces.com/contest/1797/submission/250240610

    → Reply
    »
    7 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    For problem B, the image in the description about the rotation to 180 degrees, regarding the test case 2, doesn't seem right.

    → Reply
    »
    3 months ago, # |
      Vote: I like it 0 Vote: I do not like it

    For those who didn't quite understand well the D's idea, read about the rerooting technique. It feels more natural if you knows it.

    → Reply