Idea: diskoteka, prepared: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
def solve():
n, t = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
bst = -2
for i in range(n):
if i + a[i] <= t and (bst == -2 or b[bst] < b[i]):
bst = i
print(bst + 1)
t = int(input())
for _ in range(t):
solve()
```

Idea: playerr17, prepared: playerr17

**Tutorial**

Tutorial is loading...

**Solution**

```
t = int(input())
for testCase in range(t):
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
print(max(a[0] * a[1], a[-1] * a[-2]))
```

Idea: diskoteka, prepared: diskoteka

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
cout << ((n + 1) * n) + n + 2 << "\n";
}
return 0;
}
```

Idea: isosto, pavlekn, prepared: diskoteka

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
if (n == 1) {
cout << "1\n";
continue;
}
if (n % 2) {
cout << "-1\n";
} else {
for (int i = 0; i < n; ++i) {
if (i % 2) {
cout << i << " ";
} else {
cout << n - i << " ";
}
}
cout << "\n";
}
}
return 0;
}
```

1822E - Making Anti-Palindromes

Idea: pavlekn, prepared: pavlekn

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
void solve(int n, string & s) {
if (n % 2 == 1) {
cout << -1 << endl;
return;
}
vector<int> cnt(26);
for (int i = 0; i < n; ++i) {
++cnt[s[i] - 'a'];
}
for (int i = 0; i < 26; ++i) {
if (cnt[i] * 2 > n) {
cout << -1 << endl;
return;
}
}
int pairs = 0;
vector<int> cnt_pairs(26);
for (int i = 0; i * 2 < n; ++i) {
if (s[i] == s[n - i - 1]) {
++pairs;
++cnt_pairs[s[i] - 'a'];
}
}
for (int i = 0; i < 26; ++i) {
if (cnt_pairs[i] * 2 > pairs) {
cout << cnt_pairs[i] << endl;
return;
}
}
cout << (pairs + 1) / 2 << endl;
}
int32_t main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n;
cin >> n;
string s;
cin >> s;
solve(n, s);
}
}
```

Idea: playerr17, prepared: playerr17

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
struct Value {
int64_t value = 0;
int vertex = 0;
};
vector<vector<int>> nei;
vector<vector<int>> depth_vertex;
vector<int> depth;
vector<int> parent;
void dfs(int v, int p = -1, int cnt = 0) {
depth_vertex[cnt].push_back(v);
depth[v] = cnt;
parent[v] = p;
for (int u : nei[v]) {
if (u == p) continue;
dfs(u, v, cnt + 1);
}
}
void solve() {
int n, root = 1;
int64_t k_wei, cost;
cin >> n >> k_wei >> cost;
nei.clear();
nei.resize(n + 1);
depth_vertex.clear();
depth_vertex.resize(n + 1);
depth.clear();
depth.resize(n + 1);
parent.clear();
parent.resize(n + 1);
for (int _ = 0; _ < n - 1; ++_) {
int u, v;
cin >> u >> v;
nei[u].push_back(v);
nei[v].push_back(u);
}
dfs(root);
vector<pair<Value, Value>> down(n + 1);
for (int tin = n; tin >= 0; --tin) {
for (int v : depth_vertex[tin]) {
for (int u : nei[v]) {
if (u == parent[v]) continue;
if (down[u].first.value + 1 > down[v].first.value) {
down[v].first.value = down[u].first.value + 1;
down[v].first.vertex = u;
}
}
for (int u : nei[v]) {
if (u == parent[v] || u == down[v].first.vertex) continue;
if (down[u].first.value + 1 > down[v].second.value) {
down[v].second.value = down[u].first.value + 1;
}
}
}
}
vector<int64_t> up(n + 1, 0);
for (int tin = 1; tin <= n; ++tin) {
for (int v : depth_vertex[tin]) {
int p = parent[v];
up[v] = up[p] + 1;
if (down[p].first.vertex == v) {
up[v] = max(up[v], down[p].second.value + 1);
} else {
up[v] = max(up[v], down[p].first.value + 1);
}
}
}
int64_t ans = -1'000'000'000'000'000'002;
for (int v = 1; v <= n; ++v) {
ans = max(ans, k_wei * max(up[v], down[v].first.value) - cost * int64_t(depth[v]));
}
cout << ans << endl;
}
int main()
{
int t;
cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
```

1822G1 - Magic Triples (Easy Version)

Idea: pavlekn, prepared: pavlekn

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_VAL = 1e6;
int cnt[MAX_VAL + 1];
int32_t main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
++cnt[a[i]];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += (cnt[a[i]] - 1) * (cnt[a[i]] - 2);
for (int b = 2; a[i] * b * b <= MAX_VAL; ++b) {
ans += cnt[a[i] * b] * cnt[a[i] * b * b];
}
}
cout << ans << "\n";
for (int i = 0; i < n; ++i) {
--cnt[a[i]];
}
}
return 0;
}
```

1822G2 - Magic Triples (Hard Version)

Idea: pavlekn, prepared: pavlekn

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int K = 1e6;
const int MAX_VAL = 1e9;
int32_t main() {
int t;
scanf("%d", &t);
for (int _ = 0; _ < t; ++_) {
int n;
scanf("%d", &n);
vector<int> a(n);
map<int, int> cnt;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
++cnt[a[i]];
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
ans += (ll)(cnt[a[i]] - 1) * (cnt[a[i]] - 2);
}
for (auto el : cnt) {
int num = el.first;
int val = el.second;
if (num > K) {
for (int b = 2; b * num <= MAX_VAL; ++b) {
if (num % b == 0 && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
}
}
} else {
for (int b = 2; b * b <= num; ++b) {
if (num % b == 0) {
if ((ll)num * b <= (ll)MAX_VAL && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
}
if (b * b != num) {
if ((ll)num * num / b <= (ll)MAX_VAL && cnt.find(b) != cnt.end() && cnt.find(num / b * num) != cnt.end()) {
ans += (ll)(cnt[b]) * (cnt[num / b * num]) * val;
}
}
}
}
if (num > 1 && (ll)num * num <= (ll)MAX_VAL && cnt.find(1) != cnt.end() && cnt.find(num * num) != cnt.end()) {
ans += (ll)(cnt[1]) * (cnt[num * num]) * val;
}
}
}
printf("%lld\n", ans);
}
return 0;
}
```

G2 can be solved by going threw array from left to right and for every

iget all divisors ofa[i]and for perfect square divisorsXincrease answer bycnt[a[i] / X] * cnt[a[i] / sqrt(X)]. We just need to get divisors using prime factorization which we can get by going only threw prime numbers [1, sqrt(10^9)] (only ~3000).There are ~3000 primes in [1, 10^4.5] right, not 65?

still fast

Why are you downvoting? I just wrote my approach on that problem :)

.

Alternatively for g2, we can prime factorize the number to look for candidates for k. Apparently prime factorization can be done with pollard(although I didn’t do this) and the number of perfect squares can be found in logM (someone needs to prove this I suck at math). Essentially g2 can be solved in o(n*M^1/4).

For the log constant on m, you can notice that the number of perfect squares is the number of each p divided by 2 and choosing how much of each p exists. The number of terms is maximum 6 or approximately 2^6 operations. If someone has a better analysis of this it would be greatly appreciated.

I was thinking we can do

`O(n*M^(1/6))`

because we are only considering divisors of the`SQRT(M)`

, which is`~(M^(1/2))^(1/3)`

because the number of divisors of a number`M`

doesn't exceed`O(M^(1/3))`

Ref: https://mirror.codeforces.com/blog/entry/13585?#comment-185136

How would you find factors with sqrt(M) I’m curious.

Imagine we are brute-forcing the largest value

`a[k]`

, consider the divisors of`a[k]`

, we only need to consider divisors which are perfect squares because our value`b`

will be the square root of the divisor. I think we can show the number of divisors which are perfect squares of some value is at most the sixth root of the value.Does this answer your question?

The larger number could be a perfect square and not the smaller number? If you have implementation that would help.

Sure, here is my implementation: https://mirror.codeforces.com/contest/1822/submission/203467962

Hopefully this clears things up.

It does seem to be the right time complexity but it doesn’t have noticeably better performance compared with my previous algorithm. This may be due to a high constant factor.

Yeah I bet that's related to the implementation.

Also we can solve G2 with pointers and achieve better complexity without unordered map.

Editorial for C missing last few characters

Zooming out (from 125% to 100%) worked for me. It looks like overflowing content (on zooming in) are now made hidden instead of letting them go out of the box.

F can also be solved using rerooting dp.

Here is my submission.

Can someone hack this solution

It should get a TLE verdict.

I don't know why my solution was not TLE. Could you help me? This is my g2 solution

nice div3

Can someone pls tell why I am getting TLE at test 16 For Problem G1 even though my idea is same as the official editorial. Link of submission: (https://mirror.codeforces.com/contest/1822/submission/203514583)

Use an array instead of a dictionary

Can u give a test cases where this solution did not pass link of my solution https://pastebin.ubuntu.com/p/kVh39TVsk5/

Input1

7 6

7 1 3 2 5 14 1

14 2 11 7 15 11 6

Expected output3

Your output-1

ExplanationYou have assigned a value to the

tempvariable that you cannot retrieve. It's bigger than the answer you can get, so your program can't find the answer.How does one solve D? Is it just finding the pattern? I could only figure out that there is no answer for odd (>1) and n would be the first number.

the solution is kind of hidden in the last sample. one can construct the array on other even numbers and see if it works.

I think $$$a=[n, 1, n−2, 3, n−4, 5, …, n−1, 2]$$$ is wrong.

Isn't it $$$a=[n, 1, n−2, 3, n−4, 5, …, 2, n-1]$$$.

That's how your code is written.

Does 10 ^ 8 complexity passes in CF ?? asking becouse of editorial of G1

depends on time limit. Here we have 4s. it should pass.

Alternative Solution for Problem F

Intuition and SolutionLet dist[i] = distance of vertex i from vertex 1. (We can easily make this array by using a dfs or bfs)

Now, find the max distance vertex from vertex 1 and let's name it A. (Now, A will be one of the end points of the diameter of the tree, for sure)

Now find just run a bfs or dfs from vertex A and find all the vertices that have a distance from vertex A, greater than dist[A] (distance of A from vertex 1) and put them in a vector.

Now let's try to make each of the vertices that are present in the vector as the root of the tree and calculate the profit that they can acquire. It's pretty easy.

profit = k*(distance of v from A) — c*dist[v];

dist[v] -> is the distance between 1 and v, the distance 1 have to cover for making v as a root.

Find the max. profit and that will be the answer. Also include profit = k*dist[A] in the answer while calculating max. (The case in which we doesn't have shifted the root).

Time Complexity: O(N)

Why this works?As I said earlier, A will be one of the end points of the diameter of the tree. That means all the vertices that are on a greater distance than distance of 1 from A, have a chance that they can make a better profit, because they have a better length than dist[A]. As A is one of the end points of the diameter of the tree, that means it will also cover the max distance than other nodes, i.e. it will go to other end points of diameter as well, covering max distance possible.

Making the range of the distance of nodes lying between [dist[A] +1, diameter of the tree], considering all possible ways by which we can maximize profit.

-> Code

thank you so much for the solution, it was way more simpler to understand

however i dont really get why we dont have to

alsoDFS from the other end point of the diameter (which can be found in the process of DFS from A) butonlyfrom A to find the answer?Let's dive in and Think of it.If I start dfs from another diameter of the tree, lets name it B.And A is the diameter vertex we found. It is sure the dist[B] <= dist[A] from vertex '1'. (otherwise we would be having B as selected diameter from 1 not A)

so in case dist[B] < dist[A] from 1 i.e. 1 is close to B than A, we can clearly see it's not worth it in comparison to A, because we have to move more from 1 now and we are already having less k, resulting in less score.

If dist[A] = dist[B] but we found A as the diameter. Now in this case it can be beneficial for moving according to B. But as A & B are diameters of tree, and dist[A] = dist[B], no matter at which diameter we are, the answer/root lies on either on vertex '1' (in case k<=c) or on the another diameter of the tree.

oh i get it now, tysm

how to tell that the time complexity for G2 passes ? O(M^(1/3)nlogn) seems bigger than 10^8 for M = 10^9, n = 2*10^5

Where can I have a mistake?:

Problem F — Wrong answer on test 36.

But it works:

Problem F — Accepted.

you put assign(n, 0), instead of assign(26, 0)

I should definitely stop complicating problems. I used Binary Lifting to solve F.

If anybody wants to check the stupid submission: 203630946.

Yet another solution for G2 using sqrt decomposition(excuse my English):

First,for each prime number in

(1e9^(1/4),1e9^(1/2)],simply iterate over all multiples of its square.The time complexity is at most O(M^(1/2)lnM^(1/2)),and it is clear that each number <=1e9 can have at most one of these square numbers as its factor because(1e9^(1/4))^2*(1e9^(1/4))^2=1e9,so we can precalculate it using`std::map`

in O(M^(1/2)lnM^(1/2)logM^(1/2)).Next,for each number,iterate over all prime numbers in

[2,1e9^(1/4)].It doesn't takes long since there are less than 100 primes in[2,1e9^(1/4)].Then check the map for its factor in(1e9^(1/4),1e9^(1/2)](if exist) in O(logM).At last,iterate over all its factors.Since2^2*3^2*5^2*7^2*11^2*13^2~=9e8,there are at most 2^6=64 factors to iterate over for a single number.The total time complexity is O(M^(1/2)log^2(M^(1/2))+(100+logM+64)n). Solution:203320262For F you can dfs 3 times to find the maximum distance to the leaves.

I don't understand the tutorial of G1. Can someone explay it in newbie language? ∑ni=1(cnt[ai]−1)⋅(cnt[ai]−2) I don't know exactly what are we doing here

What I don't get is the part inside the loop. Cnt[a[i]-1] * (cnt[a[i]] — 2); code is quite clear. I want to know what exactly is this .

We need to choose 3 numbers $$$x$$$, $$$y$$$, $$$z$$$ such that $$$x * b = y$$$ and $$$y * b = z$$$.

When $$$b = 1$$$, $$$x = y = z$$$. In this case, we need to select 3 of the same number.

Let's say the count of $$$x$$$ is $$$cnt_x$$$. In how many ways can you select 3 different $$$x$$$ from $$$cnt_x$$$?

The key to question E is to figure out that if m*2>=k, the answer is m/2+m%2,isn't it? In other words,there must exist some way to match every two pairs that are not the same letter when m*2>=k. I probably know how to prove it through mathematical induction, it may seem unnecessary though.

why is this not passing? code is in segfault function

https://mirror.codeforces.com/contest/1822/submission/205472462

UPD: solved it.

The tutorial for G2 says the time complexity $$$O(n \cdot M^{\frac{1}{3}} \cdot \text{log } n)$$$ with the use of std::map will pass. Why does my solution TLEs then?

https://mirror.codeforces.com/contest/1822/submission/205547154

pavlekn what do you mean? I don't understand.

deleted comment

Another solution for G2, I believe is much simpler but is somehow getting tle. Can someone verify this?

*Time Complexity: O(n*pow(M,1/3)) *Idea:

so we have ensured that time complexity is O(n*pow(M,1/3)) submission

pavlekn Help Orz

I was solving D for practice and it seems like a question which solely depends on you somehow finding the pattern and there's not much reasoning leading upto it other than figuring out that the first element will be n. So you basically don't know what you want. Not really happy with the ad-hoc nature of this question,

Also there's a mistake in a=[n, 1, n−2, 3, n−4, 5, …, n−1, 2], it should rather be a=[n, 1, n−2, 3, n−4, 5, … 2,n−1].

Okay, on further exploration I somewhat accept that this question can be solved reaching the pattern in structured way and figure out this (and few other) pattern by trying to cover all mod values, beginning from 0 and n/2 being already covered. So, thinking of mod of n in a cycle from 0 to n-1 to 0,we can then think of a pattern which has sums reaching all values and this works out for various patterns. Obviously, we can't try to cover the mod values one by one so we can think of covering them in an alternate way, there are multiple ways of alternating, one can be trying to cover numbers from n/2+1 to n in one alteration and 1 to n/2-1 in the other. Other patterns include covering 1 to n/2 and n-1 to n/2 in the other direction. It all makes sense once you start seeing it from a pattern hit-trial with all the necessary equations. Another alternating pattern which you can try is covering one odd and one even number eventually collapsing to n/2.

On even further thought, maybe not so many patterns do actually fit in really which makes me take back my original stance. ;-;

I understand there isn't a rigorous way to solve this problem as it is constructive, but I still believe that the problem was spoiled by the last sample test case, making it quite easy. One can easily arrive at the fact that odd n > 1 don't work and that n must always be in front. The last sample is 6 5 2 3 4 1. We can actually generalize a whole algorithm from here in a rigorous way by basic observations: Array: 6 5 2 3 4 1 Residues:0, 5, 1, 4, 2 One can notice that after every two residues the numbers decrease. Why? Well in the array we added blocks of n — 1. So n — 1, 2n — 2, 3n — 3. Clearly, the residues decrease if reduce this modulo n. So the last sample suggests we should center some construction around decreasing residues every other time. Now, interestingly enough the residues also increase starting from 1. Goes from 1 to 2. The sample again suggests we should do something similar to this. More clearly, the sample gives us the intuition that maybe there is some construction in which we start from n — 1 decrease the residues until we reach the halfway point and start from 1 increase residues in till we reach the halfway point. From, there you can easily prove that putting even numbers and n — 1 — even numbers always work. Say you want residue 1 and you have n — 1 before it, obv you need 2, ...no we know that for the next thing, we will have residue n — 2 (since we chose to decrease like this), well then obviously we need 4 to get this residue to increase from 1 to 2. So in general when we want residue i we know we have residue n — i from before it so we will need 2i. 2i never gets too big where it won't already be reduced mod n. I think this is extremely intuitive, and something you don't need to prove.

In conclusion, this question boils down to simple problem-solving by generalizing patterns by sample test cases. It would definitely be much harder without them, but since they are there I think the question is fairly straightforward.

what's a residue

Can anyone explain what can we learn from genious problem D?

for G1 why does creating the cnt[x] array inside the main function gives TLE while when declared globally gets aceepted

For F:

IntuitionEssentially, we have that:

If v is the node we move root to,

`solution = max( k * maxdistance(v) - c * dist(root,v) )`

over all nodes v.where maxdistance(v) is the distance of the furthest node from v. It is pretty easy to get dist(root,v) in DFS/BFS.

Note we have two cases: if c >= k, then we will never move root (since we will lose profit). if k > c, then we will always want to move root to increase the maxdistance, which means v must be either a leaf, or the root itself. If it's the root, then maxdistance(root) is just height of root. So, let's now consider non-root v.

Suppose node u is the one whose distance dist(u,v) = maxdistance(v). u and v must share some ancestor, p. also u and v must be in separate subtrees of p, otherwise p would be a better choice than v.

So,

where the height of a subtree x of p is the height of the child of p who contains node x.

the plus 2 is to include the extra edge from each child to p

my submission: https://mirror.codeforces.com/contest/1822/submission/227252588