awoo's blog

Educational Codeforces Round 132 Editorial
By awoo, history, 2 years ago, translation, In English

1709A - Three Doors

Idea: BledDest

Tutorial
Solution (awoo)

1709B - Also Try Minecraft

Idea: BledDest

Tutorial
Solution (vovuh)

1709C - Recover an RBS

Idea: BledDest

Tutorial
Solution (Neon)

1709D - Rorororobot

Idea: BledDest

Tutorial
Solution (awoo)

1709E - XOR Tree

Idea: BledDest

Tutorial
Solution (Neon)

1709F - Multiset of Strings

Idea: BledDest

Tutorial
  • Vote: I like it
  • +116
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
»
2 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Why do Edu Round editorials take more time than usual?

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

can anyone help me find what's wrong in this? submission D

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Solution for Problem C mentioned in this editorial is really nice.

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

    I found another more elegant solution, but I don't know why it works.

        int wh = 0, cnt = 0;
    for (char c : s) {
        if (c == '(')cnt++;
        if (c == ')')cnt--;
        if (c == '?')wh++;
        if (cnt + wh == 1) {
            cnt = 1;
            wh = 0;
        }
    }
    if (abs(cnt) == wh) YES
    else NO
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      We can know that the number of left and right parentheses is the same, so we can eliminate the number of left and right parentheses. If there is a left parenthesis and 0 question marks in the elimination process, the number of left parentheses can be equal to 1 and the number of question marks can be equal to 0. If there are 0 left parentheses and a question mark, the question mark must be a left parenthesis, otherwise it does not meet the conditions. The number of last question marks must be greater than or equal to the number of unmatched parentheses. If the number of left parentheses is the same as the number of right parentheses, or the number of left parentheses is the same as the number of right parentheses, there is only one remaining question mark status. Otherwise, the number of question marks is greater than the number of left or right parentheses, and there are multiple statuses. English is not good, use the translation, I am a rookie, there are errors please point out.

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

      consider ( as +1, consider ) as -1

      if (cnt + wh == 1) {
     cnt = 1;
     wh = 0;
}

      means this ? is a (

      cnt == wh means all not sure ? must be (

      cnt == -wh means all not sure ? must be )

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

problem C was harder than D

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

    A was harder than D

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

      Not really, correct me if I'm wrong, but I think D is pratically impossible if you are not familiar with RMQs and this is not a basic concept, there are a few nice ideas involved in it and it isn't super simple to implement. I would say D is pretty much just about knowing the concept.

      But I agree that it's a pretty easy problem if you have some familiarity with RMQs

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

        Although it is true that if you dont know rmq u will not be able to solve the question, there are three things which really make D very easy. First of all, rmq is a very easy concept. It is one of the first u learn about range based queries. Secondly, the fact that it was very easy to spot that i had to use rmq was quite obvious because i have to know the maximum height of blocked cells between start and finish. Also thirdly, there is not much to the question other than rmq, there are very simple conditions when the robot cant get there: diff in height divisible by k, diff in length divisible by k, highest cell that can be reached is higher than highest blocked cell between start and finish. Thats all. Which is why its such an easy question. Note i havent even read editorial yet so i may be wrong

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

          Well, you are not wrong, I guess it's mostly about knowing RMQ, but I'm not sure how easy of a concept it really is. I didn't know about it's existance until around a week ago, you can get pretty far with little theoretical knowledge.

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

C needs more explanation. It s not obvious that pitting all opening brackets before closing ones gives us best chances of forming rbs.

Dont misunderstand me, i know how to prove it now.

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

    you can explain for me ??

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I'm on mobile. Ill answer tomorrow if nobody else explaons

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      When we check for RBS, we maintain a variable which increases by 1 when we get a ( and decreases by 1 in ). If this variable is non-negative throughout the string and zero at the end, then the string is RBS.

      Assuming we know the exact number of ( and ) brackets, replacing ? with ( brackets first will maximize the chances of the variable being non-negative. The second best way is to exchange the rightmost ( bracket and leftmost ) bracket.

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

        this is what i thought too.

        if i didn't see your reply i would have been stuck with this question forever!

        thank you <3.

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

The problem 'D' was really nice. Thanks for the easy to understand editorial.

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

I can't understand problem С solution. Why do we need to change brackets (To change the balance on a segment obviously but what does this give us?) and why is this condition sufficient?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Just think about how you can decide whether a sequence is an RBS. It's always safer to use open brackets as early as possible. That makes the first part, the safest replacement of question marks. Now the second safest replacement of question marks would be the one using the first closing bracket a little bit eariler.

    → Reply
»
2 years ago, # |
  Vote: I like it +42 Vote: I do not like it

The idea of C is very elegant indeed. Very nice one!

→ Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

E, "that's why we have chosen the deepest LCA".

LCA is the lowest commont ancestor of two vertex. Now, what is the deepest LCA of a path?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    the deepest LCA of some bad path -> it means the deepest lca between all the bad paths

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

    S={LCA of a path that it's weight=0} It means the deepest element in S.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any tutorial for small-to-large method? Seen this technique multiple times but never know what is it? Or can anyone explain the idea for this method...

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

    It's more commonly referred to as 'Sack' when referred to as a 'tree variant'.

    Here's the general idea — USACO Guide tutorial

    Here's the tree variant used in this problem — Arpa's tutorial

    The idea is practically the same (each node ends up in a subset at least twice its size), so we can move a node at most $$$\log{N}$$$ times, so the total complexity ends up being $$${N}\log{N}$$$.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

In the editorial of problem C, what the balance on the segment means?

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

    It's the difference of $$$cnt_($$$ and $$$cnt_)$$$. For example, balance $$$()()$$$ is $$$0$$$, for $$$()($$$ balance is $$$1$$$

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

In problem E, i don't understand why we can choose any vertex to be the root of the tree and still get the correct answer?

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

    changing the root of the tree doesn't change the tree at all. There are the same nodes, same edges, same paths, the only thing different is the visual look of the graph and the order in which we traverse nodes when we dfs. Therefore in most questions, it doesn't matter which node we use as the root. However, most of the time we use one because it is guaranteed that there is at least one node in the tree.

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

      I'm curious about why we didn't do anything like dp-reroot here.

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

        You're smarter than me idk wtf dp-reroot is. Would you be so kind as to explain?

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

          That just a kind of dynamic programing on tree which you should solve for all possible root of the tree. Otherwise it's not going to be optimal.

          You can easily find it on the internet

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

Can anyone explain why in second RBS we are swapping last opening and first closing.

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

    Think about this: you have two RBS $$$s$$$ and $$$t$$$. How we know that they are different?

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

    Think of what should we do to make it more possible to be a RBS?

    We know that if a sequence is a RBS, there is a equal expression: considering ( is +1 and ) is -1, and f_i means the sum of s_1 to s_i. For all the s_i = ), f_i is not less than 0. So we need to put more ( left and more ) right.

    Think about not swapping the last ( and the first ), for example, we swap the first ( and the first ), what will happen? Compared with the original swapping, all the f_i between the first ( and the last ( minus 1, and the other f_i is not changed. So our now choice won't be better than the original one.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Appeal of Educational Codeforces Round 132

Dear Sir or Madam， We got a message from the system after “Educational Codeforces Round 132”：

“If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. ”

So we followed the message to appeal. In fact, we did problem C last year and I did problem D this week coincidentally (The only difference of them is the way of input and output). That is why both of our code is similar to so many others. Some of them I don’t know before, they might have done the same problem before. Some of them are my friends, we have done these two problems together, and some of the code we use is the template we decided on together.

The rules in http://codeforces.net/blog/entry/8790 said this is allowed:

“Solutions and test generators can only use source code completely written by you, with the following two exceptions: 1.the code was written and published/distributed before the start of the round, 2.the code is generated using tools that were written and published/distributed before the start of the round.”

Here are the evidences. They all wrote before the contest 132! (If you need more evidence to judge, please contact me):

C: http://acm.hdu.edu.cn/showproblem.php?pid=4915（where we find C first）

http://t.csdn.cn/5qwDN（where we learn C first）

D: https://www.acwing.com/file_system/file/content/whole/index/content/6131167/ （the templates that we wrote and published）

We apologize for the extra work this has caused. But we did not break any rules. The same problems are what none of us want to see. Please correctly judge this special case and cancel the wrong punishment for us. We also want to know what to do next time we encounter the same situation. This is not the first time we meet the same problems in codeforces contest that we have done before. Since we are teammate, we need to make our code style same, use the same template, and work on the problem together (not in contest, when we learn). It always leads to the probability of being punished by mistake when we meet the same problem we have done before. We have already done the problem coincidentally before the contest, spending lots of time to learn how it work, But we still have to spend a lot of time modify code in contest to avoid being punished for mistakes. That sounds very unreasonable! Please judge correctly. Withdraw our wrongful punishment. And tell as what to do next time we meet such a situation. (We also don’t like this situation!). If there is anything else we can do for you, please let us know. Yours, AINgray and DeepLearning-

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was hard for me. I am a python code writer. Please before making contests think about other language coders too. Not only C++. (Don't take it wrongly. if you dont like it just comment)

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

    It should be pointed that there is no different intelligence factor between py coders and cpp coders.

    But py runs a little slower than cpp somehow, and some of the submission on D was hacked(TLE) because of this reason.

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

Very interesting C & E! Thx a lot

But D may be too obvious.

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

What knowledge is "auto get =[&] (int l, int r)" in the main function?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What information is stored in the st table in question D？

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

    maximum on segment — we want to know the highest "wall" on path from left column to right

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting Time Limit Exceeded for D. Can someone help find the mistake? https://codeforces.net/contest/1709/submission/165440694

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I keep getting TLE on D. I am using sparse table, complexity is mlog(m) for building and o(1) for [l, r] query. Total complexity should be mlog(m)+q

https://codeforces.net/problemset/submission/1709/165448866

How can I fix this?

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

    Can you try using fast i/o? I was also getting TLE. Try adding this

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me? I got WA on test 7 and I don't find the mistake 165467242

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

    Segment tree need n * 4 memory(in your case is 200000 * 4 = 800000 > 300000 * 2 = 600000)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to understand "MX = (n — XS — 1) / k * k + XS;"

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

    Consider the naive algorithm of finding the greatest number with the same remainder as $$$x$$$ modulo $$$k$$$ not exceeding $$$n - 1$$$. You would keep adding $$$k$$$ to the number as long as $$$x + k \le n - 1$$$. How many times can you do this? $$$\lfloor \frac{n - 1 - x}{k} \rfloor$$$ times. So the result will be $$$x$$$ plus $$$k$$$ added this number of times.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

God I was so close for C, I incorrectly swapped the FIRST opening bracket with the first closing bracket

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For problem C, What if we modify the question and we have to find the number of distinct ways to create an RBS from the given string. Can this be solved in better than O(n^2) time?

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

Edit: I understand now, there's no need to respond to this. I wasn't getting that the editorial was referring to the deepest LCA from all possible (x,y) pairs.

On problem E, I don't understand this part from the editorial: " We need to change at least one vertex on the path (x,y). It turns out that changing the vertex v is always no worse than changing any other vertex u on this path, because all the remaining bad paths that pass through the vertex u also pass through the vertex v " What about the following example:

           4
        /     \
       1       6(y)
    /     \
   3(x)     2(z)

Here the bad path we are trying to resolve is x-y (3->1->4->6) Their deepest LCA is 4. If we change the value of 4, we would leave the bad path x-z(3->1->2). So the optimal removal would actually be removing 1. How is this not contradicting the statement from the editorial? In other words, v is 4, u is 1. It isn't true that all remaining bad paths passing through u also pass through v.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why there is TLE on 165821052?

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

    Your time complexity seems alright. It's most likely a IO issue. I tried adding this to your code ios::sync_with_stdio(false); which basically means: "Do not sync C io with C++ io".

    I usually use that trick when in doubt — especially for old problems that have time limit of 1 second, which is, well, pretty strict compare to the normal 2-4 seconds limit.

    And here is the result 165906663

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does Problem F have the tags of graphs and flows? Is there a graph solution to this problem?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gosh. I knew I should have learned about FFT, my slothfulness gets me at last!

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

hey everyone in Question D

  • 10 10
  • 2 7 1 5 2 0 6 6 2 7
  • 10
  • 10 4 10 4 8
  • 1 6 8 6 7
  • 9 7 9 7 8
  • 8 1 8 10 3
  • 7 7 7 1 3
  • 6 4 6 4 8
  • 3 5 3 9 4
  • 5 9 3 1 1
  • 5 6 5 6 9
  • 8 9 2 3 6

in this test case which is test case No. 3 the 6th query, robot is starting and ending from a blocked cell right?

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

    yea there are other cases of the robot starting/ending at a blocked cell too, i think. There are many just in this test case. No. 4

    • 10 10
    • 2 10 1 5 2 0 6 10 2 7
    • 10
    • 10 4 10 4 8
    • 1 6 8 6 7
    • 9 7 9 7 8
    • 8 1 8 10 3
    • 7 7 7 1 3
    • 6 4 6 4 8
    • 3 5 3 9 4
    • 5 9 3 1 1
    • 5 6 5 6 9
    • 8 9 2 3 6
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you enumerate matrix bottom-up in CP

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

why this seg tree submission of D is giving TLE : submission D

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

What is problem in this solution for D Your text to link here...

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

I am getting a TLE on the submission in problem D even though i am using rmq with time complexity as O(mlog(m)+q)?.https://codeforces.net/contest/1709/submission/249838457.

→ Reply