Cocoly1990's blog

Good Bye 2024: 2025 is NEAR
By Cocoly1990, 5 weeks ago, In English

Good... yes, good afternoon, Codeforces!

We are glad to invite you to take part in Good Bye 2024: 2025 is NEAR, which will start on Dec/28/2024 17:35 (Moscow time). You will be given 9 problems and 3 hours to solve them. One of the problems will be divided into two subtasks.

All the problems are authored by _istil and me.

In this round, we would like to say goodbye to the past bad memories. However, the point is we won't say goodbye to:

UPD: The score distribution is $$$500 - 1000 - 1250 - 1750 - 2000 - 2500 - 4250 - 4500 - (3000 + 2000)$$$.

UPD: as pointed out here, the official solution of 2053I2 - Affectionate Arrays (Hard Version) is wrong. We are not sure that the problem is solvable with the current constraints. We will decide how to deal with this issue within tomorrow.

UPD: the problem I2 was removed from the official contest. Its statement has been corrected for future use. The affected participants have been unrated from the contest.

UPD: Congratulations to the winners!

  1. jiangly
  2. ecnerwala
  3. Benq
  4. Egor
  5. Radewoosh
  6. Petr
  7. Ormlis
  8. ksun48
  9. Nachia
  10. EnofTaiPeople

We are pleased to announce that NEAR has supported the round!

The featured prizes in NEAR are:

  • Ⓝ 512 for the first place,
  • Ⓝ 256 each for places 2 and 3,
  • Ⓝ 128 each for places 4 to 7,
  • ...
  • Ⓝ 1 each for places 512-1023 places.
Announcement of Good Bye 2024: 2025 is NEAR
  • Vote: I like it
  • +729
  • Vote: I do not like it

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

good luck children

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

When you realize majority of the testers are in blue to orange range. Barely any anywhere else. Will that impact anything?

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

    Aren't 2 $$${\color{black}{l}}$$$$$${\color{red}{gm}}$$$, 6 $$${\color{red}{red}}$$$ and 10 $$${\color{orange}{orange}}$$$ good enough, how many do you want.

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

    If you do sliding window on the testers you can get various majority tester ranks.

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

    You can find three more red ones on the line "helping with preparation on Polygon (including testing)" :)

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

    No? If you already have some set of testers and you add like 10 blue testers that would not make round worse.

    Quantity of good testers matter, not the percentage.

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

    Well, I'm Just a children who has just learnt programming for a year.

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

      Beware: you might end up becoming an actual software engineer in your adulthood.

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

    Upvote me pls i need contribution

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

Excited to participate!

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

Please don't be like RedMachine-74

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

happy new year!

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

why was good bye 2023 rated?

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

where's score distribution?

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

As a parent, I can confirm that _istil is cute!

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

and 251Sec for being invited to test but have no time to do virtual. :(

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

Congratulates!!!!!

No 74TrAkToR RedMachine-74 for Goodbye again!!!!!!!!

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

As not a tester, I didn't test.

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

As a tester, Happy New Year, and I hope you can achieve a positive delta in this contest as a New Year gift. :)

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

I like _istil's round.

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

As a tester, _istil is cute

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

As a not-tested tester, I didn't test because of my chemistry homework (actually, my chinese homework helps as well). Anyway, wish you guys positive delta!

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

As a tester, the problems and the problemsetters are cute and wish you all have fun in this contest!

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

As a kicked test,I want to cry!

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

Hope that i wont rage quit this time uWu :)

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

As a tester for the first time, what can I say.

The other testers are very good at expressing, but I can only say that this contest is the best one of the year.

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

Rated?

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

As a tester, I went cyan, which is the same color as _istil's, to express my adoration for _istil.

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

Rated?

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

Hope it doesn't end up like good bye 2023

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

As the only "LGM" "writer" of this "specialist round" (though I proposed no problems actually), I wish you good luck, positive delta and a happy new year! (I believe an lgm may make the round look better :)

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

score distribution ??

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

chill guys , This is another masterpiece coordinated round by TheScrasse , (orz).

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

Happy New Year! and well wishes for the positive delta for upcoming year.

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

2024 is meaningful to me.It is a perfect way to end this year to take part in the expecting contest!

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

As a tester, the problems are worthy of being in Good Bye round. Do not skip this one!

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

Is this rated?

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

is this rated??

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

my last chance to get expert this year. I hope I can do it and not bottle it again 😭😭😭

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

What about score distribution and its rating?

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

aa... what are these (N) points at the end of blog?

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

-Raspberry-

-Berry-

-Grapes-

-Banana-

-Ananas-

-Kiwi-

-Apple-

-Oak-

-DragonFruit-

-Orange-

-Blueberry-

As FruitSalad community, we look forward for participating in this contest ^^

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

and 251Sec for being invited to test but have no time to do virtual.

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

As a tester, _istil is cute and problems are more interesting than Goodbye 2023. GL&HF!

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

Let's Go

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

As a tester,I've lost a chance to gain rating in the end of 2024.

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

Happy new year 2025 with lucky for everyone

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

Bye Bye 2024

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

will it be rated?

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

Is this contest gonna be rated ?

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

i hope for a very good contest before 2025.

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

Will this contest be rated?

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

Hope that the round can be much better than Goodbye 2023

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

    So what's wrong with Goodbye 2023?

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

      It was a round which has got nearly 5000 downvotes. It had an OEIS-solvable problem on H.

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

Is it rated for all divisions?

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

Is this round rated or unrated? Also, will it be like educational rounds or normal (div1+ div2) rounds?

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

Is it rated?

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

I hope I no longer need to use magic to change color :)

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

will it be rated contest?

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

Happy new year! Hope to gain more rating in the last contest of 2024, good luck and have fun!

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

is this rated??

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

hope the contest can be great

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

Is it rated?If so,the rated range?

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

    I guess it will be rated as Div.1+2, because 3 hours.

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

Is there not going to be a Hello 2025 this year? So far it isn't in the contest list..

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

I hope Good bye 2024 will not be the same as Good bye 2023

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

That ishaandas1 for green testing is more like specialist or expert , visit his profile his ranks are under 3000 and if on this basis if ranks were calculated than our rating can be deducted

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

Happy Year, an sha' allah

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

Happy New Year Guys, and I hope you get a lot ACs this yeart!

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

what do you mean by featured prizes ?? is this something related to ratings

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

Who can tell me the score of each question

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

$$$2025=45^2$$$ probably the only perfect square number year throughout my lifetime...

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

    Believe in yourself, you have the probability to live until 2116

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

Happy New Year!!!!!!

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

Hope Good Bye 2024: 2025 is NEAR != Good Bye 2023

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

Is it ICPC format (Penalty , etc) or Points format (Points per problem ) :D ??

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

i can predict that 2024 will be in either question or constraint

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

I hope to become blue in this round!!

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

As a tester I can finally write a hint for you guys.

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

Best of luck for everyone

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

Excited for this contest!

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

Time to be a pupil before the end of the year haha

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

As 2024 is coming to a close, I would like to wish everyone a Happy New Year in advance and good results in the upcoming competitions. I am very passionate about algorithm programming.

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

I hope this contest is unlike the last two T-T.

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

its gonna be rated right?

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

It is Rated contest right?

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

I Wish every person in the Competitive Programming Community Belated Merry Christmas & Happy New Year in advance...

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

What is Ⓝ? I search Bing but not results.

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

What rating does the question have? Please mention.

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

rare round dont have thanks for "MikeMirzayanov for the Codeforces platform" O.O

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

    sorry, I added that (including the score distribution) just now o.O

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

I don't get why couldn't the author just mention if the round is gonna be rated or not

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

What are those N's at the end of the blogs?

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

Will it be rated?

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

A happy new year to everyone wish i could participate too

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

score distribution?

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

Score distribution??

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

score distribution when ?

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

Ⓝ this means?

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

What is Ⓝ ? Can someone explain please

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

Wont participate because i feel like its going to be mathforces cuz of chinese setters.

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

As some testers' friends, I didn't test.

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

I am just begineer, is this round for me??

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

What is N in this, I mean in the prizes??

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

which div sir ?

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

will it be unrated ?

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

Hello , may I know for exactly which divisions is this suitable for ? I usually attempt div 3 and 4 contests , so I don't know weather to take part in this or not.

Thanks

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

Need just 31pts to reach pupil. Aiming to solve ABC, hope I finish the year green!

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

rated?

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

(insert Good Bye 2023 trauma joke here)

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

Is this rated contest? I need to become pupil

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

Excited to participate

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

howdy!

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

Just a selfish question.

It is 6 questions to hit Expert.

5 questions to remain cyan and climb a bit

4 questions to de-rank to pupil

3 questions to de-rank to pupil

=2 questions to de-rank to newbie

Am I correct?

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

    No, 6 tasks is usually a GM-level performance, 4 and 5 tasks are somewhere in between CM and M (but a lot depends on the speed), fast 3 tasks is usually expert level and lower results are for specialists, pupils and newbies. Although this may differ -- some rounds are harder, some are easier

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

    This might be true in some div4

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

    Newbie it is.

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

Hopefully I can gain some of the 100 ELO I lost after getting hacked last round.

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

very excited because this is the last contest of this year I hope we all get greens with best wishes

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

2025=45*45 probably the only perfect square number year throughout my lifetime

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

How can NEAR be received? Can top 1023 participators receive their prizes by.. TON wallet or anything other? I haven't found any wallet about NEAR in WALLET yet.

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

happy new years everyone :D

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

orz

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

Is this round rated?

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

Participating after 7 months,wish me good luck

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

i feel like if i try my best, i will solve 2 questions.

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

    fk me, cant solve B because i did not get it and C was getting tle on pretest 5. ig i needed logn for C.

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

      watching the tutorial now, i get what B meant. the ranges were for each wi. man, idk what was i on during the contest, lol. should have done B. C needed a bit of observation. good contest. i panicked maybe.

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

Time will pass, and we might meet again. Looking back at the past, everybody has lived the life they wanted. From NOI2024Day2T1

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

Pretests passed, 32 ms under time limit:

And 16 ms under TL for systests.

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

Solved D and E in 30 minutes,spent 2 hrs on C and still no idea,i hate my brain.

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

    C killed me.

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

    C was brutal

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

    it is just calculating result of f(mid,n) based on f(1,mid) you have to count how many elements are in them (it is the same for both of them) and for each element x in f(1,mid) element x + mid is in f(mid,n) so if you store the number of the elements you see in first part (lets say c) you can just add c * mid to the answer.

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

    The idea is that the splitting is symmetric about the middle of the array. So, we can just follow one sequence of splitting and multiply the average value (i.e. (n+1)/2) by the number of elements that are "symmetric" to where we are currently (kind of a shit explanation, but try to understand my code).

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

    Splitting is symmetric like imagine splitting array in half then in the left half the position of the elements we take in final sum will be same for right half too. So we don't need to branch after split hence logn time complexity.

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

How to solve C?

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

    A naive approach would be to do simple recursion:

    long long predictLuckVal(long long l, long long r, long long k) {
    if (r-l+1 < k) return 0;
    if (l == r) return l;
    long long m = (l+r)/2;
    if ((r-l+1)&1) return m+predictLuckVal(l, m-1, k) + predictLuckVal(m+1, r, k);
    return predictLuckVal(l, m, k) + predictLuckVal(m+1, r, k);
}

    This gives the correct result but is very slow. We need to optimise it.

    Notice that each time we split the current interval [l,r] in 2 intervals with equal lengths, the operations done on the 2 intervals will be exactly the same in terms of splitting. The only difference between the 2 intervals we are doing recursion on is the values that we are adding.

    Let's say we are recursing on two intervals of equal length (after a split). Call them L and R respectively.

    First observation: the number of stars that will count to our luck score from L should be exactly the same as that coming from R (why? because both intervals have same lengths).

    Second observation: for each star that is counted in from L, there is a star counted from R such that m (or m+1/2) is their midpoint. Call the star that we collect from L m1, and the one collected from R m2, then (m1+m2)/2 = m. To be precise, if the split came from an interval with odd length, the relation would be (m1+m2)/2=m, else it will be (m1+m2+1)/2 = m.

    So do we really care what the value of m1 and m2 are? No. Because at the end we collect both, so we should add m1+m2 to our luck score. This is as simple as 2m (or 2m-1).

    The solution reduces to only knowing the number of stars that we should consider in only one of the intervals obtained after the split.

    The solution will be as follows: If the current interval has odd length, the answer is m + 2mX. If the parent interval has even length, the answer is (2m-1)*X.

    Where X is the number of stars that count into our luck in only the left interval obtained after the split.

    This gives a complexity of O(logN)

    You can check my code for the implementation.

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

    We need to add the yellow numbers here, notice how 6->17 has a distance of 11 (where its subarray split), 3->9 and 14->20 have a distance of 6 (where their subarrays split) and 3->14 and 9->20 have a distance of 11 (where the subarray before them split)

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

      You can also observe that with every level the sum of midpoints is multiplied by two: $$$6 + 17 = 23$$$, $$$3 + 9 + 14 + 20 = 46$$$. So we can just keep multiplying this value by two as we split. Whether we should add the current value to the answer depends on the parity of length of the subarray, and this corresponds to the current bit value in binary representation of the array's original length. The only tricky spot is the initial split. If the array has an even length, the initial value which then will be multiplied is not an integer. In the example above it's $$$11.5$$$.

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

        i had some suspicions more math could trivialize the answer even more but ultimately didn't catch that during the contest. cool problem!

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

D explanation, please

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

    use greedy answer is always multiply elements of a, b in sorted order.

    then answer only change if a[x] == b[x] on the sorted order I mean, so update answer on those incidents

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

    First, the optimal strategy is to always re-arrange b so that the relative sort order is identical to that of a.

    In other words, the maximum item of b should be at the same position as the maximum item in a.

    This will guarantee the defined product P to be maximised.

    Rearranging b initially to fit into this condition can be done using sorting (sort both arrays while keeping track of each item's initial index).

    After doing this, calculate the initial value of P.

    After that, each time an operation happens, we need to rearrange b to fit the condition. The trick is that we don't need to do sorting again. It will be sufficient to swap at most 2 items to get the new optimal arrangement.

    To make things easier, let's first sort both arrays, keep track of the initial index of each item in map (or array), call this index_mapper_a, and index_mapper_b respectively.

    In other words index_mapper_a[i] = the index of the ith item of a in the sorted version of a (same for index_mapper_b).

    To give a concrete example: suppose a = [1,5,3,2], then a_sorted=[1,2,3,5] and index_mapper_a = [0,3,2,1]

    index_mapper_a[1] = 3 because a[1] is placed at index 3 in the sorted array.

    Now if we receive a query to increment the ith item in a. We first need to retrieve the position of this item in the sorted array. We can do this using index_mapper_a. Let's denote x = index_mapper_a[i]. We need to increment a_sorted[x]. This might ruin the sort order. We need to fix the position of the incremented item in the sorted array.

    If x == len(a)-1 or a_sorted[x] <= a_sorted[x+1], then a_sorted[x] is still in the right place (i.e. the sorting is preserved).

    Else, we need to find the new position for it. We know that a_sorted[x+1:len(a)] is already sorted. So we can simply do binary search to find the new position of the incremented item. We should binary search for the first item Y in a_sorted[x+1:len(a)] such that Y >= a_sorted[x] (after incrementation for sure), we should then place a_sorted[x] just before that item. We can do this simply with a swap.

    Example, if we had [1, 2, 2, 3, 3, 3, 5]. Let's say we had to increment the fourth item. We will get [1, 2, 2, 4, 3, 3, 5]. We binary search on [3, 3, 5] for the first Y such that Y>=4. We get 5. So 4 should we swapped with the item just before 5. So we get a sorted array again: [1, 2, 2, 3, 3, 4, 5].

    When doing these operations, you should pay attention to update the index_mapper_a.

    Finally, when we obtain all these information, we can update the value of P very simply:

    We need to remove some factor from P and add some factor to it based on which item we swapped a_sorted[x] with.

    Some final notes: - The case where no swap is needed should be handled so that we don't remove/add a factor that shouldn't have been added/removed. - Adding a factor is done by multiplying the new factor with P. - Removing a factor is done by dividing P by it. - As we need the answer modulo m, we need to also apply inverse modulo using fermat's theorem and modular exponentation.

    Check my implementation for more details.

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

Hmm interesting problems but understand statements was very challenging for me specially problem E

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

perform really badly but quality contest imo. probably one of best in 2024

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

E seems significantly easier than D , especially in a contest ..

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

    how to E? i tried a couple of intuitively decent methods but they were failing that 171 tc.

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

      brute force on every vertex(as q) and count the number of valid combinations . There are 2 cases either it should be leaf or it should be adjacent to a vertex which is parent of a leaf . And you have to ensure that p in first case is not a leaf and in the second case that it is not a leaf or parent of a leaf

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

    Not at all

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

choked on C for 1hr 20 min and solved D within 25 mins :)

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

So why can't my code for problem E pass the last test case of the samples? The answer should be 171, but my code output 170.

// #pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define eb emplace_back
#define int long long
using namespace std;
const int N = 500100;
vector<int> adj[N];
int deg[N], f[N], up[N], siz[N];
void dfs(int u, int fa) {
    up[u] = fa;
    siz[u] = 0;
    if (deg[u] == 1) {
        // f[u] = 0;
        return;
    }
    for (auto &v : adj[u])
        if (v != fa) {
            dfs(v, u);
            if (f[v] > 1) siz[u] += siz[v] + 1;
        }
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            deg[i] = 0;
            adj[i].clear();
            up[i] = -1;
            siz[i] = 0;
            f[i] = 2;
            siz[i] = 0;
        }
        for (int i = 1; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            adj[x].eb(y);
            adj[y].eb(x);
            ++deg[x], ++deg[y];
        }
        if (n == 2) cout << "0\n";
        else {
            int root = 1;
            while (1) {
                if (deg[root] > 1) break;
                ++root;
            }
            for (int i = 1; i <= n; ++i)
                if (deg[i] == 1) f[i] = 0;
                else {
                    f[i] = 2;
                    for (auto &j : adj[i])
                        if (deg[j] == 1) f[i] = 1;
                }
            dfs(root, -1);
            // int ans = 0;
            // for (int i = 1; i <= n; ++i)
            //     if (f[i])
            //         for (int j = 1; j <= n; ++j)
            //             if (j != i) {
            //                 if (!f[j]) ++ans;
            //                 else {
            //                     if (f[i] > 1 && up[j] != -1 && f[up[j]] == 1)
            //                         ++ans;
            //                 }
            //             }
            // for (int i = 1; i <= n; ++i) if (up[i] != -1 && f[up[i]] == 1 && f[i] > 1)ans -= siz[i];
            // cout << ans << '\n';
            int c0 = count(f + 1, f + n + 1, 0ll);
            int c1 = count(f + 1, f + n + 1, 1ll);
            int ans = 0;
            ans += c0 * (n - c0);
            // ans += c1 * (n - c0 - c1);
            // ans += c1 * (c1 - 1);
            int gg = 0, mm = 0;
            for (int i = 1; i <= n; ++i)
                if (up[i] != -1 && f[up[i]] == 1 && f[i] >= 1) ++gg;
            for (int i = 1; i <= n; ++i)
                if (up[i] != -1 && f[up[i]] == 1 && f[i] > 1) ++mm;
            ans += (gg) * (n - c0 - c1);
            ans -= mm;
            cout << ans << '\n';
        }
    }
    return 0;
}
→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F killed segment tree successfully!

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

    We intended to let all segment trees pass so we decreased the constraints and increased the TL (std is running for about 0.1s currently)...

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

      My segment tree fell in MLE on test 4... maybe my implementation is really messy lol

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

omg jiangly accepted G and rose up to the first position in the last minutes

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

How did problem E get by the readers/testers, being so badly written?

The problem never says that (the definitions of) p and q are updated, which is rather important...

Also, the definition of dominated is really unnecessary; one can just define the caterpillar as the path and then talk about vertices in the path (or not in the path).

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

I thought my solution to I2 is wrong so I only submitted at the end due to desperation...

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

    In this case

    1
4
1 -2 2 1

    My solution outputs 2 because it thinks that the two occurrences of 1 1 -2 2 -1 1 are different...

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

Is I1 ChatGPT-able?

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

This contest has made me think my life choices....

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

A<B<D<E<C

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

    D seemed way more painful than C to me. For C you just need to abuse the fact that each tree of the same size is identical. The only difference is you need to add a constant to the tree if the base is not 0.

    For instance if you have (base 0 -> [1, 2, 3]) and (base 3 -> [4, 5, 6]), you don't need to compute the [4, 5, 6] branch of the tree, just take the computation of the base tree and add some constant 'C' * amount of nodes taken from the smaller tree

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

Man I wasted way too much time on C, couldn't implement D quickly enough afterwards

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

Finally, I think my performance on this contest was actually representative of my skill (maybe enough to finally reach expert).

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

    Congrats on reaching expert! What was the approach for E?

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

      Thanks :))

      E solution: precompute for each node toleaf[i], denoting the shortest distance from i to any leaf (using dfs pretty simply). Then, the idea is that, if toleaf[p] < 2, A wins always. So, we just consider toleaf[p] >= 2. We can consider the cases where q is a leaf and when it is not. When q is a leaf, we have n-leaves other nodes to be p, so the answer is already set initially to (n-leaves)*leaves. Then, we consider the second case, where q is non-leaf and toleaf[p] >= 2. In this case, we iterate over each node in the tree, consider it as being q, then for each adjacent node v, consider cnt[v] (which we also will have computed before) to be the number of nodes in v's subtree that are "good" (i.e. toleaf value >= 2). "good" vertices are ones that p can be assigned to. Using this info, we can compute the number of corresponding p values for the given current q.

      UPD: I should have added the key fact: if toleaf[v] >= 2, then q being "dragged" in that direction by p will result in a tie, with A and B just reversing each other's moves.

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

quite bit surprised on the fact that A, C was not GPT solvable, which is very uncommon in recent contests. problemsetters must put a lot of effort into this.

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

Couldn't solve C ..... Shi*.

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

aaaaaaaaaaa I misread problem D thinking it was increase ai/bi by x and thus harder than it really was. I didn't realise it was only increase by one until too lateee

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

ABC felt a bit too difficult, even though I enjoyed them. E is alright — maybe a bit more enjoyable if we solve for first player, but then it'd be too easy. Gap E-F is hard, but maybe it's my skill issue :). Overall felt kind of balanced.

What I can't understand is the intended solution for D: whatever you do, you need to keep track of the two sorted sets, and be able to recover an element by index and vice versa. This is either a lot of pain to implement, or a no-brainer pbds. For div1 that's alright either way (I did a pbds), but I feel sorry for less experienced participants: if you don't know pbds, you'll likely have a really hard time debugging the implementation yourself, even though the greedy idea is a good one for this position.

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

    you need to keep track of the two sorted sets, and be able to recover an element by index and vice versa.

    No, because the operations are only $$$+1$$$, you can just add to the last occurrence of $$$A_x$$$ instead of whatever random occurrence you got. This solves the problem in a much cleaner way, and without any heavy structures. You can take a look at mine/jiangly's implementations

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

      Oh, that's smart, we basically never swap elements. Then there exists a clean solution, you are right! Still not sure if it is easily identifiable on the spot — i havent thought enough during the contest because pbds was not that difficult to include.

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

        I feel like your solution doesn't work with arbitrary changes of elements. Let's say, you have a = [1, 2, 3] and b = [1, 2, 3], and then you change a[0] from 1 to 4. Then the answer changes significantly, because 2 and 3 from a shift to lower positions. Therefore, your solution also implicitly uses the fact that the operations are just +1, and the array doesn't change a lot.

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

          It probably doesn't, I indeed do use the fact we have the groups of same values. It is just the next (not obvious for me) step — that the array transforms without swapping elements.

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

    My code for D isnt that hard

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

How to do B? Thought of an algo but it became too complicated to implement

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

    If l==r this means you do not have any choice but to fill that index with L

    If l!=r you have r-l+1 choices It is mentioned in the problem that the max value of ai can be upto 2*n

    So maintain an array (arr) of size 2*n

    if l==r set arr[l]=1

    and maintain an frequency array which stores frequency of all l's such that l==r

    Now create a prefix sum array which stores the prefix sum of the arr.

    Prefix sum array is used here to find how many indices l are present which have l==r

    now coming to algo if l==r and frequency of l>1 print 0 if l==1 print 1

    if l!=r count prefix[r]-prefix[l-1]. If that value is less than r-l+1 print 1 else print 0

    that's it!

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

Did C in log^3(N) by drawing trees and observing a pattern. Ended up being more difficult than intended.

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

I feel dumb, but these are great questions. Much to learn.

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

Why is the second player in E named Aron?) Kind of confusing (at least for me)

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

I failed to pass G because the stack limit of the problem is too small, like much smaller than the memory limit. Shouldn't the stack size be the same as the memory limit?

link. After comparing my solution with some other accepted ones I'm really sure that it should have been right.

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

    As far as I remember, it should be the same as memory limit — but maybe it was just increased to 256 MB or so.

    You have a lot of memory in the global arrays, but those should be statically allocated on data segment and not on stack, though maybe Windows calculates stack overflow differently because it's a stupid OS.

    Have you checked how much call stack can grow? Make a test with maximum DFS depth, perhaps check assembly to see how much gets pushed at every call, or measure how much you need to set stack limit so it'd narrowly pass.

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

      Stack size in codeforces is 256 MB (and in problems with lower memory limit, you will sooner get MLE than runtime error from stack overflow). So that answers why you got Runtime Error.

      As to why Codeforces does this, no idea, but it has been like this for a long time.

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

        MLE is most likely an OS check. Dynamic (heap) allocation strategies are weird and OS-dependent (like memory overcommit on Linux) and can be configured; automatic (stack) allocation not so much, but I suppose it can involve an OS check too.

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

Am I the only one who struggled with B for an hour? Is there a way to solve it without Fenwick/segment tree?

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

    use prefix sum

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

      could you elaborate the need of prefix sums, i still dont get it

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

        For a segment [l, r], you need to know whether there are (r — l + 1) distinct segments whose length is 1, and they all fall within [l, r]. While taking the input, whenever l = r, update prefix[l] = 1. After taking input, iterate over the whole prefix array from left to right in order obtain the cumulative sum. Then, if prefix[r] — prefix[l — 1] == r — l + 1 for l not equal to r, then answer for that segment is 0. Otherwise, 1.

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

          Oh i got it, thanks to you i switched it to fenwick tree for range calculation, it worked. Link And stimulating for each segment is also great, Thanks.

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

      Ooh, right, that would've been a lot easier, thanks! I'm not very sharp today, haha

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

    i used prefix sum to solve it (with a typo in my locked submission.. but the logic should still be sound)

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

    There's actually no need of a Fenwick/segment tree. I used prefix sums since l and r can be atmost 2n. You can check my submission.

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

    so ones like 1 1 and 2 2 are "forced". I used a second one called "not forced", where I would put neighbors (that is, +1 and -1) of the forced ones (if they aren't also forced). Then use set operations like lower_bound to see if they exist in not forced (again, sometimes you might still need to check if they exist in forced, because at times entries won't be in not forced because there was no close entry in the forced ones).

    Don't think it makes any sense to overcomplicate like this, however.

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

    I used Ordered_set gnu policy data structure .. can look at my submission

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

    I still cannot understand what exactly problem is trying to say. Can someone pls explain me how are putting wi values and what is the criteria for a unique subsegment in problem B ?

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

      consider this testcase:

      1

      6

      1 1

      2 2

      2 2

      1 2

      3 6

      2 6

      basically, we're asked to query for each index if it can choose a value (within l to r) that is NOT taken by other indexes

      for example, on query 0, i=0 has to take 1, because that the only value it can use within its range. it does not matter what values other indexes take, AS LONG AS it's not 1 (the value i=0 is currently using). an example answer we can get is [1,2,2,2,3,2], which is a unique subsegment for query 0.

      on query 3, we have a choice on taking value 1 or 2. however, value 1 is already taken by i=0 (we have no other choice) and value 2 is already taken by i=1 and i=2 (we have no other choice). this leaves i=3 with no values to take, because every value within its l to r range are already taken. so, no unique subsegment exists for query 3.

      we need to do this for all indexes, but doing brute force will result in TLE, so we need to try something else.

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

Screencast of me writing this round in rust will eventually be available here

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

After a rather long hiatus, I participated again in a contest. Here is some feedback on the problems:

  • A: The statement is not very interesting (and unnecessarily long).
  • B: This one is a div2B datastructure problem. It is rare to have an easy problem that involves some thoughts about datastructures and this one seems appropriate.
  • C: A cute problem that I liked. It has a project-eulerish flavour.
  • D: Ok, another easy datastructure problem. I don't see the point of this one. I knew how to solve it as soon as I finished reading it, then I pushed through the pain and implemented it (and I made a mess...). Arbitrarily adding queries to a problem to increase its difficulty should be forbidden as it creates monsters.
  • E: The problem is not very interesting. I read the statement twice as it seemed so much more complicated than the solution that I thought I had misread it. This problem looks superficially very interesting but after 1 minute of thinking it is rather clear that there is no hidden structure to discover.
  • F: To solve this one I had to think for some time and I liked having a break from coding. Of course, the hard part was implementing the solution. For some mysterious reason, I enjoyed also implementing it. My solution needed a data-structure representing an enhanced array that could support: get value, get max, max one value with, max all values with, add x to all values. It was abundantly clear to me that this was doable, but not clear how. I am rather happy with the thing I implemented, which supports all operations in O(1).
  • G: Skipped.
  • H: Skipped.
  • I1: The standings suggested that I should give a try to this one. I read the statement and it did not seem particularly interesting. After thinking for a few minutes I guessed (without proof) that the greedy algorithm might work. Maybe I could have proven it, but I decided to just have some faith (possibly because the contest was close to its end...). I implemented the greedy idea in a horrible way and magically got accepted.

Overall, the contest felt average—not particularly enjoyable, but not unpleasant either. I enjoyed solving and implementing Problem F, and I think that problem B and C could be nice for contestants less experienced than me. I hated the unnecessarily long statements involving ridiculous stories about pretty weird presents as well as all the headers before the actual statements with links to stuff in Chinese (I would be very supportive of codeforces if it were to decide to ban any kind of stuff in the statements of rated contests that has nothing to do with the problem and is longer than one line).

Thanks to the authors and to all those involved in the organization of the contest.

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

    I also thought problem D was annoying, than I realised that you don't actually need to keep track of the indices.

    Simply keep the original array, and process the queries one by one (applying them to the original arrays). When a 3 is updated to a 4 it doesn't matter which 3 was updated in the sorted version, so you just find the last 3 and increment it by one.

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

    Has there been a vote or proposal ever to rid of the fluff before the actual problem statement? I'm curious how many people would support fully abolishing all of it.

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

      Getting rid of the fluff is part of the solution.

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

D fails when using std::map and std::set and cleverly swaping elements with overall time complexity of O(Q log N), but apparently passes easily when using GNU's Tree structure with very similar constant factors. Come on, test better next time. Absolute bs.

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

Goodbye Master QQ

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

Implementation of D using only std::vector: 298847993 We only need to update the last element with the value a[x] or b[x], not the exact element at index x

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

Hello everyone,

I have the following code for D:

https://pastebin.com/sJTU7KtG

It fails the second test case of the sample cases, as shown from the output:

2 3 3 6 6

840 840 1008 1344 1680 2016 2016 2016 2016

2116800 2646000 3528000 3528000 3528000 4233600 4838400 4838400 4838400

205272023 205272023 205272023 264129429

Could someone help me figure out what is wrong?

Thanks!

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

Nice problems!

DE were especially sweet, very neat and not implementation heavy. Sadly, I couldn't finish E in time as I spent too much time on CD.

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

Any hints for F? Please

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

I feel I1 is overscored than its difficulty. Normally, the subtask score is given so that it is slightly lower than its difficulty, so I guessed the difficulty of I1 is about 3500pts problem in this contest, but actually F>I1 for me.

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

Every time I participated goodbye round, my rating is also "goodbyed".

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

Thanks for the round!

My screencast with mumbling and a 8-minute post-contest recap at the end.

Two points from the video:

  • I finished I2 in 5-10 more minutes after the end of the round, and it passed systests, and it would be enough for the second place :(
  • The way I solved G, and the way I was planning to solve H if I had more time (and how Egor solved H) is to use a stress-test to verify and/or improve reasonably motivated but unproven simple approaches. Which is notoriously close to how LLMs seem to be solving problems :)
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    And of course I have solved the same wrong version of I2 as the contest authors, where we count not just arrays b, but also the ways to choose a out of b.

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

    the way I was planning to solve H if I had more time (and how Egor solved H) is to use a stress-test to verify and/or improve reasonably motivated but unproven simple approaches.

    I'm curious, is there some way to solve H without stress testing when you get WA? I don't see how anyone could deal with all the $$$a_i=w$$$ cases correctly on the first try.

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

      iirc, StarSilk told me he didn't use any stress test during his vp, and he solved it.

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

Liked the problems but not the statements. Specially the statements of problem A, B and E were unnecessarily complex.

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

    bro i could not understand B in the contest T-T. it was a doable question.

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

Problem C.

  1. Let's solve only for odd sized array.
  2. Say N=11, then 6 is selected.
  3. Some elements from the range [1..5] and some from [7..11] will also get selected.
  4. By symmetry, if 2 is selected then 8 will also be selected.(2nd element from the left half and 2nd element from the right half).
  5. This means the average of the element selected from left and right halves will be = 6 or (N+1)/2.
  6. So problem reduces to finding how many total elements(other than the middle element) will be selected.
  7. By symmetry, equal elements will be selected from both halves. So we need to only find count of elements that will be selected from a segment of size (N-1)/2.
  8. Final answer = middleElementValue + middleElementValue*(countOfElementsSelectedFromRightHalf)*2.

countOfElementsSelectedFromRightHalf can be calculated using recursion in logN time.

Similar reasoning can be used to find answer if N is even.

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

2025=45*45 perhaps the only square number year throughout my lifetime...

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

https://codeforces.net/blog/entry/137621?#comment-1233118 Is this means that intended solution for I2 is broken? If so, how do we treat about this is it wholey unrated?

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

    Yes, it is broken. It's being discussed here. Personally, I don't think making the contest unrated is a good way to solve this: there are prizes involved, not giving them to anyone would be wrong (especially when the amount of people receiving prizes is much bigger than the amount of people affected by this), so that has to be dealt with, and giving the prizes while also making the contest unrated doesn't really make sense to me.

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

Will there be any Hello 2025?

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

Why are these problem statements so confusing to me, this is way too many words for me. Like when reading the problem A statement it's: logical conclusion -> logical conclusion -> logical conclusion, just to get to the real problem at hand after that, which is actually quite easy.

I'm sure the problems are actually great! I'm just wondering if anyone else found the problem statements a bit more difficult to read then usual? But I also didn't take my adhd meds today..

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

C was very new to me, E was a very nice problem if I was not stuck on problem C, I could've solved E.

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

Can someone clarify why my submission to problem B 298887302 was accepted in Java 8 32-bit, but the same solution with submission ID 298901051 is giving a TLE in Java 21 64-bit?

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

    937ms is very close to the time limit. Maybe another submission in Java 8 will give TLE.

    The reason is that Scanner is very slow. Look for faster method of input.

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

Guys, knowledge that cins/couts are very slow on big inputs/outputs is important on contests, and in this task this was one of the problems.

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

Some cf rounds really tell me how mathematically challenged i really am. I was able to solve A,B,D but my mind died solving C. I have respect for everyone who was able to solve C by themselves.

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

Yes I'm that Aquawave in problem F as the leader of RiOI team XD

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

Can someone explain me problem B? The input and output do not make sense to me. Also the question itself. Thanks

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

    basically you have print 1 if you can give ith query a unique value like between (Li and Ri) while making sure other values in array can be anything but not equal to the value you giving to current i. basically if you are assinging 'X' to current (ith query) , you have to check it will be unique like (other query can be assigned some diffrent value). Only values that can cause concern is when Lj==Rj. I dont know if u understood. you can use line sweep or ordered set to implement it

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

      Thank you. I didn't quite get it through your explanation but understood it from one of the YouTube videos.

      Do you think the wording of the question was weird?

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

        wording in question 1 and 2 was weird and tbh it was even tricker to figure out what was required and implement it , for q2 it was hard for sure

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

Problem B:

//code for Problem B 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const ll MOD = 1e9 + 7;

void solve(){
    ll n;
    cin >> n;
    ll left[n];
    ll right[n];
    ll arr[400001];
    map <ll,ll> m;
    for(ll i=0; i<400001; i++){
        arr[i] = 0;
    }
    for(ll i=0; i<n; i++){
        cin >> left[i] >> right[i];
        if(left[i] == right[i]){
            m[left[i]] += 1;
            arr[left[i]] = 1;
        }
    }
    
    ll prefix[400001];
    prefix[0] = 0;
    for(ll i=1; i<400001; i++){
        if(arr[i] == 0){
            prefix[i] = prefix[i-1]+1;
        }
        else{
            prefix[i] = prefix[i-1];
        }
    }
    for(ll i=0; i<n; i++){
        if(left[i] == right[i]){
            if(m[left[i]] > 1){
                cout << 0;
            }
            else{
                cout << 1;
            }
        }
        else{
            ll free = prefix[right[i]] - prefix[left[i]-1];
            if(free > 0){
                cout << 1;
            }
            else{
                cout << 0;
            }
        }
    }
    cout << endl;
    return;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll tt;
    cin >> tt;
    while(tt--){
        solve();
    }
}

Can someone tell me WHY this was TLE'ing, I couldn't figure it out for the life of it and had probably my worst contest ever.

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

    there are t = 10^4 test cases at max, and for each test case you are initializing a vetor of size 400001, which makes overall time complexity to be O(t*400001) which wouldnt run in given time limit of 1 sec

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

      I don't know why I could not realize this and should have just used 2*n. Hopefully next year, I start making actual progress (: . Thanks for your comment

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

Why did GroupMatrix's rating drop, while the performance is 3114 (way higher than the previous rating)? MikeMirzayanov

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

    My final solution of G passed with a maximum running time of 9874ms(9624ms actually when testing pretests), which has a great risk of getting TLE during system testing. After I found that, I soon told Error_Yuan to rejudge that(yes, FSTs on pretests can be avoided if you told the staff). However, the rating calculation is done before that, and now I'm waiting for the rating rollback.

    Update: you can't.

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

Anyone who had a bad performance will send that he was affected by I2, and thus, all the people who had negative rating change will be unofficial which will affect the rating of other people, for example, being the 300th on 20000 participants is better than being 300th on only 5000.

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

    Surely this is false; there has to be some level of reasonability to these requests, for example a newbie with no past experience of even solving or attempting to solve D's or E's is highly unlikely to be affected by I2. In fact, it's very likely if you haven't solved everything until F that would would be affected by I2 because why would you be attempting I2 in the first place?

    edit: technically it is true, but the extremeity of the jump shouldn't be (it would probably go from 20000->19000 at worst realistically)

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

I don't know if some of the problems of this contest are solvable by major AIs! I'm curious to know, is it possible to create such div2B and div2Cs that are not solvable by paid AI's? recently heard about AI achieving AGI , is it still possible to create such div2B and div2C,D that are not solvable by these AIs? I'm just curious,as I don't have access to any of the paid AIs.

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

if u check this code for problem C 298817735 (its ecnerwala's btw)can anyone help me how they come up with the calculation for the top_left...

can anyone throws some light

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

I wish everyone good luck and success

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

Teacher SkyWave!!/se

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

Why does the Problem I2 have 2 dp tags?

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

Congratulations, @jiangly You're my inspiration and my idol.

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

Did the Near prizes get sent out?

How will I know when I got it (system notif)?

How much time does it generally take

Also if anyone is in India can they tell the easiest way to cash it

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

    They will be sent once Mike finalizes the results and shares the final table with me.

    The delay is usually due to relatively time consuming process of making sure there's no plagiarism and other violations.

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

Hello. My submission for problem D got skipped for being too similar to another one. I didn't cheat. 1/3 of my code is a template, 1/3 is fast exponentiation (both of those I can find in my past submissions for sure) and the rest is a primitive solution. The other submission's author studied in the same school as I did, but I don't know him personally and never spoke to him ever. TheScrasse

→ Reply