satyam343's blog

ICPC India Chennai 2025 — 2026
By satyam343, 5 months ago, In English

Hi everyone,
The ICPC Chennai onsite regional round is ongoing from 9:15 AM IST to 2:15 PM IST. You can follow the public ranklist here

UPD1:

We invite you to participate in ICPC Chennai 2025 Onsite — Replay Round (Unrated), on Wednesday, 31 December.

Time: 10:00 AM — 3:00 PM IST

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

»
5 months ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

The ranklist is completely blank right now.

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

Can someone pls help with missing case for J.

Following was our approach:

  • If k=0 and m=n-1 then make a tree.

  • If k=0 and m=n then make a tree with a cycle of size 3

  • If k=n and m>=n make a cycle using all vertices and keep on adding edges until m completed

  • If n>k>=4, then keep on making triangles (cycle of size 3) connected at 1 common vertex until m>n. Once m=n then while k>0 add and connect vertices to a corner vertex of the triangles. And once k=0 then connect vertices to common vertex of the triangles.

  • Else output -1
→ Reply
  • »
    »
    5 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    I missed the same case that you did T_T

    When $$$k \in [1, n)$$$ and $$$m \gt n$$$, it's not always correct to have all the triangles share a common vertex, you might need to instead first create two base triangles that are connected by an edge, and attach all the other triangles to one of the interior nodes of the two base triangles (the ones connected by the edge between the two base triangles).

    edit: I’m fucking stupid, this wasn’t even the mistake. You just have to check that >1 triangle is added in the last case.

    → Reply
»
5 months ago, hide # |
← Rev. 2  
Vote: I like it -11 Vote: I do not like it

What's the point of having $$$n = 5e5$$$ with a TL of 4 seconds in A? As far as I know, there aren't any trivial $$$O(n \log^2{n})$$$ or $$$O(n^{3/2})$$$ solutions. I somehow managed to rack up 10 penalties (and simultaneously ruin my team's entire performance) fixing the constant-factor TLE of my $$$O(n \log{n})$$$ solution (FUCK TEST CASE 45).

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

    can you share the problem set?

    → Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    Uh, the intended solution is $$$O(n)$$$. But we did not want to cut $$$O(n \log n)$$$ solutions. So, we kept $$$n \le 5 \cdot 10^5$$$ and TL = 4s, as $$$O(n \log n)$$$ solutions were passing comfortably in less than 2s on CodeChef. In the actual contest, 12 out of 15 ACs were under 2s and the remaining two (excluding your AC) were under 3s. It seems like your multiset operations were quite costly :)

    I think that had we changed the constraint to $$$n \le 2 \cdot 10^5$$$, we might have reduced TL as well, because TL did not seem tight.

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

The link shows your are not allowed to view the contest . Is there any glitch which will be resolved before the contest or any problem with my account?

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

Editorial

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

Where can we submit our solutions? The replay contest doesn't seem to be accepting submissions.

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

my approach for problem H. RobinHood

I store all the unique elements of the array inside a temporary array (let's call it temp) and start traversing it. Let's say I am currently at an element with value $$$x$$$ and frequency $$$F[x]$$$, where $$$F$$$ is data structure used to store the frequency of elements (I used a map). The logic is as follows

  • If I delete none of the occurrences of $$$x$$$, I get $$$F[x]$$$ occurrences to keep.
  • If I decide to delete one occurrence of $$$x$$$, then I get $$$F[x]$$$ + $$$F[x-1]$$$ — $$$1$$$ elements to keep.
  • similarly if I decided to delete two occurrence of $$$x$$$ then I get $$$F[x]$$$ + $$$F[x-1]$$$ + $$$F[x-2]$$$-$$$2$$$ to keep.
  • I perform this process $$$min(freq, x)$$$ times, taking the maximum among all results.

and i do this for every unique x and at last i take the maximum stored among all the x's and output

size of array — maximum i could get

what is wrong in this? any test case where this fails ? our team got hard stuck on this, thanks in advance.

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

Is PDF version of the problemset available?

In codechef, the problems are sorted. I want to checkout problemset without it being sorted :)

→ Reply