chromate00's blog

Codeforces Round 1000 (Div. 2)
By chromate00, 5 weeks ago, In English

Hello Codeforces, and the legends of across $$$999$$$ and more rounds!

wuhudsm, Yugandhar_Master, and I are beyond excited to invite you to Codeforces Round 1000 (Div. 2) at 22.01.2025 15:05 (Московское время). Please note the unusual time of the round ($$$\color{red}{2.5}$$$ hours before the usual time)!

The contest contains $$$6$$$ carefully crafted tasks, one of them divided into two subtasks, to be solved in $$$2$$$ hours. You will solve tasks themed around Little John and his shenanigans aimed towards getting his own dream home (featuring, probably, galvanized square steel).

This round could not exist without the thankful help of these so many people:

The score distribution is as follows.

$$$\mathbf{500-1000-1500-2250-2750-(1750+1500)}$$$

Before finishing the announcement, I would like to spoil you a little of how the round's story ends.

Little John worked hard, honest and diligent for years, and finally got a home of his dream.

In that sense, I want You to be like Little John in this round.

Hard, honest and diligent will give you the rewards you deserve.

Anyways, that's all for the announcement; Good luck, and have fun!

UPD1: The score distribution has been announced.

UPD2: The editorial is posted here. Also we have good news that I will post as a separate report blog soon...

Spoiler

UPD3: Congratulations to the winners!

All participants:

  1. sunjia (oops, the user is gone now)
  2. Golovanov399
  3. maspy
  4. jiangbowen
  5. A_G
  6. fnoihzhyan

Rated only:

  1. sunjia (oops, the user is gone now)
  2. fnoihzhyan
  3. RGB_ICPC9
  4. wangzirui123
  5. Network_Error
  6. BSpioneer

UPD4: Anti-LLM Evaluation Report is published — the first of its kind for Div.2! Please kindly take a look if you have some free time or are just interested.

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

»
5 weeks ago, # |
  Vote: I like it +149 Vote: I do not like it

As a tester, I tested the 1000th round.

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

As a tester, this round was certainly one of the rounds of all time.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The 1000th round is not just a number, but proof that legends live here!

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

As a tester, this is indeed a historical round!

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

As a tester, I didn't really test.

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

As a tester,

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

As a tester, I can confirm that $$$10^2=1000$$$

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

As a non-tester, I commented before SirPh.

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

letssssss gooooooooooo 1000th round!!! Sad I can't participate bc I have final exam :(

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

1e3 Nice

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

1e3

Spoiler
→ Reply
»
5 weeks ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

As a tester,I was expert when I tested.

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

as a tester, we needed more testers

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

As a tester, this was my first contest for testing.

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

As a non-tester we need more testers

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

Am I the only one who subconsciously thought "Yay, contest 8 in binary!" instead of "Yay, contest 1000!" after reading this? (Yes, that was my actual first thought)

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

As a tester, this is my first "As a tester" comment

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it +70 Vote: I do not like it

As a tester the chain is an elaborate plot to farm contribution (and this one too)

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

that sounds like the 8th contest in other words

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

As a tester of Codeforces Round 960 (Div. 2), hope the round will be interesting for you, or learn new knowledge, or get good delta.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow so very excited to attend the 1000th contest on codeforces !

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

As a tester, I can confirm that firefly is my waifu.

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

A millennium of brilliance! Congratulations, CodeForces! #CF1000

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

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this a hint that the contest is HARD. Scared but will participate anyways.

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

As a first time tester, it is cool that my first time is in such a special round.

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sadly I'd be missing out this round, good luck to all the participants.

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

hope for many bitset problems

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

Quite Excited for the 1000th round :)

→ Reply
»
5 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

Why unusual time in 1000th round :(

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It finally happened

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

As a tester, I am so happy to have tested the 1000th round. Fun fact: 1000 is the smallest composite number after 999.

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

    There are so many fun facts about 1000, for example it has exactly 2 times more prime divisors than 1024.

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

Finally, someone has not forgotten about grey testing. Wait...

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

Wow. 1000 contests. Whatever you have, school, work, whether it is night or early in the morning we must all participate. Let's make the 1000th contest the best ever.

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

As a tester, I FORGOT TO COMMENT

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I hope you get your fair share of contribution :)

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for setting the Round 1000 on the first day of my winter vacation, instead of during the final exam.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

probably the strongggest tester-lineup ever. orz!

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

First round I tested :)

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can we know what are the points for every question please :)

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

galvanized steel mentioned!!!!

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The 1000th contest is at 4AM for me but I'll probably still participate.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like no interactives. Saaaad (|;/

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The Round 1000 with unusual time! A good time for Chinese

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

As an author, I can confirm that gcd of the score distribution is 250, excuse me if it changes to 500.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    As an author, it is certain that it is a multiple of 250 anyways

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

As a participant, I can confirm that the contest has 1000 — 1 problems if we see F1 and F2 as 10 problems.

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

As someone who knows nothing about the round, I hope that:

At least one problem has $$$n \leq 1000$$$.

Every problem has $$$t \leq 1000$$$.

There is a *1000 rated problem (luck based).

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

Bold Score distribution ??? , chromate00 is cooking.

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

I was here !!!

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

Hell yeah baby!!!! excited

→ Reply
»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Why is the monumental codeforces round 1000 at 7am in the definitively best timezone on a weekday??? (did I just piss off a good part of the world? yes and I'm not sorry)

I really wanted to learn about Little John and his galvanized square steel, screws he borrowed from his aunt, and eco-friendly wood veneers

Sadly I guess I wont be able to.

GLHF to those participating, may bitset waifu bless you.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

why not the usual time :(

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

do i consider trying F after C

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

As a tester, this cunning dogo encourages you all to participates in this round.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

As a yellow tester, I was able to be promoted to red tester before the contest.

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

As a participant, i will try to solve 10^C Problems :)

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

As a non-tester, I would like to become a tester for any of the rounds. :)

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

Let's go We are in the new era

→ Reply
»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Wow — Just 24 to go until a big round-number milestone!

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but I don't think we can see the next milestone after 1024......

    It took 10 years to get to 1000 and we'll probably leave CP by then, but anyways, gl on round 1000.

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

Will this contest use mod = 1e9 + 9 ?

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

The 1000th round of codeforces, also the 1st round in the jiangly era

～(∠・ω< )⌒★

→ Reply
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I think the D will be difficult, so I will do the D first. If I can't do it, I will give up the contest without any submissions. :(

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

Man it's starting earlier than usual, sad. would have to miss the 1000th round due to my labs at that time :(

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

as a participant, it is my 100th contest

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

as someone who missed 999, i will not miss 1000 round.

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

I'm really excited to take this significant round at 6am on a weekday. Good luck to everyone else participating!

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

I mean, I just have to leave something here to prove I will be in such a historical contest

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

I have moved to a country which is exactly 2.5 hours ahead of my home. Good luck for me that this contest happens to fall at my "usual" time at home. I have to participate for old times sake.

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

Glad to be here for a big milestone.

→ Reply
»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

As a tester, I tested the 1000th round.

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

this contest's time make me can't participate, so sad!

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Participating 1000th round before Ronaldo hits 1000 goals

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

Let's Go!!

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

Hopefully I can become an expert through this contest.Good luck.

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Waiting

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

As a Chinese student, I think 20:05 UTC+8 is a great time to be tested by a contest.

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

As a non-tester, I believe that this context will be something more than just a context, this is a mark of 1000, we can say that this is a very memorable mark in codeforces itself, for which I very much congratulate them

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

From this round, I’m restarting my journey of giving contests on Codeforces! Best of luck to everyone participating in this contest!

→ Reply
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

It would be great if i could solve 3 problems in 45 mins and 4th one by end of the contest

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

As a participant, I'm gonna participant in a historically legendary round!

I wish success to everyone who is participating and thanks to everyone who tested, problemsetted and overall contributed to this round!

<3

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

It's the time

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

qp

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

ROUND 1000!

WISHING EVERYONE +Δ ON THIS LEGENDARY ROUND!

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

as a newbie, We need more rounds

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

As a participant i hope to reach cyan

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

Thank goodness the time has changed to 20:05(UTC+8)!

Or I'm not able to participate again......

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

1000 less go!!

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

Congratulations to Codeforces for allowing a confirmed cheater to host and write an announcement post for their thousand-th round, which is criticized by a confirmed sub-account (lol)

→ Reply
»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Dominater069 for identifying as green;

So did he test the contest as green or is this him coming out? lol

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Round 1000! Great!

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

I was here too.

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

Codeforces Round 1000, I'll definitely participate the contest!

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

Really excited to give the 1000th contest of CF.I beginner in CP ,anyone who can advise me how to do CP as a beginner.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I started with Round 320 and now at 1000 today! The excitement is still the same. What a ride it's been. Here's to many more!

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

I will give this round from my office :)

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

It's wonderful to be able to participate in such a historical round.

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

I wonder if there will be such day where i would solve div 2 D

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

Came to register for contest and found that contest is almost over. Totally didn't missed to notice the unusual timing.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

What's up with C? Why is removing the highest degree node, updating degrees, and then removing the highest degree node again wrong?

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    there may be multiple nodes with the highest degree, meaning arbitrarily choosing one of them may not be optimal.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Counter example please.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
        ← Rev. 4   Vote: I like it +1 Vote: I do not like it

        The program should pick non-adjacent nodes if possible. If you pick adjacent nodes, you will have one less connected component than you expect, because the removal of the edge connecting the adjacent nodes does not lead to a new connected component (as there is nothing in between the two nodes — they are adjacent).

        In case there is only one node with the highest degree (for each removal), the idea works; but otherwise, you might pick adjacent nodes (even though you can do the opposite), which leads to the situation described above.

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          In case there are two nodes for the highest degree it still works because picking a non-maximal node would at best yield the same result than picking two maximal adjacent nodes, so the latter is optimal. But cases where there are three or more such nodes should be handled in a separate manner.

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

        three max degree vertices in a line.

        2 cases => one of the two choosen is middle one.

        other case when middle one not choosen.(more connected parts then above case)

        One test case:

        1

        11

        1 2

        2 3

        2 4

        5 6

        5 7

        5 8

        8 9

        8 10

        8 11

        → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried all the highest degree nodes, doing it naively in O(n^2) and got TLE on test 9 (don't know what I was expecting). Waiting for the editorial to find out how to do it correctly.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i also tried all highest degree node but optimally

      → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's a dp type idea: we solve it for each subtree. For a root of a subtree, i, there are 2 cases: (1) remove i and some descendant, or (2) remove 2 descendants. To do this properly, we have to precalculate mxdeg[v] for all vertices v, denoting the max node degree in v's subtree, excluding v. Just look at my code for further detail.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think I can see your submissions, but the editorial solution seems to suggest bruteforcing the maximum degree vertex and then finding the maximum degree vertex among the resulting subtrees using a priority queue or a multiset. A shame I didn't see that.

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

      the main idea is if there exists a pair of highest degree nodes that are not neighbourhood, one's removal will not affect another one.

      hence if there are 2 highest degree nodes, check if they are neighbourhood. if there are 3 or more, there must exists such pair since it is a tree.

      edit: typo

      → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      ans is highest degree + next_highest_degree-1 , and now u have to choose such a node for highest degree that removing it maximize next_highest_degree , cause removal of some node can lead to decreasing it

      → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lets say if u remove highest degree node then degree of surrounding nodes will decrease by one

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

    1 2 / 1 3 / 2 4 / 4 5

    you can consider the case where node 2 is chosen first.

    → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u need to consider two cases, one where the selected nodes are adjacent and another where they are not

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

D kills me.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    It's ok! It's the idea to do greedy but remembering past choices so you can undo them when needed!

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Help me out please why is my DP solution for C giving WA on test 2?

Edit: Nvm I got it. I missed the case where we take 2 descendants.

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

this contest want to make me kill my self

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

i hate myself

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nothing can save us, but reborn as gifted Chinese kid next life. there is no way around this is OVER! I'm done with CP

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

Wow opened codeforces the moment contest ended and missing the 1000th contest because of missing the time . Yayy Luck :)

→ Reply
»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I think this contest is perfect! Problems have no mistakes and their qualities are high. I have a nice experience through this contest!

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

forgot to remove my debugging prints on my last submit lol

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

Wasn't able to implement it but here is what i think the solution for F2 is, let use assume that we are trying to find the answer for the first $$$i$$$ segments, we define the score of any segment $$$j$$$ as the number of points inside the segment $$$j$$$, for which $$$j$$$ is the minimal segment i.e. for any point $$$i$$$ and segment $$$(l,r)$$$, this segment is minimal, if $$$l \le i \le r$$$ and there doesn't exist any other segment $$$(l1,r1)$$$ such that $$$l1 \le i \le r1$$$ and $$$r1-l1+1 \lt r-l+1$$$. Now, the answer is the product of the catalan numbers for each segment's score by 2.

To handle addition of segment $$$(l_i,r_i)$$$ efficiently, you just need to find the minimal segment $$$(l,r)$$$ for any point inside $$$(l2,r2)$$$ and change the score of this segment and update the answer. This is a standard problem that can be done in $$$O(logn)$$$.

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Why am I getting wa on pretest 3 for C? Code In first dfs I tried deleting 2 nodes from subtree of a node. In second I tried deleting current node and one node from its subtree. I kept a check if difference in height of max children node and current node is 1 to subtract 1 for the empty middle portion.

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

Second Question was quite confusing .....

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

My screencast (in Rust). Should be available when video is uploaded.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    your screencast are always boring that's why noone watch them

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

Why my code for C failed at pretest 4, My Code 1. I tried removing highest degree node,then recalculating degrees and then again removing highest degree node

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Removing the highest degree node greedily won't always work. Suppose:

    Tree: 1-3-2-4-5.

    Here nodes 2,3 & 4 have degree 2. But here we have to remove node 3 & 4 to get the maximum.

    → Reply
»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

thankfully, data structures made round 1000 go terrible!

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

C was quite typical for me I knew i have to remove the two nodes with maximum adjacent nodes I m implementing it wrong ig :(

Can anyone explain to me like a 5 year old

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try looking at the case where you have 5 nodes: 1-2-3-4-5.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      all in a straight line so 1 connected to 2 and 2 connected to 3 so forth so on.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ;( what was ur approach regarding this

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i don't like my approach a lot tbh I think editorial might have a better way. the way I did it was you count how many nodes have highest number of adj nodes (so number of nodes with highest degree). If the number of nodes with highest degree is >= 3 then you know you can basically split it like this twice. ex: if you have 3 nodes with degree 4 you know that 2 of them aren't connected so you can remove them both. else if there are only 2 or 1 nodes with highest degree the algorithm you are doing will work. I just added one if for testing if number of nodes with highest degree is >= 3 and brute forced that answer. I think editorial might have a better way tho :D

          → Reply
          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            damnnn imma look at editorial later will try to upsolve it thanks bro

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

OpenAI o1 only solved 1 problem.

ChatGPT BTFO XD

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

i am never using accumulate again in my life

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You missed the question because of overflow when using accumulate with start value 0?

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah

      i lost about an hour trying the find the bug it was an overflow due to the 0 being int not long long

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

This cloudfare stoped me from submitting my correct code to E。

It stucked me for about 3 minute。 Do I look like a robot？

I can't be CM now。

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

Can anyone please tell me why my code for problem $$$D$$$ got WA on test 6 ?

my idea was to take the highest value between $$$a.back() - a.front()$$$ and $$$b.back() - b.front()$$$ if I can

and if this will result in reducing the number of ways to take the last triangles, I will output the answer and then remove the highest value and take the smallest one

what is wrong with this idea ?

→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Consider that all of a's have huge space between them and b's are close. You will always pick 2 a's and 1 b until there are few a's (say 1 or 2 depending on how you coded the last cases). Then you will be forced to pick 1 a for the last cases and you will be left with a bunch of b's and no a's. You could have picked more b's in the start to keep the process going for longer. Your solution is correct with regards to optimizing the first cases, but from a point onwards your process will halt prematurely (your k_max will be less than the answer).

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

Can D be solved using ternary search? By the time I finished implementation the contest just got over. My code is passing samples, will have to wait for system tests to finish to see if it works.

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

I am fortunately that I didn't participate in this contest, if I do, i will become a Specialist.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

1000th round and I messed it all up

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

So what's the meaning of F1 :thinking:

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

????

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

It could have been a better idea to be extra careful when organizing a special round like this one. It's not just numbers; "the 1000th round" feels like a very inspiring round to attend. This was the first round I attended in 7 months. My rustiness alone doesn't explain my terrible performance. Ending my break with a contest like this was not nice, and I think many of you have similar feelings.

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

Missed F1 by 1 second :(

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

I thick E is much easier than D.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C really tricked me into doing a casework DP :(

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I first thought to apply DP on trees but figured out that greedy selection of nodes with maximum net degree would work !!

    → Reply
»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it
Help ! My submission on C wasn't passed to system testing
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    chromate00 Can you fix the problem ?

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I tried rejudging it, but it still doesn't get to system testing. I will ask the coordinator and KAN about it.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is Accepted now. Thanks to everyone who participated in the making of this nice contest!

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

Is this round rated or not? I solved 1 problem and expected my rating to rise.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wait !! It takes some time to calculate the ratings. It is rated as of now.. You will get a rating soon !!

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

    As far as I know, there is some initial boost given to you for your first few rounds. See this.

    (Edit: Wait, I might have misinterpreted your comment as your rating being predicted to increase. Sorry if that is the case.)

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I'made a mistake,I took the round way too casually.

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

a historical moment XD

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

Happy 1000 everyone!!

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

This was such a beautiful contest thanks !!

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

Do something to cheaters Youtube channel This youtube channel is providing solutions in live stream.

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

Can somebody give me some solid edge test cases for C problem, I don't know why my code is failing?

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

For C, is this a valid testcase? Answer should be 5 but one of my code gives 4 but it got accepted.

1

12

1 2

1 3

2 4

2 5

3 6

3 7

1 8

4 9

5 10

6 11

7 12

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

As a tester, this is indeed a historical round!

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

every time i see miku in comments i remember De3b0o

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

For problem D , after fixing $$$[l, r]$$$ for a fixed $$$k$$$ , how do we calculate the maximum value of $$$f(k) = \max_x g(x, k - x)$$$

→ Reply
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

what happened to sunjia?

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

Good

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

Is it just me or other people also thinks that the problems D, E and F1 have similar difficulty?

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

gg

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

A,B,C,D,E Video Solutions here: https://www.youtube.com/watch?v=v4Dt37mBIBA

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

Contest is awesome

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

I received a message saying that my submission matches with another user, in this matter i would say that the problem was very simple and had a straight answer, also since the variables were already mentioned in the question, we i didn't bother to change them. Also our time stamps of submission are very different. Please look into the matter.

→ Reply
»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

as a tester,

→ Reply