Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
for _ in range(int(input())):
x = int(input())
a = [0] + [int(x) for x in input().split()]
print("YES" if a[x] != 0 and a[a[x]] != 0 else "NO")
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]
r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]
for i in range(n - 1):
l[i + 1] += l[i]
r[i + 1] += r[i]
for _ in range(m):
s, t = map(int, input().split())
if s < t:
print(l[t - 1] - l[s - 1])
else:
print(r[s - 1] - r[t - 1])
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
auto check = [](const string& s) {
int bal = 0;
for (char c : s) {
if (c == '(') ++bal;
if (c == ')') --bal;
if (bal < 0) return false;
}
return bal == 0;
};
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
vector<int> pos;
int op = s.size() / 2, cl = s.size() / 2;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '?') pos.push_back(i);
if (s[i] == '(') --op;
if (s[i] == ')') --cl;
}
for (int i = 0; i < pos.size(); ++i) {
if (i < op) s[pos[i]] = '(';
else s[pos[i]] = ')';
}
bool ok = true;
if (op > 0 && cl > 0) {
swap(s[pos[op - 1]], s[pos[op]]);
if (check(s)) ok = false;
}
cout << (ok ? "YES\n" : "NO\n");
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(m);
forn(i, m) scanf("%d", &a[i]);
int l = 0;
while ((1 << l) <= m) ++l;
vector<vector<int>> st(l, vector<int>(m));
forn(i, m) st[0][i] = a[i];
for (int j = 1; j < l; ++j) forn(i, m){
st[j][i] = st[j - 1][i];
if (i + (1 << (j - 1)) < m)
st[j][i] = max(st[j][i], st[j - 1][i + (1 << (j - 1))]);
}
vector<int> pw(m + 1, 0);
for (int i = 2; i <= m; ++i) pw[i] = pw[i / 2] + 1;
auto get = [&](int l, int r){
if (l > r) swap(l, r);
++r;
int len = pw[r - l];
return max(st[len][l], st[len][r - (1 << len)]);
};
int q;
scanf("%d", &q);
forn(_, q){
int xs, ys, xf, yf, k;
scanf("%d%d%d%d%d", &xs, &ys, &xf, &yf, &k);
--xs, --ys, --xf, --yf;
if (ys % k != yf % k || xs % k != xf % k){
puts("NO");
continue;
}
int mx = (n - xs - 1) / k * k + xs;
puts(get(ys, yf) <= mx ? "YES" : "NO");
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 13;
int n;
int a[N], b[N];
vector<int> g[N];
set<int> vals[N];
void init(int v, int p) {
b[v] = a[v];
if (p != -1) b[v] ^= b[p];
for (int u : g[v]) if (u != p)
init(u, v);
}
int ans;
void calc(int v, int p) {
bool bad = false;
vals[v].insert(b[v]);
for (int u : g[v]) if (u != p) {
calc(u, v);
if (vals[v].size() < vals[u].size()) vals[v].swap(vals[u]);
for (int x : vals[u]) bad |= vals[v].count(x ^ a[v]);
for (int x : vals[u]) vals[v].insert(x);
vals[u].clear();
}
if (bad) {
ans += 1;
vals[v].clear();
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x; --y;
g[x].push_back(y);
g[y].push_back(x);
}
init(0, -1);
calc(0, -1);
cout << ans << '\n';
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

Why do Edu Round editorials take more time than usual?

Authors are lazy x)

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

Line 103, upper bound for segment tree is $$$m - 1$$$, not $$$n - 1$$$.

Corrected submission

You ar so gentle

Solution for

`Problem C`

mentioned in this editorial is really nice.I found another more elegant solution, but I don't know why it works.

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.

looks good to me!

consider ( as +1, consider ) as -1

means this ? is a (

`cnt == wh`

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

means all not sure ? must be )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.

Good Solution! Much wow.

it is so cool!

problem C was harder than D

A was harder than D

a[x] like if x is 1 then check if a of x not zero but for this a[a[x]] is not zero

Inside 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

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

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

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.

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.

you can explain for me ??

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

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.

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

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?

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.

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

Can you explain this one? A shorter solution. https://codeforces.com/blog/entry/105164?#comment-935234

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?

the deepest LCA of some bad path-> it means the deepest lca between all the bad pathssay like say

Edit: I understood now :D

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

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

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

In the editorial of problem C, what the

`balance on the segment`

means?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?

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.

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

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

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

I see, thank you.

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

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

we will check if s is equal to t or not

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.

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.com/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.com/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-

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)

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.

Very interesting C & E! Thx a lot

But D may be too obvious.

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

I think it's a lambda expression.

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

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

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

you can check my solution i also solved it using segment tree https://codeforces.com/contest/1709/submission/165454933

Actually I was not using fast i/o. After I added os_base::sync_with_stdio(false); cin.tie(NULL); it got accepted.

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.com/problemset/submission/1709/165448866

How can I fix this?

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

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

Thanks, it worked :)

https://codeforces.com/contest/1709/submission/166149264

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

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

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

May you explain to me Why does it need n * 4? :c

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

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.

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

For problem C, What if we modify the question and we have to find the

number of distinct ways to create an RBSfrom the given string. Can this be solved in better than O(n^2) time?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:

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.

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

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

Thanks :)

https://codeforces.com/contest/1709/submission/166149264

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

Can you tell me why I am getting wrong answer on that test case?

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

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