### 18o3's blog

By 18o3, history, 13 days ago,

This year there will be two separate online qualifier rounds for the two regionals.

The contest for Mathura is from 2pm to 4pm IST on 18th March 2023. Link
The contest for Amritapuri site is from 8pm to 10pm IST on 18th March 2023. Link

Let's use this blog to discuss the rounds after they end.

Hope to see you all on the leaderboard.

• +57

 » 13 days ago, # |   +17 Best of Luck everyone!
 » 12 days ago, # |   +141 Kanpur Mathura prelims has to be the worst ICPC contest, probably ever. Imagine setting 4 problems for a team of 3, and so easy that all of them could easily be solved in $\lt$ 20 minutes total. And then to add icing on the cake the penalty for a single wrong submission is 20 minutes as well
•  » » 12 days ago, # ^ | ← Rev. 2 →   +33 Agree.... feeling sad after making wrong submissions blindly :(
•  » » 12 days ago, # ^ |   +29 And that surprise "Case 1:" twist was the ultimate test :)
 » 12 days ago, # |   +32
 » 12 days ago, # |   +53 Was this ICPC qualifier or leetcode contest? 0_0
•  » » 12 days ago, # ^ |   +75 No, leetcode contests are harder.
•  » » 12 days ago, # ^ |   +54 Enough with the direspect bro, this can’t be accepted,leetcode contests are much better than this
 » 12 days ago, # |   +33 speedforces
•  » » 12 days ago, # ^ |   +30 full shit sherlock
•  » » » 12 days ago, # ^ | ← Rev. 2 →   +31 | || || |_
•  » » » » 12 days ago, # ^ |   +22 Feeling sorry for your 1 2 2 50.
 » 12 days ago, # |   0 Can anybody tell why this got TLE?
•  » » 12 days ago, # ^ |   +6 They added extra tests and rejudged your submission. After rejuding, execution time has not been updated.
•  » » 12 days ago, # ^ |   +1
 » 12 days ago, # |   +111 If you take 10 lakh rupees as cumulative fees for just the prelims, it is just downright shameful coming up with such a problemset. Probably should reassess whether your priority is advancement of CP or just a pitiful money grab
•  » » 12 days ago, # ^ |   +27 mathura laxmi chit fund
 » 12 days ago, # |   +93 Refund.
 » 12 days ago, # |   +3 Can someone please tell me why this got TLE ?
•  » » 12 days ago, # ^ |   +6 You can't rely on 2d-vectors where your complexity is $\mathcal{O}(N^2 \cdot T)$ which is probably $8 \cdot 10^8$ iterations, with time limit of 3s.Use 2d-arrays instead.
•  » » » 12 days ago, # ^ |   0 Thanks a lot!
•  » » » 12 days ago, # ^ |   0 I'm about to cry
•  » » » » 12 days ago, # ^ |   0 Already did :) Four TLE's because of this lol.
•  » » » » » 12 days ago, # ^ |   0 Guess what
•  » » » » 9 days ago, # ^ |   0 idk why, my solution got accepted , i have used 2-D vectors too. Any idea how many slots are there in kanpur-mathura? I hope there should be 120 seats :/
•  » » » » » 9 days ago, # ^ |   0 Lucky you :')As always, no official info. from them. But if we see last year, Kanpur had 70 seats, so Kanpur + Mathura should be around 120 to 140. Just a guess though.
 » 12 days ago, # |   +58 How to make a 1600 rated problem 1800.Give input in floating points.
•  » » 12 days ago, # ^ |   0 More like 1200 into 1400 but yeah, that was so annoying (:
 » 12 days ago, # |   +14 Speedforces af.
 » 12 days ago, # |   +8 worst contest I have seen
»
12 days ago, # |
Rev. 2   +23

### Preparing for ICPC prelims:

 » 12 days ago, # |   -11 Can anyone give a testcase that fails this code for B? Cannot understand what is wrong with this approach.
•  » » 12 days ago, # ^ |   0 What when s[i] is equal to value at both pointers!
•  » » 12 days ago, # ^ |   0 I used the same approch but sill not able to understand why equal value would effect
•  » » » 12 days ago, # ^ |   0 Try this test case 1 5 abdcd dcabd
 » 12 days ago, # | ← Rev. 2 →   0 What happened to that tradition of ICPC where one problem is solved by all teams and one problem is not solved by any team Why having prelims as div 69420 contest
 » 12 days ago, # |   +14
 » 12 days ago, # |   +11 How many teams will be selected from each institute ?
 » 12 days ago, # |   +5 Kanpur regionals qualification rules have been updated here
•  » » 12 days ago, # ^ |   0 do you have the same for Amritapuri regionals?
 » 12 days ago, # |   +3 Does anyone know how many slots are there for Mathura Regionals?
 » 12 days ago, # |   0 The quantity of questions was less. More sort of data structure problems.
 » 12 days ago, # | ← Rev. 2 →   0 Friendly remainder: s=s+b not equal to s+=b
 » 12 days ago, # |   0 Why is nlogn solution giving TLE for XOR sort?
•  » » 12 days ago, # ^ |   0 For me it didn't
•  » » » 12 days ago, # ^ |   +1 This gave TLE Spoiler#include using namespace std; typedef int ll; vector compress (vector v){ vector > w((ll)v.size()); for(ll i=0;i<(ll)v.size();i++){ w[i].first = v[i]; w[i].second = i; } sort(w.begin(),w.end()); vector res((ll)v.size()); for(ll i=0;i<(ll)w.size();i++){ res[w[i].second] = i; } return res; } void solve(){ ll n; cin >> n; vector v(n), order(n), pos(n); for(ll i=0;i> v[i]; } v = compress(v); for(ll i=0;i> ans; sort(order.begin(),order.end()); for(ll i=0;i> tc; for(int i=1;i<=tc;i++){ //cout << "Case #" << i << ": "; solve(); } return 0; } 
•  » » » » 12 days ago, # ^ |   +28 #define endl "\n"195 ms
•  » » » » » 12 days ago, # ^ |   +53 I’m jumping off the terrace
•  » » » » » » 12 days ago, # ^ |   +7 after 1st tle even optimized it to o(n), still didn't make it. Our team is jumping off too. code#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair p32; typedef pair p64; typedef pair pdd; typedef vector v64; typedef vector v32; typedef vector> vv32; typedef vector> vv64; typedef vector> vvp64; typedef vector vp64; typedef vector vp32; ll MOD1 = 998244353ll; ll MOD2 = 998244353ll; double eps = 1e-12; #define forl(i, e) for (ll i = 0; i < e; i++) #define forls(i, s, e) for (ll i = s; i < e; i++) #define rforl(i, s) for (ll i = s; i >= 0; i--) #define rforls(i, s, e) for (ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define INF 2e18 #define fast_cin() \ ios_base::sync_with_stdio(false); \ cin.tie(NULL); \ cout.tie(NULL) #define all(x) (x).begin(), (x).end() #define sz(x) ((ll)(x).size()) #define endl "\n" void solve() { ll n; cin >> n; ll v[n]; ll s[n]; unordered_map> m; ll curr = n - 1; forl(i, n) { cin >> v[i]; s[i] = v[i]; } sort(s, s + n); forl(i, n) { if (v[i] != s[i]) { m[s[i]].pb(i); } } vector> ans; while (curr >= 0) { if (v[curr] == s[curr]) { m[v[curr]].pop_back(); curr--; } else { ll x = curr + 1; ll y = m[v[curr]].back() + 1; ans.pb({x, y}); ans.pb({y, x}); ans.pb({x, y}); // ll el = v[y - 1]; m[v[curr]].pop_back(); swap(v[curr], v[y - 1]); } } cout << ans.size() << endl; for (auto x : ans) { cout << x.fi << " " << x.se << endl; } } int main() { fast_cin(); ll t = 1; cin >> t; while (t--) { solve(); } return 0; } 
•  » » » » » » 9 days ago, # ^ |   -8 Wanna hear some fuel-to-fire stuff? Python soln didn't get TLE Codefrom collections import defaultdict def solve(): n = int(input()) arr = list(map(int, input().split())) og = sorted(arr, reverse=1) ans = [] idx = defaultdict(set) for x,i in enumerate(arr): idx[i].add(x) for x, i in enumerate(og): pos = idx[i].pop() if pos == n-1-x: continue arr[n-x-1], arr[pos] = arr[pos], arr[n-1-x] idx[arr[pos]].remove(n-x-1) idx[arr[pos]].add(pos) ans.extend([ (n-x, pos+1), (pos+1, n-x), (n-x, pos+1) ]) # print(arr) print(len(ans)) for i in ans: print(*i) for _ in range(int(input())): solve() 
 » 12 days ago, # |   0 How to solve central subset? link
•  » » 12 days ago, # ^ |   -9 Centroid decomposition ig
•  » » 12 days ago, # ^ | ← Rev. 2 →   +23 Let sz(x) mean the size of the subtree rooted at x. Formally $sz(x) = 1 + \sum sz(v)$ for all children $v$ of $x$.Choose an arbitrary root and walk through the tree normally with a dfs calculating values of $sz$. For any node where $sz(x) \geq \sqrt{n}$, add $x$ to the subset and consider $sz(x) = 0$ for further calculations.Why does this work? For any child $v$ of $x$, $sz(v) \lt \sqrt{n}$, so the distance between any node in this subtree from $v$ must also be $\lt \sqrt{n}$. Since $v$ is a child of $x$, the distance of any node in the subtree from $x$ is $\lt \sqrt{n} + 1$ or in other words $\leq \sqrt{n}$. Since $sz(x) \geq \sqrt{n}$ whenever we perform this, we add at most $\frac{n}{\sqrt{n}} = \sqrt{n}$ nodes to the subset.
•  » » » 9 days ago, # ^ |   0 wait so all we have to do is traverse graph and pick every node after root(N) dfs calls? as in this, would work? Spoilervoid dfs(long long start, vector> &graph, long long distance, long long lim, queue &q, long long vis[] ) { vis[start] = 1; bool one= true; if(distance == lim) { q.push(start); one = false; } for(long long i=0; i
•  » » 12 days ago, # ^ | ← Rev. 2 →   +6 1) Pick any spanning tree and root at node $1$.2) Pick the node having the max depth, go up $\sqrt{n}$ for that node following parents, push this one in the answer, and remove that subtree.3) Do step 2 until the tree is not empty.
 » 12 days ago, # | ← Rev. 2 →   +43 Kudos to Amritapuri online round setters, it felt like a fairly nice and balanced round (except for maybe a bit of an aggressive difficulty jump after the first problem). I really liked how cute the solution to problem A is. Not at all biased by rank 11 in Amritapuri qualifier vs rank 227 in Mathura qualifier :P
•  » » 12 days ago, # ^ |   0 Yeah Amritapuri was relatively better, getting a lower rank didn't hurt in Amritapuri but it did in Mathura ;(
 » 12 days ago, # |   +1 What are the qualification rules for amritapuri?
 » 12 days ago, # |   0 Did anyone manage to get non-TLE with $n \sqrt{n}$ on A?
•  » » 12 days ago, # ^ |   0 Ya I guess my worst case would be n^(3/2), you can refer here
 » 12 days ago, # |   +4 Will there be additional system testing on the Amritapuri prelims?
•  » » 12 days ago, # ^ |   0 is that common?
•  » » 12 days ago, # ^ |   +4 Nope, full tests are run during contest time.
 » 12 days ago, # |   0 How many seats are there for kanpur-mathura regionals?
•  » » 12 days ago, # ^ |   0 maybe around 120?
 » 12 days ago, # | ← Rev. 4 →   +8 For the mathematicians and physicists problem of amritapuri region we did dp ( very similar to this problem), but got mle even after replacing 2 d input array by a map of pairs.Any suggestions?
 » 12 days ago, # | ← Rev. 3 →   -28 Thank you.
 » 12 days ago, # |   +13 How to solve The number of good subarrays
•  » » 12 days ago, # ^ |   0 For each L you can find the smallest R by binary search and if L,R is good then L,(R+1) is also good.
•  » » » 12 days ago, # ^ |   0 Could you please elaborate your checker function of binary search
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 So for checking if a subarray is good after removing [l,r] you need to count the f(rem) array, for that you can take the contribution of each bit for example if ith bit is set in k subarrays then the contribution will be 2^i*k for finding the number of subarray that has ith bit set you can do is total_subarray-number_of_subarrays_where_ith_bit_is_off. For achieving this you can keep some prefix suffix arrays.Refer this code for solution: herePS: Sorry for my alien language :(
•  » » » » » 11 days ago, # ^ |   0 Thank you
 » 12 days ago, # |   +9 Kanpur-Mathura Online Qualifier Round unofficial list here. (made by me :))
•  » » 12 days ago, # ^ |   0 What are the numbers next to the college name? The number of teams qualifying?
•  » » » 12 days ago, # ^ |   0 Nope, they're just the count, stating the no of times that college is present in under 100.
•  » » 11 days ago, # ^ |   0 is the selection criteria for kanpur-mathura regionals same as amritapuri regionals? Like do they too 1st select the top team from every other colleges?
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 Our team has rank 45 from Kanpur-Mathura and we are the 2nd team from our college and the 1st team has rank 10 so do we stand a chance for regionals
•  » » » 10 days ago, # ^ |   +1 Yes, ofc!
•  » » » » 10 days ago, # ^ |   0 If one team is selected from a college, 2nd team wouldn't be allowed, right ?
•  » » » » » 10 days ago, # ^ |   +4 That is the rule for Amritapuri regionals, not Mathura regionals. You can check last year's criteria here.I can't believe that such a great singer is on Codeforces. I am your big fan.
 » 12 days ago, # |   +15 Are qualification rules for Amritapuri same as last year? Can more than 3 teams qualify from an institute?
 » 10 days ago, # |   +29 Any ideas as to when the results would be announced? As the regional dates are close approaching, and most of us would need to book flights to get to Bangalore/Amritapuri.
•  » » 9 days ago, # ^ |   +6 Results for Amritapuri have been announced: link
 » 9 days ago, # |   +7 gwalior pune region info anyone
 » 9 days ago, # |   0 We got 180 rank. Is it good for qualifying mathura site!
•  » » 9 days ago, # ^ |   0 Depends upon the no. of slots :)
 » 8 days ago, # |   +3 When will mathura region results gonna be declare?
•  » » 7 days ago, # ^ | ← Rev. 3 →   0 today or tomorrow, there are 150 seats Source — codedrills telegram channel(someone claimed to got reply from icpc mathura-kanpur via email )
•  » » » 7 days ago, # ^ |   0 The guy who said on telegram : "Source: Trust me bro"
•  » » » 7 days ago, # ^ |   0 150 seats, r u serious?? Haha, According to Kanpur max to max 70-80 seats.
•  » » » » 7 days ago, # ^ |   0 Yeah the seats in kanpur will be 70-80 but the combined seats of kanpur mathura should be atleast 130
•  » » » » » 7 days ago, # ^ |   0 It's not a combined regional site. It's only Mathura where the regionals are going to be held as per my knowledge.
•  » » » » » » 7 days ago, # ^ |   0 Actually it's clearly mentioned on the icpc kanpur-mathura page that the contest is jointly hosted by GLA University,Mathura and CSJM University,Kanpur.
•  » » » » » » » 7 days ago, # ^ |   0 Ohh! Thank you for the info.
 » 7 days ago, # |   +4 Selected teams for kanpur — mathura No. of slots = 150
 » 7 days ago, # |   0 can someone share official telegram link for mathura regionals?
•  » » 5 days ago, # ^ |   0 +1
•  » » 5 days ago, # ^ |   0 Is there any telegram group for individual regionals?