Идея: BledDest
Разбор
Tutorial is loading...
Решение (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")
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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])
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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");
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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';
}
Идея: BledDest
Разбор
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
Why this Seg tree submission of D giving TLE: submission D
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.me/contest/1779/submission/187831216
Solution for
Problem Cmentioned 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.
consider ( as +1, consider ) as -1
means this ? is a (
cnt == whmeans all not sure ? must be (cnt == -whmeans all not sure ? must be )problem C was harder than D
A was harder than D
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.
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.
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.me/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 paths
say 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 segmentmeans?It's the difference of $$$cnt_($$$ and $$$cnt_)$$$. For example, balance $$$()()$$$ is $$$0$$$, for $$$()($$$ balance is $$$1$$$
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?
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.me/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.me/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.me/contest/1709/submission/165440694
you can check my solution i also solved it using segment tree https://codeforces.me/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.me/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 :)
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)
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 RBS from 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 :)
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!
hey everyone in Question D
in this test case which is test case No. 3 the 6th query, robot is starting and ending from a blocked cell right?
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
When you enumerate matrix bottom-up in CP
why this seg tree submission of D is giving TLE : submission D
What is problem in this solution for D Your text to link here...
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.me/contest/1709/submission/249838457.