Educational Codeforces Round 132 Editorial

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
7	-is-this-fft-	150
9	pajenegod	145
10	BledDest	144

Tutorial

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

1709B - Also Try Minecraft

Idea: BledDest

Tutorial

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

1709C - Recover an RBS

Idea: BledDest

Tutorial

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

1709D - Rorororobot

Idea: BledDest

Tutorial

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;
}

1709E - XOR Tree

Idea: BledDest

Tutorial

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';
}

1709F - Multiset of Strings

Idea: BledDest

Tutorial

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

Comments (76)

Show archived | Write comment?

Abito

21 month(s) ago, # |

+59

Why do Edu Round editorials take more time than usual?

→ Reply

lis05

21 month(s) ago, # ^ |

+52

Authors are lazy x)

ashu_3916

+11

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

ToniB

← Rev. 2 →

+25

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

Corrected submission

vaibhav_t_3000

18 months ago, # ^ |

← Rev. 3 →

Why this Seg tree submission of D giving TLE: submission D

SergiiGolovko

15 months ago, # ^ |

Replace endl with “\n” in you output.

it was a fast I/O mistake, thanks btw

Can you please debug This solution of segment tree

https://codeforces.com/contest/1779/submission/187831216

arutsudar

+14

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

_Cade_

+12

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

Cat_cpp

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.

gongxi

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 )

Enoki

problem C was harder than D

racercoder

+20

A was harder than D

PMiguelez

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

TheOpChicken123

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.

MijPeter

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.

Slazenger

you can explain for me ??

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

Immerser

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

np_incomplete

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

chu65536

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?

freehandle

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.

+42

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

spookywooky

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

k1r1t0

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

uraqt

say like say

Edit: I understood now :D

Imdie

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

Ivan_len

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

nichke

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

moyan1082

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

people_plus_plus

19 months ago, # ^ |

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

Duy_e

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.

v_i_sh_a_l

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?

Gokix

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.

AINgray

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-

Pakgamer2022

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)

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

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?

Valenz

I think it's a lambda expression.

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

NTTilted

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

little_finger

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

faizanhussain2310

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.

rsegvic

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

Christopher_Rdz

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

Kawaii

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

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

awoo

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.

AW_Flister

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

nitin12384

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?

RedSnowstorm

← Rev. 4 →

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.

AIphaZero

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

Chilllll

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

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

jinsuichen

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

Socrates1232

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

parag776

19 months ago, # |

← Rev. 5 →

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?

rliu4936

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

Alex.Svanidze

When you enumerate matrix bottom-up in CP

18 months ago, # |

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

silenttkillerr

12 months ago, # |

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

anand.panda

9 months ago, # |

Regarding a solution of problem B.

165337873

std::cout << a[x] - a[y] + p[x] - p[y] << "\n";

I see that he made an prefix sum array for moving right. But I don't know how the same array is being used for moving left.

Please help.

abhinavgangil

6 weeks ago, # |

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.com/contest/1709/submission/249838457.

awoo's blog