We are really sorry that C is tough and E is easier than D. But anyway hope you can enjoy the problems themselves and learn something from them.
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=500005;
const int inf=0x3f3f3f3f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b<=d&&c<=a+d-b) {
cout<<(d-b)+(a+d-b-c)<<"\n";
} else {
cout<<"-1\n";
}
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=200005;
const int inf=0x3f3f3f3f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
int sum0=0;
bool f=false;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
if(x==0) {
sum0++;
} else if(x>=2) {
f=true;
}
}
if(sum0<=(n+1)/2) {
cout<<"0\n";
} else if(f||sum0==n) {
cout<<"1\n";
} else {
cout<<"2\n";
}
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=400005;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
ll ans=0,sum=0;
for(int i=1;i<=n*2;i++) {
cin>>a[i];
ans+=abs(a[i]);
sum+=abs(a[i]-(-1));
}
if(n==1) {
ans=min(ans,abs(a[1]-a[2]));
}
if(n==2) {
ans=min(ans,abs(a[1]-2)+abs(a[2]-2)+abs(a[3]-2)+abs(a[4]-2));
}
if(n%2==0) {
for(int i=1;i<=n*2;i++) {
ans=min(ans,sum-abs(a[i]-(-1))+abs(a[i]-n));
}
}
cout<<ans<<"\n";
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=500005;
const int inf=0x3f3f3f3f;
const int mod=998244353;
int a[maxn];
int f[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
for(int i=1;i<=n-1;i++) {
cin>>a[i];
}
f[1]=1;
for(int i=1;i<=n-1;i++) {
f[i+1]=1ll*f[i]*(i-a[i])%mod;
}
int ans=0;
for(int i=1;i<=n-1;i++) {
ans=(1ll*ans*i+(!a[i])*f[i])%mod;
cout<<ans<<" ";
}
cout<<"\n";
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=100005;
const int sqrtn=325;
const int B=320;
const int inf=0x3f3f3f3f;
int n,q;
int a[maxn];
int h[maxn];
int fa[maxn];
int cnt[maxn];
int depth[maxn];
ll f[maxn][sqrtn];
vector<int> tree[maxn];
void dfs(int x,int d) {
h[x]=++cnt[d],depth[x]=d;
for(int to:tree[x]) {
dfs(to,d+1);
}
}
ll ask(int x,int y) {
if(!x&&!y) {
return 0;
}
if(cnt[depth[y]]<=B&&f[x][h[y]]) {
return f[x][h[y]];
}
ll ans=ask(fa[x],fa[y])+1ll*a[x]*a[y];
if(cnt[depth[y]]<=B) {
f[x][h[y]]=ans;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
for(int i=2;i<=n;i++) {
cin>>fa[i];
tree[fa[i]].push_back(i);
}
dfs(1,0);
while(q--) {
int x,y;
cin>>x>>y;
cout<<ask(x,y)<<"\n";
}
}
1806F2 - GCD Master (hard version)
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define int128 __int128
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=1000005;
const ll inf=9e18;
const int128 inf128=(int128)(inf)*(int128)(inf);
ll a[maxn];
ll b[maxn];
ll g[maxn];
ll ra[maxn];
int128 suma[maxn];
int128 sumb[maxn];
int128 ans[maxn];
ll gcd(ll x,ll y) {
return !y?x:gcd(y,x%y);
}
void print(int128 x) {
if(!x) {
return ;
}
print(x/10);
cout<<(int)(x%10);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n,k;
ll m;
cin>>n>>m>>k;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
sort(a+1,a+n+1);
int t=0,r=0;
for(int i=1;i<=n;i++) {
if(i>1&&a[i]==a[i-1]) {
b[++r]=a[i];
} else {
ra[++t]=a[i];
}
}
n=t;
for(int i=1;i<=n;i++) {
a[i]=ra[i];
g[i]=gcd(g[i-1],a[i]);
suma[i]=suma[i-1]+a[i];
}
for(int i=0;i<=k;i++) {
ans[i]=-inf128;
}
for(int l=1;l<=n;) {
int r=l;
while(r<=n&&g[r]==g[l]) {
r++;
}
r--;
ll Max=-inf;
for(int i=r+1;i<=n;i++) {
a[i]=gcd(a[i],g[l]);
Max=max(Max,a[i]-ra[i]);
}
for(int i=r;i>=l;i--) {
ans[i]=suma[n]-suma[i]+Max;
a[i]=gcd(a[i],g[l]);
Max=max(Max,a[i]-ra[i]);
}
l=r+1;
}
for(int i=1;i<=r;i++) {
sumb[i]=sumb[i-1]+b[i];
}
int128 final=-inf128;
if(k<=r) {
final=suma[n]+sumb[r]-sumb[k];
}
for(int i=0;i<=r&&i<=k;i++) {
final=max(final,sumb[r]-sumb[i]+ans[k-i]);
}
print(final);
cout<<"\n";
}
}
so fast editorial!
Stucked for a long in problem C. hardForces
Orz
this editorial is so fast!
.
you mean "EITHER" , not "NEITHER" !!! .
I solved E with Mo's algorithm on tree.
When I visited a pair $$$(u, v)$$$ with Mo's algorithm order, I already have most of the data of every node on the path from $$$u$$$ to $$$v$$$. To solve the problem, I only need to maintain the following things:
cnt_layer[d]— number of touched nodes with depth $$$d$$$.layer_prod[d]— the product of value of touched nodes with depth $$$d$$$.So when
cnt_layer[d]equals 2, I'll addlayer_prod[d]to the answer, otherwise, I remove it from the answer.The total complexity is still $$$O((n + q) \sqrt n)$$$
what does the "ranges::" thing do ?
This is a new feature in C++20 with functional programming idea. It is interesting , but many functions won't complete before C++23. You can go to cppreference to see more details.
Passed D just by finding patterns.
Also, it feels a little wierd that unordered_map can pass E but map cannot.
Your Accepted solution has now TLE. I tried the same!!
True, I wonder what happened too.
I solved E again with hand-written hash table. 198019367 Hope this solution won't get TLE again...
UPD: For some reason, all AC submissions of mine got TLE on Test 10. Just write the hash table by hand and create a hash table as big as possible that it has the best efficiency. 198019367
The time limit is strict for problem E, so I write two important optimizations in solving E here.
1) Reorder the node pair that x<y. This reduces the number of possible pairs in half.
2) Use vector<unordered_map<int,ll>> instead of simply using (unordered) map<pair<int,int>> or long long where {x,y} is replaced by x<<32+y. This reduces the time spent from O(log(xx*yy)) to O(1)+O(log(yy)). (xx is the range of x, and yy resp.)
Yet now that I think about this, optimization 1) should make no improvement for the worst case, but without this optimization my solution would get MLE/TLE. Does it imply that there is still plenty room for uphacking? XD
how can i assume the complexity of unordered_map ? isn't it O(1) but how could it be as slow as O(logn) idon't get the" O(log(xx*yy)) to O(1)+O(log(yy))" Because in my limited knowledge and experience that is hash and it should be O(1)->O(1) ,so how vector will be faster?
Sorry for my inaccurate expression. The analysis is based on map.
If two procedures have time asymptotics of $$$\mathcal{O}(1)$$$ this does not necessarily mean that they would have same running time. In case of
std::unordered_mapit has a large constant factor, which makes it much slower thanstd::vector.you are right,thx
I got AC using something like path compression and it runs in ~1sec but I can't analyse the time complexity could you provide some help ?
AC submission : https://codeforces.com/contest/1806/submission/198034329
Your optimization makes perfect sence, and it's a complexity-level optimization. Map and unordered_map can both pass the problem by this optimization. 198070832 198070932
Denote the distance between two memorized layers by $$$d$$$, for each query you need go up $$$O(d)$$$ layers to reach a memorized layer, so the time spent in this part is $$$O(qd)$$$.
For each memorized layer, check the worst case of my original solution, where all $$$a_i=\sqrt{q}$$$. There are $$$\frac{n}{d\sqrt{q}}$$$ memorized layers in this case, and each layer requires storing and checking $$$q$$$ different pairs, which is done by (unordered) map, hence there are $$$\frac{n\sqrt{q}}{d}$$$ memorized pairs in total. If the check failes, each memorized pair need to go up $$$O(d)$$$ layers, and the time spent in this part is $$$O(n\sqrt{q})$$$.
Therefore, the afterall time complexity after this optimization is $$$O(qd+n\sqrt{q})$$$ + $$$O(\frac{n\sqrt{q}}{d}\cdot t_{map})$$$, where $$$t_{map}$$$ is the time complexity of the data structure we store the value, in this case it's (unordered) map.
If we choose $$$d=\frac{n}{\sqrt{q}}$$$, the time complexity is $$$O(n\sqrt{q})+O(q\cdot t_{map})$$$.
However, this solution has it's own worst case, where the data puts all vertices at layer $$$kd$$$, and the other layers only have 1 vertex. But this can be easily fixed by selecting the $$$k$$$th memorized layer randomly in $$$[kd,(k+1)d)$$$. The expected numbers of memorized pairs in each layer would be $$$ \frac{\sum\limits_{i=1}^{d}\min\left(a_i^2,q\right)}{d}$$$, and the sum of all layers would be $$$\sum\limits_{j=0}^{\frac{n}{d}}\frac{\sum\limits_{i=1}^{d}\min\left(a_{jk+i}^2,q\right)}{d}=\frac{\sum\limits_i\min(a_i^2,q)}{d}$$$, and the worst case is the same as my original solution.
A simple solution for TLE is to precompute all pairs with same depth when a depth have less than $$$\sqrt n$$$ nodes. The trick is to precompute only for depths such that $$$k$$$ is a divisor of the depth for a fixed $$$k$$$, this has the complexity $$$O(\frac{n\sqrt n}{k} + kq)$$$. This gives 400ms with $$$k$$$ = 20.
Can you teach me how to find the pattern?
Sure. I start with the second sample. You can see that in the second sample, the numbers seems to be proportional.
You can observe 2 patterns $$$a_i=a_{i-1}\cdot i$$$ and $$$a_i=a_{i-1}\cdot i+k$$$, and which pattern to follow is related to the 0/1 in the input. The problem remained is the value of $$$k$$$.
You can see that $$$k$$$ also follows some pattern, 1 * 3 = 3, 3 * 4 = 12, 12 * 5 * 5 = 300, 300 * 7 = 2100. For continuous 0 the $$$k$$$ is multiplied by $$$i$$$, and for 1 the $$$k$$$ is multiplied by $$$i-1$$$. Though there is no continuous 1 in the sample, we can guess that this pattern stays correct for continuous 1. This results in my solution 197972006
But it's very rare that the sample contains the complete pattern for the solution, the problem setter can easily avoid this by limitting the information in the sample, and you may at least need to write a brute-force code yourself. And afterall, observing the pattern doesn't work for most of the time.
Those were amazingly wild guesses! Many thanks for your detailed reply.
Why the solution of problem E, where we just memorizing all the answers for all encountered pairs of vertices is getting TLE test 10?
There is about $$$449 \cdot 225 \cdot (10^5 : 450) \approx 22 \cdot 10^6$$$ pairs we need to memorize in the worst case, so it should fit the constraints. Worst case is when the tree forms a "sun" $$$-$$$ a graph, where all subtrees of the root are bamboos and in every query we choose two leaves of different bamboos, and in every query this pair of bamboos is distinct. I chose $$$450$$$ bamboos of length approximately $$$222$$$. In that case we could choose $$$10^5$$$ distinct pairs of bamboos for $$$10^5$$$ queries and bamboos are as long as possible.
Maybe it's just because that this problem has strict time limit, and map & unordered map are too slow for some ways of implement. Your time complexity seems right to me.
It seems quite strange to me, because $$$22 \cdot 10^6$$$ isn't really much and I feel like map/unordered_map can handle it in $$$3$$$ seconds (at least I used to think so and it always worked)
197986245 I changed the unordered_map[xx<<32+yy] to vector[xx][yy] in your code, and it passed. (Actually a little faster than my own solution) I cannot analyze it for unordered_map, but for map, the difference is from log(xx*yy) to O(1) + log(yy), but the overall complexity is the same. It reduces the constant factor by about half, I suppose.
Wow, nice optimization, thank you!
Actually, noticed another interesting observation there: if you try to submit the code from your AC submission using GNU C++ 17, it will still get TLE test 10. Seems like unordered_map received a decent performance improvement in C++ 20 =)
Thank you for your information. It never occured to me that compiler option can make so much difference. I'll raise my attention from now on XD
https://codeforces.com/contest/1806/submission/198003630
why tle on test 58, submitted i have changed my code thousand times but it just wont submit!??
Somehow my code passed previously doesn't work anymore. Try hand-write hash table and make it as big as possible to maximize the efficiency.198019367
My code is almost the same as yours, but I received a TLE error at test case 10 when using an unordered_map, and at test case 58 when using a map
I TLEd using hashtable for E. Thought it should work but figured I was missing something as it seemed to simple for a question E.
I didn't even work out question B this time. Actually, this question is so simple.I need to work harder.
Hoshino kawaii!
do you know why answer would be <=2?
Case 1: 0 is less than half. Then we can construct like
0 a 0 b 0 c ... 0 x 0. It's clear that $$$a_i+a_{i+1} \neq 0$$$ forall $$$1\leq i\leq n-1$$$. So mex = 0.Case 2: 0 is greater than half and the rest is all 1. No matter what order we construct , there always exist adjacent
0 0and0 1. But we can separate adjacent 1 with 0 to make sure there are no1 1. So mex = 2.Case 3: 0 is greater than half and the rest is not full of 1. We know there always exist adjacent
0 0. So we can construct like0 0 0 ... 0 x a b c d ...($$$x \neq 1 , x,a,b,c,...\neq 0$$$). So mex = 1.Beware corner cases.
I have seen C when practicing math olympiad problems but I am not sure which olympiad it was from.
Ok just found it, it was ELMO 2016 P1: https://artofproblemsolving.com/community/c6h1262189p6556895
About problem E.
How do I understand this? Why did $$$k$$$ in the formula disappear and why the maximum value is it?
Sorry for my poor english and math , but I still want to know how the conclusion came out.
I just write my proof here.
Denote all vertices with the same depth as a layer. Our solution is to store all different pairs that may be visited.
Consider a layer with x nodes. There can be x^2 different pairs in this layer, but because for each query, only 1 pair would be visited for each layer, so the total amount of different pairs visited is min(x^2,q)
Now consider all k layers. Because there are n nodes in total, so sum of x_i = n, and there are sum min(x_i^2,q) pairs may be visited in total.
This value gets maximum when all x_i = sqrt(q). A simple proof is that for x_i < x_j < sqrt(q), moving a node from layer i to layer j would make more possible pairs.
Therefore, we have x_i = sqrt(q), and hence there are n/sqrt(q) layers in total, where each layer have q different pairs. So there may be n/sqrt(q)*q = n*sqrt(q) possible pairs in maximum.
Thanks a lot.
:D
If possible, can you please elaborate the proof for x_i = sqrt(q)?
The number of different pairs is $$$\sum\limits_{i=1}^n \min(a_i^2,q)$$$, where $$$a_i$$$ is the number of vertices in the $$$i$$$th layer. Hence, the number of pairs in the worst case can be transformed into the following problem: Imagine you have a sequence $$$a_1,a_2,\dots,a_n$$$ and a value $$$q$$$, you have $$$\sum a_i=n$$$, and you want to maximize $$$\sum \min(a_i^2,q)$$$.
Because for any $$$a_i\le a_j<\sqrt{q}-1\;(i\neq j)$$$, $$$a'_i=a_i-1$$$ and $$$a'_j=a_j+1$$$ results in a larger sum, so the resulting sequence must not have such $$$a_i$$$ and $$$a_j$$$, which means at most 1 of $$$a_i$$$ satisfies $$$0<a_i<\sqrt{q}-1$$$, and the rest are no less than $$$\sqrt{q}-1$$$.
Finally able to understand.. thanks
Unfortunately, I couldn't catch solving C within time (I solved it like 5 minutes post-contest).
Anyway, my question is, Was the only way to solve it by brute-forcing good-Q arrays and looking for a pattern? (That's how I figured out my solution but was wondering if there's a faster way)
I mean you can always prove your solution (if you're good enough at math).
Can you recommend resources to get better at math? (Proving stuff like this always puzzled me)
Evan Chen's website
Oh I didn't explain well, I'm horrible at math and I didn't prove my solution to problem C but you can solve these type of problems fast if you can prove your solutions.
Hi, in problem C, if n = 3, then what is the good array ?
according to editorial, the array is as below,,,
{ -1 , -1 , -1 , -1 -1 , 3 }
Now, LHS => -1 * -1 * -1 = -1 , RHS => 3 + (-1) + (-1) = 1
Since LHS != RHS, how can this be a good array ??
If n = 3, the only good array is {0, 0, 0, 0, 0, 0}
I had a strong feeling that there is a very limited number of possible good arrays since there are a lot of constraints. This is because each set of $$$N$$$ elements should have the property mentioned in the problem statement.
Then, I kinda "guessed" that all numbers should be the same, call it $$$C$$$, which gives exactly $$$1$$$ possible unique set of $$$n$$$ numbers, or only $$$1$$$ number is different than the other $$$2 \times N-1$$$ $$$C$$$'s, call it $$$X$$$, which gives exactly $$$2$$$ possible unique sets of $$$n$$$ numbers, one with the $$$X$$$ and one without it. I tried for $$$n=2$$$ to generate a set of $$$4$$$ different numbers to follow all conditions but did not feel possible, and it is not. So I explored all possible values for $$$C, X, N$$$, which were very limited as I guessed initially.
Anyway, following my guess for the first case is equivalent to solve $$$C^N = NC$$$ would result in the followings:
$$$N=1$$$ [Trivial]
$$$C=0$$$ [Trivial]
$$$N=2, C=2$$$, meaning that the array is $$$[2,2,2,2]$$$
And for the second case would reduce the problem into the following equations:
$$$(1)$$$ $$$C^N=X+(N-1) \times C = X + NC - C$$$
$$$(2)$$$ $$$C^{N-1}X=NC$$$
By subtituting RHS of $$$(2)$$$ in RHS of $$$(1)$$$, my cases were limited to the followings:
$$$C^{N-1}=-1 → C=-1$$$ and $$$N$$$ is even. Subtituting in $$$(2)$$$ results in $$$X=N$$$. Meaning that the array is $$$[-1,-1,...,-1,N]$$$
$$$C=X$$$ which belongs to the first case.
So, all the cases were limited to these cases of the array:
$$$[C, C]$$$, when $$$N=1$$$
$$$[2,2,2,2]$$$, when $$$N=2$$$
$$$[0,0,...,0]$$$ for any $$$N$$$.
$$$[-1,-1,...,-1,N]$$$ when $$$N$$$ is even (total number of elements is divisible by $$$4$$$).
Thanks a lot
Wow!
What a stupid idea for $$$E$$$... I abandoned this idea and thought, that it is impossible to make it pass.
But the magical complexity analysis is also a part of the algorithm , isn't it?
My submission to E: 197981349
Process the queries with ascending depths. For each of the queries move up the tree node by node, and stop if we encounter a preexisting pair. However we only memorize the current answer every 300 moves.
If we don't memorize the current answer and only the final answer (i did this in contest), it gets TLE on test 27: 197946777 :(
Can you elaborate on memorizing every 300 moves? I was also getting TLE on test case 27 during contest. Submission Link — 197963238
I stuck in problem C , wondering Did the good q exist...... Then ,I found $$$q_n$$$ , with 10 minutes left , too late to write code......hardForces
Hi, in problem C, if n = 3, then what is the good array ?
according to editorial, the array is as below,,,
{ -1 , -1 , -1 , -1 -1 , 3 }
Now, LHS => -1 * -1 * -1 = -1 , RHS => 3 + (-1) + (-1) = 1
Since LHS != RHS, how can this be a good array ??
editorial says that case happens when n|2 , so if n = 3 good array is only {0,0,0,0,0,0}
Understood, thanks.
[deleted].
Can anybody help, why am I getting TLE on test $$$10$$$?
My submission
I tried similar Brute Force approach as told in the editorial.
Map is much slower than hashtable because it's $$$O(\log n)$$$ , and the complexity in total will reach $$$O(n\sqrt{n}\log{n})$$$. I think you can use an array of hashtable like
unordered_map<int,long long> umap[200005]and use it just likeumap[x][y] = value.Thank you so much!
I modified your code to pass the problem 197988689. In addition to mashduihca's comment, another important optimization is to reorder the two nodes x, y that x<y. This reduces the number of possible pairs in half, and otherwise it keeps getting MLE and TLE. The removal of your optimization that x=y may be unnecessary, I removed it to find the reason of MLE.
Thanks a lot!
Can you please tell a bit more about why doing $$$x < y$$$ halves the number of possible pairs.
Yes. For example, for the pair {2,3}, without this optimization it may appear 2 times as {2,3} and {3,2}. Yet now that I think about this, this optimization should make no improvement for the worst case, but without this optimization it would get MLE/TLE. Does it imply that there is still plenty room for uphacking? XD
OK Understood, thanks again for your time!
:D
For example, now you are calculating $$$a_3 \times a_5$$$. It's a waste if you save both (3,5) and (5,3) because the order isn't important at all. And as we know , the constant of hashmap is too large , maybe even 10 times more than a single swap operation , so we don't want use it more.
Yes, understood!
Thanks!
You're truly welcome.
i submit your solution again.it's not pass.
I solved it again with hand-written hash table. 198019367 Though I still wonder why I'd get TLE on test 10, which I passed previously.
Maybe new case added.
Problem E is so strict that i cant solve it by map/unordered_map in limited time
OK, Testcase 58 ??? I tried other code but tle, this question must use array instead of unordered_map? I dont know why .
I found that if you just climb up T(const) steps, and then run the normal memorized search, the solution might be faster. I have tried some Ts and has found that it's fastest with T around 700. I think it's kind of 'metaphysical'. Can anyone explain this phenomenon?
BTW, if T = 0, my solution will get a TLE.
The observation in F is really amazing. This task is truly a great one(and hard).
What? The intended solution of E is not Mo's algorithm on tree? But my HashMap solution failed many times.
Can anybody help in problem B, why is the answer always <=2?
3 cases
1) Less than a half numbers are 0. In this case, we can insert 0 into the positions between positive numbers, and no sum will be 0, hence the mex would be 0.
2) More than a half numbers are 0, and there exists positive numbers >1. In this case, there must be a sum equals to 0, so place all 0 on the left, followed by a positive number >1, and the rest can be ordered arbitarily. Because there are no sum equals to 1, the mex would be 1.
3) More than a half numbers are 0, and all positive numbers are 1. In this case, sums equals to 0 and 1 are both inevitable. But by inserting 1 into the positions between two 0, we can prevent sums equal to 2. Hence the mex would be at most 2.
The 'a half' in former text is a little different than n/2. It's a border that the number of 0 > the number of positive integers + 1.
I still don't understand why problems setters add problems like F1 and F2 to a DIV2 contest! Isn't the round meant for div2 participants? Or your div2 testers were able to solve it? I see even Div1 participants struggled with the problem.
Actually it is common to have a problem harder than 2800 in a div2 contest.
Yes, but why?
It is a custom in programming contests that the hardest problem in a contest should be unsolvable for most contestants,which is used to distinguish top contestants.
E is barely possible with Java :(. Had right solution but still tle.
In problem E, I don't understand the part: "It's easy to discover that when $$$s_i > \sqrt{n}$$$, the contribution of it will equal to the contribution when $$$s_i = \sqrt{n}$$$"
Because for each query, it only accesses 1 pair of nodes in each layer, so the number of pairs accessed in a layer has an upper bound of q, making it min(s_i*s_i,q).
I have upsolved 1806E - Tree Master in $$$O\left(n \cdot q\right)$$$.
My accepted submission (1300 ms)
Unfortunately, my $$$O\left(n \cdot q\right)$$$ solution, which have passed all of the pretests, got TLE on 56-th system test during the system testing. It required 2 additional fixes before becoming accepted. Hope, that in the next time I will be better in using of AVX2.
You can find an explanation of main ideas of $$$O\left(n \cdot q\right)$$$ solution under a spoiler below.
Solving in $$$O\left(n \times q\right)$$$ means, that we will calculate an answer on each question in linear time. Lets start from arrays.
If we are given 2 distinct arrays of integers, we can calculate dot product of them in $$$O\left(\dfrac{n}{8}\right)$$$ with 256-bits YMM registers (AVX2 extension) with next function:
Now we are able to calculate dot product for two arrays. The next step is preparing of these arrays: convert each path in tree to subsegment of some array. We can do it with Heavy-Light Decomposition.
Now, we can start to calculate an answer on query. If two vertices stay on different paths in HLD, we will calculate part of answer with our dot product function and go up. When two vertices will stay on the same path, then they will stay on the same position (so, $$$u = v$$$) of this path and we can use precalculated sum of squares on path to root.
UPD. With a honest going up to root I got 1800 ms. Submission
Solution of E with block algorithm: Mark every node whose depth is divisible by sqrt(n) and subtree has at least sqrt(n) nodes as important nodes.There are at most sqrt(n) important nodes.for every pair of important nodes whose depth are the same,calculate the answer and store it.As there are at most n pairs of important nodes and for every pair of important nodes,there must be another pair of important nodes after sqrt(n) jumps,the time complexity is O(n*sqrt(n)).For every query,there must be a pair of important nodes after at most 2*sqrt(n)-1 jumps.So the time complexity is O(q*sqrt(n)).
overall time complexity:O((n+q)*sqrt(n)),overall memory complexity:O(n).
code:https://codeforces.com/contest/1806/submission/197990830
Can you elaborate more on why
There must be a pair of important nodes after at most 2*sqrt(n)-1 jumps. Is it because we need to have at least sqrt(n) nodes in the subtree ? Shouldn't the jumps besqrt(n) + 1, since it will satisfy both conditions for important nodes?If there is a subtree with size sqrt(n)-1 and the depth of its root is divisible by sqrt(n),for one node of a query in the subtree,we will jump at most sqrt(n)-1 times to the root of the subtree,but as the size of subtree is not greater than sqrt(n),this will not be a important node.We have to jump sqrt(n) more times to find another node whose depth is divisible by sqrt(n).The subtree of this node must have at least sqrt(n) nodes.So there must be an important node after 2*sqrt(n)-1 jumps.For the other node,it is the same.So there must be a pair of important nodes after at most 2*sqrt(n)-1 jumps.
Thanks, understood.
How I can derive a equation for this type of problems? : like Problem A. I was trying to solve this by brute-force approach(with two cases) but that didn't work. I get stuck at this type of problems.
It doesn't need any equation....just need observation...firstly you can increase x and y simultaneously so first of all d>=b must hold because you can never decrease y and to reach d you have to increase b by (d-b) and a will also increase by (d-b) then our another move is (x-1,y) so now c<=a must hold since we can't increase x coordinates now.
Hi mazihang2022, I just tried to uphack my own solution for problem E and got the response "unexpected verdict". Could somebody look into this? https://codeforces.com/contest/1806/hacks/895387
I think it works now. You can try again.
More and more unexpected verdict. What should u do?
I see your hacks. It is just because I wrongly marked some code as AC in polygon. The intended solution works fine and uses about only 600ms in your input. I think everything should be fixed now.
In problem C, many good arrays are not being considered. For instance, 1 2 3 1 2 3 is a good array. So for a given array [1,2,4,1,2,3] the output should be 1, the given code gives output 14
Problem E appeared in CodeChef long challenge 2.5 years ago: link
can someone tell me what is wrong here https://codeforces.com/contest/1806/submission/197944882 i didn't understand why it didn't work
I'm kind knew to Codeforcese T_T
−10^8≤a,b,c,d≤10^8 Its too slow. (One test can pass in 1 second maybe, but the number of testcases is like 10^4) You need O(1) solution here
Problem F has been appeared on CPSPC 2017, here
Could anyone explain D in a more concise way? The editorial is a bit too brief for me :(
Here's my gathering:
Let's denote node number 1 as
N1.f(k)is equal to the count of permutations of[1,..,k]such that, in corresponding graph of nodes[1,..,k+1], all the nodes have a path toN1, either directly or indirectly.Now let's derive
f(k)fromf(k-1). First of all, if some permutation of[1,..,k]results in all the(k+1)nodes to have a path toN1, then removing numberkfrom this permutation will also result in remainingknodes to have a path toN1. Which means, the value off(k)is somehow related to the value off(k-1). Now take some permutation of[1,..,k-1]which contributes tof(k-1). Then ifA(k)is0, i.e there will be an edge(k+1) -> (k)at some point, we can insert numberkto anywhere in between[1,..,k-1]and resulting permutations will also contribute tof(k). IfA(k)is1, i.e there will be an edge(k) -> (k+1)drawn at some point, denote the root of weakly connected component whichkbelongs to asroot(k), just before we draw this(k) -> (k+1)edge. If thatroot(k)is notN1, future edges will connectroot(k)toN1, by definition off(k-1). Ifroot(k)isN1, which can only be after last edge draw of[1,...,k-1], new edge becomesroot(k) -> (k+1), i.e,1 -> (k+1), so such a choice doesn't contribute tof(k+1).To calculate answer, let's denote total number of incoming edges of
N1in all[1,..,k-1]permutations asans(k-1). Then we can insert numberkanywhere in between any of these permutations and incoming degree ofN1coming from[1,..,k]doesn't change, since numberkis only responsible for(k) -> (k+1) edge. (or (k) <- (k+1) depending on A(k)Since, there arekslots to insert numberk,ans(k) = ans(k-1) * k+count of permutations where node k+1 is directly pointing to N1. Note that since new nodek+1appeared when we switched fromk-1-length tok-length permutations, this new node can also directly point toN1. It can happen only when all[1,2,...k]first nodes are already connected toN1(either directly or indirectly) inf(k-1)ways, and when we apply(K+1) -> (K)edge as the last edge, which only can be applied whenA(K)is0. Submission: https://codeforces.com/contest/1806/submission/198274330Thanks for this amazing detailed explanation. Had a hard time understanding editorial solution.
Ohh, I got stucked until I read this tutorial. I can understand now. Thanks a lot! You helped me! <3
I think the last part is not quite right, but I might be misunderstanding some things.
The incoming degree of $$$N_1$$$ can change after adding $$$k$$$, since $$$k$$$ is not only responsible for the edge connecting $$$k$$$ and $$$k+1$$$; as you said, it can also be directly connected to $$$N_1$$$ or other nodes ($$$root(k)$$$ with $$$k+1$$$ to be precise).
What happens is that, for each permutation of $$$[1,...,k-1]$$$, the in-degree of $$$N_1$$$ either stays the same or increases by one after adding $$$k$$$ somewhere in there. So it would be $$$ans(k) = ans(k-1)*k$$$ + number of permutations that increased (because we are adding +1 to each of them), which are the ones where node $$$k+1$$$ is directly pointing to $$$N_1$$$.
As you said, that is only possible when nodes $$$[2,...,k]$$$ point directly or indirectly to node $$$1$$$ before adding $$$k+1$$$ and $$$a_{k}=0$$$. So, we need to add $$$f_k$$$ if $$$a_k=0$$$.
It may also be helpful to visualize the problem as the union of segments in the $$$x$$$ axis instead of nodes floating around, that helped me with the proofs.
I still don't know why unordered_map will TLE in problem E = =
Because it's too slow,you should achieve it yourself.
Can someone explain D why If ai=1 only inserting at the end is invalid, so fi+1=fi⋅(i−1)?
here's my understanding: https://codeforces.com/blog/entry/114048?#comment-1014400
There is a mistake in editoral of D. The last two paragraph, the fi+1 should be fi. means (i,i+1,0)operation can make contribution only when it's at the end of operations. I think the editorial it's too brief for us,and it lack a lot of proof.
Formula fixed. But I'm not quite sure how to explain it in a clearer way :(
Can anybody share their thoughts on how they came up with problem C? How did they think and what made them think that way?
为什么没有中文版？
Why is there no Chinese version?
I think it is necessary,too.
Please help me explain the problem D's formula to calculate ans array! I have been stuck in that. :'(
Why F1=F2=2900? F2 is much harder than F1...
I remember the problem F2 from last years Turkish End of the Winter Camp OI (I just made up the name, TEWOI sound kinda cool tho) (It doesn't). I'm pretty sure that Turkish writers have stolen the problem from an obscure OI, and the only difference was you needed to solve the problem for all values of K, which was a nice addition to the problem for who wan't to solve. I'm not saying contests writers intentionally used an idea from another OI tho, idea of grouping numbers and summing up their gcds is not something that odd, and pretty sick problem nevertheless, I'm just surprised no one else from that camp mentioned it, also sorry for kinda necrocommenting, I just saw the problem yesterday.
Still solve the problem for the array with unique elements and use the fact that there are only $$$O(\log m)$$$ different prefix gcds, and notice that the different element that you merge with prefix can only be a different element other than the first element at most $$$O(\log m)$$$ times. (When prefix gcd changes.) So like adding the multiple elements you need to do at last, you can extract elements between prefix gcd changes. Use binary search or two pointers to find how many numbers you will add and extract for each different prefix gcds, thus solving it in $$$O(n \log^2 m)$$$ or $$$O(n \log m)$$$ (And sorry, I know the way I write is not in any means rigarous, just yell at me in the comments if you wan't me to clear something)
Seriously I need help . I am still not able to understand Tree Master Problem E, read all comments and editorial but cant really understand what is the logic behind it.
Firstly try to implement an "naive" solution that would give right answers without worrying about execution times. One way to verify its correctness is to pass the first several tests.
Then, analyze why the solution takes long time on larger trees, and think about how to optimize it. One natural idea is to memorize the result of visited pairs (x, y) in a map and re-use the results in future queries. Such "natural" idea however would still lead to TLE and require more optimizations.
One such optimization is to skip adding pairs to the cache in the first M (like 1000) steps walking-up the tree. More other ideas were discussed in the thread.
could you please elaborate more I mean the entire approach
The tree in the first example input is like below. Each node has two numbers id and value.
The first query is (4,5), which has following path to root respectively:
multiple corresponding value of these nodes we have the answer 33 for the pair (4,5).
If you understand this example and apply the idea generally you will get a "naive" solution. If you could NOT understand this example, I suggest you focus on solving problem A, B, C instead and skip E and above.
which leads to 2 | n and .
Doubt 1- What is the meaning of 2 | n in the Editorial part of C?
Similarly, for each exactly n−1 numbers in q3,q4,⋯,q2n, their product will be −1, which leads to q3=q4=⋯=q2n.
Doubt 2- How all these numbers are equal. It may be possible that some of them will be 1 too while odd number of them will be -1 to get overall -1. mazihang2022
Got it. Thanks
DownVote Me
Not satisfied with one Downvote ? Downvote me again
Is Editorial of Problem E intended approach ? It looks like it passed due to inability of creating strong TC ? But using of hashmap of $$$N*sqrt(N)$$$ and its parameters was implemented in nice way I think which helped solution to pass is entire subtree got pruned by storeing the pair and there will be atleast one level which has value less than $$$sqrt(N)$$$ atmax distance of $$$sqrt(n)$$$