Thank you for participating! We hope you enjoyed the problems!
1805A - We Need the Zero
Idea and preparation: Alexdat2000
Hint 1
Recall the basic properties of the $$$\oplus$$$ operation: $$$A \oplus 0 = A$$$, $$$A \oplus A = 0$$$, $$$A \oplus B = B \oplus A$$$.
Hint 2
Consider the cases of even and odd array lengths.
Editorial
Tutorial is loading...
Solution
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
xor = 0
for x in a:
xor ^= x
if xor == 0:
print(0)
else:
if n % 2 == 1:
print(xor)
else:
print(-1)
1805B - The String Has a Target
Idea and preparation: Alexdat2000
Hint 1
What should be the first character if we are trying to make the string lexicographically minimal?
Hint 2
Consider the string «baba». If you choose $$$i=2$$$, you get the string «abba», and if you choose $$$i=4$$$ you get «abab». Try to generalize this reasoning to any string.
Editorial
Tutorial is loading...
Solution
for _ in range(int(input())):
n = int(input())
s = input()
ind = s.rfind(min(s)) # Find the last ind such that s[ind] = min(s)
print(s[ind] + s[:ind] + s[ind + 1:])
1805C - Place for a Selfie
Idea and preparation: Alexdat2000
Hint 1
Note that the distance between the line and the parabola will also be a parabola. Then what is the condition that the line and the parabola have no common points?
Hint 2
Recall the discriminant formula from school: If a parabola $$$ax^2 + bx + c$$$ is given, then calculate $$$D=b^2 - 4ac$$$ (discriminant). Then, if $$$D > 0$$$, the parabola has $$$2$$$ roots, if $$$D=0$$$, it has one root, if $$$D<0$$$, it has no roots.
Hint 3
If we choose the parabola $$$ax^2 + bx + c$$$, then the lines with such coefficient $$$k$$$ that $$$(b-k)^2<4ac$$$ have no common points with it. How can we find such $$$k$$$ among the given lines?
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector <int> lines(n);
for (int i = 0; i < n; i++) {
cin >> lines[i];
}
sort(lines.begin(), lines.end());
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
int ind = lower_bound(lines.begin(), lines.end(), b) - lines.begin();
if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) {
cout << "YES\n" << lines[ind] << "\n";
continue;
}
if (ind > 0 && (lines[ind - 1] - b) * (lines[ind - 1] - b) < 4 * a * c) {
cout << "YES\n" << lines[ind - 1] << "\n";
continue;
}
cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q = 1;
cin >> q;
while (q--) {
solve();
}
return 0;
}
1805D - A Wide, Wide Graph
Idea: FairyWinx, preparation: Alexdat2000
Hint 1
At what maximal $$$k$$$ does the graph $$$G_k$$$ not decompose into single components? What happens if we decrease $$$k$$$ by $$$1$$$?
Hint 2
Consider some diameter of a tree (the path of the longest length). If in the graph $$$G_k$$$ a vertex has a neighbor, then it is also connected by an edge to one of the ends of the diameter. How can we use this fact to find the answer for $$$k$$$ if we know the components of graph $$$G_{k+1}$$$?
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const int N = 1e5 + 228;
vector<int> G[N];
void dfs(int v, int par, int h, vector<int> &d) {
d[v] = h;
for (int i : G[v]) {
if (i != par) {
dfs(i, v, h + 1, d);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
G[a - 1].push_back(b - 1);
G[b - 1].push_back(a - 1);
}
vector<int> d1(n), d2(n);
dfs(0, -1, 0, d1);
int a = max_element(all(d1)) - d1.begin();
dfs(a, -1, 0, d1);
int b = max_element(all(d1)) - d1.begin();
dfs(b, -1, 0, d2);
for (int i = 0; i < n; ++i) {
d2[i] = max(d2[i], d1[i]);
}
sort(all(d2));
int ans = 0;
for (int i = 1; i <= n; ++i) {
while (ans < n && d2[ans] < i) {
++ans;
}
cout << min(n, ans + 1) << ' ';
}
cout << '\n';
}
1805E - There Should Be a Lot of Maximums
Idea and preparation: Alexdat2000
Hint 1
Let $$$M$$$ — $$$MAD$$$ of the whole tree. What is the answer if there are many vertices with value $$$M$$$ in the tree?
Hint 2
Note that for many edges the answer is $$$M$$$. And for which edges is it not so?
Hint 3
Let the tree have only two vertices with value $$$M$$$. Then for the edges not on the path between them we know the answer. What about the path between two vertices of $$$M$$$? Can we walk along it by calculating the answer for all vertices?
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
vector <pair <int, int>> g[N];
int val[N];
vector <int> ans;
map <int, int> cnt1, cnt2;
set <int> mad1, mad2;
vector <int> path, path_ind;
bool used[N];
bool dfs(int v, int tar) {
used[v] = true;
path.push_back(v);
if (v == tar) {
return true;
}
for (auto [i, ind] : g[v]) {
if (!used[i]) {
path_ind.push_back(ind);
if (dfs(i, tar)) {
return true;
}
path_ind.pop_back();
}
}
path.pop_back();
return false;
}
int mad() {
int mx = 0;
if (!mad1.empty()) {
mx = max(mx, *mad1.rbegin());
}
if (!mad2.empty()) {
mx = max(mx, *mad2.rbegin());
}
return mx;
}
void recalc(int v, int ban1, int ban2) {
cnt1[val[v]]++;
if (cnt1[val[v]] == 2) {
mad1.insert(val[v]);
}
cnt2[val[v]]--;
if (cnt2[val[v]] == 1) {
mad2.erase(val[v]);
}
for (auto [i, _] : g[v]) {
if (i != ban1 && i != ban2) {
recalc(i, v, -1);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
map <int, vector <int>> ind;
for (int i = 0; i < n; i++) {
cin >> val[i];
ind[val[i]].push_back(i);
cnt2[val[i]]++;
if (cnt2[val[i]] == 2) {
mad2.insert(val[i]);
}
}
while (!ind.empty() && ind.rbegin() -> second.size() == 1) {
ind.erase(prev(ind.end()));
}
if (ind.empty()) {
for (int i = 0; i < n - 1; i++) {
cout << "0\n";
}
return 0;
} else if (ind.rbegin()->second.size() > 2) {
for (int i = 0; i < n - 1; i++) {
cout << ind.rbegin() -> first << "\n";
}
return 0;
}
int a = ind.rbegin()->second[0], b = ind.rbegin()->second[1];
dfs(a, b);
ans.assign(n - 1, ind.rbegin() -> first);
recalc(path[0], path[1], -1);
ans[path_ind[0]] = mad();
for (int i = 1; i + 1 < path.size(); i++) {
recalc(path[i], path[i - 1], path[i + 1]);
ans[path_ind[i]] = mad();
}
for (int i : ans) {
cout << i << "\n";
}
return 0;
}
1805F2 - Survival of the Weakest (hard version)
Idea and preparation: sevlll777
Hints for the simple version:
Hint 1
Figure out how to implement the function $$$F$$$ in $$$O(n log n)$$$
Hint 1.1
You'll need $$$std::priority\_queue$$$ or $$$std::set$$$
Hint 2
If you run $$$F$$$ for $$$O(n log n)$$$ $$$n - 1$$$ times, we'll get the solution in $$$O(n^2 log n)$$$. However, the numbers in the array can grow very fast. Can you somehow modify the numbers in the array so that $$$F$$$ changes in a predictable way?
Hint 2.2
$$$F([a_1, a_2, \ldots, a_n]) = F([a_1 - x, a_2 - x, \ldots, a_n - x]) + x \cdot 2^{n-1}$$$
Hints for the hard version:
Hint 3
How to solve the problem if $$$a_i \leq 1$$$? $$$\leq 2$$$? Can you notice anything about these solutions?
Hint 4
If $$$n$$$ is large enough, then $$$F(F(\ldots F([a_1, a_2, \ldots, a_n])\ldots)) = F(F( \ldots F([a_1, a_2, \ldots, a_{n-1}, X])\ldots))$$$ where $$$X$$$ any number $$$\geq a_{n-1}$$$, in other words: the largest element is useless for the final answer
Hint 5
Only a small number of the smallest elements of the original array will affect the answer
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(x) x.begin(), (x).end()
using namespace std;
const int M = 1000000007;
long long ans = 0;
int real_len = 0;
long long binpow(long long a, int x) {
long long ans0 = 1;
while (x) {
if (x % 2) {
ans0 *= a;
ans0 %= M;
}
a *= a;
a %= M;
x /= 2;
}
return ans0;
}
void chill(vector<int> &b) {
int mn = b[0];
ans += (int) ((long long) mn * binpow(2, real_len - 1) % M);
if (ans >= M) {
ans -= M;
}
for (auto &x : b) {
x -= mn;
}
}
void F(vector<int> &b, int sub = 0) {
--real_len;
vector<int> cnd;
for (int i = 0; i < b.size(); i++) {
for (int j = i + 1; j < b.size(); j++) {
if (i * j >= b.size()) break;
cnd.push_back(b[i] + b[j]);
}
}
sort(all(cnd));
vector<int> b2((int) b.size() - sub);
for (int i = 0; i < (int) b.size() - sub; i++) {
b2[i] = cnd[i];
}
chill(b2);
b = b2;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(all(a));
int L = 64;
vector<int> b(min(n, L));
for (int i = 0; i < min(n, L); i++) {
b[i] = a[i];
}
real_len = n;
chill(b);
while (b.size() < real_len) {
if (b[1] + b[2] > b.back()) {
F(b, 1);
F(b, 1);
} else {
F(b);
}
}
while (real_len > 1) {
F(b, 1);
}
ans += b[0];
ans %= M;
cout << ans << '\n';
}
The title says "Разбор" which is not translated ig
fixed, thanks
Where can I read more about the XOR property mentioned in problem A?
The property is simply that XOR of two same numbers is zero and XOR of a number with zero is the number itself.
Yes, but I was asking about the property in the editorial sections, where it says about the case when n is even and when n is odd. Where can I read about that?
its literally the same thing...
$$$A ⊕ A = 0$$$, so if there is even number of $$$A$$$'s then the result is zero
otherwise, its $$$A$$$.
stupid
This might help
Alternative solution for D: we can compute maximum distance of some node for each node in a tree, now if k>maximum distance between any two nodes , number of connected components is n. let number of nodes with maximum distance be x. then for k=x, answer is n-x+1. Now iterate from x to 1 , answer for k=y is n-(freq[y]+freq[y+1]+freq[y+2]......+freq[x])+1,where freq[x] denotes number of nodes with maximum distance equal to x. link to submission
Clean ac submission with this idea : https://codeforces.com/contest/1805/submission/200446467
Do we need to do rerooting for finding the maximum distance for each node ?
not really, I managed to do it in two dfs calls, you can see it in this submission, for example
No. General idea is for any node in a tree the farthest node from it will be an endpoint of the diameter of that tree. We can use this idea to get max distance from every node to every other node in 2 dfs / bfs calls.
oh wow, I overcomplicated my stuff so much then
my idea was that there can be two options of the longest path from a vertex: 1. it is one of its children (if we root the tree arbitrarily, say in 1). so, it's the depth of the tree from this vertex 2. it's to a child of one of its parents. to calculate this one, the a dfs call also saves the largest value of (depth of tree of a node — its depth from root), and this value is passed on as max(this value in current iteration, what was passed on already), but the value of in this iteration is the maximum depth of any tree of a son of this vertex, except the one we are going into
so, the path can be calculated for each of the vertices in a dfs call, where we pass on the value from (2), and the parent of the vertex
the 2 max depths of a tree of a son of each vertex and the depth of each vertex from root can be calculated in the first dfs call
weird stuff, really. idk how I came up with that instead of the diameter idea
Absolutely, I had also applied the same concept, finding the farthest distance for each node, and took their frequency, and solved using same concept,
Submission Link . All can view my alternative implementation for Problem D, if you want.
Yep, this is a well known problem that can be found in CSES
keep them parabolas to yourself
There is an easier and more beautiful (imo) observation in C:
When we know that we need to find such a $$$k$$$ that $$$(b-k)^2<4ac$$$, we could rewrite this inequality as $$$k^2-2kb<4ac-b^2$$$. $$$4ac-b^2$$$ is fixed for one parabola, so for each parabola we need to minimize $$$k^2-2kb$$$. But this is also a parabola (but there is $$$k$$$ instead of $$$x$$$), so its minimum is in $$$k = \frac{2b}{2} = b$$$. Now we can just binary search for $$$b$$$ in the sorted array of $$$k$$$ and check the closest values to $$$b$$$ to the left and to the right of found value in the $$$k$$$ array to satisfy the $$$(b-k)^2<4ac$$$.
Couldn't implement it so I looked at your code, could you explain why you used two additional conditions(ind<=n and ind>1) after BS? Thanks.
Because sometimes we don't have the closest element to $$$b$$$ to the left (when $$$ind = 1$$$) or to the right (when $$$ind > n$$$)
How can the minimum be $$$k = \frac{2b}{2} = b$$$? What approach did you use? Did you differentiate? How can the equation($$$k^2-2kb$$$) be a form of the equation of a parabola? Can you please explain it?
Math equation for the parabola is $$$y(x) = ax^2+bx+c$$$. It's also a known fact that vertex of the parabola $$$(x_0, y_0)$$$ has $$$x_0 = -\frac{b}{2a}$$$. If parabola has $$$a>0$$$ then $$$(x_0, y_0)$$$ is also a minimum of the parabola.
In our case we have $$$y(k)=k^2-2kb$$$. So x-coordinate of the minimum point is just $$$x_0=-\frac{b}{2a}=-\frac{-2b}{2}=b$$$. (Note that there are different $$$b$$$ variables in this equations — from $$$y(x)$$$ and $$$y(k)$$$)
no need to think, a brute-force solution works for problem 1805A - We Need the Zero
My solution link: 200395467
Can someone explain Hint 2.2 of problem F1?
If you subtract same integer from all numbers in array, they sorted order will not change, and same with sorted order of all pairs of elements. Basically it means that arrays $$$F([a_1, a_2, \ldots, a_n])$$$ and $$$F([a_1 - x, a_2 - x, \ldots, a_n - x])$$$ are formed by the same pairs of indexes.
I.e: $$$F([a_1, a_2, \ldots, a_n])_i - 2x = F([a_1 - x, a_2 - x, \ldots, a_n - x])_i$$$ for all $$$i$$$.
So we can prove Hint 2.2 by simple induction on $$$n$$$. Base case $$$n = 1$$$ is obvious. What I wrote above is basically a transition from $$$n$$$ to $$$n - 1$$$ case
Got it sevlll777 , i was confused because in Hint 2.2 above both LHS and RHS have n values.
In hint3 of solution of F:
There's an extra '?' character
That's not an error, that was intended to be 2 questions
Problem A, hint 1: $$$A \oplus 0 = 0$$$ should be $$$A \oplus 0 = A$$$
fixed, thanks
Problems were nice. And to make this comment less nonsence
In D every vertex that was chosen on i-th step has at most 1 neighbour which wasn't chosen yet and it will be chosen on (i-1)-th step (also it can't be leaf). So you can search only for leaves with distance i from diameter ends, and with those neighbours they will be all i-th chosen vertexes
Actually, it's big overthinking, but anyway
Problem C is a good example for ternary search. Solution.
Great contest! if you people feel stuck on Problem A, Problem B, Problem C, Problem D then you can refer to my video editorial here-video editorial
Thanks, it helped me clearing my doubts over D. xD
Thnq so much.It helped me for D
There is a simple solution to problem E, which works even if MAD operation is defined as max value appearing at least k times.
Subtrees are basically subsegments of a tree Euler tour. The other tree is prefix and suffix. Which is also a single segment if you concatenate Euler tour with itself.
We can do it offline.
Sort queries by the right end in non-decreasing order. Now process numbers of the array one by one from left to right. When you process a number, you need to find k-th number of the same value amongst previously added. Let’s update the position of that number with this value (rmq data structure). Now we process all queries, that end at the index of the newly processed number. Simply ask rmq for the answer.
We can even use fenwick tree, if we sort queries by the left end in non-increasing order and process array from right to left (prefix before processed numbers will have zeros which do not affect the answer).
Can you please expand the approach a bit. When the tree is collapsed to seg tree by Euler tour. How is finding $$$k^{th}$$$ number of the same value equivalent to our query. I get that somehow you will maintain for each query the valid answers, can you please just let me know how exactly that gets maintained with updates.
Go from left to right in the array formed after Euler tour, if you are at index $$$i$$$ then find $$$k$$$$$$th$$$ number to the left of same value as $$$a$$$$$$i$$$. Now any active range whose left boundary is or before that $$$k$$$$$$th$$$ number's index then that particular number will contribute to the answer for that range. After updating, query for maximum element in the range.
Note : We have sorted the queries on the basis of right boundary, hence we are going from left to right. Iterate and add numbers till your i is less than current right index of the query.
You can check my submission and ask whatever part is unclear in it.
And what about the prefix and suffix?
copy the sequence and append to itself, then the prefix and suffix can turn into a subsegment, too.
I overcomplicated my approach to C https://codeforces.com/contest/1805/submission/200453634 it gives Wa test 5 could anyone help?
Dont use decimal calculations here, it has precision error. A simple approach is to find the largest k smaller than b and smallest k larger than b and check for the condition (b-k)^2 <4ac.
Hi, I write the brute force solution for problem C and expected the "TLE" but it gives me the "WA" verdict. Can you check my code? https://codeforces.com/contest/1805/submission/200462356
The value of k can be -1, so initializing answer with -1 is wrong.
Is Task C somehow related to task A of the first day of the regional stage of the VSOSH 2023?)
Я придумал свою задачу где-то год назад так что вряд ли есть связь
In problem C, at last we need to find a k which satisfies the equation $$$b - \sqrt{4ac} < k < b + \sqrt{4ac}$$$.
But how do we find any such k if $$$4ac < 0$$$? i.e. how do we find a real number between two imaginary numbers?
If 4ac<0 then (b-k)^2>4ac so the answer is NO
I solved E using (segtree + euler tour + mo algorithm + coordinates compression + frequency array).
Submission: 200485345
Segtree + Mo's algorithm? Is that $$$O(n \sqrt{n} \log(n))$$$ or I missed something?
Yes, I actually used a
multisetbut got TLE so I moved to a fast segtree implementation which doesn't have all the overhead of the STL containers. At the end the worst case is still $$$O(n\sqrt n \log(n))$$$, but this is the worst case which is unlikely to happen (I think). Because we don't always update the segtree, it is updated when some condition is satisfied.To be honest I didn't notice the time limit during the contest and took too long time thinking about the solution till the contest ended. If I had the time and noticed the time limit I wouldn't submit it.
You can use square decomposition to update in $$$O(1)$$$ and find the maximum value in $$$O(\sqrt{n})$$$. Therefore, the complexity is $$$O(n * \sqrt{n})$$$, which is much more comfortable than using Segment Tree, which takes $$$O(\log {n})$$$ for each update.
Where can I learn about techniques like coordinate compression and mos algorithm?
Check Errichto's video: https://www.youtube.com/watch?v=BJhzd_VG61k
check out my similar solution, I didn't have to use a segment tree just like how steveonalex explained. This is a really important trick so if you don't know it, I would recommend that you have a look at it.
Thank you, bro
Has anyone solved E using rerooting technique?
Can anyone explain Question D in more detail?
Check My explanation.
I have different solution for problem D. Let's calculate farthest leaf from node i (this can be done by rerooting) and keep this value in fd[i] (short for farthest-distance). Now, for specific k, we check if node fd[i] is greater or equal to k. If this statement is false, then this node is isolated from every other node completely. Otherwise every node which satisfy this statement will be connected into one whole component. Thus we can calculate number of isolated components by prefix sum and add one as a "main" component. Consider fact that you can get answer n + 1 so you have to print min(n, answer).
Here's code for better understanding 200435906
P.S. If you liked this explanation or it helped you solve this problem, please add me as a friend. Reply if you need proof for this type of solution.
In problem C, can someone point out my mistake? 200462857
Finally became specialist! :)
E's idea is pretty straight forward yet somehow I failed to notice the simplest implementation...
I noticed that the biggest value appears more than 2 times will be the answer for all edge and all values that appear 2 times will update all the edges that are not on their path, yet to update and maintain maximum value on a tree in O(1) or O(logn) is beyond me(in the worst scenario n/2 updates)(and yes, I thought about HLD which I only know about the general idea).
The lesson here(at least for me) is: practice your tools until you are perfectly familiar with it, so you know exactly what it can do, what can be done with it and what can't.
My submission 200473816 for F1 has passed but I believe it should fail. I have represented every number in the form a.m + b where m = 1000000007 and b < m. Since the number can reach $$$2^{3000}$$$, it should still be insufficient to store such numbers. Can someone please look into this?
I had this same approach when i was trying this problem during the contest. But since the numbers can grow very fast, i eventually discarded it. I think subtracting the smallest $$$a$$$ at every iteration from every term will make much sense similar to editorial, using this approach we can just directly output the remainder stored as $$$b$$$
Yeah. My code should WA for the given constraints, right?
Not sure about WA or not, but overflow is definitely possible. So to avoid it, i would be subtracting smallest $$$a$$$ at every iteration to avoid any overflows.
As in the constraints $$$1 <= array_i <= 10^9$$$, the initial values of quotient $$$a$$$ will be 0, it is likely that pairs of $$$a = 0$$$ or pairs with smaller $$$a$$$ are affecting the result more than any other pair.
It is indeed overflowing like I expected. The value of $$$a$$$ (first element of the array in priority queue) becomes negative after a few iterations. What's blowing my mind is that my code is still giving the correct answer for every large input I generated. The output matches with that of the editorial code. I would really appreciate if someone could take a look and explain why this is happening.
I stress-tested your solution with 4 generators, for $$$~10$$$ minutes for each generator. Countertest was not found. And I don't how can I generate countertest myself.. I believe countertest should exists, but it seems literally impossible to generate it in any way (at least for me)
That is really surprising because if all the array elements are non-zero, it is guaranteed to overflow after less than 100 iterations since $$$2^{100} »» 10^{18+9}$$$. Therefore, every such test case should be vulnerable to failure in theory if $$$n > 100$$$. Correct me if I am wrong. In practical, it is working properly even for very large arrays.
Overflow is happening $$$mod 2^{64}$$$, so if two number overflow at the same time they sorted order is the same despite of overflow. So to break it we need to build test where of 2 important numbers at some step one of them overflow, when other not. And if you read F2 tutorial, you know that in fact only 50 smallest numbers of array affect the answer. And also we cant give any array to test overflow, because first 30 runs of your function F will be correct. And after applying F 30 times all arrays are kind specific. This is why its Hard to create a test where overflow actually matters.
Is that 3 dfs in D a common trick to find all ending nodes of diameter? Can't figure out an efficient way to do so during contest.
great round
For F2 the smallest K that works is 43
Yes, this is correct. Btw, here is an equation to evaluate this number:
There is a $$$O(Nlog^2N)$$$ solution for Problem E using Sack on tree..
We can root the tree at any arbitrary node. Now every edge between a parent and child in the tree will break the tree into two components. One of the components is the subtree of the child and the other component is all the other nodes. Now if we had to find the largest value having a frequency greater than x, we can do that normally with sack. However, it won't work for the other component. To solve for the other component we can have an additional data structure. Initially, we will add all the node information to this data structure. Then we can start with our sack on the tree. Whenever we add any node to the data structure for a subtree, we delete it from the additional data structure and vice versa.
Now coming on to the data structure required. We have to support the following actions, increase or decrease the frequency of any value and find the maximum value having the frequency>=2. For performing both of these operations quickly we can use a map and set together. We can update the frequency in the map and then use the set to answer queries about the maximum value. We will have to use a frequency array instead of map for our code to work within the tl.
Implementation
Can you please explain the time complexity a bit more? I understand that the $$$O(N log N)$$$ complexity comes from each node being relocated (merged into a larger vector) up to $$$log N$$$ times. However a relocation operation (your update function) in this case may need a set insertion/deletion, which is another $$$log N$$$ factor. Can you prove that in the worst case the time complexity wouldn't be $$$O(N log^2 N)$$$?
For example, imagine a tree where every value appears in exactly two nodes. Therefore, the possible frequency of any value is limited to { 0, 1, 2 }. In this case, every relocation seems highly likely to need a set insertion/deletion.
I completely overlooked that part. Really dumb on my part.
Thanks for pointing out.
For D
let $$$min(f(k)+1, n)$$$ equals the solution for k
If we have x nodes that their farthest distance are less than k So, f(k) equals $$$x$$$.
I think this approach would work if this statement is true
let d(x,y) equals the distance between x and y. Then suppose d(a, b) >= k and d(c, d) >= k then one of d(a, c), d(a, d) must be >= k which means if the vertics is not indvidual, then it is connected to all other non-indvidual verticeswhich means there is one or zero big connected component and all the other vertices are indviduial. So the answer of k should be the number of indvidual vertices ( + 1 if their number is not (n)).which equals the first equation$$$min(f(k)+1, n)$$$this is the approach I used in my solution here but it got WA 4
Could anyone please tell me where I went wrong?
Take a look at Ticket 16805 from CF Stress for a counter example.
Thanks man!
It worked wheh I fixed the algorithm of finding the farthest distance from each node
Submission
excuse me, for question C, if there exits a solution so the max k for this open upwards parabolas is bigger than which has been input and the min k is lower than which has been input, so I tried to check : double nma = b[i] + 2 * sqrt(a[i] * c[i]); double nmi = b[i] — 2 * sqrt(a[i] * c[i]); also there are some special I did checked xd. but wrong answer on test(2,57), is that mean "double" can not fit this solution? Sorry about my poor English. Here is my code, thx if you can drop some advices. https://codeforces.com/contest/1805/submission/200577146
It's a common mistake that multiply two 32bit integer and surprisingly get unexpected answer.
My O(nlog^2(n)) solution to problem E using small to large merging technique. Implementation
Why couldn't I passed promblem E with Segtree + Mo's algorithm,or this way is wrong,can somebody help me,thanks so much! 200585844
Dumb $$$O(N\sqrt{N}\log{N})$$$ solution using Mo's for problem E which runs very fast: Link
May I ask if there is a tutorial for the fastset in the code?
It's just a template I copied from some grandmaster. If you any doubts about how to use it, you can ask me.
1805C - Place for a Selfie A simple solution for C 200620934
I got TLE on test 5 in problem F1,I think my progress time complexity is O(n^2 logn),can sombody help me. This is my submission,thanks so much! 200650061
This problem can't be solved in this way.
I subscribed you on bilibili！
谢谢
I tried to use dsu on tree in problem E,I think its time complexity is O(nlogn),but I got TLE.can sombody help me. This is my submission,thanks so much! https://codeforces.com/contest/1805/submission/200871054
I have a question about F2.
Here is one a submission.
I used the same solution as F1, but instead maintained each number and its number of occurrences, in the random case the different numbers are few and far between, the code works fast, but it gets time limit exceeded on test 26.
I would like to know what kind of data can be used to maintain a large number of different numbers during the operation. Can anyone help me?
My English is bad, if there are any grammatical errors, please point them out.
for problem E, my approach is to flatten the tree and apply mergesort tree for queries (similar to number of unique numbers in range but here we need to find maximum value non unique number).
Im getting wrong answer in testcase 18.
my submission: https://codeforces.com/contest/1805/submission/200885370
please anyone say whether my approach was wrong or any mistake in my code. thanks in advance.
Take a look at Ticket 16813 from CF Stress for a counter example.
thanks a lot. found the mistake.
Alternative Solution to E in $$$O(nlog^2n)$$$:
We can use small to large merging technique. We will maintain $$$3$$$ vectors of sets:
$$$\cdot$$$ $$$Current: $$$ will maintain current $$$MAD$$$ values in subtree $$$\newline$$$ $$$\cdot$$$ $$$Unusable: $$$ will maintain values that are occur less than $$$2$$$ times in the other created tree but occur more than $$$2$$$ times in the total tree $$$\newline$$$ $$$\cdot$$$ $$$Other: $$$ will maintain the largest values that occurs more than $$$2$$$ times in the total tree but less than the values is $$$Unusable$$$ $$$\newline$$$ First one is pretty easy to update, just update it when you currently have less than $$$2$$$ values in the node but will have more than $$$2$$$ when updating it with a subtree.$$$\newline$$$ Second one is updated is a similar way, if you have more than 2 values not occurring but updating it with a subtree results in less than 2 values not occurring add to this set. Also when we add to this set make sure is the value occurs in $$$Other$$$ erase it from there $$$\newline$$$ Third one is a little bit more annoying to update. Find the value right before the current value that occurs at least twice in the tree. Make sure it is not the smallest value in the tree and also that this value does not occur in $$$Unusable$$$. $$$\newline$$$ After doing the merging mentioned right above, we have to do a little casework. $$$\newline$$$ $$$1.$$$ If $$$Current$$$ is empty and number of values occurring at least twice is equal to the amount of numbers in $$$Unusable$$$ the answer is $$$0$$$ $$$\newline$$$ $$$2.$$$ Let $$$max$$$ define the largest number that occurs twice in the tree. If $$$max$$$ is not in $$$Unusable$$$, the answer is $$$max$$$ $$$\newline$$$ $$$3.$$$ Otherwise the answer is equal to the maximum of the largest number that is in $$$Current$$$ and $$$Other$$$ $$$\newline$$$
First log factor comes from the sets, other one comes from small to large merging. Be warned the constant factor is extremely tight and i had to do many things to barely fit into TL so this is not recommended.
Implementation: 201189988
Please add the rating of the tasks in the archive:)
Actually, for problem $$$E$$$ small to large merging is an overkill.
The first thing to notice, as the editorial states, is that numbers that appear once or thrice can effectively be accounted for quite simply. Thus, we only need to consider numbers that appear twice. From here on out, assume that every number appear twice.
Of all the numbers that appear twice, one of the numbers is going to be the maximum (as in, find the maximum number that appears twice). Say this maximum number is $$$x$$$, and it appears on vertices $$$u$$$ and $$$v$$$. Then, for all edges not on the path from $$$u$$$ to $$$v$$$, the maximum number you can get is going to be $$$x$$$, since $$$u$$$ and $$$v$$$ will be on the same connected component after the split.
Therefore, we only have to deal with vertices on the path from $$$u$$$ to $$$v$$$. To do this, we can root the tree at $$$v$$$ (or I guess, by symmetry, at $$$u$$$) and naively update the connected components.
If done right, the complexity of this approach is $$$O(N)$$$. In my implementation (211295484), the complexity is actually $$$O(N \log N)$$$ because I used maps, but you can do it without maps.
Why isn't it necessary for the problem C to use long long? Won't it overflow?
Embarrassed, I made a mistake.
In the solution of C, we have found
lower_boundin the sorted array (ind) and then checkedind-1afterwards. Shouldn't it beupper_boundinstead? Because we are trying toupper_boundgives us the index of element just greater than b (in case b isn't present) and then we subtract 1 from it to get the index of element just smaller than b.I tried submitting the same code given in the editorial with just this small change of
lower_boundtoupper_boundand it was accepted. Link.