Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
for _ in range(int(input())):
a = [list(map(int, input().split())) for i in range(2)]
cnt = sum([sum(a[i]) for i in range(2)])
if cnt == 0:
print(0)
elif cnt == 4:
print(2)
else:
print(1)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << 2 << '\n';
for (int i = 1; i <= n; ++i) if (i % 2 != 0)
for (int j = i; j <= n; j *= 2)
cout << j << ' ';
cout << '\n';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
}
vector<int> cnt(n);
forn(i, m) ++cnt[a[i]];
auto check = [&](int t){
long long fr = 0, need = 0;
forn(i, n){
if (t >= cnt[i])
fr += (t - cnt[i]) / 2;
else
need += cnt[i] - t;
}
return need <= fr;
};
int l = 0, r = 2 * m;
int res = -1;
while (l <= r){
int m = (l + r) / 2;
if (check(m)){
res = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%d\n", res);
}
return 0;
}
```

1701D - Permutation Restoration

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int& x : b) cin >> x;
vector<pair<int, int>> ev(n);
for (int i = 0; i < n; ++i)
ev[i] = {(i + 1) / (b[i] + 1) + 1, i};
sort(ev.begin(), ev.end());
set<pair<int, int>> s;
int j = 0;
for (int i = 1; i <= n; ++i) {
while (j < n && ev[j].first == i) {
int id = ev[j++].second;
s.insert({b[id] ? (id + 1) / b[id] : n, id});
}
a[s.begin()->second] = i;
s.erase(s.begin());
}
for (int& x : a) cout << x << ' ';
cout << '\n';
}
}
```

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
vector<int> zf(const string &s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
++z[i];
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
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, t;
cin >> n >> m >> s >> t;
int ans = 1e9;
bool bad = false;
vector<int> lpos(m), rpos(m);
for (int i = 0; i < m; ++i) {
if (i > 0) {
lpos[i] = lpos[i - 1] + 1;
} else {
lpos[i] = 0;
}
while (lpos[i] < n && s[lpos[i]] != t[i]) {
++lpos[i];
}
if (lpos[i] >= n) {
bad = true;
break;
}
}
for (int i = m - 1; i >= 0; --i) {
if (i + 1 < m) {
rpos[i] = rpos[i + 1] - 1;
} else {
rpos[i] = n - 1;
}
while (rpos[i] >= 0 && s[rpos[i]] != t[i]) {
--rpos[i];
}
if (rpos[i] < 0) {
bad = true;
break;
}
}
if (bad) {
cout << -1 << endl;
continue;
}
for (int pos = 0; pos <= n; ++pos) {
string tmp = s.substr(0, pos);
reverse(tmp.begin(), tmp.end());
tmp += "#" + t;
reverse(tmp.begin() + pos + 1, tmp.end());
vector<int> z = zf(tmp);
for (int suf = 0; suf <= m; ++suf) {
if (pos - suf < 0) {
continue;
}
if (suf < m && rpos[suf] < pos) {
continue;
}
if (suf - 1 >= 0 && lpos[suf - 1] > pos) {
continue;
}
int rg = 0;
if (suf != 0) {
int sum = (pos - z[pos + 1 + m - suf]) + (pos - suf);
rg = (sum != 0) + sum;
} else {
rg = pos;
}
ans = min(ans, (n - pos) + rg);
}
}
cout << ans << endl;
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
const int M = 200001;
typedef array<long long, 3> vec;
typedef array<vec, 3> mat;
vec operator+(const vec& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
return c;
}
vec operator-(const vec& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
return c;
}
vec operator*(const mat& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
c[i] += a[i][j] * b[j];
return c;
}
mat operator*(const mat& a, const mat& b)
{
mat c;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
c[i][j] = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
c[i][k] += a[i][j] * b[j][k];
return c;
}
mat F = {vec({1, 0, 0}), vec({1, 1, 0}), vec({1, 2, 1})};
mat B = {vec({1, 0, 0}), vec({-1, 1, 0}), vec({1, -2, 1})};
mat E = {vec({1, 0, 0}), vec({0, 1, 0}), vec({0, 0, 1})};
vec S = {1, 0, 0};
vec Z = {0, 0, 0};
vec t[4 * N];
mat f[4 * N];
bool active[4 * N];
bool has[N];
int d, q;
vec getVal(int v)
{
if(!active[v]) return Z;
return f[v] * t[v];
}
void recalc(int v)
{
t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);
}
void build(int v, int l, int r)
{
if(l == r - 1)
{
f[v] = E;
t[v] = S;
active[v] = false;
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
f[v] = E;
recalc(v);
active[v] = true;
}
}
void push(int v)
{
if(f[v] == E) return;
t[v] = f[v] * t[v];
f[v * 2 + 1] = f[v] * f[v * 2 + 1];
f[v * 2 + 2] = f[v] * f[v * 2 + 2];
f[v] = E;
}
void updSegment(int v, int l, int r, int L, int R, bool adv)
{
if(L >= R) return;
if(l == L && r == R)
{
if(adv) f[v] = F * f[v];
else f[v] = B * f[v];
return;
}
push(v);
int m = (l + r) / 2;
updSegment(v * 2 + 1, l, m, L, min(m, R), adv);
updSegment(v * 2 + 2, m, r, max(m, L), R, adv);
recalc(v);
}
void setState(int v, int l, int r, int pos, bool val)
{
if(l == r - 1)
{
active[v] = val;
return;
}
push(v);
int m = (l + r) / 2;
if(pos < m)
setState(v * 2 + 1, l, m, pos, val);
else
setState(v * 2 + 2, m, r, pos, val);
recalc(v);
}
void addPoint(int x)
{
int lf = max(0, x - d);
int rg = x;
if(lf < rg)
updSegment(0, 0, M, lf, rg, true);
setState(0, 0, M, x, true);
}
void delPoint(int x)
{
int lf = max(0, x - d);
int rg = x;
if(lf < rg)
updSegment(0, 0, M, lf, rg, false);
setState(0, 0, M, x, false);
}
void query(int x)
{
if(has[x])
{
has[x] = false;
delPoint(x);
}
else
{
has[x] = true;
addPoint(x);
}
vec res = getVal(0);
printf("%lld\n", (res[2] - res[1]) / 2);
}
int main()
{
scanf("%d %d", &q, &d);
build(0, 0, M);
for(int i = 0; i < q; i++)
{
int x;
scanf("%d", &x);
query(x);
}
}
```

I 'll tell you about codeforces round 131 .These tasks are very interesting not only by condition, but also by solutions.

Please make more rounds like this one, they make me feel a bit better about myself

Me tooorz

Please No more binary search :(. I'm bad at identifying binary search in the wild. If someone suggests me to use binary search then I'm able to solve the problem easily but when I encounter them in the wild they ravish me. Any suggestion on how to handle them?

binary search on answer if we can come up with a function (the over all complexity will be O((complexity of this function)*log(total range))) which can verify if the current answer(tracked by mid) is a correct answer(but may be not max or min) and the output of this function should be monotonic i,e. (00000111111111) 0 -> not possible 1-> possible. or (11111110000) and we want to find min or max in the possible range. and our main job here is to write that verification function efficiently and correctly main part of identification is to check if there is a monotonic nature in the possible answer space. and if it's possible to come up with a efficient verification function for each answer often this function is done greedly because we just have to check if it's possible or not.

Just think that someone has suggested you to use binary search

correct xd

ye, me too. i just love the concept behind each problem :3

can someone explain the idea of problem E with DP pls, I've seen many solutions with an array like f[N][3] or f[N][N][3], can anyone explain the approach pls.

(sorry if this is a bit long/confusing, I'm not the most experienced at explaining)

First off, imagine choosing some subset of the letters in $$$s$$$ that form $$$t$$$: for example if $$$s$$$ is

`zzzabczzz`

and $$$t$$$ is`abc`

, then the`abc`

is useful but all the`z`

s are useless fluff.Then you want to delete all the fluff. Here's one approach: first, you delete fluff from the end of the string until you come to useful letters. Then, you iterate past the useful letters, until you come to more fluff to delete. Repeat until all the fluff is gone.

This may not always be optimal, for example if $$$s$$$ is

`zaaaa`

and $$$t$$$ is`aaaa`

: then you want to go to the start, go forward, and delete the singular`z`

.When you're deleting fluff from the back, it takes $$$1$$$ operation to iterate past useful letters and $$$1$$$ operation to delete the fluff. When you delete fluff from the beginning, it takes $$$1$$$ operation to iterate past useful letters, but $$$2$$$ operations to delete fluff (you need to iterate forward then delete).

Then, the optimal solution will look something like this: there is some prefix (possibly empty) of the string where you've deleted from the beginning, then some contiguous segment of useful letters you haven't iterated over, and finally, some suffix of the string where you've deleted from the end.

If the prefix isn't empty, then it needs $$$2x+y+1$$$ operations, where $$$x$$$ is the number of fluff characters in the prefix, and $$$y$$$ is the number of useful characters. Otherwise it takes $$$0$$$ operations.

Next, the contiguous segment of useful letters, this takes $$$0$$$ operations since you don't iterate over it at all.

Finally, for the suffix, it takes $$$x+y$$$ operations.

At least in my solution, the dp[3][N] was something like this: 0 for the prefix, 1 for the contiguous segment, and 2 for the suffix. The transitions were somewhat tedious to implement but fairly straightforward.

Thanks! P/S : It's a very nice explanation.

Problem C and D were really good problems.In C it's little tough to get binary search intuition.

how did you come up with the idea of using binary search... it didn't click for me

It's pretty clear that you have to use binary search because you have to try to minimize the number of hours your need. If you can complete all the tasks in x hours then you can surely complete them in x+1 hours.

Can you please prove the greedy part of it that each worker should first take the entire available time to do all the tasks he is expert in first before helping others?

I really liked problem E, the solution is very interesting for me(also like a problem)

In the problem E's editorial while calculating the answer for prefix, the substring notations used were t[0;m-suf] and s[0;n-pos], then acc to editorial we have to build the z-function on $$$s[0;pos)^{-1}$$$ + # + $$$t^{-1}$$$, shouldn't it be n-pos instead of pos?

Yeah, this is a typo. It should be $$$s[0; pos)$$$ and $$$t[0; m - suf)$$$. Thanks.

In the second para there is a typo I guess then, the suffixes rather being $$$s[n-pos,n)$$$ and $$$t[m-suf,suf)$$$, shouldn't it be $$$s[pos,n)$$$ instead ? I am confused about pos, is it assumed as a forward iterator or a backward iterator?

Yeah, it is $$$s[pos; n)$$$. Forgot to fix that along with previous typos.

Idk Why I always try to solve in O(N) and never think of an O(N^2) approach :(

Video Solutions of Problem C and Problem D.

Link Any idea why this is giving wrong on 4900th test on testcase2? I did not use binary search instead used multiset. To briefly explain what I did, I took maximum time consuming person and minimum time consuming person and just exchanged their hours of work, with min+2, and max-1, and broke off when the time stopped decreasing. I feel this should work, but I am unable to see the test case where it fails. :((

Take a look at Ticket 15631 from

CF Stressfor a counter example.Btw F can be solved using SQRT decomposition on queries in $$$O(NsqrtN)$$$

submission

I think this contest is quiet interesting, but in my opinion, there are two drawbacks.

First, it is easier than other div.2, like problem C and D, they are a little bit easy.

Secound, why both problem C and D are all binary search. It's kind of repeated.

One way of doing F without storing $$$f(i)^2$$$ would be to observe that $$$\frac{(f(i)+1)f(i)}{2} - \frac{f(i)(f(i)-1)}{2} = f(i)$$$. In other words, if a point is added in its range, the change in its contribution to the answer is simply $$$f(i)$$$. Thus, for each point $$$i$$$, we can store only two values: whether it is currently in the set, and what its value of $$$f(i)$$$ is.

To change the answer when a point $$$j$$$ is added, it suffices to query the sum of $$$f(i)$$$ over the interval $$$[j-d,j)$$$ and to calculate the value of $$$f(j)$$$ itself by querying how many points in $$$(j,j+d]$$$ are in the set. Removing a point works similarly.

I have a solution to problem C in linear time.163331694

There's an $$$\mathrm{O}(q\log q)$$$ solution for Problem F with balanced search trees (Splay, Treap, etc).

We may consider new/deleted beautiful triples when point $$$x$$$ is added/deleted from the set as three parts, in which:

It's quite simple to calculate the first two types, since we may find the number of $$$y$$$'s that satisfy $$$y \in (x-d, x)$$$ or $$$y \in(x, x+d)$$$, then add two arithmetic progressions of common difference $$$1$$$. But we find it not very easy to add the number of type 3 triples instantly. So it's necessary to maintain 'if we add/delete point $$$x$$$ from the set, the number of $$$x$$$-as-the-middle triples being added/deleted' in some way.

Let's discuss how many triples will turn invalid when we

removea point from the set. One may notice that if we'readding$$$x$$$ to the set $$$S$$$, then for each $$$y \in S, y \in (x-d, x)$$$, for every point $$$z$$$ satisfying $$$z \in [x-d, y), z \in S$$$, $$$(z, y, x)$$$ will be a new beautiful triple in which $$$y$$$ sandwiching in between $$$x, z$$$. Let $$$c_y$$$ be the number of such $$$z$$$'s for each $$$y$$$. Obviously if we consider all valid $$$y$$$'s in increasing order (denoting $$$x-d<y_1<y_2<\cdots<y_k<x$$$), then $$$c_{y_i}=i-1$$$. It's similar for $$$y \in (x, x+d)$$$. Thus we may maintain set $$$S$$$ with a binary search tree, and add arithmetic progressions on a specific segment — which is a classic trick — when adding an element to $$$S$$$. Once we want to remove a point $$$x$$$ from the set, substract the number of first 2 types along with the count of type 3 triples from the answer, which we've stored on the BST. Also, its deletion will lead to a negative contribution of $$$c_{y_i}$$$ for all valid $$$y$$$'s mentioned above, so don't forget to add the opposite number of a progression on the BST maintaining $$$S$$$.The next part is considering 'if $$$x$$$ is not in the set, how many $$$x$$$-in-the-middle triples will turn valid after

addingit'. Suppose we're adding $$$x$$$ to the set $$$S$$$. We still consider $$$x-d<y_1<y_2<\cdots<x$$$; then for each $$$i \in \lbrace{1,2,\cdots,k-1}\rbrace$$$, for all $$$z \in (y_i,y_{i+1})$$$, $$$(y_j,z,x), j \in \lbrace{1,2,\cdots,i}\rbrace$$$ will be new beautiful $$$z$$$-in-the-middle triplesif $$$z$$$ is added after $$$x$$$. It's obvious that for all $$$z$$$ in the same segment whose endpoints are adjacent $$$y$$$'s, the numbers of potential new valid triples are the same. Similarly, for each segment, the sequence of new potential valid triples is an arithmetic progression of common difference $$$1$$$. Thus we may use another BST to maintain all segments $$$(l,r), l\in S, r\in S, \nexists p \in S, p \in (l,r)$$$ and proceed the sum of progressions. If we want to add $$$x$$$ to set $$$S$$$, then add the sum of contributions of type 1 & 2 triples and the segment's to the answer,splitthe segment it belongs to to two (empty segmentsshould be preserved), and do operations above.When removing $$$x$$$ from $$$S$$$, we may first add the opposite number of contributions of $$$x$$$ on two BST. What about

mergingtwo segments on the second BST? Do they have the same potential new triples after $$$x$$$ is deleted? The answer is YES. Apparently, for $$$x,y$$$ in segment $$$(l, r)$$$, if $$$(p, x, q), p\leq l, q \geq r$$$ is a valid potential triple, so does $$$(p, y, q)$$$ and vice versa. So it's ok to set the contribution of new $$$(l, r)$$$ (in which $$$x$$$ has just been removed) as $$$(l, x)$$$'s.A careful and efficient implementation is required for this solution. Submission #163416351

Sorry for any grammar/vocabulary mistakes above.

Solution to the first problem: If the number of units is 0 then the answer is 0, otherwise if the number of units is 4 then the answer is 2, otherwise the answer is 1.

Thank you! It is a good idea.

anyone please tell me why i am getting TLE on test case 4 in problem C . 163421348

edit — the problem accepted when i used priorty_queue instead of multiset 163422803

The problem is in the method 'findMax' and 'findMin' you are copying the entire data structure each time the method is calling.

int findMin(multiset my_set) this means that the first argument will be copied, so in the worst scenario it will copy a huge data structure each time.

The solution is this add '&' before the identifier of the argument: int findMin(multiset &my_set), now the multiset won't be copied.

There are two ways to pass an argument, by reference or by coping the entire argument.

This is your solution only adding '&' in those two methods: https://codeforces.com/contest/1701/submission/163423017

I hope this could help, greeting bro

thank u

Let's calculate value of $$$\sum f(i)$$$ in every node (it's simple). If we know this sum, we can restore value of $$$\sum f^2(i) - f(i)$$$. Let's say, we already somehow calculate it after some query: $$$F(i) = \sum f^2(i) - f(i)$$$.

If we add $$$k$$$ to all $$$f(i)$$$ we need to update our $$$F(i)$$$ value. Now the right value must be equal to $$$\sum (f(i) + k)^2 - (f(i) + k)=\sum f^2(i) + k^2 + 2 \cdot kf(i) - (f(i) + k)=\sum f^2(i) - f(i) + \sum k^2 + 2 \cdot kf(i) -k$$$.

$$$\sum f^2(i) - f(i)$$$ we already know, it is $$$F(i)$$$. Let's find $$$\sum k^2 + 2 \cdot kf(i) - k$$$. Value of $$$\sum 2 \cdot k f(i)$$$ we know too, because we store value of $$$\sum f(i)$$$ in every node. Value of $$$\sum k^2 - k$$$ we can calculate if we know how many points are now "active" in our node.

So now we get $$$F(i) = F(i) + 2 \cdot k \cdot \sum f(i) + cnt \cdot (k^2 - k)$$$; $$$f(i) = f(i) + cnt \cdot k$$$, where $$$cnt$$$ equals to number of active points.

Can anyone give a greedy approch for Question C . I got wrong ans on a test 2 .

I solved it with greedy approach https://codeforces.com/contest/1701/submission/163284252

Create an array of size = number of workers . iterate through the tasks and for each tasks that can be done faster increase the array value of that worker by 1 . now you have an array that incorporates all the tasks but these are assigned to the most efficient worker . e.g- 3 workers , tasks = [1,1,1,2] would look like a[1]=3 , a[2]=1 a[3]=0

TO solve this know that if a worker has 3 tasks and other has 0 the array would look like [3,0] .So you can a[i]-- and a[j]=a[j]+2 (because the non profecient will do it in +2 time ).

Now you need a data structure that can find the min element , maximum element , insertion , deletion in log (n) time . So use multiset or pair of min heap and max heap .

Multiset approach — while(1) let minimum ele be =x , max ele = y and check if x+2>=y then break else you remove the minimum element and the maximum element . Then do x=x+2 , y=y-1 and insert x and y into the multiset again .

After getting your final multiset , the answer is the highest element in the array which can be found in O(n) time

good round

Problem C : If anyone can help to find a mistake in this 163459281. I have tried using both priority queue and multiset. I have tried to do x = (max-min)/3. And now deleted max and min and added min+2x and max-x. But it is giving wrong answer. But if i try to do using x=1 only then it gives right. Why is it so??

I don't get what is (a — b) / 3. push to both heaps (a — 1) and (b + 2), i.e. you are giving one task to person who doesn't specialize in this task. But here it is more convenient to use multiset https://codeforces.com/contest/1701/submission/163284252

See when you are saying push a-1 and b+2 that means a-b = 3. So for example a = 10, b = 3. Then by a-1, b+2 we will be doing a = 9, b = 5, then again a=8, b=7. Bu if I do a = 10-(7/3) = 8 and b = 3 + 2*(7/3) = 7. Isn't it more convenient. But with this approach, I am getting 9712th testcase wrong in the 2nd.

answer: 182

your approach gives: 27

if you use priority queue you need to delete a and b from both queues, and insert a and b to both queues, but it will be slow. So it's better to use multiset. But here also your approach will fail on this test

answer: 6

your approach gives 7

In Problem 2, whats the difference between these two codes ?? Wrong Code- void solve() { int n;cin>>n: cout<<2<<endl;//d will be always 2

}

Right Code- void solve() { int n;cin>>n; cout<<2<<endl;//d will be always 2

}

You are not updating value of iRight bro, thnx for the help

In problem D, sweep line is not needed. Simply sorting the range in increasing order of ending point is enough. AC code: https://codeforces.com/contest/1701/submission/163624301

It would be nice if you added some comments to the solution code for F.

If you are/were getting a

WA/REverdict on problems from this contest, you can get thesmallestpossiblecounter examplefor your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.Disclaimer: There is a quota of 1 request per 24 hours on the free plan.

You don't need to use binary search in problem D, here's my priority queue solution:

https://codeforces.com/contest/1701/submission/163729522

Problem D is a pain in the a$$

How to check if the tasks can be completed by some time t? What that means is that all workers have t hours to work on some tasks. If all tasks took 2 hours to complete, then each of them could complete ⌊t2⌋ of them. Thus, together they would be able to complete ⌊t2⌋⋅n tasks.

i'm not getting these lines

can anyone help on which test case my solution fails problem C — Schedule Management here is my code // cyber12 Copyright 2021-2022 the only code by cyber12

## include <bits/stdc++.h>

## include

// #include<ext/pb_ds/assoc_container.hpp> using namespace std; // using namespace __gnu_pbds; // typedef tree<int,null_type,less,rb_tree_tag,tree_order_statistics_node_update>

## define fast ios_base::sync_with_stdio(false);

## define input cin.tie(NULL);

## define frin(a,n) for(int i=0;i<n;i++){cin>>a[i];}

## define frout(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}

## define vout(v) for(auto i:v){cout<<i<<" ";}

## define vin(v,n) for(int i=0;i<n;i++){int k;cin>>k;v.pb(k);}

## define in ll n;cin>>n;

## define ss string

## define pb push_back

## define mp make_pair

## define out(num) cout<<num<<"\n";

## define asrt(a,n) sort(a,a+n);

## define vsrt(v) sort(v.begin(),v.end());

## define ll long long

## define fr(n) for(int i=0;i<n;i++)

## define ii pair <ll, ll>

## define vii vector

## define vi vector

## define py cout<<"YES\n";

## define pn cout<<"NO\n";

## define pm cout<<"-1\n";

## define INF 1000000000

string int2binary(ll num) { ll n = (ll)(log2(num)); return bitset<64>(num).to_string().substr(64 — n- 1); } ll binary2int(ss s) { return stoi(s, 0, 2); } void solve() { ll n,m; cin>>n>>m; ll a[m]; frin(a,m); if(m==1) { out(1); return; } vector< ll >v(n+1,0); fr(m) { v[a[i]]++; } vector<pair<ll,ll>>vp; for(int i=1;i<=n;i++) { if(v[i]>0) { vp.pb(mp(v[i],i)); }

}

int main() { fast input

}

for solution 2 you gave the intuition for d=2 we will have the best possible permutation(according to this question).....Meanwhile you have given d=3 as ans in the main question....then how can a person get this intuition.