Indian ICPC 2022-23 Regionals — Qualifier Rounds

21 month(s) ago, # |

+17

Best of Luck everyone!

→ Reply

xox0

21 month(s) 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

→ Reply

This is just sad. Wait, no, not just sad. Sad and enraging. Great job!

21 month(s) ago, # ^ |

← Rev. 2 →

+33

Agree.... feeling sad after making wrong submissions blindly :(

→ Reply

jaglike_makkar

21 month(s) ago, # ^ |

+29

And that surprise "Case 1:" twist was the ultimate test :)

→ Reply

satyam343

21 month(s) ago, # |

+32

→ Reply

tanmay.raj.29

21 month(s) ago, # |

+53

Was this ICPC qualifier or leetcode contest? 0_0

→ Reply

yash_daga

21 month(s) ago, # ^ |

+75

No, leetcode contests are harder.

→ Reply

blitztage

21 month(s) ago, # ^ |

+54

Enough with the direspect bro, this can’t be accepted,

leetcode contests are much better than this

→ Reply

islingr

21 month(s) ago, # |

+33

speedforces

→ Reply

magga

21 month(s) ago, # ^ |

+30

full shit sherlock

→ Reply

tamajitbuba

21 month(s) ago, # ^ |

← Rev. 2 →

+31

| ||

|| |_

→ Reply

vrintle

21 month(s) ago, # ^ |

+22

Feeling sorry for your 1 2 2 50.

→ Reply

18o3

21 month(s) ago, # |

Can anybody tell why this got TLE?

→ Reply

satyam343

21 month(s) ago, # ^ |

They added extra tests and rejudged your submission. After rejuding, execution time has not been updated.

→ Reply

islingr

21 month(s) ago, # ^ |

just write it iteratively, and/or use booleans rather than max

→ Reply

blitztage

21 month(s) 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

→ Reply

l1ability

21 month(s) ago, # ^ |

+27

mathura laxmi chit fund

→ Reply

o.O.o

21 month(s) ago, # |

+93

Refund.

→ Reply

21 month(s) ago, # |

Can someone please tell me why this got TLE ?

→ Reply

vrintle

21 month(s) ago, # ^ |

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.

→ Reply

21 month(s) ago, # ^ |

Thanks a lot!

→ Reply

SilverWing05

21 month(s) ago, # ^ |

I'm about to cry

→ Reply

from Imgflip Meme Generator

21 month(s) ago, # ^ |

Already did :) Four TLE's because of this lol.

→ Reply

SilverWing05

21 month(s) ago, # ^ |

Guess what

→ Reply

angry_pikachu

21 month(s) ago, # ^ |

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 :/

→ Reply

SilverWing05

21 month(s) ago, # ^ |

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.

→ Reply

yash_daga

21 month(s) ago, # |

+58

How to make a 1600 rated problem 1800.

Give input in floating points.

→ Reply

xox0

21 month(s) ago, # ^ |

More like 1200 into 1400 but yeah, that was so annoying (:

→ Reply

shiv_codegen

21 month(s) ago, # |

+14

Speedforces af.

→ Reply

rakesh272611

21 month(s) ago, # |

worst contest I have seen

→ Reply

tanmay.raj.29

21 month(s) ago, # |

← Rev. 2 →

+23

Preparing for ICPC prelims:

→ Reply

VS-Codes

21 month(s) ago, # |

-11

Can anyone give a testcase that fails this code for B? Cannot understand what is wrong with this approach.

→ Reply

_Aryan_

21 month(s) ago, # ^ |

What when s[i] is equal to value at both pointers!

→ Reply

_CHEEMS_

21 month(s) ago, # ^ |

I used the same approch but sill not able to understand why equal value would effect

→ Reply

dedsec_29

21 month(s) ago, # ^ |

Try this test case
1
5
abdcd
dcabd

→ Reply

Runtime-Terr0r

21 month(s) ago, # |

← Rev. 2 →

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

→ Reply

s_prateek26

21 month(s) ago, # |

+14

→ Reply

Bosscoder

21 month(s) ago, # |

+11

How many teams will be selected from each institute ?

→ Reply

WAtoAC2001

21 month(s) ago, # |

Kanpur regionals qualification rules have been updated here

→ Reply

_aka5h

21 month(s) ago, # ^ |

do you have the same for Amritapuri regionals?

→ Reply

-214748364

21 month(s) ago, # |

Does anyone know how many slots are there for Mathura Regionals?

→ Reply

21 month(s) ago, # |

Why is nlogn solution giving TLE for XOR sort?

→ Reply

DCSekhara

21 month(s) ago, # ^ |

For me it didn't

→ Reply

21 month(s) ago, # ^ |

This gave TLE

Spoiler

#include <bits/stdc++.h>
using namespace std;
typedef int ll;

vector <ll> compress (vector <ll> v){
        vector <pair<ll,ll>> 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 <ll> 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 <ll> v(n), order(n), pos(n);
        for(ll i=0;i<n;i++){
                cin >> v[i];
        }
        v = compress(v);
        for(ll i=0;i<n;i++){
                pos[v[i]] = i;
                order[i] = v[i];
        }
        vector <pair<ll,ll>> ans;
        sort(order.begin(),order.end());
        for(ll i=0;i<n;i++){
                if(pos[order[i]] == i){
                        continue;
                }
                ll x = i;
                ll y = pos[order[i]];
                ans.push_back(make_pair(x,y));
                ans.push_back(make_pair(y,x));
                ans.push_back(make_pair(x,y));
                pos[v[x]] = y;
                pos[v[y]] = x;
                swap(v[x],v[y]);
        }
        cout << (ll)ans.size() << endl;
        for(auto x : ans){
                cout << x.first+1 << " " << x.second+1 << endl;
        }
        cout.flush();
}

int main(){
#ifndef ONLINE_JUDGE
        //freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
#endif
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int tc;
        tc = 1;
        cin >> tc;
        for(int i=1;i<=tc;i++){
                //cout << "Case #" << i << ": ";
                solve();
        }
        return 0;
}

→ Reply

aryanc403

21 month(s) ago, # ^ |

+28

#define endl "\n"
195 ms

→ Reply

21 month(s) ago, # ^ |

+53

I’m jumping off the terrace

→ Reply

meet.05

21 month(s) ago, # ^ |

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 <bits/stdc++.h>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
typedef pair<double, double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int>> vv32;
typedef vector<vector<ll>> vv64;
typedef vector<vector<p64>> vvp64;
typedef vector<p64> vp64;
typedef vector<p32> 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<ll,vector<ll>> 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<pair<ll,ll>> 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;
}

→ Reply

VaibhaveS

21 month(s) ago, # |

How to solve central subset?

link

→ Reply

21 month(s) ago, # ^ |

-9

Centroid decomposition ig

→ Reply

ExplodingFreeze

21 month(s) 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.

→ Reply

gupta_nitin

21 month(s) ago, # ^ |

← Rev. 2 →

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.

→ Reply

ExplodingFreeze

21 month(s) 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

→ Reply

jeal0uspengu1n

21 month(s) ago, # ^ |

Yeah Amritapuri was relatively better, getting a lower rank didn't hurt in Amritapuri but it did in Mathura ;(

→ Reply

WeaponizedAutist

21 month(s) ago, # |

What are the qualification rules for amritapuri?

→ Reply

crimsonred

21 month(s) ago, # |

Did anyone manage to get non-TLE with $$$n \sqrt{n}$$$ on A?

→ Reply

shrapnelzz

21 month(s) ago, # ^ |

Ya I guess my worst case would be n^(3/2), you can refer here

→ Reply

pvtr

21 month(s) ago, # |

Will there be additional system testing on the Amritapuri prelims?

→ Reply

_aka5h

21 month(s) ago, # ^ |

is that common?

→ Reply

xennygrimmato

21 month(s) ago, # ^ |

Nope, full tests are run during contest time.

→ Reply

shreyas_v

21 month(s) ago, # |

← Rev. 4 →

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?

→ Reply

21 month(s) ago, # |

+13

How to solve The number of good subarrays

→ Reply

sobhagyaSD

21 month(s) ago, # ^ |

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.

→ Reply

21 month(s) ago, # ^ |

Could you please elaborate your checker function of binary search

→ Reply

sobhagyaSD

21 month(s) ago, # ^ |

← Rev. 2 →

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: here

PS: Sorry for my alien language :(

→ Reply

21 month(s) ago, # ^ |

Thank you

→ Reply

21 month(s) ago, # |

Kanpur-Mathura Online Qualifier Round unofficial list here. (made by me :))

→ Reply

Newtech66

21 month(s) ago, # ^ |

What are the numbers next to the college name? The number of teams qualifying?

→ Reply

21 month(s) ago, # ^ |

Nope, they're just the count, stating the no of times that college is present in under 100.

→ Reply

swapbeast

21 month(s) ago, # ^ |

← Rev. 2 →

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

→ Reply

21 month(s) ago, # ^ |

Yes, ofc!

→ Reply

wannaBe

21 month(s) ago, # ^ |

If one team is selected from a college, 2nd team wouldn't be allowed, right ?

→ Reply

adityagamer_simp_edition

21 month(s) ago, # ^ |

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.

→ Reply

Jeffin

21 month(s) ago, # |

+15

Are qualification rules for Amritapuri same as last year? Can more than 3 teams qualify from an institute?

→ Reply

AAK

21 month(s) 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.

→ Reply

21 month(s) ago, # ^ |

Results for Amritapuri have been announced: link

→ Reply

Panther339

21 month(s) ago, # |

gwalior pune region info anyone

→ Reply

CodeKar

21 month(s) ago, # |

When will mathura region results gonna be declare?

→ Reply

angry_pikachu

21 month(s) ago, # ^ |

← Rev. 3 →

today or tomorrow, there are 150 seats

Source — codedrills telegram channel

(someone claimed to got reply from icpc mathura-kanpur via email )

→ Reply