### awoo's blog

By awoo, history, 3 weeks ago, translation,

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

• +116

 » 3 weeks ago, # |   +59 Why do Edu Round editorials take more time than usual?
•  » » 3 weeks ago, # ^ |   +52 Authors are lazy x)
 » 3 weeks ago, # |   +11 can anyone help me find what's wrong in this? submission D
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +25 Line 103, upper bound for segment tree is $m - 1$, not $n - 1$.Corrected submission
•  » » » 3 weeks ago, # ^ |   -21 You ar so gentle
 » 3 weeks ago, # |   +14 Solution for Problem C mentioned in this editorial is really nice.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +12 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 
•  » » » 3 weeks ago, # ^ |   +8 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.
•  » » » » 3 weeks ago, # ^ |   0 looks good to me!
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 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 )
•  » » » » 3 weeks ago, # ^ |   0 If cnt is a negative number, I think it is to replace the right bracket with a question mark to eliminate the left bracket. 1 from the remainder represents the left bracket, otherwise it is illegal.
•  » » » 3 weeks ago, # ^ |   0 Good Solution! Much wow.
•  » » » 2 weeks ago, # ^ |   0 it is so cool!
 » 3 weeks ago, # |   +6 problem C was harder than D
•  » » 3 weeks ago, # ^ |   +20 A was harder than D
•  » » » 3 weeks ago, # ^ |   -8 a[x] like if x is 1 then check if a of x not zero but for this a[a[x]] is not zeroInside a of x means first a of x for how this second give a[a[x]]Damage repair before happened Quote by me don't let someone hurt if he ask basic question
•  » » » 3 weeks ago, # ^ |   0 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
•  » » » » 3 weeks ago, # ^ |   0 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
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 3 weeks ago, # |   +5 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.
•  » » 3 weeks ago, # ^ |   +5 you can explain for me ??
•  » » » 3 weeks ago, # ^ |   +1 I'm on mobile. Ill answer tomorrow if nobody else explaons
•  » » » 3 weeks ago, # ^ |   +15 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.
 » 3 weeks ago, # |   +8 The problem 'D' was really nice. Thanks for the easy to understand editorial.
 » 3 weeks ago, # |   +8 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?
•  » » 3 weeks ago, # ^ |   +12 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.
 » 3 weeks ago, # |   +42 The idea of C is very elegant indeed. Very nice one!
•  » » 3 weeks ago, # ^ |   0 Can you explain this one? A shorter solution. https://codeforces.cc/blog/entry/105164?#comment-935234
 » 3 weeks ago, # |   +22 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?
•  » » 3 weeks ago, # ^ |   +1 the deepest LCA of some bad path -> it means the deepest lca between all the bad paths
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 say like sayEdit: I understood now :D
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 S={LCA of a path that it's weight=0} It means the deepest element in S.
 » 3 weeks ago, # |   0 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...
•  » » 3 weeks ago, # ^ |   +8 It's more commonly referred to as 'Sack' when referred to as a 'tree variant'.Here's the general idea — USACO Guide tutorialHere's the tree variant used in this problem — Arpa's tutorialThe 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}$.
 » 3 weeks ago, # | ← Rev. 2 →   +1 In the editorial of problem C, what the balance on the segment means?
 » 3 weeks ago, # | ← Rev. 3 →   +3 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?
•  » » 13 days ago, # ^ |   0 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.
•  » » » 13 days ago, # ^ |   0 I'm curious about why we didn't do anything like dp-reroot here.
•  » » » » 13 days ago, # ^ |   0 You're smarter than me idk wtf dp-reroot is. Would you be so kind as to explain?
•  » » » » » 13 days ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » 13 days ago, # ^ |   0 I see, thank you.
 » 3 weeks ago, # | ← Rev. 2 →   0 Can anyone explain why in second RBS we are swapping last opening and first closing.
•  » » 3 weeks ago, # ^ |   0 Think about this: you have two RBS $s$ and $t$. How we know that they are different?
•  » » » 3 weeks ago, # ^ |   0 we will check if s is equal to t or not
•  » » 3 weeks ago, # ^ |   +3 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.
 » 3 weeks ago, # |   0 Appeal of Educational Codeforces Round 132Dear 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 https://codeforces.cc/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 https://codeforces.cc/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-
 » 3 weeks ago, # |   0 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)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +19 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.
 » 3 weeks ago, # |   +1 Very interesting C & E! Thx a lotBut D may be too obvious.
 » 3 weeks ago, # | ← Rev. 3 →   0 What knowledge is "auto get =[&] (int l, int r)" in the main function?
•  » » 3 weeks ago, # ^ |   +3 I think it's a lambda expression.
 » 3 weeks ago, # |   0 What information is stored in the st table in question D？
•  » » 3 weeks ago, # ^ |   0 maximum on segment — we want to know the highest "wall" on path from left column to right
 » 3 weeks ago, # |   0 Getting Time Limit Exceeded for D. Can someone help find the mistake? https://codeforces.cc/contest/1709/submission/165440694
•  » » 3 weeks ago, # ^ |   0 you can check my solution i also solved it using segment tree https://codeforces.cc/contest/1709/submission/165454933
•  » » » 3 weeks ago, # ^ |   0 Actually I was not using fast i/o. After I added os_base::sync_with_stdio(false); cin.tie(NULL); it got accepted.
 » 3 weeks ago, # |   0 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)+qhttps://codeforces.cc/problemset/submission/1709/165448866How can I fix this?
•  » » 3 weeks ago, # ^ |   0 Can you try using fast i/o? I was also getting TLE. Try adding thisios_base::sync_with_stdio(false); cin.tie(NULL);
•  » » » 3 weeks ago, # ^ |   0 Thanks, it worked :)
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 https://codeforces.cc/contest/1709/submission/166149264I am getting TLE too, can you check please?Edit : I realised I was not passing the vector by reference hence it was slow. So this is how it feels to resume CP after 9-10 months.
 » 3 weeks ago, # |   0 Can somebody help me? I got WA on test 7 and I don't find the mistake 165467242
•  » » 3 weeks ago, # ^ |   0 Segment tree need n * 4 memory(in your case is 200000 * 4 = 800000 > 300000 * 2 = 600000)
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 May you explain to me Why does it need n * 4? :c
 » 3 weeks ago, # |   0 How to understand "MX = (n — XS — 1) / k * k + XS;"
•  » » 3 weeks ago, # ^ |   +5 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.
 » 3 weeks ago, # |   0 God I was so close for C, I incorrectly swapped the FIRST opening bracket with the first closing bracket
 » 3 weeks ago, # |   +2 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?
 » 3 weeks ago, # | ← Rev. 4 →   0 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.
 » 3 weeks ago, # |   0 Can someone please tell me why there is TLE on 165821052?
•  » » 3 weeks ago, # ^ |   0 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
•  » » » 3 weeks ago, # ^ |   0 Thanks :)
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 https://codeforces.cc/contest/1709/submission/166149264I am getting TLE too, can you check please?Edit : I realised I was not passing the vector by reference hence it was slow. So this is how it feels to resume CP after 9-10 months.
•  » » » 13 days ago, # ^ |   0 Can you tell me why I am getting wrong answer on that test case?
 » 2 weeks ago, # |   0 Why does Problem F have the tags of graphs and flows? Is there a graph solution to this problem?
 » 2 weeks ago, # |   0 Gosh. I knew I should have learned about FFT, my slothfulness gets me at last!