Indian ICPC 2022-23 Regionals — Qualifier Rounds

→ Обратите внимание

До соревнования
Codeforces Round 941 (Div. 1)
4 дня

До соревнования
Codeforces Round 941 (Div. 2)
4 дня

→ Трансляции

CodeChef Starters 131 Solution Discussion

aryanc403

До начала 34:26:40

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	146
8	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя 18o3

Indian ICPC 2022-23 Regionals — Qualifier Rounds

Автор 18o3, история, 13 месяцев назад, По-английски

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.

icpc, icpc india, online prelims

18o3
13 месяцев назад
98

Комментарии (86)

Показать архивные | Написать комментарий?

coderdhanraj

13 месяцев назад, # |

+17

Best of Luck everyone!

→ Ответить

xox0

13 месяцев назад, # |

+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

→ Ответить

coderdhanraj

13 месяцев назад, # ^ |

← Rev. 2 →

+33

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

→ Ответить

jaglike_makkar

13 месяцев назад, # ^ |

+29

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

→ Ответить

satyam343

13 месяцев назад, # |

+32

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

→ Ответить

tanmay.raj.29

13 месяцев назад, # |

+53

Was this ICPC qualifier or leetcode contest? 0_0

→ Ответить

yash_daga

13 месяцев назад, # ^ |

+75

No, leetcode contests are harder.

→ Ответить

blitztage

13 месяцев назад, # ^ |

+54

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

leetcode contests are much better than this

→ Ответить

islingr

13 месяцев назад, # |

+33

speedforces

→ Ответить

magga

13 месяцев назад, # ^ |

+30

full shit sherlock

→ Ответить

tamajitbuba

13 месяцев назад, # ^ |

← Rev. 2 →

+31

| ||

|| |_

→ Ответить

vrintle

13 месяцев назад, # ^ |

+22

Feeling sorry for your 1 2 2 50.

→ Ответить

18o3

13 месяцев назад, # |

Can anybody tell why this got TLE?

→ Ответить

satyam343

13 месяцев назад, # ^ |

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

→ Ответить

islingr

13 месяцев назад, # ^ |

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

→ Ответить

blitztage

13 месяцев назад, # |

+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

→ Ответить

l1ability

13 месяцев назад, # ^ |

+27

mathura laxmi chit fund

→ Ответить

o.O.o

13 месяцев назад, # |

+93

Refund.

→ Ответить

Greyhound

13 месяцев назад, # |

Can someone please tell me why this got TLE ?

→ Ответить

vrintle

13 месяцев назад, # ^ |

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.

→ Ответить

Greyhound

13 месяцев назад, # ^ |

Thanks a lot!

→ Ответить

SilverWing05

13 месяцев назад, # ^ |

I'm about to cry

→ Ответить

Greyhound

13 месяцев назад, # ^ |

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

→ Ответить

SilverWing05

13 месяцев назад, # ^ |

Guess what

→ Ответить

angry_pikachu

13 месяцев назад, # ^ |

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

→ Ответить

SilverWing05

13 месяцев назад, # ^ |

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.

→ Ответить

yash_daga

13 месяцев назад, # |

+58

How to make a 1600 rated problem 1800.

Give input in floating points.

→ Ответить

xox0

13 месяцев назад, # ^ |

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

→ Ответить

shiv_codegen

13 месяцев назад, # |

+14

Speedforces af.

→ Ответить

rakesh272611

13 месяцев назад, # |

worst contest I have seen

→ Ответить

tanmay.raj.29

13 месяцев назад, # |

← Rev. 2 →

+23

Preparing for ICPC prelims:

→ Ответить

VS-Codes

13 месяцев назад, # |

-11

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

→ Ответить

_Aryan_

13 месяцев назад, # ^ |

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

→ Ответить

_CHEEMS_

13 месяцев назад, # ^ |

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

→ Ответить

dedsec_29

13 месяцев назад, # ^ |

Try this test case
1
5
abdcd
dcabd

→ Ответить

Runtime-Terr0r

13 месяцев назад, # |

← 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

→ Ответить

s_prateek26

13 месяцев назад, # |

+14

from Imgflip Meme Generator

→ Ответить

Bosscoder

13 месяцев назад, # |

+11

How many teams will be selected from each institute ?

→ Ответить

WAtoAC2001

13 месяцев назад, # |

Kanpur regionals qualification rules have been updated here

→ Ответить

_aka5h

13 месяцев назад, # ^ |

do you have the same for Amritapuri regionals?

→ Ответить

-214748364

13 месяцев назад, # |

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

→ Ответить

YPK

13 месяцев назад, # |

Why is nlogn solution giving TLE for XOR sort?

→ Ответить

DCSekhara

13 месяцев назад, # ^ |

For me it didn't

→ Ответить

YPK

13 месяцев назад, # ^ |

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;
}

→ Ответить

aryanc403

13 месяцев назад, # ^ |

+28

#define endl "\n"
195 ms

→ Ответить

YPK

13 месяцев назад, # ^ |

+53

I’m jumping off the terrace

→ Ответить

meet.05

13 месяцев назад, # ^ |

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;
}

→ Ответить

VaibhaveS

13 месяцев назад, # |

How to solve central subset?

link

→ Ответить

YPK

13 месяцев назад, # ^ |

-9

Centroid decomposition ig

→ Ответить

ExplodingFreeze

13 месяцев назад, # ^ |

← 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.

→ Ответить

gupta_nitin

13 месяцев назад, # ^ |

← 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.

→ Ответить

ExplodingFreeze

13 месяцев назад, # |

← 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

→ Ответить

jeal0uspengu1n

13 месяцев назад, # ^ |

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

→ Ответить

WeaponizedAutist

13 месяцев назад, # |

What are the qualification rules for amritapuri?

→ Ответить

crimsonred

13 месяцев назад, # |

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

→ Ответить

shrapnelzz

13 месяцев назад, # ^ |

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

→ Ответить

pvtr

13 месяцев назад, # |

Will there be additional system testing on the Amritapuri prelims?

→ Ответить

_aka5h

13 месяцев назад, # ^ |

is that common?

→ Ответить

xennygrimmato

13 месяцев назад, # ^ |

Nope, full tests are run during contest time.

→ Ответить

shreyas_v

13 месяцев назад, # |

← 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?

→ Ответить

adityagamer

13 месяцев назад, # |

+13

How to solve The number of good subarrays

→ Ответить

sobhagyaSD

13 месяцев назад, # ^ |

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.

→ Ответить

adityagamer

13 месяцев назад, # ^ |

Could you please elaborate your checker function of binary search

→ Ответить

sobhagyaSD

13 месяцев назад, # ^ |

← 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 :(

→ Ответить

adityagamer

13 месяцев назад, # ^ |

Thank you

→ Ответить

coderdhanraj

13 месяцев назад, # |

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

→ Ответить

Newtech66

13 месяцев назад, # ^ |

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

→ Ответить

coderdhanraj

13 месяцев назад, # ^ |

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

→ Ответить

swapbeast

13 месяцев назад, # ^ |

← 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

→ Ответить

coderdhanraj

13 месяцев назад, # ^ |

Yes, ofc!

→ Ответить

wannaBe

13 месяцев назад, # ^ |

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

→ Ответить

adityagamer_simp_edition

13 месяцев назад, # ^ |

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.

→ Ответить

Jeffin

13 месяцев назад, # |

+15

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

→ Ответить

AAK

13 месяцев назад, # |

+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.

→ Ответить

Greyhound

13 месяцев назад, # ^ |

Results for Amritapuri have been announced: link

→ Ответить

Panther339

13 месяцев назад, # |

gwalior pune region info anyone

→ Ответить

CodeKar

13 месяцев назад, # |

When will mathura region results gonna be declare?

→ Ответить

angry_pikachu

13 месяцев назад, # ^ |

← Rev. 3 →

today or tomorrow, there are 150 seats

Source — codedrills telegram channel

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

→ Ответить

adityagamer

13 месяцев назад, # ^ |

The guy who said on telegram : "Source: Trust me bro"

→ Ответить

sk.dubey

13 месяцев назад, # ^ |

150 seats, r u serious?? Haha, According to Kanpur max to max 70-80 seats.

→ Ответить

ToXic_saumyy

13 месяцев назад, # ^ |

Yeah the seats in kanpur will be 70-80 but the combined seats of kanpur mathura should be atleast 130

→ Ответить

sk.dubey

13 месяцев назад, # ^ |

It's not a combined regional site. It's only Mathura where the regionals are going to be held as per my knowledge.

→ Ответить

ToXic_saumyy

13 месяцев назад, # ^ |

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.

→ Ответить