1311A - Add Odd or Subtract Even

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
if (a == b) cout << 0 << endl;
else cout << 1 + int((a < b) ^ ((b - a) & 1)) << endl;
}
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution (n^2)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> p(n);
for (int i = 0; i < m; ++i) {
int pos;
cin >> pos;
p[pos - 1] = 1;
}
while (true) {
bool ok = false;
for (int i = 0; i < n; ++i) {
if (p[i] && a[i] > a[i + 1]) {
ok = true;
swap(a[i], a[i + 1]);
}
}
if (!ok) break;
}
bool ok = true;
for (int i = 0; i < n - 1; ++i) {
ok &= a[i] <= a[i + 1];
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
```

**Solution (n log n)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> p(n);
for (int i = 0; i < m; ++i) {
int pos;
cin >> pos;
p[pos - 1] = 1;
}
for (int i = 0; i < n; ++i) {
if (p[i] == 0) continue;
int j = i;
while (j < n && p[j]) ++j;
sort(a.begin() + i, a.begin() + j + 1);
i = j;
}
bool ok = true;
for (int i = 0; i < n - 1; ++i) {
ok &= a[i] <= a[i + 1];
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
```

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, m;
string s;
cin >> n >> m >> s;
vector<int> pref(n);
for (int i = 0; i < m; ++i) {
int p;
cin >> p;
++pref[p - 1];
}
for (int i = n - 1; i > 0; --i) {
pref[i - 1] += pref[i];
}
vector<int> ans(26);
for (int i = 0; i < n; ++i) {
ans[s[i] - 'a'] += pref[i];
++ans[s[i] - 'a'];
}
for (int i = 0; i < 26; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int a, b, c;
cin >> a >> b >> c;
int ans = 1e9;
int A = -1, B = -1, C = -1;
for (int cA = 1; cA <= 2 * a; ++cA) {
for (int cB = cA; cB <= 2 * b; cB += cA) {
for (int i = 0; i < 2; ++i) {
int cC = cB * (c / cB) + i * cB;
int res = abs(cA - a) + abs(cB - b) + abs(cC - c);
if (ans > res) {
ans = res;
A = cA;
B = cB;
C = cC;
}
}
}
}
cout << ans << endl << A << " " << B << " " << C << endl;
}
return 0;
}
```

1311E - Construct the Binary Tree

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
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 - 1))) ++cd;
ld += cd - 1;
}
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;
while (cur > d) {
int v = -1;
for (int i = 0; i < n; ++i) {
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) {
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 << "YES" << endl;
for (int i = 1; i < n; ++i) cout << par[i] + 1 << " ";
cout << endl;
}
return 0;
}
```

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (Fenwick tree)**

```
#include <bits/stdc++.h>
using namespace std;
long long get(vector<long long> &f, int pos) {
long long res = 0;
for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
res += f[pos];
return res;
}
void upd(vector<long long> &f, int pos, int val) {
for (; pos < int(f.size()); pos |= pos + 1) {
f[pos] += val;
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<pair<int, int>> p(n);
for (auto &pnt : p) cin >> pnt.first;
for (auto &pnt : p) cin >> pnt.second;
sort(p.begin(), p.end());
vector<int> vs;
for (auto &pnt : p) vs.push_back(pnt.second);
sort(vs.begin(), vs.end());
vs.resize(unique(vs.begin(), vs.end()) - vs.begin());
long long ans = 0;
vector<long long> cnt(vs.size()), xs(vs.size());
for (auto &pnt : p) {
int pos = lower_bound(vs.begin(), vs.end(), pnt.second) - vs.begin();
ans += get(cnt, pos) * 1ll * pnt.first - get(xs, pos);
upd(cnt, pos, 1);
upd(xs, pos, pnt.first);
}
cout << ans << endl;
return 0;
}
```

**Solution (pbds)**

```
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef
tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<pair<int, int>> p(n);
for (auto &pnt : p) cin >> pnt.first;
for (auto &pnt : p) cin >> pnt.second;
sort(p.begin(), p.end());
ordered_set s;
long long ans = 0;
for (int i = 0; i < n; ++i) {
int cnt = s.order_of_key(make_pair(p[i].second + 1, -1));
ans += cnt * 1ll * p[i].first;
s.insert(make_pair(p[i].second, i));
}
s.clear();
for (int i = n - 1; i >= 0; --i) {
int cnt = int(s.size()) - s.order_of_key(make_pair(p[i].second - 1, n));
ans -= cnt * 1ll * p[i].first;
s.insert(make_pair(p[i].second, i));
}
cout << ans << endl;
return 0;
}
```

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

nicely done :)

awsome spookywooky

in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way

Can you explain your solution? Thanks in advance...

Lets call a position where we cannot swap the two elements a border. So, for every position there is a border nearest left of it.

All elements left of the border cannot pass the border (because we cannot swap there).

In var ma2 we maintain the maximum value left of the border. Then we compare the current element (which is right to the border) to ma2.

The var ma is used to maintain the current maximum, which is moved to ma2 whenever we find a border position.

Problem B We can use map to see can we go from a point to another and see for every a[i]

Here is The code : 71906289

nice!

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

Can you explain your approach ? Thank advance ^_^!!

Statement 1: There is no exist the tree with sum of depths of all vertices more than unary tree.Statement 2: There is no exist the tree with sum of depths of all vertices less than balanced tree.Let's create unary tree for default. Sum of depth for this tree — is the sum of ariphmetic progression. We must decrease it to the d. Fix the deepest vertex. Fix the top vertex of the tree. If we can't attacth the lower vertex to the higher because the sum of depth will be smaller than d, it means that we must deepen the upper vertex. And as we go from top to bottom the difference on every step decreases exactly 1. It means that there isn't exist the better solution.

Add to these the condition that every layer must be not greater than 2 size of previous layer and this will be a solution.

Wow!! Thank you for the detailed explanation. What a nice solution :>

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

I explained some reasoning behind this solution but I should have posted it here: this is it:

First there is a trick to sum all $$$x_j-x_i$$$ for $$$i<j$$$ in a sorted array $$$x[]$$$ in linear time: Errichto wrote some blogs calling it the contribution technique.

Now in our problem say $$$x=[100,50,75,25]$$$, and the corresponding sorted $$$v=[1,2,3,4]$$$. First we sort $$$x=[25,50,75,100]$$$. Then we can sum $$$x_j-x_i$$$ using the above technique. Look at the ways 75 gets added:

(from 75-50, 75-25, and 100-75)

Now let's iterate through $x$ in sorted $$$v$$$ order: when we get to the third element 75, we see that for our answer we should only have a single

term due to the

; we only want $x_j-x_i$ where $$$v_j>v_i$$$. Coincidentally this equals the net sum of the three terms above. The reason is that if $$$75$$$ has the same rank in both the sorted $$$x$$$ and the sorted $$$v$$$ versions, then there is a symmetry in how $$$[25,50,75,100]$$$ mutates into $$$[100,50,75,25]$$$: we can let other elements "jump over" 75 to anywhere on the other side, and the symmetry is that the number of jumps going right over 75 equals the number of jumps going left: 100 jumped left, but then 25 jumped right. So the rank of 75 is equal in both cases, and we don't need to correct the $$$+75,+75,-75$$$ in our final answer.

Another case is $$$25$$$, which is rank 1 with respect to $$$x$$$, but rank 4 with respect to $$$v$$$: From the contribution method, we had

due to 50-25, 75-25, and 100-25. But because the rank changed from 1 (w.r.t $$$x$$$) to 4 (w.r.t $$$v$$$), we must have had 3 jumping overs to the left: and every such jumping over means we shouldn't have included a $$$-25$$$, so we correct with $$$+25$$$ 3 times, and end up with $$$0\cdot 25$$$ in the final answer.

I managed to solve F using a modified version of Merge Sort and prefix sums. Code.

why after changing vector<pair<int,int> >vec(n); into vector<pair<int,int> >vec; then it will get a Runtime Error? Is the data type "pair" responsible for this? Thanks.

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?

`(c / B) * B`

and`(c / B) * B + B`

are the two consecutive multiples of B such that C lies in between them.`(c/B) * B <= C <= (c/B) * B + B`

So C could be closer to either of the multiples. We have to check both.

I have a problem is that (c/B) * B it can't ensure the C >= B,but the ans need the B < C.So why we need to consider both? we can't get the wrong ans?Could you tell me about that?

Whether C will get larger than or equal to B or it won't, we will always find an answer such that A < B < C. This is because the distance |c-C| + |b-B| will be larger when B >= C compared to any other possible solution where B < C.

Also, when B > c (remember the lower-case letters are input variables), then c/B < 1, which means floor(c/B) = 0 and thus C = 0 or C = B which are both not feasible and will fetch us larger total distance sum compared to any feasible solution. It's hard to prove why but you can kind of imagine that.

Thank you so much!

Is there actually a prove to the problem that "There is feasible solution having a smaller distance comparing to the solution that C=0 or C=B?"?

I can kind of think about why it is so but cannot prove it. Maybe somebody good at Maths here can prove it

Could you please explain why do we iterate A to maximum 2a?thanks in advance.

Because we can iterate A to 1 at the same cost as iterating A to 2a. And it's clear that 1 can divide more numbers than 2a can divide.

Oh, I understand that now. Thanks a lot.I also have some ideas to share with you.

Thinking carefully, you'll find that the the reason behind checking all multiples of A to maximum 2b is

the same asiterating A to maximum 2a.while $$$A>=2*a-1$$$, it works the same as $$$a=1$$$（maybe $$$a=1$$$ works more）,but that costs more, so $$$A\in [1,2*a-1)$$$

In the same way, iterating B to A costs the same as iterating B to b+b-A, but while $$$B=A$$$, it works more,so $$$B\in [A, 2*b-A)$$$

You're welcome, thank you too.

Thank u, I can understand now. I prefer visualizing the thinking. Because B divide by A, C divide by B, so C divide by A. If you take $$$B > 2b$$$, you always can take B = a and this choice even give c more chance to reach C, because B (with > 2b) has multiple point is subset of B (with = A).

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)$$$

nice <3

Great solution but I think if constraints had been n <= 1e5 or n <= 1e6, then memory limit would have exceeded because space complexity is O(N*sqrt(N))

As far as I know, the sum of the count of divisors of numbers from $$$1$$$ to $$$n$$$ is about $$$n \times \log n$$$. Please correct me if I am wrong.

I had the same solution with limit on B set to 1e5 and it passed easily.

Looks like we both are making lesser accurate approximations :

Link

If i understood the proposed algorithm right then I calculated :

1.The number of divisors of all numbers from 1 till n. Let this be f(n)

2.The number of multiples of i till 2*n for all i from 1 to n. Let this be g(n)

If these numbers are correctly calculated then there could have been a problem with memory limit.

Also, I think your solution passed because the constrains were upto 1e4. I am unsure of it, so do correct me if I'm wrong.

My submission.

It considers $$$MAX = 10^{5}$$$ and precomputes all factors of numbers from 1 to $$$MAX$$$.

There seems to be no problems with memory but problems with time, it nearly hit the TL(due to multiple tests), but memory is fine.

And I think I know why, since according to me, it should take $$$MAX \log MAX$$$ memory which is about 1.6 million ~ 12 MBytes (assuming long long), this seems to be consistent with the memory my submission took(9.6 MB).

I did not calculate the actual memory upper bound but you are right here. And your calculations are consistent with mine also. For n = 1e5, I also estimated 1.6M numbers in total. Which is passable.

For n <= 1e6 it should fit in the memory limit as well, it would take something as high as 150 MB which is fine.

About the link you gave regarding the upper bound on divisors. I think the upper bound on divisors of a single number is not tight enough to give sum of count of divisors of all numbers in a range with good margin of error. (Some numbers have more factors, some less, so error accumulates)

See this comment for details about my estimation comment

You are correct about this. Thanks for correcting me.

I thought that

`finding closest divisor of given number`

has the complexity of O(sqrt(n)) since you have to iterate`all the divisors of given number`

and check the diff of them ?Is there a way to approach

`find closest divisor of given number`

in O(log n) ?In this particular problem you can precompute all divisors of all numbers up to $$$10^4$$$ and have them in memory, so finding the closest one to a given number is a binary search so $$$O(log n)$$$. Check this code.

I dont understand, can you go in more detail. I mean the source of your algorithm ?

Precomputation is like sieve of prime factors, we iterate on numbers and push current number to all of its multiples. Overall complexity is given by harmonic series sum, $$$O(n + n / 2 + n / 3 + ... + 1)$$$ which reduces to $$$O(n \times \log n)$$$.

With this, we get list of divisors of all numbers from $$$1$$$ to $$$n$$$ now use binary search to find closest divisor.

great solution! But I'm wrong because I think that the range of possible B is 1 to 10^4. In your answer, you set it up to 2 * 10 ^ 4. Can you tell me why? Thanks

Take for eg 137 10000 10000, the optimal solution would be 137 10001 10001, so the value(s) of a,b and c can exceed 10000.

But we know that the value can never exceed 20000, since we could always bring down a,b or c<=10000 to be equal in less than 10000 steps.

wow, thanks!

why till 2*10^4 . How did you get this number ?

I did the same but why till 2e4 and in the editorial why till 2a, could u plz explain? I got some intuition but unable to formalize it.

We consider only the values <= 2*a because the cost of transforming a into a value >2*a is greater than the cost of transforming it into 1, and 1 will always be solution as every number is divisible by 1

awesome, great explanation

great!!!

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 ?

We are iterating over multiples of "a",to find "b" as b is a multiple of "a".Its a kind of sieve that through which we don't have to consider all the values of b<=2*10^4.

for(int i=1;i<=20000;i++) for(int j=i;j<=20000;j+=i) (Here i represents "a" and j represents "b")

So,the time complexity in O(t*n*log(n)).

Thanks

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

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

I was hacked...

That's bad :-(

I was rank 62 when I went to sleep,and rank 226 when I woke up,and found myself hacked.

why are we setting limit to 20000? I do not understand this, can you please explain. Thank you

because i know that 10000 is not enough (for example

`173 10000 10000`

)but i can't find the real limit so i just set the limit 20000.(it's easy to prove that 20000 is enough)

maybe 15000 is enough

Greate problem!

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?

Oh I understand that now. B must satisfy: |B-b|<=|A-b|, thus B<=2b.

hi could you please elaborate a little more. Thanks in advance.

if |B-b|>|A-b|, then change B to A, and the result will be better

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

I also got wrong answer during the contest. And the wrong answer was always on test 4. After the contest, I found the problem is on the cmp function. You can delete the cmp function and change "sort(a.begin(), a.end(), cmp)" into "sort(a.begin(), a.end())". Then you will get accepted. But I still don't know the specific reason until now and want to know why this type of cmp will cause wrong answer. I hope this can help you.

thankyouu :) williamwangx

Try changing your

`comp`

function to this:AC. thank you for your precious time Ravenclaw_OIer !

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

Let's say A is bigger than 2a, then in order to get A from a, we need A — a > a add operations. No matter what B we pick, we can always use a — 1 subtract operations to get A = 1 from a, which always meet the requirement B % A = 0. So going over 2a always yields a worse answer than simply decrease a all the way down to 1.

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?

you should have defined

Pwith size ofNnotMas the set of positions is in range(1 ≤ pi < n)your code after defined

Pwith size ofN71849815sorry for my bad english

ooh! how stupid I'm XD .

ty

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

In the tutorial,why it is $$$n^2$$$ and $nlogn$，I don't think so

I also..

Any good source to learn pbds?

Benq's template

I made B, by using dfs

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

No

I don't agree, it was a good aha moment for me to figure out upper bounds, and I think it is a big part of the problem.

By the way, my weak/loose bound on $$$C$$$ was $$$4 \times 10^{4}$$$ but I took $$$5 \times 10^{4}$$$ during the contest just to be sure.

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:

codeIt is my input :

It is my output:

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

could you help me please? @Kirundel

Please place codes in spoilers.

It seems $$$O(n * (n^2 - d))$$$, but the algorithm just runs if there is an answer.

Therefore $$$n\log_2 n \leq d$$$ or $$$n \leq \frac{d}{\log_2 n} $$$ and the algorithm runs in $$$O(\left( \frac{d}{\log_2 n} \right) ^3)$$$ which is enough to pass. This result also matches your experiment as $$$\left(\frac{5000}{\log_2 650}\right)^3 \approx 153204056$$$.

Code is O(max value possible — min value possible) per test case. If you only take cases where min value possible <= 5000 then the max possible gap is 218448 so final complexity is O(2*10^8) with pretty low constant

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://codeforces.com/contest/1311/submission/71846993

I solved B a bit differently in NlogN, first I made sorted copy of array, then for each element found its index in sorted array, and checked if theres positions in array p for each index from 1 to i-1.

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?

Coordinates compression and Fenwick tree. Read about both techniques and I think you'll understand the solution.

Thank you! :)

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:

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 $$$>2c$$$, $$$b$$$ to $$$>2c$$$, and $$$c$$$ to $$$>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 $$$>2c$$$, and in raising $$$c$$$ to $$$>2c$$$, already exceeds the number of moves in making both $$$a$$$ and $$$b$$$ equal to $$$c$$$: $$$(c-a)+ (c-b) \leq 2c$$$.

.

I don't understand why I'm getting downvoted

Why we go till 2*b only ? Please tell is my explanation correct. So suppose we choose a multiple which is more than 2*b so total cost will be B — b which is more than b coz B > 2*b + cost of changing a + cost of changing a.

We choose a such that it's cost dosen't exceed a (A <= 2*a) but in turn we have made the cost of b > b coz(B > 2*b) so as b > a we have made our costs worse. So we need to optimise cost of b before a. So suppose we optimise the cost of b and it will be <= b (coz B <= 2*b) for any given C. Now with this fixed B we can choose A in such a way that cost of a dosen't exceed a (A <= 2*a) to make it a divisor of B. Thus we improved cost of both a and b simultaneously. Hence we should only consider multiples upto 2*b as we can always get some A <= 2*a and B <= 2*B so that the condition B%A == 0 and C%B == 0 holds.

Can someone tell if my idea is correct or it has some flaw.

In problem E, what is the logic behind calculating lower boundld?The least value of sum of depths will be least only when all the layers of the binary tree are filled except possibly the last level. You could show that if this was not the case, you could move one of the leaves to a lesser depth and reduce the total sum of depths. This type of binary tree is called 'Complete Binary Tree'.

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

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

can someone explain me why in B,in nlogn solution we have checked for p[i]==0 ??

`p[i] == 0`

means this`i`

index is not present in`p`

and hence continue to next iterationbecause in this solution we are finding continues segment of

`p[i] == 1`

thanks

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?

In

PROBLEM F, Can anybody explain at what point below coordinates coincide? ~~~~~ 3 1 5 10 9 6 1 ~~~~~ A B C (suppose names of points)Ans is 0 I guess. But I don't understand at which point? (maybe I'm assuming something wrong)

At 1 sec: A = 10, B = 11, C = 11 (Only d(B,C)=0)

At 1.x sec:

A = 11.a, C = 11.a, B = 11.b where b>a ( only d(A,C)=0)

At 1.y sec: (y>x)

C = 11.c, A = 11.d, B = 11.d where b>a (only d(A,B)=0)

At 1.z sec: (z>y)

C = e, B = f, A = g where g>f>e (diff increases more hereafter)

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

If Suppose A=2a+1 then |A-a|=a+1 so better convert a to 1. So, the difference then will be a-1.

Got it thank you.

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)

One can use comparison of $$$\sum\limits_{n=1}^M \frac{1}{n}$$$ with $$$\int\limits_{1}^M \frac{1}{x} \, dx$$$

In Problem F. WHy do we need to make compression ?? I didn't make it and got wrong answer. but I coudn't understand why? Thanks for help

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 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!

in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way

if a == b then obviously answer is 0,

if a < b then we have to add a number to get from a to b, but we can add only odd numbers which is good if a is odd and we want to go to even number (o+o=e), or if a is even and we need to go to odd numbers (e+o=o), other wise we can subtract 1 from a to get to one of the above mentioned stage,

do the same reasoning for a > b..

In the fourth question, we can enumerate a, B and C. the upper bound is 2 * C, which can also be crossed.

can anyone tell me why I am seeing O(n^2) and O(n^3) answers getting accepted in probD, here n = 10^4, how is that even possible, isn`t 10^8 too much to pass through 2 seconds limit.