18o3's blog

Indian ICPC 2022-23 Regionals — Qualifier Rounds
By 18o3, history, 3 years ago, In English

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.

  • Vote: I like it
  • +57
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

Best of Luck everyone!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +141 Vote: I do not like it

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
»
3 years ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +53 Vote: I do not like it

Was this ICPC qualifier or leetcode contest? 0_0

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

speedforces

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anybody tell why this got TLE?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +111 Vote: I do not like it

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
»
3 years ago, hide # |
 
Vote: I like it +93 Vote: I do not like it

Refund.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Can someone please tell me why this got TLE ?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +58 Vote: I do not like it

How to make a 1600 rated problem 1800.

Give input in floating points.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Speedforces af.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

worst contest I have seen

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +23 Vote: I do not like it

Preparing for ICPC prelims:

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

How many teams will be selected from each institute ?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Kanpur regionals qualification rules have been updated here

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why is nlogn solution giving TLE for XOR sort?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    For me it didn't

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      This gave TLE

      Spoiler
      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it +28 Vote: I do not like it

        #define endl "\n"
        195 ms

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it +53 Vote: I do not like it

          I’m jumping off the terrace

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            Vote: I like it +7 Vote: I do not like it

            after 1st tle even optimized it to o(n), still didn't make it. Our team is jumping off too.

            code
            → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve central subset?

link

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it -9 Vote: I do not like it

    Centroid decomposition ig

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +23 Vote: I do not like it

    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
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +6 Vote: I do not like it

    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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +43 Vote: I do not like it

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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

What are the qualification rules for amritapuri?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Will there be additional system testing on the Amritapuri prelims?

→ Reply
»
3 years ago, hide # |
← Rev. 4  
Vote: I like it +8 Vote: I do not like it

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
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

How to solve The number of good subarrays

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Could you please elaborate your checker function of binary search

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        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
»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

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
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

gwalior pune region info anyone

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

We got 180 rank. Is it good for qualifying mathura site!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

When will mathura region results gonna be declare?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Selected teams for kanpur — mathura No. of slots = 150

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can someone share official telegram link for mathura regionals?

→ Reply