### Gheal's blog

By Gheal, 4 months ago, ## 1831A — Twin Permutations

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate Problem

## 1831B — Array Merging

Author: tibinyte

Hints
Solution
Code (tibinyte, C++)
Rate problem

## 1830A — Copil Copac Draws Trees

Author: alecs

Hints
Solution
Code (Gheal, C++)
Code (alecs, C++)
Rate problem

## 1830B — The BOSS Can Count Pairs

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate problem

## 1830C — Hyperregular Bracket Strings

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate problem

## 1830D — Mex Tree

Author: Gheal

Hints
Solution
Code (tibinyte, C++)
Rate problem

## 1830E — Bully Sort

Author: valeriu

Thanks to errorgorn for the solution!

Solution
Code (tibinyte, fenwick tree + ordered_set C++)
Code (tibinyte, sqrt decomposition, C++)
Code (errorgorn, divide and conquer, C++)
Rate problem

## 1830F — The Third Grace

Author: tibinyte

Thanks to errorgorn for the editorial!

Solution
Code (errorgorn, C++)
Code (valeriu, C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments. Tutorial of Codeforces Round 875 (Div. 1) Tutorial of Codeforces Round 875 (Div. 2) Comments (170)
 » 4 months ago, # | ← Rev. 2 →   "If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments." One thingIt's unclear how you publish these editorials so fast! :D
•  » » Can you explain how to do Div2 E (Hyperregular Bracket Strings). I can't understand the editorial. So, i understood the logic of splitting the overlapping intervals, then how did you proceed further? Also, if I have 3 intervals (1,20),(3,12),(4,9) -> (1,2),(3,12),(13,20),(4,9) -> (1,2),(3,3),(4,9),(10,12),(13,20) -> this should be impossible right? As (3,3) will never be a regular interval
•  » » » They don't mean to split intervals like that. Imma illustrate their idea. As an example, let's say $n=10, k=3, (l_1, r_1) = (1, 8), (l_2, r_2) = (3, 4), (l_3, r_3) = (7, 10)$. I'll use the letter $x$ to denote an empty space. Let's write a sequence of $n=10$ empty spaces: $xxxxxxxxxx$. If a position is covered by the $1^{st}$ interval, put $1$. If a position is covered by $1^{st}$ and $2^{nd}$ intervals, put $2$. If a position is covered by $3^{rd}$ interval, put $3$. If a position is covered by $1^{st}$ and $3^{rd}$ intervals, put $4$. So the sequence of empty spaces turn into this: $1122114433$. Now look at subsequences containing only $1$, $2$, $3$, $4$: $1111$, $22$, $33$, $44$. We count ways to make RBS on these four subsequences and then multiply them together: $2 \cdot 1 \cdot 1 \cdot 1 = 2$,which is the correct output.
•  » » » » Thanks. Got it. Can you explain the step after that too? Regarding hashing?
•  » » » » » The main idea is every time we input an interval, we modify a subarray (the array here is the sequence $xxxxxxxxxx$) according to the interval so that each position knows which intervals cover it. So like after inputting $l_1 = 1$ and $r_1 = 8$, we do something in the subarray $[1,8]$, so every positions from $1$ to $8$ knows they are covered by $(l_1, r_1)$. The editorial does this by assigning each interval a random number and XOR every element in the subarray $[l_i, r_i]$ by it, but some solutions I saw use addition instead of XOR.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   But why they don't have to fix hash conflict?There are 2^30000 subsets of intervals in total, hashed into a 64-bit integer. Won't that be lots of conflicts?I don't really understand.
 » i love this round
•  » » +1
 » I had almost solved Div-1C, I had the idea of overlapping and included intervals! but I couldn't find a way to implement it :(
•  » » same problem! kinda sad that I missed the chance to solve ABCd1
 » Can Div-1B be solved with smth like CHT or LiChao tree? We can reduce the problem to two operations: $add \_ line(k, b)$ — add line $kx + b$ to our structure. $count(x, y)$ — count number of lines s. t. $kx + b = y$ (or $\leq y$). Is there anything what can support these operations?
•  » » Tried thinking along that line too. But i don't think LiChao can do operation 2 due to overcounting?
 » Solved Div2 C in practice using BFS. Or is it also DP in disguise? https://codeforces.com/contest/1831/submission/207670475
•  » » Yes. It will consider two cases using BFS. It actually corresponds to two cases of dp.
 » Please add this to the contest material of Div 2 :) currently it can only be seen from Div1.
 » For some reason Div2 A prolem time limit is failed when using Java 17 with standart util.Scanner.Yes, I know util.Scanner is not fast, but I guess there should be enough time to read data by standart tools, if you have algorithm with needed complexity (O(N) in this task)https://codeforces.com/contest/1831/submission/207588412
•  » » Same for Golang and non-buffered output via fmt — failed on system test: https://codeforces.com/contest/1831/submission/207639426
 » Can someone try hacking https://codeforces.com/contest/1830/submission/207655131 , or explain why it’s good. It is solution for Div1C, and i am basically keeping a stack to calculate answer. But when two intervals partially intersect, i delete the latter , but add back a needed interval to my set of intervals.
•  » » 4 months ago, # ^ | ← Rev. 2 →   Deleted
•  » » » i dont think i understand how it explains the complexity.
 » Div1B is terrible. The goal of a problem should be figuring out the solution, and not trying to squeeze your code to pass after you know the solution.
•  » » The model solution runs in under 1.2s, which I think is fairly reasonable for a problem with a 4s TL.
•  » » » It's not about the complexity of your solution. It's about the people who had the same idea as the editorial but failed to solve it because they used for instance hashmap against map, or some tiny constant.
•  » » » » Dear contestant,Please don't worry if you had to make some formulas shorter in order to pass a time limit that was set as a triple of our solution's running time. In a programming competition, the way you express your ideas in code actually matters. Apologies if this does not fit your view.Thanks for the feedback.
•  » » » Why does the model solution use 500MB of memory out of the allowed 512MB?
•  » » » » +1. I resubmitted (with 2 extra WAs which were my fault) because I was afraid 518k KB would MLE systests. I don't think it's a bad problem but I feel allowing 1024MB would've been ok here. Especially since the model solution uses a similar amount of memory.
•  » » » » We also have solution with linear memory, but it's not posted there.
•  » » » » » pls share.
•  » » » » » » Code/** _ _ __ _ _ _ _ _ _ |a ||t ||o d | |o | | __ _| | _ | __| _ | | __ |/_ | __ /__\ / _\| **/ #include using namespace std; typedef long long ll; const int N_MAX = 400000; int n; int a[N_MAX + 2]; int b[N_MAX + 2]; vector occ[N_MAX + 2]; int mp[N_MAX + 2]; int main () { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; occ[a[i]].push_back(i); } for (int i = 1; i <= n; i++) { cin >> b[i]; } ll answer = 0; for (int x = 1; x * x <= n * 2; x++) { if (occ[x].empty() == false) { for (int i : occ[x]) { mp[b[i]]++; } for (int y = x; x * y <= n * 2; y++) { if (occ[y].empty() == false) { int s = x * y; ll cnt = 0; for (int i : occ[y]) { if (1 <= s - b[i] && s - b[i] <= n) { cnt += mp[s - b[i]] - (x == y && b[i] * 2 == s); } } if (x == y) { cnt /= 2; } answer += cnt; } } for (int i : occ[x]) { mp[b[i]]--; } } } cout << answer << "\n"; for (int x = 1; x <= n * 2; x++) { occ[x].clear(); } } return 0; } 
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   Yeah, but why didn't you think that it is a good idea to set ML to 1024MB if one of the authors solutions uses $n \sqrt{n}$ memory?
•  » » » » » » Authors test 1000s (a bit of exaggerated) solns, its not necessary to allow all of them to pass.
•  » » » Can someone explain time complexity of 207670551?I do not understand why its fast enough (run in <350 ms), worst case I can think of will take $O(n*sqrt(n))$.
•  » » 4 months ago, # ^ | ← Rev. 2 →   .
•  » » i felt the same
 » div1B killed
•  » » 4 months ago, # ^ | ← Rev. 2 →   for me, honestly, finding solution for div1B was much easier than understanding problem statement for problem Div1A/Div2C.I spent more than 30 minutes to understand problem statement and test case '1' in problem C. I solved problem Div1B,Div2D within 28 minutes. xD
•  » » » this is not hard to find solution, but it is hard to code it
 » 4 months ago, # | ← Rev. 9 →   Since there is lot of discussion going on about problem D with tight timelimit, I personally feel that time limit was sufficient to pass O(N * log N) + O ( N * sqrt(N) * log N ) , which is more than sufficient. Solution with Simple map and binary searchI would also like to share my approach, please go ahead and share your thoughts. you need to use the fact that the values of a[i] and b[i] are less than or equal to "N". So, for each pair (a[i],b[i]), we have to traverse till sqrt(N) at max, and see if the reverse pair exists or not. first of all, shard the pairs(a[i],b[i]) based on the first value (a[i]). Also sort each shard for applying faster search operation using binary_search. We also need to keep track that how many times particular pair has been encountered in past, to do so we need a map < pair , int > where map[(x,y)] denotes, how many times particular pair (x,y) has been encountered yet. for(int i = 0 ; i < n ; i++) { shard[a[i]].push_back(b[i]) } for(int i = 1 ; i <= n ; i++) { // sort each shards sort(shard[i].begin(),shard[i].end()) } // suppose shard pairs are (1,2),(1,3),(2,3),(2,1),(4,8),(4,12),(4,4) // shard = { 2 , 3 } // shard = { 1 , 3 } // shard = { empty , because no pair has a[i] == 3 } // shard  = { 4 , 8 , 12 } // Hope part 1 is clear... Core logic part is here now, suppose (a[i] , b[i]) and (a[j] , b[j]) are expected pair, then we will a[i] * a[j] - b[i] = b[j] , for better understanding I will use (x,y) and (p,q) instead of (a[i],b[i]) and (a[j],b[j]) from now on. so, (x*p — y == q) must hold in order to count the pairs.if shard[x] has value 'y' in it, that means, we have a pair (x , y) somewhere. Now, any pair (x , y) and (p, q) to be in the answer, we must make sure that x * p <= 2*n, otherwise answer is never possible ( because of the restriction that 1 <= y <= n && 1 <= q <= n,,, their sum will be 2 <= y + q <= 2*n. ) , that's why x * p must be less than 2 * n ;So, now using above facts, please go through code, code for understanding with commentsfor(int i = 1 ; i <= n ; i++) { for(int j = 0 ; j < shard[i].size(); j++) { int x = i; int y = shard[i][j]; // now assume that p is 1,2,3... until p * x <= 2 * n; for(int p = 1 ; p <= i ; p++) { if( x * p > 2 * n ) break; // here answer is never possible, // Now, try to find in shard[k], whether the value x*p - y is available or not // to do so, we can use binary_search, or set, or lower_bound() or anything auto it = lower_bound(shard[k].begin(),shard[k].end(),x*p-y); if(it != shard[k].end() && *it == x*p-y) { // Condition to see if the x*p-y is present or not // if the current value is present, then we have to add it number of times it has been encountered till now, ans += map[(x,y)] } } // once we have processed a pair (x,y), // we also have to add it to our map of encountered pairs map[(x,y)]++; } } // finally return ans, dont forget to initialise it with 0 by the time declaring it. :) . } 
•  » » 4 months ago, # ^ | ← Rev. 4 →   I think that TL was enough but the great problem was in the ML. By the way you're code is very clean. got AC with this time complexity!! Take a look at my code which should have $O(n\sqrt n)$ with time complexity of 1123ms 207646321
•  » » But how are you maintaining the condition 1<=i
•  » » » understood!!
•  » » Where did shard[k] come from? Shouldn't it be shard[p]?Thank you for your explanation you are a legend.
 » https://codeforces.com/contest/1830/submission/207653094The code is giving runtime error with GNU G++ 17.No runtime error with GNU G++20.Why is it happening ??
•  » » Yes the same happened to me...
 » 4 months ago, # | ← Rev. 2 →   thanks for the contest, solving D1D was very fun
 » 4 months ago, # | ← Rev. 2 →   Yesterday's abc_E tilted me towards a leaves-first idea for div2C, counting up the number of out-of-order edges on the way to the root. It's an approach that can work, but I seemingly stumbled into every possible way to make it break, even after getting a fake AC.TLE: long path from root into many leaves risks repeatedly traversing that pathWA: attempts to bail early on lack of update worked, but (hindsight) since I was updating and testing on different vertices, I had to leave in the == no-update case... which meant it was still very possible to TLE as beforeuphackTLE: in attempting to test vs. that worst case, I neglected to clear out all shuffling/randomizing code in my generator, so the 'far' root 1 was always randomly somewhere convenient and/or the number of passes really did need updatingtechnical-debt-TLE: (hindsight again) a bug-free version of my per-leaf approach was still vulnerable because there could be a tree that actually did have progressively better passcounts per traversal obviating my early-out flailing. What I really needed was the post/return half of a dfs/bfs, only proceeding rootward after all children were accounted for... OR not getting the leaf-first idea stuck in my head from yesterday.tl;dr free uphack and maybe some giggles...
 » The idea of Div1B was fine, but the tests were so weak. Even the system tests cannot save it as most solutions got TLE on tests provided by hackers, and I don't even think that my solution is good enough to get AC :D
 » Good round, I like it.
 » The Memory limit Div1 B was soo tight, but it was fun to solve tho
 » 4 months ago, # | ← Rev. 4 →   This was my first Div. 1 contest. I solved A, but not very fast because I wanted to get accepted with one submission. Then I started to think about problem B. In about 1 hour and 20 minutes I got accepted (I was happy to increase my rating on my first Div. 1 contest). But, unfortunately, I got FST (TLE on test 15) during the system testing. And I want to share with you my solution and a bug, which was tricky to find.The main idea of my solution is similar to many of the other solutions.I keep the answer in $ans$. First, I define an array of vectors $c$, where I store all $b_i$-s for every element in $a$ (i. e. for every pair of $(a[i], b[i])$, I push $b[i]$ to $c[a[i]]$) and then I sort every $c[i]$.Then I brute force every $i$ and $j$, such that $i*j <= 2*n$ and $i •  » » I did exactly what you did, but I can't prove the time complexity. Could you please explain it clearer how choosing the smaller between c[i] and c[j] results in that time complexity? •  » » » I apologize that I can't prove it formally, but intuitively, if there is one with many elements, there has to be another with few elements. Also, it is obviously better to brute force through the one with fewer elements.  » Div2 D has an O(nlog^2n) solution. Let cnt(x, y) be the number of indexes i such that a[i] = x and b[i] = y. b[i] + b[j] = a[i] * a[j] <= 2 * n, so for fixed i there are 2 * n / a[i] possible values of a[j]. Thus, iterating over all possible pairs of values (a[i], a[j]) takes O(nlogn) operations (2n/1 + 2n/2 + ... + 2n/n = 2n * (1 + 1/2 + 1/3 + ... + 1/n) = 2n * logn). For given pair (x, y) we can iterate over all i such that a[i] = x (totally O(n) time) and add to the answer cnt(y, x * y - b[i]). cnt(x, y) can be calculated for O(logn) using binary search. •  » » 4 months ago, # ^ | ← Rev. 2 → I don't think that would work. For example, when iterating$a[i] = 1$, based on my understanding, you find all$i$such that$a[i] = 1$, then also iterate over all$y = 1, 2, ...2n$, and then add$cnt(y, 1 * y - b[i])$to the answer. But this step is actually$O(n^2)$, because there could be$O(n)$indices$i$such that$a[i] = 1$. •  » » » 3 months ago, # ^ | ← Rev. 2 → But what if I apply a little optimization?For a$(a_i, a_j)$calculation, we get two (multi)sets$S = \{ b_k | a_k = a_i \}$and$T = \{ b_k | a_k = a_j \}$.Then if$|S| > |T|$, swap them, and iterate$S$.It finally get passed(211334263), but I can't figure out it time complexity, or whether it's a truly correct approach. Could anyone tell me this?  » https://codeforces.com/contest/1831/submission/207670314Could someone point out mistake in my code been trying for very long ,dont see the mistake getting WA in test 2 ,i did a bfs like soln •  » » did you try cleaning the global variables after solve()? Probably it's bugged when you have more testcases •  » » » i did that at the end of the code after cout •  » » » » 4 months ago, # ^ | ← Rev. 2 → Sorry, i didn't see that.Took a while but i found an actual counterexample: ans is 2, your code says 3152 31 24 52 4 You do some weird stuff with ok. You're looking for the minimum index edge, but i think you should set it while you do the bfs: something like  ok[c.first] = c.second; if(c.second > ok[x]) dis[c.first] = dis[x]; else dis[c.first] = dis[x]+1;  •  » » » » » oh ok i see the mistake thanks a lot  » Problem Div 2D has a good idea IMO. But my solution of$n \sqrt{n}$was not passed the time limit because I used unordered_map to count the frequency (207642815)I have used the unordered_map optimization using custom_hash function referring to this blog. Which got me to think : Did my solution wrong? I used set to maintain unique elements only. The difference with author solution is I didn't skip when$a_i > \sqrt{n}$. But I did the break the loop tho If assuming my implementation indeed is$n \sqrt{n}$What kind of test case that breaks the unordered_map constant factor? •  » » Your solution is$O(n^2)$,here is a sample. If$a \dots a[\frac n 2]$are$1$,the other$\frac n 2$of$a[i]$are large and different from each other,when you find the answer of$a \dots a[\frac n 2]$,all of the elements will be found,then your solution become$O(n^2)$•  » » » Ah I guess that makes sense. Didn't cover that kind of test case. Thanks! •  » » 4 months ago, # ^ | ← Rev. 2 → yeah i too tried many$n\sqrt{n}log(n)$and then tried with hashing (not custom), and I'm of the opinion that either im a really poor implementor or the limits are too strict •  » » » Asking to remove the log factor of the map is somewhat strict imo. You had to use an array instead of a map to erase the log in the complexity. Usually if i can use a map to make it faster to implement i do it and for this reason i got a lot of TLEs before realizing that O(1) access gives ~1/4 time of map •  » » » » if they didnt force to remove log, the problem would definitely be solvable by n^2 (already was) i think they should have just forced linear memory, so it becomes clear this solution is out instead of being on edge •  » » » » » Fair enough. Effectively n² is close enough to n^(3/2)log n. Actually plugging n it's ~1.5e9, which is obviously too big •  » » » » » » I have solved it with O ( N * log N) + O ( N * sqrt(N) * log N) . I have used O(log N) complexity for searching element in sorted array with binary search. and my solution passes easily. I dont understand why you guys couldn't pass the solution ? Can you please share your solution which is getting TLE ? •  » » » » » » » 4 months ago, # ^ | ← Rev. 2 → I was using a vector s (s[a][b] = count of the pair a-b for a •  » » » » » » » 207656497, if you wish  » Is it any problem in 1C's editorial?if$l_1\leq l1_2\leq r_1\leq r_2$,the groups formed by two intervals are$[l_1,l_2-1],[l_2,r_1],[r_1+1,r_2]$?But it doesn't matter :D  » Want to point out that, for Div1 C, to derive the number of regular bracket strings of length 2n, this is essentially equivalent to having a simple random walk that start at 0 and end at 0 while never touching -1. The reflection principle is commonly used to calculate it.  » 4 months ago, # | ← Rev. 2 → Can 1B exist any polylog solution?I guess the answer will no more than$O(n\log n)$or$O(n)$if all pairs of$a,b$are distinct,but I have no idea how to find them in no more than$O(n\log^2n)$:(  » 4 months ago, # | ← Rev. 2 → How to solve problem B?  » I'm wondering why I got TLE for div2 C. I pretty much did the same thing as the editorial. I have an array to store the index of each edge, and then I did BFS. At each node, I compare the index of the edge that connects that node and the parent with the index of the edge that connects the parent and the parent of the parent. code#include #define dumb long #define ff first #define ss second using namespace std; const long long ninf = -1e15; const int MOD = 1000000007; int comefrom; pair ap; pair dataa; int idx; //based on receive int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); //freopen("rental.in", "r", stdin); //freopen("rental.out", "w", stdout); int t; cin >> t; while(t--){ int n; int ans = 1; cin >> n; vector> g(200003); for(int i = 0; i < n-1; i++){ int a,b; cin >> a >> b; //idx[make_pair(min(a,b),max(a,b))] = i; dataa[i].ff = a; dataa[i].ss = b; g[a].push_back(b); g[b].push_back(a); if(min(a,b)==1){ ap[max(a,b)].ff = 1; ap[max(a,b)].ss = i; } } vector vis(200003); int node = 1; ap.ff = 1; ap.ss = -1; queue pq; while(vis[node]==0){ vis[node] = 1; for(int i : g[node]){ if(!vis[i]){ pq.push(i); comefrom[i] = node; } } if(pq.empty()) break; node = pq.front(); pq.pop(); } for(int i = 0; i < n-1; i++){ if(comefrom[dataa[i].ff]==dataa[i].ss){ idx[dataa[i].ff] = i; //cout << dataa[i].ff << ' ' << dataa[i].ss << ' ' << comefrom[dataa[i].ff] << endl; } else if(comefrom[dataa[i].ss]==dataa[i].ff){ idx[dataa[i].ss] = i; } } for(int i = 0; i <= n+1; i++) vis[i] = 0; node = 1; ap.ff = 1; ap.ss = -1; while(!pq.empty()) pq.pop(); while(vis[node]==0){ vis[node] = 1; for(int i : g[node]){ if(!vis[i]){ pq.push(i); comefrom[i] = node; } } if(node!=1){ int thisindex = idx[node]; //idx[make_pair(min(node,comefrom[node]),max(node,comefrom[node]))] if(thisindex •  » » nvm I figured out why, apparently I was creating vectors of size 2e5 for every testcase, so for some reason creating a vector of size n is O(n)?? •  » » » "the sum of n over all testcases is 2e5" But if you have 10,000 testcases and make an array 2e5 long you have that the total complexity is 2e5 *1e4 = 2e9, which is a big overhead considering that to have t=1e4 you have average n = 20 •  » » » » 207786285Is this the reason why my solution gets a TLE too ? (I have tried to maintain an ans value (current.first in the submission) along with the edge-number for each node. And update the ans everytime a node is fully "explored"). •  » » » » » It's possible. Just try and change resize(N) to resize(n+1) and see if it works •  » » » » » » 4 months ago, # ^ | ← Rev. 2 → Holy shit, that worked. Thankyou so much. I would have wasted the entire week trying to find out why if it wasn't for your comment.The TLE was happening because effectively the complexity was more like O(n*t) where t is the number of tests in one big-test-case ? Or is it that making such a long array for each test case is just inherently very "slow" to do ? •  » » » » » » » Your complexity is O(maxn*t) and if t = maxt you have the worst case. Btw you can check in the docs the complexity of resize (it's linear in the difference to the current size)  » F can be solved with lazy propagation on kinetic segment tree: code  » Really liked div 1, C and D. Also, I think there is a simpler way to implement div 1 C using segment tree instead of xor hashing, for the union part of solution. Was close but could not solve it in contest though :(  » my rating stayed as is, haha what were the odds!  » Would someone be able to check why my solution to Div 2 D TLEs on case 8?It's basically the same as the official solution and runs in O(n*sqrt(n)), so I'm unsure why it TLEs.  » Can somebody debug my problem B code where i'm doing mistake: Approach: I stored the max frequency of each number of a and b in mpa and mpb. After that i calculated the ans as the sum of frequency from a and b. code#include using namespace std; const int N = 1e5+10; void solve(){ int n; cin>>n; vectora(n),b(n); for(int i=0;i>a[i]; } for(int j=0;j>b[j]; } stacksta, stb; mapmpa, mpb; sta.push(a); mpa[a] = 1; int cnt=1; for(int i=1;i>t; while(t--){ solve(); } }  •  » » You gotta keep the counts of the longest subarray of similar integers, for every integer in a and b find out the maximum length of of all equal elements, do this for both array and in the end just store the sum of length of contiguous equal subarrays for all integers in both arrays. Why are you using stacks? •  » » » i used stack to count the max frequency of each number present in a array, btw i figured out the issue with minor changes my code got accepted. If you want to have a look code#include using namespace std; const int N = 1e5+10; void solve(){ int n; cin>>n; vectora(n),b(n); stacksta, stb; mapmpa, mpb; for(int i=0;i>a[i]; mpa[a[i]]=1; } for(int j=0;j>b[j]; mpb[b[j]]=1; } sta.push(a); int cnt=1; for(int i=1;i>t; while(t--){ solve(); } }  •  » » » » stacks + maps pretty heavy, I guess the runtime will stay around 500ms anyways  » Only if I proved my solutions :(  » What is the time complextity of my solution: 207651808?First, I iterated through the values of a[i], this part is$O(n)$Then, I iterated through the values of a[i] * a[j], until now it's$O(n log n)$After that, I iterate through the indices i that have value a[i] and used binary search (this add another log) to count number of satisfied indices j. Here, I optimized it by iterate through indices j instead if there is fewer of them.Somehow this passed systest, (actually during the systest I saw it TLE on pretest 3, but AC when I checked again this morning).  » Div 2 problem B.Array merging... Editorial looking so complex Here is my approach 1-->Intially after reading the arrays take the contigues frequencies of all elements and update if it is greter than the previous freq of that element make this for both the arrays after making that just iterate from 1 to 2*n and take the max of res and fre[i] would give you the solutionand here is my submission have a look https://codeforces.com/contest/1831/submission/207716898  » Div2 D is the most interesting problem for me. •  » » I am having difficulties understanding the editorial, can you help me out a bit?? thanks! •  » » » Well, the basic idea is lim = sqrt(2 * n) and fr[a[i][b[i]] (a[i] <= lim). For each i, instead of running all over the array (which takes O(n)), you can just use the formula fr[j][ai⋅j−bi] where j runs from 1 to lim denotes for a[j], a[i].j — b[i] denotes for b[j] while you have known a[i] and b[i] which takes O(lim), enough to pass the tests! •  » » » » yess, that makes sense. I understood the equation which you gave. But I am still confused with the equation given in the editorial for ai=aj and and ai>aj. Can you explain how those two equations work.. •  » » » » » the equation of a[i] > a[j] is as I've explanied above. But I don't truly understand the equation a[i] = a[j] though. •  » » » » » » Okay Thank you! •  » » » » » » assuming you understood the fr[a[i]][a[i]^2 — b[i]] part of the equation, notice that we overcount such cases in the expression: let's say we got a[i] = 2 and b[i] = 2 for some i, then a[i] * a[i] = b[i] + b[i], so the pair (i, i) is counted as good, but since the problem only asks for good pairs where i < j, we need to subtract all such cases, and what do these cases look like? since we have a[i] * a[i] = b[i] + b[i] iff a[i]^2 = 2 * b[i] iff a[i]^2 / 2 = b[i], so we need to subtract fr[x][x^2 / 2] for all 1 <= x <= lim, and that's where the numerator of the equation comes from. now the reason we divide the numerator by 2 is because we're counting all good pairs twice since if (i, j) is a good pair then (j, i) is also a good pair, and we need to count only one of these. •  » » » » » » » thanks!  » In A we can also make vector of pair consisting of values with the value and its index. Then sort it. Then the sequence is sorted along with its index. Now, we know that in order to maintain the condition we can put the largest number in permutation i.e. n with the smallest element in the permutation that is 1. This can be done by doing iterating the above sorted array and putting ans[pair.second]= n-pair.second+1. Thank you  » Can someone help me with Div2 D, please? Thanks!  » 4 months ago, # | ← Rev. 2 → Can anyone explain how the formula is arrived in DIV2 D for the cases ai=aj and ai>aj ?  » Can anyone explain what's wrong with my submission for Div2B? https://codeforces.com/contest/1831/submission/207612809 •  » » while checking maxi keep an iterator from 1 to 2*n and for every i in the m1 and m2 update the maxi  » Can we download the full testcases ? I want to debug my code. Can anyone help with this, here is my solution link https://codeforces.com/contest/1831/submission/207738412  » 4 months ago, # | ← Rev. 2 → I saw Div2B if..else in for and to add else block after for loop pattern, million times yet I couldn't solve it Goal for 2025: Newbie after solving 1000 problems  » In div-2, problem C was amazing.  » I was so sad that i could not solve b in contest time . but i just realized that the range of array a and array b is <= 2*n . •  » » same happened with me •  » » that fact of a[i] , b[i] <= 2 * n doesnt matter? you can just coordinate compress it to that range anyways •  » » » Yea but I am dumb.  » In div2 D why this soln gives TLE-> Let's traverse on unique pairs of a(i),b(i) and for each a(i) we will traverse for all distinct values of a(j) and find the value of b(j) corresponding to the known a(i), b(i) and fixed value of a(j) and thus can then easily calculate the number of pairs formed using an unordered_map with custom hash in avg o(1) complexity..Now for fixing the value of a(j) lets see two cases for a(i)-> 1. a(i) >sqrt(2*n)->in this case since a[i]*a[j] should be less than on equal to 2*n (as shown in editorial), hence possible values of a[j] would be from [1, sqrt(2*n)]. hence for each a[i]> sqrt(2*n) we can traverse all possible values of a[j] in sqrt(n) complexity a(i)<= sqrt(2*n)-> in this case value of a[j] can be from [1, n] but since all the pairs of a[i] with a[j]>sqrt(2*n) is already covered in case 1 hence we need to iterate only on the values in range [1,sqrt(2*n)]. hence overall complexity is o(n*sqrt(2*n))please help Gheal  » Am i the only onr who solved div2 C using lazy segmenttree with O(nlog(n)) ??  » Could someone explain how's the first summation came out in Div2D/Div1B? Thanks!:)  » 4 months ago, # | ← Rev. 2 → In Div1D, the maximum size of a connected component is$O(\sqrt n)$. But what's the exact upper bound of it? Theoretically, it's$\sqrt{3n}\approx 774$, but my submission, where I suppose it doesn't exceed 400, got accepted. Can anyone prove it or hack it? •  » » We have proof that it's 258.  » 4 months ago, # | ← Rev. 3 → I have been wondering for the past two days how the hell did my submission passed the tests in div.2 C and didn't get TLE: https://codeforces.com/contest/1831/submission/207638978In a test like this: 12000001 21 31 41 51 61 7.........1 1999991 200000The only thing I realized is that this corner test case isn't in the test cases or there are some hidden info in the constrains I didn't notice. But I don't think so. •  » » That case was just missing. Your solution is now hacked. •  » » » Thank you! •  » » » » 4 months ago, # ^ | ← Rev. 2 → BTW how do I uphack a submission after the round is finished? •  » » » » » A "hack" button appears on the submission page, but only if you're 1900+ rated (or 2100+, I can't remember which)  » I think that I have trouble understanding the first code of 1F.The tutorial says that we should subtract the contribution of some lines, but in the code, the only update is adding new contribution.Maybe I have made some stupid mistakes. Can anyone please explain it? QaQ •  » » You can check my code 207890019 •  » » » That helps a lot. Thank you!  » nice contest  » I'm new to hashing. In Div1 C, is there a chance of a wrong answer when using randomly generated numbers? And can we choose some numbers on our own to avoid that situation?  » Do you know solution for Hyperregular Bracket Strings without random? •  » » https://codeforces.com/contest/1830/submission/207644804Maybe you can check this submission. •  » » You can find all minimum ranges by scanning line and heuristic merge(?not sure about this name), and the rest can be solved as a bracket sequence. One implementation is 207718096. However, I think this is just a coincidence that there exists a non-random solution. I still recommend you learn the randomized solution, it's very general.  » https://codeforces.com/contest/1831/submission/207616298 Can anyone help me with the runtime error in my submission. I am not able to figure out the what is the reason for this.  » In the solution of Div1/C, for the case 2 (partially overlapping intervals), won't the groups formed should be [l1,l2-1],[l2,r1] and [r1+1,r2] instead of [l1,l2-1],[l2,r2] and [r2+1,r1]. Gheal •  » » Thanks, fixed. :thumbsup:  » In div1 C, I spent most of my time during the contest trying to use sweep line to construct a tree with hierarchy of intervals. I have read the hints in the tutorial, it's mentioned that it is difficult to construct that tree. Gheal, do you know an algorithm that constructs that tree? or if anyone could provide useful resources. •  » » Sorry for the late reply. If I'm not mistaken, Vladithur had a deterministic solution while testing, I've reuploaded it here.  » For the solution code of Div 2E/1C, if I change LLONG_MAX to LONG_MAX in uniform_int_distribution rnd(0,LLONG_MAX), I get WA on test case 4, which is a big-number test case where n = 300000 and k = 300000 (207948273) (I submitted multiple times and it's always WA on test case 4). When I print the hash values, they all seem to be as random and large as the solution code.Can anyone explain why this happens? Thanks in advance. •  » » oh nvm, it's due to compiler differences.  » problem cvector> edg[NMAX]; ... edg[u].push_back({v,i}); edg[v].push_back({u,i});how does this work? why we create a new pair in the vector element?  » There is an alternative solution for Div.2 C, where you essentially simulate the process. You keep a std::set of all the edges you can draw and a pointer of where you currently are in the edge list. Using the lower_bound function we can find the next edge we will encounter and when we do, we update the set of edges we can draw and update the pointer to the index of the currently processed edge + 1. In the case when the largest element in the set is smaller than the pointer we set the pointer to 0 and add 1 to the answer. We will process each edge exactly once so the complexity is O(n*log(n)). You can see my submission here: https://codeforces.com/contest/1831/submission/207936976  » For div 2 c question I think the statement of each edge is not accurate, I ran the code I think it is checked the edge below this edge[problem:1831C]  » 4 months ago, # | ← Rev. 3 → May someone explain me why the computation of the dp in Div1 D is$O(n\sqrt n)$? it's hard to prove for me, even that I know how to prove that the time complexity of the "7-th trick" is$O(n^2)$. •  » » In the "7-th trick" the time complexity is$\sum siz(v) \cdot siz(u) \le n^2$over all dp merges. In our case, we have time complexity$\sum \sqrt{siz(v)} \cdot \sqrt{siz(u)}$so we have the sum of square roots of these values. Let's define$\sqrt{siz(v) \cdot siz(u)}$as just a value$a_i$. We know$\sum_{i=1}^n a_i^2 \le n^2$(there are actually$n-1$summands but it doesn't matter). Dividing both sides by$n$and taking a square root we get$\sqrt{\frac{\sum_{i=1}^n a_i^2}{n}} \le \sqrt{n}$. But on the left-hand side we have the quadratic mean which is at least the arithmetic mean by the means inequality. So$\frac{\sum_{i=1}^n a_i}{n} \le \sqrt{\frac{\sum_{i=1}^n a_i^2}{n}} \le \sqrt{n}$.$\sum_{i=1}^n a_i \le n \sqrt{n}$follows which is exactly what we wanted. •  » » » Thanks for your generous help! That helps a lot for me. The prove is definitely right and I know exactly how to realize it by code. However, the time complexity of the standard method is$\sum_{i=1}^n min(siz[v],lim)\times min(siz[u],lim)$, which$lim = \sqrt{3n}$. If possible, I hope you can provide relevant proof. Thank you very much! •  » » » » 4 months ago, # ^ | ← Rev. 2 → Oh, wait, is it? I think in trick 7 it is just the product of sizes. But even if it's not, it is easy to see that just the sum of products of sizes is$O(n^2)$because you can think about the product of sizes as uniting two sets and listing all pairs of elements where one element is from the first set and the other elements is from the second set. In this way, every pair of elements in total will be listed at most once (exactly at their LCA), so the total sum is at most$n \cdot (n-1) / 2$.And well, taking min with$lim$can only decrease the sum but it is actually irrelevant. •  » » » » » 4 months ago, # ^ | ← Rev. 2 → Is it irrelevant? I believe that if you merge in$min(sz_u,lim) \cdot min(sz_v,lim)$the time complexity becomes$O(n \cdot lim)$. I don't know how to prove it tho but perhaps it's something similar to the$lim = \sqrt{n}$case. •  » » » » » » We merge in time$\sqrt{sz_u} \cdot \sqrt{sz_v}$. •  » » » » Ok. Now I understand your question. I guess the solution in the editorial is a bit different from what I read there. Without loss of generality, we can assume that our tree is binary because we kinda assume it anyway: we merge all the children of a vertex one by one which is equivalent to having a bamboo in which we add them one by one to the tree. If you take$\sum \min(sz_v,lim) \cdot \min(sz_u, lim)$, then you can consider$v_1, v_2, \ldots, v_k$to be all the vertices$u$in the graph such that all children of$u$have$sz_u \le lim$but for the parent$pr_u$of$u$it is not true (so$pr_u$has some child (either$u$or not) that is large). Then$v_i$can't be an ancestor of any$v_j$(otherwise its parent would have a big child and then$v_i$would also). It means that all subtrees of$v_i$s are disjoint so$\sum sz_{v_i} \le n$. Inside every subtree of$v_i$by trick 7 we work in time$sz_{v_i}^2$. But both children of$v_i$have sizes$\le lim$, so$sz_{v_i} \le 2 lim+1$. Then Inside all these subtrees we work in time$\sum_{i=1}^k sz_{v_i}^2 \le \sum_{i=1}^k (sz_{v_i} \cdot (2 lim+1)) = (2 lim+1) \sum_{i=1}^k sz_{v_i} = O(lim \cdot n) = O(n \sqrt{n})$. We are left with all the bigger subtrees that do not lie inside$v_i$subtrees (call all these vertices$u_i$s). There are two types of vertices$u_i$: they either have at least one of their child as one of the$v_l$s or they have both of their children as$u_j$and$u_k$. In the first case, we work in time$\le v_l \cdot lim$which sums up to$\sum v_l \cdot lim \le lim \cdot \sum v_l \le lim \cdot n = O(n \sqrt{n})$. In the second case, we work in time$lim^2$per vertex but there are at most$O(n / lim)$such vertices so we work in time$O(n \cdot lim) = O(n \sqrt{n})$in total for them too. •  » » » » » That is right! Amazing! Thanks you!!! :) •  » » Take a look at this comment, it explains the exact dp formulation used in solution. Complexity is$O(nk)$where$k=\sqrt n $. Proof is based on iterating over all pairs such that their preorder differs by at most$2k$.You can imagine it when you merge two subtrees, in the left subtree you "keep" only last$k$nodes and in right subtree you "keep" first$k$nodes, so their preorder number differs by at most$2k$, if subtree contains less than$k$nodes just iterate through them. Because of that you go through$min(sz[u],lim)$.For each$i$we have at most$2k$pairs of the form$(j,i)$such that$j
•  » » » Thank you! The method you mention to prove this task inspired me a lot! :)
 » I think the editorial of D D2/C D1 was wrong in case 2, when l 1 < l 2 ≤ r 1 < r 2 The three groups formed by these two intervals are: [l1, l2 — 1] [l_2,r_1] [r1 + 1, r2]
 » can some one tell me why the editorial guy is subracting fr[i][i/2] from the case when a[i]=a[j]
 » Hi Gheal & Vladithur, Python solution in the editorial for problem Div2D (1830B — The BOSS Can Count Pairs) throws TLE. Can you please fix it? https://codeforces.com/contest/1831/submission/208150150
•  » » Never use puthon 3, use pypy3 64 instead. It is 5 times faster
•  » » » Same result with PyPy 3-64: https://codeforces.com/contest/1831/submission/208270626
 » fr[i[[i.i/2]? how is this well defined?
 » Can anyone help me with Div2B? I can't pass test 2.Code is here
•  » » Take a look at Ticket 16863 from CF Stress for a counter example.
•  » » » Thanks a lot!
 » Still cannot understand the description for 1830F. If there is just one activated point covered by two intervals, the cost of each interval should be the coefficient of that point.For the first example, however, the last point (30) appears in two intervals ([2, 8] and [3, 8]), but 30 is only added once to the result. Also, for the second example, why don't we activate the last point? It is covered by [1,6] interval.
•  » » 2 8 in the first test case and 1 6 in the second test case aren't intervals; they're n m, i.e. the number of intervals and number of coordinate points for the test case.
•  » » » Oh thanks... I am spoiled by LeetCode and didn't do much of input parsing before...
 » 4 months ago, # | ← Rev. 2 →   Solution of 1830A, without using DP and using a visited array (space complexity remains same). This question -> https://codeforces.com/contest/1830/problem/A
 » Can someone explain what "connected component" means in Div1D please. If the graph is a tree then shouldn't the size of connected component be of size $N$?
•  » » A maximal region with nodes of the same color.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   Can you further explain why the the "connected component" have $loss \geq \displaystyle\frac{(k)(k+1)}{2}$ please.
•  » » » » It's beacause every path in a connected component contains exactly one color, so the mex surely is not 2.
•  » » » » » Got it! Thank you so much for the help
 » Can anyone please explain to me what merging exactly is in the question1831B — Array MergingI tried but couldn't understand what † A merge of two arrays results in an array c composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of c . We repeat this operation as long as we can (i.e. at least one array is nonempty). this exactly meant.
 » Regarding Div2 C , Can we do it without DP?