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

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

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)
Разбор задач Codeforces Round 864 (Div. 2)
  • Проголосовать: нравится
  • +214
  • Проголосовать: не нравится

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

Super Fast Editorial

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

problem descriptions were very bad. learn english.

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

this contest is better than the previous one div2

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

Fast Tutorial.

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

Thanks for very fast editorial!

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

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

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

Very good contest!

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

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

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

    unordered_map can be "hacked" to be linear per operation

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

      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)

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

orz contest. Problems are gold

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

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

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

      E and F were Epic.

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

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

        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.

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

          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.

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

            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.

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

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

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

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

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

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

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

Thanks for good problems and lightning-fast Editorial!

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

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

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!

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

Great contest and fast editorial!

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

going to expert possibly:))))

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

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

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

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

    I'll fix them soon.

    UPD: fixed.

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

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

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

        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.

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

editorial faster than my code's time complexity

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

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

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

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

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

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)

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

Such a great contest, well done, authors

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

Nice problems,fast Editorial and fast ranting update.

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

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.

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

    three-point localization www

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

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

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

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

Probably the stupidest mistake ever in C.

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

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

Я снял видео-разбор задач A, B, C, D. Кому интересно, разбор можно посмотреть по ссылке: https://youtu.be/DjynOzLa818

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

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

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

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

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

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

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

    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)$$$.

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

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.
    »
    21 месяц назад, # |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nice problems

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

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

    https://codeforces.net/contest/1797/submission/201367288

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

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

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

    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!

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

    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.

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

    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

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

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

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

      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

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

        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)"

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

    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!

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

      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

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

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

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

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

    1797D

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

    ****

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

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

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

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

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

    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.

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

    oh,I think my mind is we

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

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

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

    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

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

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

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

    I think the problem descriptions were clear!

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

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

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

    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.

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

    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?

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

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

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

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

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

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

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

    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.

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

    For $$$E$$$, how do you not exceed the memory limit? Your parent function alone is $$$6 \cdot 5000000 \cdot 32 = 960MB$$$. How does this pass the memory limit?

    Memory limit should def be $$$1024MB$$$.