Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
string s;
cin >> s;
bool ok = true;
if (s.length() % 2 == 0) {
forn(i, s.length() / 2)
if (s[i] != s[i + s.length() / 2])
ok = false;
} else
ok = false;
cout << (ok ? "YES" : "NO") << endl;
}
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
set<int> a;
for (int i = 1; i * i <= n; i++)
a.insert(i * i);
for (int i = 1; i * i * i <= n; i++)
a.insert(i * i * i);
cout << a.size() << endl;
}
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
void solve(){
ll a, s;
cin >> a >> s;
vector<int>b;
while(s){
int x = a % 10;
int y = s % 10;
if(x <= y) b.emplace_back(y - x);
else{
s /= 10;
y += 10 * (s % 10);
if(x < y && y >= 10 && y <= 19) b.emplace_back(y - x);
else{
cout << -1 << '\n';
return;
}
}
a /= 10;
s /= 10;
}
if(a) cout << -1 << '\n';
else{
while (b.back() == 0) b.pop_back();
for(int i = len(b) - 1; i >= 0; i--) cout << b[i];
cout << '\n';
}
}
int main(){
ios_base ::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t){
solve();
t--;
}
return 0;
}
```

Idea: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
//
// Created by Vlad on 17.12.2021.
//
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
int n, m;
vector<vector<int>> p;
bool check(int x){
vector<bool> abl(m);
bool pair = false;
for(int i = 0; i < n; ++i){
int c = 0;
for(int j = 0; j < m; ++j){
if(p[i][j] >= x){
abl[j] = true;
c++;
}
}
if(c > 1) pair = true;
}
if(!pair && m > 1) return false;
bool ans = true;
for(bool b: abl){
ans = ans && b;
}
return ans;
}
void solve() {
cin >> n >> m;
p.assign(n, vector<int>(m));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> p[i][j];
}
}
int l = 1, r = 2;
while (check(r)) r *= 2;
while (r - l > 1){
int mid = (r + l) / 2;
if(check(mid)) l = mid;
else r = mid;
}
cout << l;
}
bool multi = true;
signed main() {
//freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
int t = 1;
if (multi) {
cin >> t;
}
for (; t != 0; --t) {
solve();
cout << "\n";
}
return 0;
}
```

Idea: SixtyWithoutExam

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5;
int main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n;
cin >> n;
vector<int> a(n), cnt(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[a[i]]++;
}
sort(a.begin(), a.end());
stack<int> st;
vector<ll> ans(n + 1, -1);
ll sum = 0;
for (int i = 0; i <= n; ++i) {
if (i > 0 && cnt[i - 1] == 0) {
if (st.empty()) {
break;
}
int j = st.top();
st.pop();
sum += i - j - 1;
}
ans[i] = sum + cnt[i];
while (i > 0 && cnt[i - 1] > 1) {
cnt[i - 1]--;
st.push(i - 1);
}
}
for (ll x : ans) {
cout << x << ' ';
}
cout << '\n';
}
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n, m, k;
cin >> n >> m >> k;
vector<int> p(n);
forn(i, n)
p[i] = i;
if (tt > 0)
cout << endl;
forn(round, k) {
int index = 0;
forn(table, m) {
int size = n / m;
if (table < n % m)
size++;
cout << size;
forn(j, size)
cout << " " << p[index++] + 1;
cout << endl;
}
rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
}
}
}
```

Idea: Gol_D

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int k;
map <int, vector<int>> mx;
map <int, vector<int>> my;
map <pair<int ,int>, bool> used;
map <pair<int, int>, int> time_of;
int dfs(int x, int y) {
used[{x, y}] = true;
int _min_ = time_of[{x, y}];
auto i = lower_bound(mx[x].begin(), mx[x].end(), y);
auto j = lower_bound(my[y].begin(), my[y].end(), x);
if (++i != mx[x].end() && !used[{x, *i}] && abs(*i - y) <= k) {
_min_ = min(_min_, dfs(x, *i));
}
--i;
if (i != mx[x].begin() && !used[{x, *(--i)}] && abs(*i - y) <= k) {
_min_ = min(_min_, dfs(x, *i));
}
if (++j != my[y].end() && !used[{*j, y}] && abs(*j - x) <= k) {
_min_ = min(_min_, dfs(*j, y));
}
--j;
if (j != my[y].begin() && !used[{*(--j), y}] && abs(*j - x) <= k) {
_min_ = min(_min_, dfs(*j, y));
}
return _min_;
}
void solve() {
mx.clear();
my.clear();
used.clear();
int n;
cin >> n >> k;
vector <pair<int, int>> a(n);
int x, y, timer;
for (int i = 0; i < n; ++i) {
cin >> x >> y >> timer;
a[i] = {x, y};
time_of[{x, y}] = timer;
mx[x].push_back(y);
my[y].push_back(x);
}
vector<int> res;
for (auto now: mx) {
sort(mx[now.first].begin(), mx[now.first].end());
}
for (auto now: my) {
sort(my[now.first].begin(), my[now.first].end());
}
for (auto now: a) {
if (!used[now]) {
res.push_back(dfs(now.first, now.second));
}
}
sort(res.begin(), res.end());
int ans = res.size() - 1;
for (int i = 0; i < res.size(); ++i) {
ans = min(ans, max((int)res.size() - i - 2, res[i]));
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
```

1619H - Permutation and Queries

Idea: Brovko

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
//#define int long long
#define ld long double
#define x first
#define y second
#define pb push_back
using namespace std;
const int Q = 100;
int n, q, p[100005], r[100005], a[100005];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 0; i < n; i++)
{
cin >> p[i];
p[i]--;
}
for(int i = 0; i < n; i++)
r[p[i]] = i;
for(int i = 0; i < n; i++)
{
int x = i;
for(int j = 0; j < Q; j++)
x = p[x];
a[i] = x;
}
while(q--)
{
int t, x, y;
cin >> t >> x >> y;
if(t == 2)
{
x--;
while(y >= Q)
{
y -= Q;
x = a[x];
}
while(y--)
x = p[x];
cout << x + 1 << "\n";
}
else
{
x--;
y--;
swap(r[p[x]], r[p[y]]);
swap(p[x], p[y]);
int ax = x;
for(int i = 0; i < Q; i++)
ax = p[ax];
int x2 = x;
for(int i = 0; i < Q; i++)
{
a[x] = ax;
x = r[x];
ax = r[ax];
}
swap(x, y);
ax = x;
for(int i = 0; i < Q; i++)
ax = p[ax];
x2 = x;
for(int i = 0; i < Q; i++)
{
a[x] = ax;
x = r[x];
ax = r[ax];
}
}
}
}
```

Really liked Problem D. The observation about how pigeonhole theorem can be used in the check function of binary search was very good.

You guys used binary search ? Wow

How have you solved it? Would you like to share your approach?

https://codeforces.com/contest/1619/submission/140109705

podtelkin could you please explain why this idea worked?

UPD:Got it. Nice idea你可以在这里看到中文版本(Link)

I think I can explain it.

(Please forgive my poor English.)

my code is here

According to the description of the problem, you can easily get the follow inequality:

I use

`a[i][j]`

to describe the`j`

's contribution to friends numbered`i`

.Then let's suppose $$$n-1 \leq m$$$.

Now I give a strategy for choosing gifts:

`I`

, and find his favorite gift`J`

.`a[1][J]`

,`a[2][J]`

,...,`a[n][J]`

, and pick the corresponding`I'`

.`I`

and`I'`

will be given the gift`J`

.`top1ByFriends[I]`

and`top2ByShops[J]`

.`top1ByFriends[i]`

.`I`

, we will have several $$$\alpha$$$ that satisfy the following condition:`top1ByFriends[I]`

<`top2ByShops[J]`

, the $$$\alpha$$$ will be determined by`top1ByFriends[I]`

so any`I'`

who has`a[I'][J]`

bigger than`a[I][J]`

is OK, because he won't influence the result in this situation.So now we can say:

You can prove the result is exactly $$$\text{min{minTop1ByFriends[i],maxTop2By Shops[j]}}$$$ by category discussion.

Supplement:

If $$$n-1$$$ > $$$m$$$, everyone can get their favorite gifts.

So ans is

`minTop1ByFriends[i]`

.And you can find that at least two friends will have their favorite gifts in the same shop, so the

`maxTop2ByShops[j]`

won't less than`minTop1ByFriends[i]`

.Thank youvery much manThank you very much :)

I think one simple way of explaining this approach is:

1) we have to pick at least two gifts from the same store (by the pidgeonhole principle).

2) we can always choose the store that has the highest second max, and pick the max and second max gifts from this store and give them for the respective friends (lets call this decision opt*), and I argue this choice can always be made and still achieve an optimal solution: if our solution has 2 other items from any same store, then the second highest of these two will be smaller than the second highest of the opt* choice (by definition of highest second max), making it a worse choice. thus, we can always choose opt* and still get a optimal solution.

3) now pick the best n-2 for the remaining n-2 friends.

What i did in the contest was we know that we can visit n-1 shops ,so the idea is that for every shop we can see the maximum and the 2nd maximum joy values which are attained for any two friends .let say its i and j ,so leaving these two friends apart we can easily take the maximum of joys from any shops for the rest of the friends .i won't suggest you to see my implementation it's really messy and the binary search logic is way more easy to implement and think .my implementation involves map of multiset of pair of int which was the best i could think in the contest

well, i have a solution using sort and some magic

this is my solution. I scared to fail the system test, but some how it passed.140057739

here are my thoughts while doing this problem btw:

I also used the pigeonhole principle to solve it but the binary search part is still unclear to me... Like how I can prove that if I can get x units of joy I would be able to get x-1 units of joy? Please care to explain...Thankyou

The binary search function $$$f(x)$$$ means I can get $$$x$$$ or more units of joy (not necessarily exactly $$$x$$$ units)

If $$$f(x)$$$ is true, then $$$f(i)$$$ for $$$i < x$$$ is definitely true

If $$$f(x)$$$ is false, then $$$f(i)$$$ for $$$i > x$$$ is definitely false.

So you find the maximum $$$x$$$ for which $$$f(x)$$$ is true by binary search.

Ohh, thanks a lot... Misunderstood binary search function.

Whenever i see maximize the minimum of something my brain just automatically think of binary search. In this problem i struggled with verifying if a particular mid can be achieved.

Solution to problem D without binary search :-my submission

Edit: I don't have any proof, but it works

When upsolving G with an unordered_map I got TLE for problem G. When using a map it passes. Took me a long time to realize this was the problem.

Gol_D Did you on purpose make a test case that blows up an unordered_map? I doubt this could've happened accidentally. Especially since my code runs quickly on other max cases, it's only Case 14 that is slow.

Yes, they do keep such a test case on purpose.

I believe it is because someone got hacked using unordered_map during the open hacking phase, then the test case used was included in the main tests

Implementation of C really messed up my contest it was failing on test case 3. Did anyone else face this issue.My Solution Can someone please have a look and point out what I missed.

It is not an implementation issue, there is a logical error in this part:

Please check 140048744 for what should have been in place of the above piece of code.

can anyone please explain G in bit more detail ?

This is actually a graph problem, let's see it in graph terms.

Let each bomb be a node in our graph, there is an edge between two nodes if they share a coordinate and have distance $$$\leq K$$$. Now look at its connected components. Clearly if we trigger a bomb, then the entire connected component containing that bomb will explode as well. So a connected component can be triggered by either: we trigger any bomb by ourselves, or we let the earliest bomb explode naturally.

Now we have two tasks to solve: Find all the connected components (and the minimum bomb timer in each component), and choose which components to trigger manually (and which will explode naturally).

To find connected components: Suppose all bombs are on a straight line, then it's easy. Sort the bombs, add an edge between all pairs of consecutive bombs with distance $$$\leq K$$$. For the general problem, use a

`map<int, vector<int>> mapx, mapy;`

or something like that to store bombs on the same x-straight line or y-straight line and solve it as if all bombs are on the straight line. You now have the graph.To choose which components to trigger: Try solving the problem for $$$K = 0$$$ (i.e. no bombs trigger one another). Obviously we want to sort the bomb timers, and trigger the highest timers first, until the rest explodes naturally.

Ahh, sorry I meant H, there are so many problems in contest nowadays, nice explanation, thanks :) I understand sqrt decomp. is applied. I got the idea of query of type 2, but not of type1, why we need inverse indices and that part.

Think about the permutation as a functional graph where each vertex points to another vertex. In order to answer type 2 queries efficiently, we need a "jump" array which gives the index we will be at if we step forward $$$Q$$$ times. When we perform a type 1 query on indices $$$x$$$ and $$$y$$$, most values do not need to be recomputed--the only indices are $$$x$$$ and the $$$Q-1$$$ ones that jumped over $$$x$$$, so $$$r_x$$$, $$$r_{r_x}$$$, etc., and similarly for $$$y$$$.

To recalculate these, start with $$$x$$$ and step forward $$$Q$$$ times to find $$$jump_x$$$. Then step backwards using the reverse permutation to calculate $$$jump_{r_x}$$$, $$$jump_{r_{r_x}}$$$, etc.

Thanks !!

140270271 Can you take a look at this submission of G, please? I would appreciate a lot.

In problem C's code it should be 18 instead of 19

if(x < y && y >= 10 && y <= 19) b.emplace_back(y — x);2 one digit numbers can never sum upto 19. It can be at worse 9+9.

No in the worst case both a and b contain 9,9. so 9 + 9 = 18

I saw some solutions for problem H that use link cut tree, could anyone help me to understand the idea behind these solutions?

My understanding is:

To simulate the above process, all you need is a data structure that represents cycles and supports quick split/merge (for type 1 queries) and find k-th element (for type 2 queries). One obvious choice is the splay tree. Given link-cut tree is mostly based on splay tree, I guess that would work as well.

couldn't get AC on E because of integer overflow. makes me wonder if there are any downsides to always using

`long long`

instead of`int`

, I couldn't see any time difference with $$$2.10^9$$$ operationsMaybe it will need more memory

yes, it will require double the memory. however, most questions have 256 MB of memory and I don't think I've ever used half of it.

Here are the times for $$$2.10^9$$$ operations

`int`

:`1107 ms, 1154 ms`

`long long`

:`1154 ms, 1123 ms`

In problem E editorial code why

`sort(a.begin(), a.end());`

? is it a mistake , or something i'm missing ?the sorting is not required. you don't even need to store all elements in a[], all you need is the frequency array (cnt[]).

Can someone explain this part from Problem G ?Calculating Min From ComponentsI guess you forgot to sort res vector, I also did the same mistake

If you are considering bombs till component i to be exploded by timeout, then remaining bombs need to be detonated manually. The count of remaining bombs is (res.size()-i-1). Since you can start detonating from time 0, total time taken to manually detonate remaining bombs is ((res.size()-i-1)-1) i.e. (res.size()-i-2). For a particular i, you would be taking max of time taken to manually detonate and time taken to explode by timeout. Because we can be sure that in that time, all bombs are gone. The minimum such time where all bombs are gone would be the answer.

Solution for problem D without the log factor:For every person, find $$$B_i$$$. $$$B_i$$$ means the best shop to choose while buying a gift for person $$$i$$$. From now on, I'll rephrase "buying a gift for a person $$$i$$$ from shop $$$s$$$" as "assigning person $$$i$$$ to shop $$$s$$$.

Case 1:Number of different "optimal" shops (i.e. number of distinct integers $$$B_i$$$ for $$$1 \leq i \leq n$$$) does not exceed $$$n - 1$$$. We can assign person $$$i$$$ to $$$B_i$$$ and calculate the answer directly.Case 2:Otherwise. Then there has to be at least one person $$$i$$$ such that it's not assigned to $$$B_i$$$. Let's call such a person "unhappy". Then I claim that there is no more than $$$2$$$ unhappy people in an optimal assignment. Proof is left as an exercise for the reader.What we can conclude from here is that in an optimal assignment, we'll choose exactly $$$2$$$ people and assign both of them to the same shop. Note that none or one of them can be assigned to their best shop. And every person $$$i$$$ in remaining $$$n - 2$$$ people are assigned to $$$B_i$$$.

Call the shop with $$$2$$$ people assigned as $$$s$$$, and friends to be assigned to $$$s$$$ as $$$x$$$ and $$$y$$$. Without loss of generality, assume that $$$p_{sx} \leq p_{sy}$$$. What is the answer for a fixed $$$x$$$, $$$y$$$, $$$s$$$? Turns out it's the minimum of $$$min_{1 \leq i \leq n, i \neq x, i \neq y}(p_{B_ii}), p_{sx}$$$ and $$$p_{sy}$$$.

Note that we can assume as if $$$y$$$ is also assigned to $$$B_y$$$ because we know that $$$p_{sy}$$$ can't minimize the answer while $$$p_{sx}$$$ is there. Therefore we don't have to iterate over $$$y$$$'s and only take the minimum of $$$min_{1 \leq i \leq n, i \neq x}(p_{B_ii})$$$ and $$$p_{sx}$$$. So let's iterate over different $$$x$$$ and $$$s$$$. But we have to find a way to ensure that there is at least one $$$y$$$ such that $$$p_{sx} \leq p_{sy}$$$ holds for a fixed $$$x$$$, $$$s$$$.

Here is a way to check it: We can store for every shop the value of its most valuable gift and its count. Call it $$$V_s$$$ and $$$C_s$$$ for shop $$$s$$$ respectively. If $$$p_{sx} < V_s$$$ or $$$p_{sx} = V_s$$$ and $$$C_s \geq 2$$$ then it is a valid $$$(x, s)$$$ pair.

Complexity is $$$\mathcal{O}(nm)$$$:

In case 1, checking is done in $$$\mathcal{O}(nm)$$$. In case 2, at every iteration of $$$x$$$, you first find $$$min_{1 \leq i \leq n, i \neq x}(p_{B_ii})$$$ in $$$\mathcal{O}(n)$$$ and iterate shop $$$s$$$ in $$$\mathcal{O}(m)$$$. Total runtime is $$$\mathcal{O}(n(n + m))$$$, which is bounded by $$$\mathcal{O}(nm)$$$ because $$$n \leq m$$$ must hold at case 2.

See example submission: 140114559. Note that I have swapped the dimensions of $$$p$$$ in the problem for implementation simplicity. I also have a vector $$$d$$$ to count the number of distinct shops for case 1.

Brilliant!

Can you help me rectify error in this comment, i have described a similar idea but i can't make sense of downvotes

I can't figure out what's wrong in my solution? It's failing on test 2. Can anyone please help? my code.

You should consider the situation that (num2<num1 && j<=0), here is the revised one based on your code.140230892

Thank you very much dude, I got my mistake.

At first, I think the permutation in problem H can be considered with a graph with n nodes and n edges (A Base loop tree)

Finally, I realize that it is just a graph with serval loops.

What a pity!

In problem B, replacing

`sqrt(n)`

with`sqrt(n+ 0.5L)`

give correct answer. Why is this happening? Thanks in advance.Hacked solution : https://codeforces.com/contest/1619/submission/140041728

Accepted solution : https://codeforces.com/contest/1619/submission/140180623

Because of representation of real numbers in binary. For example, pow(10^9, 1/3) = 999.9999... and not 1000 as it should be. By adding 0.5 you're avoiding this problem.

problem F is actually a joke

Can you please explain the joke part in it?

it's easier than D and E. look at this submission

Only after you realize it/read the editorial :)

D/E are like just do whatever said, F needs a lil bit of thinking

No buddy, he is right, problem F is comparable to C, just a little bit of implementation and knowledge of deque(I used it for putting last to front), D involved more than 5x thinking than F... I am more convinced on this fact also due to the line mentioned in the announcement also that problems may not be in their proper order... According to me, the order could be A B C F E D.

Whenever you see a problem like "maximize the minimum" most of the time it turns out to be a binary search problem. That's the reason I said D didn't require much thinking for me.

Why need to sort the input array of problem E? As we use the frequency array later, any need to sort the input array?

you are completely right, filling and sorting of

`vector a`

are not requiredPlease help me debugging my code for problem G. It is getting WA on test case 2 line 6. 140296294

I think I am committing some mistake in calculating

`ans`

at the very end of the code.I solve B using inclusion and exclusion principle. here's my submission:

140032787

I was worried about the case where I use both sqrt and cbrt but it passed all testcases!

After the contest I found that most of the contestants solved this problem using set or any other data structure. However, I find this solution much easier.

Brilliant idea!

for someone who can't understand this idea...

numbers of the form x^6 are counted twice so we subtract them once.

ans = A2 + A3 — A6

Problem C : I'm getting

`Memory limit exceeded on test 2`

. I can't rectify my code. Plz help. My SubmissionNo need to sort the array in problem E.

Problem E: If anybody is getting TLE then try

`multiset.upper_bound(num)`

rather than`upper_bound(multiset.begin(), multiset.end(), num)`

. ReasonWhat is the meaning of res.size()-i-2 in the G tutorial?

-if we want to find the remaining number of elements after index 'i' , to do so we need to make the difference between the size and the index we are at.

-Indexes are from 0 to res.size()-1 , so the actual difference would be res.size() — (i+1) = res.size()-i-1. (Or you can think it as res.size()- 1 — i too)

-So we found out that the numbers of remaining elements after index 'i' is res.size()-i-1

-Assume we have 'x' remaining elements . Since the seconds begin at 0 , the minimum number of seconds we need to erase the remaining 'x' elements is 'x-1'.

-So we found out that the minimum number of seconds we need to erase the remaining elements after current index 'i' is "the number of remaining elements"-1 = (res.size()-i-1)-1 = res.size()-i-2.

-------------------------------------------------------------------------------------------------

## Below is explanation of the approach if needed

Assume you are at index 'i' in the sorted array 'a' in which you stored the Minimum time u have to wait until 1 bomb from the 'i'th component will explode , erasing the whole component with it.

Since the array is sorted , you wonder : What is the minimum time for all the bombs to explode , if you wait until components 1->i explode (without exploding anything by myself) , and you erase all the remaining components in front of the one from index 'i' by yourself.

Assume it takes 30 seconds for the 'i'th component to explode (all the i-1 components will explode too since the array is sorted) , and u have 40 more components after that . U need to wait 30 seconds , but u needed at least 40 seconds to erase all the remaining ones , so u take the maximum from these 2 values. (If we had 20 more components after this , we needed 20 seconds to erase those by ourselves , so waiting 30 seconds for 'i'th one to explode will be enough , so again we had the maximum from those 2).

thank you, I understand.

Did anyone solve prolem H with treap?

Indeed, it's quite reminiscent of this problem from SecondThread's treap educational contest. Just need to figure out the right treap operations to do, and implement a few new ones.

Came up with treap solution as my first approach and became unable to think of the $$$O((N+Q)\sqrt{N})$$$ one :(

Can you guys leave submission link / code?

140540828

(apologies in advance for the rather rambly Rust code lol... Rust doesn't come with a RNG in its standard library, so there is also code for it)

Edit: I also recommend this tutorial video by SecondThread to learn about implementing treaps

Can anyone prove or help in proving the greedy approach for problem D? Thank you.

UPD: got it.

In the question named "Squares and Cubes".....just use unordered_set rather than ordered_set, it will reduce time complexity. :D

Could someone tell me what is wrong with my code?

C Problem/*package whatever //do not write package name here */

import java.io.*; import java.util.*;

public class GFG { public static Scanner scn=new Scanner(System.in); public static void main (String[] args) { int t=scn.nextInt(); while(t-->0) { long a=scn.nextLong(); long s=scn.nextLong();

}

I think I have an O(n + qlogn) solution for problem H:

A permutation is a composition of circles (i -> p[i] -> ... -> i). We can represent those circles with treaps, one for each circle, when the nodes are i, p[i], p[p[i]], ... from left to right. Note that we can use split and join to make any element the leftmost.

first-type queries can be answered — When we swap p[i], p[j] and i,j are in different circles, we merge two circles with O(1) split & join operations to receive: (i) -> (p[j] -> ... -> j) -> (p[i] -> ... i). When we swap P[i], p[j] and i,j are in the same circle, we split two circles with O(1) split & join operations to receive: (p[j] -> ... i), (p[i] -> ... -> p[j]).

Second-type queries can be answered easily — we will keep for each subtree it's size.

*We will keep an arrays of pointers, Arr[i] is a pointer for the node that represents i.

last problem is crazy!!!

I implemented E with a std map instead

145083862

Could anyone help me Problem E? Why my submission is Memory limit exceeded? submission