B works in O(n), no sort needed. Code

If we use 2 pointers in E, complexity will be O(n). https://mirror.codeforces.com/contest/1311/submission/71823186

F can be solved without pbds and fenwick tree, look at this submission.

How to solve F if there is integer t or positive integer t restriction.could we reduce any one restriction to nlogn time or some optimal time.

On problem D, I understood why do we iterate A to maximum 2a but what is the reason behind checking all multiples of A to maximum 2b? Also if we don't check for C = (c / B) * B + B, can we get the true answer?

Another solution for D: Let's precompute divisors and multiples (up to $$$2 \times 10^4$$$) for all numbers up to the $$$10^4$$$. Let's then fix a value of $$$B$$$, then $$$A$$$ has to be a divisor and $$$C$$$ a multiple. We find such $$$A$$$ closest to $$$a$$$ and $$$C$$$ closest to $$$c$$$ in $$$O(log n)$$$, compute the number of operations for that particular $$$B$$$, and repeat this for all possible $$$B$$$'s. Total complexity $$$O(n log n)$$$

WoW, thanks for the tutorial.

In problem B, thought if I approach find a -> find b -> find c. I have to iterator for (all possible a), for (all possible b), (find c), which run in O(q * a * b) then get TLE. But now I learn more that I just need to go for (all possible a), for (mutiples a), (find c). O(q * a log a)

IN D why editorial code O((n^2)*10^2) is working even after a<=10^4 and b <=10^4 ?

Does anyone uses brute force algorithm like me in problem D?XD

#define n (20000)
int a,b,c;cin>>a>>b>>c;
int ans=9999999,_a=0,_b=0,_c=0;
for(int i=1;i<=n;++i) for(int j=1;j<=n/i;++j) for(int k=1;k<=n/i/j;++k) 
{
	int now=abs(i-a)+abs(i*j-b)+abs(i*j*k-c);
	if(now<ans) _a=i,_b=i*j,_c=i*j*k,ans=now;
}
cout<<ans<<endl<<_a<<' '<<_b<<' '<<_c<<endl;

I heard that a lot of people were hacked because they set the limit only 10000 XD

On problem D, I understand why we iterate A to maximum 2a but what is the reason behind checking all multiples of A to maximum 2b?

can anyone please tell me what is wrong in my solution for problem B :

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " : " << x << endl;
 
bool cmp(pair<int, int> a, pair<int, int> b){
			return a.first < b.first;
}
 
int main() {
	const int N = 105;
	int t;
	cin >> t;
	while (t-->0) {
		int n, m;
		cin >> n >> m;
		vector <int> b(N);
		vector <pair<int, int> > a(n);
		for (int i=0; i<n; i++) {
			cin >> a[i].first;
			a[i].second = i;
		} 
		sort(a.begin(), a.end(), cmp);
		for (int i=0; i<m; i++) {
			int val;
			cin >> val;
			b[val]++;
		} 
		bool flag = true;
		for (int i=0; i<n; i++) {
			int pos = a[i].second;
			// deb(i);
			// deb(pos);
			// deb(a[i].first);
			for (int j=min(pos, i); j < max(pos, i); j++) {
				if (b[j + 1] == 0) {
					flag = false;
				}
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}

" A cannot be bigger than 2a, " Proof please. (Problem D)

For D I have different approach. I brute force C up to 2c. We know that number of divisors for numbers up to 20000 maximum is 60. So, if you prebuild all divisors for all numbers up to 20000, then for each C you can try each B (divisor of C) and for each B try each A (divisor of B). So each test is done roughly in 2c * 60 * 60 tries.

I didn't prove that C is not exceeding 2c. Is there proof? Or, perhaps hack? 71792331

can someone tell me why this submission got WA 71787302. and this AC 71788262. why could defining arrays in main is wrong?

In Problem B you can try the logic of Bubble sort.. 71787966

Any good source to learn pbds?

I made B, by using dfs

For D -> The Upper Bound of B and C should be mentioned in the problem statement.

Why the complexity of the solution of Problem E in this tutorial is $$$O(nd)$$$. The while loop from n*(n-1)/2 to the lower bound that approximately equal nlogn. So I suspect it's complex is $$$O(n^3)$$$. (n<700) And I copy the solution written at the tutorial, and add a variant to count the time complex as below:

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, d;
		cin >> n >> d;
		int ld = 0, rd = n * (n — 1) / 2;
		for (int i = 1, cd = 0; i <= n; ++i) {
			if (!(i & (i &mdash; 1))) ++cd;
			ld += cd &mdash; 1;
		}
                cout << ld << endl;

		if (!(ld <= d && d <= rd)) {
			cout << "NO" << endl;
			continue;
		}
	
		vector<int> par(n);
		iota(par.begin(), par.end(), -1);
		
		vector<int> cnt(n, 1);
		cnt[n - 1] = 0;
		
		vector<int> bad(n);
		
		vector<int> dep(n);
		iota(dep.begin(), dep.end(), 0);
		
		int cur = n * (n - 1) / 2;
                int iter = 0;
		while (cur > d) {
            
			int v = -1;
			for (int i = 0; i < n; ++i) {
                                iter++;
				if (!bad[i] && cnt[i] == 0 && (v == -1 || dep[v] > dep[i])) {
					v = i;
				}
			}
			assert(v != -1);
			int p = -1;
			for (int i = 0; i < n; ++i) {
                                iter++;
				if (cnt[i] < 2 && dep[i] < dep[v] - 1 && (p == -1 || dep[p] < dep[i])) {
					p = i;
				}
			}
			if (p == -1) {
				bad[v] = 1;
				continue;
			}
			assert(dep[v] - dep[p] == 2);
			--cnt[par[v]];
			--dep[v];
			++cnt[p];
			par[v] = p;
			--cur;
		}
	
                cout << iter << endl;
		cout << "YES" << endl;
		for (int i = 1; i < n; ++i) cout << par[i] + 1 << " ";
		cout << endl;
	}
		
	return 0;
}

It is my input :

1
650 5000

It is my output:

4837
268511100
YES
1 2 3 4 5 6 7 8 9 ...

It seems that the complex is bigger than $$$O(nd)$$$. 650*5000=3250000 and it iters 268511100 times.

Another solution for B is use DSU. We will define x and x + 1 is an edge, then we merge them . Then we sort the array A with storing the original position. We will consider all elements of A ( after sorting ), Call POS[] is a array to store the original pos, If Pos[i] < Pos[i + 1] we continue the loop, else we check if they have the same root , if not the answer is NO and we return, else the answer is YES. My solution : https://mirror.codeforces.com/contest/1311/submission/71846993

I can't figure out which is the editorial, the blog or the comments? :D

vovuh For problem F, I am not familiar with the fenwick tree coordinates compression technique. Can you elaborate a bit more on this?

The following statement in your editorial probably has something to do with this technique? add our current point to the Fenwick trees (add 1 to the position Vi in the first tree and Xi to the position Vi in the second tree).

I have some knowledge on fenwick tree but not so much with the coordinates compression technique. I assume it is needed because the input can be in range[1, 10^8] which would consume too much memory, right?

More clear explanation for sentence in D editorial "Then let's iterate over all possible multiples of A from 1 to 2b. Let this number be B." While we want to choose B if we choose it bigger than 2b this mean we need to have at least (b+1) operations. Except this if we just equalize the B to A at most we do b operations. Because highest value of |b-A| can be (2a-b) or (b-1) and these are smaller or equal to b because a<=b. So that we can't choose B upper than 2b.

is there a proof for solution to E?

I am getting the error for testcase4 in Problem B. Please help me my code

It seems like for D, any reasonably tight bounds will work: here is the one I came up with (after the contest...) and a proof:

• $$$a$$$ ranges from $$$i = 1$$$ to $$$2c$$$;
• $$$b$$$ equals $$$ji$$$ where $$$j$$$ ranges from $$$1$$$ to $$$ji\leq 2c$$$

Complexity: $$$O(c\log c)$$$ by counting all pairs $$$(i,j)$$$ with $$$ij\leq 2c$$$ (use harmonic series).

Proof: $$$a$$$ will never be above $$$2c$$$: because instead of taking $$$a$$$ to $$$ \gt 2c$$$, $$$b$$$ to $$$ \gt 2c$$$, and $$$c$$$ to $$$ \gt 2c$$$, we could simply take $$$a$$$ and $$$b$$$ to $$$c$$$.

And for the same reason, $$$b$$$ will never be above $$$2c$$$; because the number of moves in raising $$$b$$$ to $$$ \gt 2c$$$, and in raising $$$c$$$ to $$$ \gt 2c$$$, already exceeds the number of moves in making both $$$a$$$ and $$$b$$$ equal to $$$c$$$: $$$(c-a)+ (c-b) \leq 2c$$$.

In problem E, what is the logic behind calculating lower bound ld?

For E, Can anyone explain me why the time complexity is O(nd)?

why is this incorrect for fourth question (D).

In F , what if the points start moving simultaneously at time t=0. how to solve then?

Can anyone explain why we need to consider only upto 2*a in problem D?

Could anyone share the simplest way you've figured out to build that tree(in E)? Thanks in advance.

why in problem D the harmonic series is estimated as log n? (I would like to see the proof)

Problem B solution using disjoint sets

include<bits/stdc++.h>

using namespace std;

int giveParent(int x,int *parent) { if(parent[x] == -1)return x; else{ return giveParent(parent[x],parent); } }

void solve() { int n,m; cin>>n>>m;

int a[n+1],b[n+1];
for(int i=1;i<=n;i++){
       cin>>a[i];
       b[i] = a[i];
}


int parent[n+1];
memset(parent,-1,sizeof(parent));
while(m--)
{
    int x;
    cin>>x;
    parent[x+1] = x;
}

sort(b+1,b+n+1);
bool visited[n+1];
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++)
{
    if(b[i] ==  a[i])
    {
           visited[i]=true;
           continue;
    }
    else{
        int j;
        for( j=1;j<=n;j++)
        {
            if(b[j] ==  a[i] && visited[j] == false)
            {
                if(giveParent(i,parent) == giveParent(j,parent)){
                    visited[j] == true;
                    break;
                }

            }
        }

        if(j==n+1)
                {
                    cout<<"NO"<<endl;
                    return;
                }
    }
}

cout<<"YES"<<endl;

}

int main() { int T; cin>>T; while(T--) solve(); }

For problem F,while updating and querying Fenwick tree we generally isolate the last bit and the update our loop control variable as x+=(x&-x) and x-=(x&-x).However,here we are using different updating statements in the functions(pos=(pos & (pos + 1)) — 1) and (pos |= pos + 1).Can someone please explain me this.I am new to Fenwick trees. Thank you!