Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
bool solve() {
string s;
cin >> s;
vector<int> d(3);
int x = s[0] - 'A';
int y = s.back() - 'A';
if (x == y)
return false;
d[x] = 1; d[y] = -1;
if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2)
d[3 ^ x ^ y] = -1;
else
d[3 ^ x ^ y] = 1;
int bal = 0;
for (char c : s) {
bal += d[c - 'A'];
if (bal < 0) return false;
}
return bal == 0;
}
int main() {
int t; cin >> t;
while (t--) {
cout << (solve() ? "YES\n" : "NO\n");
}
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n, U, R, D, L = map(int, input().split())
for mask in range(16):
rU, rR, rD, rL = U, R, D, L
if mask & 1:
rU -= 1
rL -= 1
if mask & 2:
rL -= 1
rD -= 1
if mask & 4:
rD -= 1
rR -= 1
if mask & 8:
rR -= 1
rU -= 1
if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2:
print("YES")
break
else:
print("NO")
Idea: adedalic
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 calc(const vector<int> &a, const vector<int> &b){
int n = a.size();
int m = b.size();
vector<int> su(n + 1);
int r = m - 1;
for (int i = n - 1; i >= 0; --i){
su[i] = su[i + 1];
while (r >= 0 && b[r] > a[i]) --r;
if (r >= 0 && b[r] == a[i]) ++su[i];
}
int ans = 0;
int j = 0;
r = 0;
forn(l, m){
while (j < n && a[j] <= b[l] + j) ++j;
while (r < m && b[r] - b[l] < j) ++r;
ans = max(ans, r - l + su[j]);
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n), b(m);
forn(i, n) scanf("%d", &a[i]);
forn(i, m) scanf("%d", &b[i]);
vector<int> al, bl, ar, br;
forn(i, n){
if (a[i] < 0) al.push_back(-a[i]);
else ar.push_back(a[i]);
}
forn(i, m){
if (b[i] < 0) bl.push_back(-b[i]);
else br.push_back(b[i]);
}
reverse(al.begin(), al.end());
reverse(bl.begin(), bl.end());
printf("%d\n", calc(al, bl) + calc(ar, br));
}
return 0;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
const int N = 505;
int n;
int a[N][N];
int c[2 * N];
vector<pair<int, int>> e;
int calc(vector<int> ls) {
if (sz(ls) == 1)
return ls[0];
int res = -1;
for (int u : ls)
res = max(res, a[ls[0]][u]);
vector<vector<int>> ch;
ch.push_back({ls[0]});
for (int i = 1; i < sz(ls); ++i) {
int v = ls[i];
int group = -1;
for (int j = 0; j < sz(ch); ++j) {
if (a[v][ch[j][0]] != res) {
group = j;
break;
}
}
if (group == -1) {
group = sz(ch);
ch.push_back({});
}
ch[group].push_back(v);
}
int v = n++;
c[v] = res;
for (int i = 0; i < sz(ch); ++i) {
int u = calc(ch[i]);
e.emplace_back(u, v);
}
return v;
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> a[i][j];
for (int i = 0; i < n; ++i)
c[i] = a[i][i];
vector<int> ls(n);
iota(ls.begin(), ls.end(), 0);
int root = calc(ls);
cout << n << '\n';
for (int i = 0; i < n; ++i)
cout << c[i] << ' ';
cout << '\n' << root + 1 << '\n';
for (auto it : e)
cout << it.first + 1 << ' ' << it.second + 1 << '\n';
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef pair<int, int> pt;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
map<pt, int> allEdges;
set<pt> difPairs, eqPairs;
fore (q, 0, m) {
char tp; cin >> tp;
if (tp == '+') {
int u, v;
char c;
cin >> u >> v >> c;
if (allEdges.count({v, u})) {
if (allEdges[{v, u}] == c)
eqPairs.emplace(min(u, v), max(u, v));
else
difPairs.emplace(min(u, v), max(u, v));
}
allEdges[{u, v}] = c;
} else if (tp == '-') {
int u, v;
cin >> u >> v;
if (eqPairs.count({min(u, v), max(u, v)}))
eqPairs.erase({min(u, v), max(u, v)});
if (difPairs.count({min(u, v), max(u, v)}))
difPairs.erase({min(u, v), max(u, v)});
allEdges.erase({u, v});
} else {
int k;
cin >> k;
bool hasAns = !eqPairs.empty();
if (k & 1)
hasAns |= !difPairs.empty();
cout << (hasAns ? "YES" : "NO") << '\n';
}
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 300043;
int n, m;
set<int> g[N];
set<int> g2[N];
vector<int> res;
void euler(int x)
{
while(!g2[x].empty())
{
int y = *g2[x].begin();
g2[x].erase(y);
g2[y].erase(x);
euler(y);
}
res.push_back(x);
}
bool check(int c)
{
for(int i = 1; i <= n; i++)
g2[i] = g[i];
res = vector<int>();
euler(c);
int curm = 0;
for(int i = 1; i <= n; i++)
curm += g[i].size();
for(int i = 1; i <= n; i++)
g2[i] = g[i];
for(int i = 1; i < res.size(); i++)
{
int x = res[i - 1];
int y = res[i];
if(g2[x].count(y) != 1)
return false;
g2[x].erase(y);
g2[y].erase(x);
}
return curm / 2 + 1 == res.size();
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
g[x].insert(y);
g[y].insert(x);
}
for(int i = 1; i <= n; i++)
{
set<int> pr = g[i];
set<int> diff;
for(auto x : pr)
if(g[x].size() % 2 == 1)
{
g[i].erase(x);
g[x].erase(i);
diff.insert(x);
}
if(check(i))
{
res.push_back(-1);
for(auto x : diff)
{
res.push_back(x);
res.push_back(i);
}
printf("%d\n", res.size());
for(auto x : res) printf("%d ", x);
puts("");
exit(0);
}
for(auto x : pr)
{
if(g[i].count(x))
{
g[i].erase(x);
g[x].erase(i);
diff.insert(x);
}
else
{
g[i].insert(x);
g[x].insert(i);
diff.erase(x);
}
if(check(i))
{
res.push_back(-1);
for(auto x : diff)
{
res.push_back(x);
res.push_back(i);
}
printf("%d\n", res.size());
for(auto x : res) printf("%d ", x);
puts("");
exit(0);
}
if(g[i].count(x))
{
g[i].erase(x);
g[x].erase(i);
diff.insert(x);
}
else
{
g[i].insert(x);
g[x].insert(i);
diff.erase(x);
}
}
for(auto x : diff)
{
g[i].insert(x);
g[x].insert(i);
}
}
puts("0");
}
Good contest and editorial!
First time I will reach Pupil
Thanks for EaRly editorials.
It was a very fast Editorial Indeed. Anyhow, I loved the round. Thanks to authors !
Finally the editorial :)
Can anyone please help me understand why my approach to B is wrong? I have basically done a recursive backtrack since the possibilities are very small. 108948906
In this case , your code may first fill the top row just as the green line (n-1 case), then fill the rightmost column just as the blue line (n-1 case). However, the top-rightmost cell (in red circle) is covered twice , which is incorrect .
when L=0,U=n-1,R=n,D=0 ,your code will output "YES" but the correct answer is "NO" .
(Sorry for my poor English :P)
Thank for the (early?) editorials. I love the contest , especially problem D & E .
Problem B
The easiest solution And I Get AC
108991755
I also did it this way: My submission
I tried C using binary search but I am getting a TLE, I iterated through all the special positions and calculated the total number of boxes at special positions if we stacked all the boxes before the ith position and the last stacked box is at the ith position and added the untouched boxes at special position which are to the right of the ith position My submission. Could someone help with this please.
I did the same thing. Maybe looking at my solution would help.
I wanted to know the reasoning behind the TLE.
I think
std::findcausing the TLE since it's linear.Hey tyagsa .I replaced find to the map.I have gone AC 109024868. I'm think find works in O (N)
Can you briefly explain the naive algorithm mentioned in q? I am not even able to understand that :((
We cannot move boxes that are in negative positions to positive ones because we cannot pull boxes on ourselves.
So. we will solve for positive and similarly for negative, we add the results and print it! We can iterate to which position we will pull the boxes (the boxes to this position will be sequential). Is this position always a special position because it makes no sense to pull after a special position ?. binsearch will find how many boxes will stand consequtevely and again, binsearch will find how many consequtevely boxes are on superpositions and add suf [i + 1] to the answer, which is equal to the number of boxes that we have not moved but they are on special positions.
P.S. Sorry for bad English 109027439
i did the same thing as you at first got WA Here.
After reading your code i did a little change of lowerbound(checking if the value at the position we found with lowerbound is strictly greater than the value at out current special index and then decrease if strictly greater) to upperbound in the first binary search and got AC Here.
Can u help me in finding my mistake
[UPD: found mistake (accessing the end of array in some cases)]
Hey, your mistake in 2 point.
1)after first lower_bound -> (if(p[j] > sp[i]) j--;) i replaced it by if(p[j] == sp[i]) j++; think why?
2) and in second lower bound instead sp[i]-j i do sp[i]-j + 1. because we have j boxes, not j + 1
109054593 check it
Thank you. For highlighting these points, especially point 2 but in point 1 i think i was accessing the nth element in somecases. which was giving some garbage.(did this and got AC)
Appreciate your time and effor in correcting me. Thank You.
Thank you very much! never looked at the find function while debugging, will keep this in mind next time.
Thanks for the blazing fast editorial !
Complexity calculation of problem D did not seem so trivial to me. Can anyone explain the complexity of the model solution?
The time complexity is $$$O(n^{3})$$$
First of all let's find an upper bound on the number of vertices in the graph, that is, an upper bound on $$$k$$$, in terms of $$$n$$$.
I claim that the maximum number of vertices is $$$2n$$$. We can prove it by induction on depth (maximum distance from root to a leaf) of the tree. (Its really easy induction, you can try it yourself or lemme know in reply if you run into some trouble).
Now for each node which is not a leaf, let's observe what happens in the recursive function $$$calc()$$$ in the editorial code. The $$$O(n^{2})$$$ for loop is executed exactly once. Then a linear number of recursive calls for its children. So, if we sum up for all non-leaf nodes, ee have $$$nO(n^{2}+n)$$$ operations over all non-leaf nodes. Which gives us a time complexity of $$$O(n^{3})$$$.
Great explanation!
Another way to visualise the maximum possible number of vertices is this: Start with the root. For the current list of leaf-nodes, what would be the worst possible split? If there are $$$X$$$ leaves, it would be a two-way split of $$$X-1$$$ and $$$1$$$. The right list cannot be split further, and we assume a similar split for the left one. This would lead to $$$N$$$ leaves and $$$N - 1$$$ non-leaves (supervisors), giving us an upper bound of ~$$$2N$$$.
Why does this splitting yield maximum nodes? For each split you make, you gain a supervisor. For $$$N$$$ leaves, you can make a maximum of $$$N-1$$$ splits, and hence you can gain a maximum of $$$N-1$$$ supervisors.
Edit: ignore this comment.
Actually you are wrong in saying that each pair of nodes can be compared no more than $$$O(\log_2 n)$$$ times, for here you assume that the maximum number of levels is $$$O(\log_2 n)$$$, which is false, because if you look at the example provided by svince in the comment above, you will see that his tree has $$$n$$$ levels, so the bottom two leaves will be compared $$$n$$$ times here.
Edit: nvm made a mistake assuming the number of levels.
The time complexity is actually $$$O(n^{2}\log_2{n})$$$. Given a level in the tree, let the number of nodes in that level be $$$m$$$ and the number of leaf descendants for each node be $$$l_{j}$$$ where $$$1 \leq j \leq m$$$. Notice $$$\sum_{j=1}^{m} l_{j} = n$$$ and that the time complexity for processing the entire level is $$$O(\sum_{j=1}^{m} l_{j}^{2})$$$. This implies that the time complexity for the level is $$$O(n^{2})$$$ and the overall time complexity is $$$O(n^{2}\log_2{n})$$$ because the maximum levels in the tree is $$$\log_2{n}$$$.
if you see the above comment, I provided an example where the level of the tree is not $$$\log n$$$
I don't think that example justifies that for loops would run $$$\mathcal O(n^2)$$$ in the worst case. Since, that example claims that at each $$$n$$$ level you would split $$$x - 1$$$ and $$$1$$$ but the inner for loop would run only once for all $$$x - 1$$$ nodes due to the break statement and $$$x - 1$$$ times for the last node in the worst case. Summing up, the runtime of that example would be $$$\mathcal O(n^2)$$$.
I never said that the example justifies that the loop runs for $$$O(n^{2})$$$ in the worst case. I said that it is a counter-example to the assumption that there are atmost $$$\log n$$$ levels.
So unless you have a proof that the complexity is indeed $$$O(n^{2} \log n)$$$, your comment below means nothing to me.
Yes. You never said that. But your claim on algorithm's runtime $$$\mathcal O(n^3)$$$ implies that the loop would run $$$n^2$$$ times in the worst case. Unbeknownst to you, you made two people to feel wrong about the time complexity which is right.
In summary, the algorithm's runtime is not $$$O(n^3)$$$.
The proof would be writing a paragraph for me. But I already proved it can't be $$$O(n^3)$$$.
You're mistaken the depth would be $$$n$$$ but it's the number of nodes at the last level or leaf nodes. Since you mentioned it's trivial to see the number of nodes of the tree is $$$2n$$$ which implies it's a binary tree. And depth should be $$$log_2n$$$. Thus, it's $$$log_2nO(n^2 + n)$$$.
Ok, you are so wrong here in the last paragraph that I won't even bother correcting you. Have a nice day, and don't reply.
Actually, it's $$$\Theta(n^2)$$$ overall. Here's a precise estimation:
calcis obviously $$$\Theta(n^2)$$$, and dominated by reading the input.calcis called exactly once for each subtree, and hence at most $$$2n - 1$$$ times. In that call,lscontains each leaf in that subtree exactly once, andchgrows up to a size equal to the number of children of that subtree's root.calcwhich isn't $$$O(n)$$$ per call tocalc(and hence $$$O(n^2)$$$ overall) is the nested for loops. Totaled over every call tocalc, the inner for-loop is run at most once for each pair $$$(L, C)$$$ where $$$L$$$ is a leaf node and $$$C$$$ is a child of some ancestor of $$$L$$$. Thus, this inner loop runs at most $$$n \times (2n - 2)$$$ times, which is also $$$O(n^2)$$$ overall.Alternative solution for problem D (109027989)
Process pairs of nodes $$$(a, b)$$$ in increasing order of weight $$$w$$$. Consider the highest ancestors of $$$a$$$ and $$$b$$$. If they are equal, skip that pair. If one of them has weight $$$w$$$, connect it to the other ancestor. Otherwise, create a new node with weight $$$w$$$ and connect it to both the ancestors.
In problem B, I tried choosing the biggest number out of the 4, reduced its value to 0 and then correspondingly decreased the adjacent numbers by 1 if required (decreased both adjacent numbers by 1 if the chosen number is n or decreased the maximum of the adjacent numbers by 1 if it is n-1). Then, I checked if any number is negative (answer is NO) or all numbers are equal to 0 (answer is YES).
Keep repeating all the above steps until you get an answer.
I got a wrong answer for this approach. Can anyone explain why this is incorrect?
Regarding dynamic connectivity for problem F with larger constraints: All of the necessary information to answer the relevant connectivity queries in $$$O(1)$$$ is easy to calculate while building a DFS tree. (For each back-edge leading to $$$c$$$, which DFS-child of $$$c$$$ is its other side a descendant of? For each DFS-child of $$$c$$$, is there a back-edge to some ancestor of $$$c$$$ in that subtree? Is $$$c$$$ the root?) The reasoning is basically the same as for the famous classical algorithms for finding bridges and articulation points.
How to solve the problem F with n,m <= 2 * 10^5
@awoo in your editorial in problem C, both of these vectors are not used at all correct? would you mind removing this line if so?
Whoops, sure, they were used for a slow solution and I forgot to remove them.
Problem F was beautiful.
Can someone elaborate editorial for F? I can't quite understand meaning behind solution.
Can anyone tell me why (problem B) for test cases 2 1 1 2 2 answer is YES? should it not be NO? nevermind got it :)
I can't seem to find what's wrong with my implementation for question C, it's basically the same as the editorial, but I'm getting WA on test 2 on the 78th case.
It's coming 'tutorial is not available'!!