Kuroni's blog

Codeforces Global Round 25
By Kuroni, history, 8 months ago, In English

Xin chào Codeforces (・ω・)ﾉ

We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.

On Apr/06/2024 17:35 (Moscow time) we will host Codeforces Global Round 25.

Codeforces Global Round 25 marks the first round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.

The prizes for this round are as follows:

  • The top 30 participants will receive a t-shirt.
  • 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.

The prizes for the 4-round series in 2024:

  • In each round, the top-100 participants get points according to the table.
  • A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
  • The top 20 participants across the series will receive sweatshirts and placement certificates.

We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!

The problems were all marinated and cooked by MofK and Kuroni.

Our sincerest gratitudes go to:

Round Information:

  • Duration: $$$3$$$ hours.
  • Number of problems: $$$9$$$ problems.
  • Score distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 2750 - 3250 - 3500 - 4000$$$.

A tiny bit of personal note at the end, this is our first round on Codeforces in 3 years, and it feels a bit nostalgic to be back here again :) We eagerly anticipate your participation and let's all make it an awesome contest together!

Blooper

UPD: Added score distribution.

UPD: The round has concluded. Congratulations to the winners!

  1. Geothermal
  2. ecnerwala
  3. Um_nik
  4. maroonrk
  5. jqdai0815
  6. Benq
  7. hos.lyric
  8. antontrygubO_o
  9. cmll02
  10. AlternatingCurrent

Tutorial can be found here, and playlist of songs used in the problem statements can be found here.

Announcement of Codeforces Global Round 25
  • Vote: I like it
  • +605
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +139 Vote: I do not like it

GLOBAL ROUND COMEBACK LET'S GOOOO!!1!

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

omg kuroni round

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

As the author of at least 1 problem, hi! (updoot on the right)

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

As a tester, I love this contest. And I hope you will too!
Kuroni senpai orz

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

As a tester, I enjoyed this round and I hope you will too!

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

I pray to God that I can solve C this time.

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

Please marry me

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

As a tester, meow

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

MofKuroni orz let's gooooooooooo

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

As a tester, I hope you guys enjoy this round

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

cuteroni

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

As a tester, I need one more rating point but Kuroni say No.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Easiest way to gain $1$ rating
    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! Everyone is so excited! Which makes me even more excited! Why everyone so excited?

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

Finally!! Finally it's back!!!

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

As a tester, I can't speak too much, or Kuroni will send two Bocchi plushies to subdue me

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

omg kuroni round vietnam gm orz so cute i love u uwu

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

My waifu Ikuyo Kita is soooooo cute!

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

Omg global round

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

Kita wants to let you know something

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

good luck everyone, hope you all get a higher rank this round!!!

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

As the 🧌 coordinator, I can't participate :(

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

FINALLY GLOBAL ROUND ARE BACK!!!

I hope this would be a best Global Round ever!!

Good Luck for every one!!!!!!!

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

Is it rated ?

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

kuroni la ai ?

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

Is it rated?

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

Can somebody share the link to the blogpost that explains the legacy of CF global rounds or could just simply explain abt it.I am a bit curious to know abt it.

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

3 hours 🤢

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

As a tester, i tested

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

I hope it will not be MathForces.

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

4000 score question!

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

a

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

I know you are looking for a Vietnamese comment here

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

How hard are the questions? I mean what div?

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

Is it rated?

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

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

Dad please we need it right now, every single minute waiting is extremely painful

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

    Waiting for so long so much suffering Where are you?

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

      You are completely ignorant, holidays are coming everything is closed there's no food for days, putting someone alone through all of this is simply inhumane

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

As a participant, I will participate in this round.

Good luck everyone <3

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

leaving a comment for the culture

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

.

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

T made a mistake replacing X(his ex) else it would have been a lot of fun (XXX)

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

Let's go!!! and defeat all the questions. I can't wait to see the green accepted submission!!!!!!!

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

I hope I can solve 3 today !!! :(

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

Is it rating contest?

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

the blooper gif :skull: :eyes_with_spiral: :sob:

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

kuroli came back :((((((

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

let's see how rusty i am

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

    AINT NO WAY YOU CAME BACK FOR THIS

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

      WE NEVER SKIP KURONI CONTESTS

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

I can feel the wa energy

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

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

found amogus in Problem D. ඞ

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

genuine question, is the song for each problem from author's playlist or it's just random bangers from youtube?

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

    We know about these songs beforehand :) but they are random bangers indeed

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

      song for problem I is such a banger. RIP wowaka

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

You Bad, heat you.

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

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

I took a short break from CP, but i am glad, that i came back for this one. I absolutely liked the problems, especially ones i didn't solve. Looking forward to the editorial to up-solve some.

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

Me spending two hours thinking of C "wait what kind of simulation is needed for this clusterhex?"

Me prepassed C at 2hr: "wtf just greedily sorting?????"

I should catch a break...

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

    that's me

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

      Hell that and an absurdly stupid +4 late on B will cost me my orange for sure...

      Terrible day for me T.T

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

For problem G, OEIS saves my day!

Spoiler

I'm wondering if H is even easier than D/E or just my simple greedy algo passed the pretests?

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

    Okay so H's solution is dead simple but we spend 5 days to solve it correctly with proof. I think it's just hit or miss.

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

got 13 WA on B

How to solve it??

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

    notice that it's only optimal for you to swap numbers with index smaller than you. It's because it's better for our index to be as small as possible so we can win more matches. Notice again that we're not going to win if an element is bigger than ours but has smaller index. So, when there's a bigger element with smaller index than us, just swap them and then see number of wins. But there is another case. Consider that we don't need to swap anything or there's no element bigger than ours that has smaller index. In that case, swap first element with kth element. It's because we want index as small as possible so we can win more matches :)

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

      I stucked and do not know what to do with 2 test cases

      6 5 7 2 727 10 12 13 5 5 386397236 187533184 8314578 802929321 432147499 please explain!

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

        In conclusion we have to check for two cases. Case 1: we swap first element and kth element then find winning matches. This works because. if the elements to the left of us are smaller than its better to switch ours on the left. ex: pretend our element is 5

        1 2 4 (5) 3 10 11 -> only win one match

        (5) 1 2 4 3 10 11 -> win four matches.

        and case 2: if there's a an element bigger than the kth element with smaller index, we swap them then find winning matches. This is because if there's an element that is bigger than us but has smaller index then we cannot win at all:

        ex: ours is 5

        1 10 3 (5)

        match result: 10 10 10 -> we cannot win at all.

        swap:

        1 (5) 3 10 -> we win twice.

        After we find case 1 and case 2, then just take the bigger one.
        6 5

        7 2 727 10 12 13

        case 1: swapping kth element with 1st element

        12 2 727 10 7 13

        max(12, 2) = 12 (ours win match), max(12, 727) = 727, max (727, 10) = 727, max(727, 7) = 727, max(727, 13) = 727 -> we only win 1 match

        case 2: swapping kth element with first element that's bigger than us with smaller index

        7 2 12 10 727 13

        max(7, 2) = 7, max(7, 12) = 12 (ours win match), max(12, 10) = 12 (ours win match), max(12, 727) = 727, max(727, 13) -> we win 2 matches

        result = 2 because we find the max of the two.

        note: you don't actually need to swap element in the code if you don't want to (but you could if you prefer to). I just say swap to make it simpler. Hope this helps :)

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

    I think the solution is just: try swapping with the first cow, and see what score you get, try swapping with the first cow that beats you, see what score you get. Take the maximum of these two. You can get both scores in linear time.

    The reason this should work is: 1) you should never swap with anything later than the first cow that beats you, because then you will lose all your games 2) all the cows before the first one that beats you, you will beat, so if you swap with anything before the first cow that beats you, you might as well swap with the very first one (then you'll get to play the maximum number of matches before you go up against the first one that beats you).

    I don't know though. I have 999 WA on this as well.

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

How to solve C using binary search ?

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

    I was also initially doing C through binary search on answer but later figured out that binary search was not needed at all after getting tle on test 5

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

    i solve using heap and some maths , but somewhere i felt it was a typicall binary search question but couldn't figure out till last.

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

      can you explain it ?

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

        sort the days in increasing order of their price and pick the very first ceil(k/m) number of days and buy maximum number of possible tickets on each day. Just dont forget to increment the price of upcoming days ticket by the number of tickets bought on current day [this could be done by just maintaining a varialbe "i named it tax"]

        i used max_heap to find the ceil(k/m) number of the smallest element from the cost array rather than sorting. I did come up with a proof , but its long and i am lazy to type , if you really need it do tell me.

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

          thank you brother for the given time

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

    I don't think you need BS. just keep track of how many you've taken so far and any $$$ a_i + soFar $$$ will give you the current price at that index. then you can check if we want to take it or not. Just use sorting for minimizing the total cost you get.

    Time Complexity: $$$ O(nlogn) $$$

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

Geothermal orz, is this your first Div1 win? (assuming no FST)

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

    This was not a div 1 round, it was global round. div 1 + div 2, get it ?

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

      For the top participants (who are in div1), their ranking in a div1 versus their ranking in a div1+div2 will be pretty much identical. Thus, a div1+div2 is functionally a div1 for someone at the top of the leaderboard. They don't need to be categorized separately in this case.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it -53 Vote: I do not like it

        If you knew how codeforces rating system works, you'd know that you're completely wrong.

        Again, this was not a Div 1 round and Geothermal is yet to win his first Div 1 round.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          ← Rev. 3   Vote: I like it +29 Vote: I do not like it

          I know how the rating system works, and I know that for div1 participants at the top of the leaderboard (like top $$$100$$$ or smth), it doesn't matter if the contest is a pure div1 with ~$$$1000$$$ at least candidate masters, or if there are also $$$10\,000$$$ more lower rated participants in the contest. Someone rated $$$3200$$$ or similar is expected to place higher than someone rated $$$1800$$$ or lower with probability nearly equal to $$$1$$$, and assuming the $$$3200$$$ places high, they will have placed higher than (almost all if not) all $$$\le 1800$$$ participants, so their participation in the contest has no significant effect on the rating change of the $$$3200$$$ participant.

          If the $$$3200$$$ participant solves no problems, then they will lose more rating in a div1+div2 than they would in a pure div1. But this is not really a realistic situation, so it doesn't matter in practice.

          Technically winning a div1+div2 is more difficult than winning a pure div1, since a div1+div2 has more participants. Also, div1+div2's often might also have more good participants than pure div1's, especially when the rounds have prizes.

          Also, why are you so keen on the technical definition of "div1"? It doesn't actually matter how a word is technically defined, what matters is how the word is used in practice. And in practice div1 participants use the word "div1" to refer to a Codeforces contest which is rated for participants with no rating upper bound. Div1+div2 falls into this category, so it is called a div1 contest.

          If you reply, I probably won't be replying back anymore. I don't want to engage in arguments with people who are overconfident about things they don't understand correctly.

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

    vgtcross orz, can you please share your thought process and how do you make observation and come up with a solution for problem C it will be helpful for other people also.

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

Problem E

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

    Yeah and it's pretty easy to google

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

      Can you please tell how do you search such problems , I couldn't find it when i googled.

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

    How can i see the solution here... please help, i am not familiar with this Timus Online Judge website.

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

Nightwish feat. Jonsu — Erämaan Viimeinen big love.

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

Solved C without proving

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

    How to solve C?

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

      It is obvious that you have to buy tickets in at least p = (k + m — 1) / m days. So, sort a, and take the first $$$p$$$ $$$a_i$$$ to buy. Then you need to decide which day you will buy the least tickets. And I "feel" that it should be the day with max $$$a_i$$$ among those p days, and the index of that day is the smallest as possible (Here is when I can't prove)

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

        "the day with max $$$a_i$$$ among those p days"

        I wrote several cases on paper, and it seems to me, that it doesn't matter, which day to choose for least number of tickets, as long as the multiset of numbers of bought tickets is the same (which is of form $$$x, \dots , x, x - 1, \dots , x - 1$$$).

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

          Glad to hear you say that, as I swear it doesn't work with my random approach :v

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

          i did calculations but i cant prove why the order doesn't matter any idea??

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

            after analyzing the problem, you need to find the minimum sum {v[i] * s[i], 1 <= i <= n} + sum {s[i] * sum {s[j], 1 <= j < i}, 1 <= i <= n} (where v[i] is the initial ticket value and s[i] is how many tickets you buy in day i). the second part of the equation is just sum {s[i] * s[j], 1 <= j < i <= n}, which is equal to ((sum {s[i], 1 <= i <= n}) ^ 2 — sum {s[i] ^ 2}) / 2. But (sum {s[i], 1 <= i <= n}) ^ 2 = k ^ 2, and all you need to now is to minimize the sum {v[i] * s[i], 1 <= i <= n} — sum {s[i] ^ 2 / 2, 1 <= i <= n} = sum {- 1 / 2 * s[i] ^ 2 + v[i] * s[i], 1 <= i <= n}. this is how i proved that the order of the elements doesn't matter. after this, is pretty easy to see why the greedy algorithm works.

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

      You have to buy the maximum tickets on the day it has minimum cost, but wait it's not that simple because what you have bought on previous days ( more like will eventually buy in previous days if necessary ) will change the price in the future (i.e. can change today's price.) but we don't know whether I will or have bought anything previously at the point when I am trying to just find the minimum price day. so we must store the minimum price day's index along with how many we buy that day. later sort them according to the index, i.e. the day number as only the days previous to current can change today's price. and from that get the final answer. check this out. sorry for the template code ignore them. :) 255354516

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

    Same, and it feels tougher than D and E, possibly even F if my approach is correct.

    Though to be fair, I feel like most people would have guessed the approach to E as well.

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

      What's the proof for E? I guessed two is always possible, but did not want to submit without proof.

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

        No clue at all, I just guessed that if the answer is YES, its always possible by splitting the string into at most 2 parts. I stress tested against a few million small palindromes to convince myself and then submitted.

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

          Tbh I expected E to be much harder and felt like I'd waste my time coding the hashing solution so I stuck on D (which I also was trying to guess), after throwing a guess on C after being stuck on it for an hour. This contest was a nightmare.

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

            Yeah, I expected I would fail at implementing the hashing approach, so I just copied a Manacher's implenentation from cp-algo.

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

              Came up with the same hypothesis but couldn't implement it in time :/

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

        Disclaimer: A simpler proof may exist.

        We will show that every string falls into (at least) one of the following categories:

        • one substring works (the string is not palindrome)
        • two substrings works (there exists a non-palindromic prefix-suffix partition)
        • no solution exists

        If $$$s$$$ is not a palindrome, one substring works. Now assume $$$s$$$ is palindromic.

        If every character in $$$s$$$ is equal, no solution exists. Now assume $$$s$$$ contains at least two distinct characters.

        Let $$$a = s_1 = s_n$$$, i.e. $$$a$$$ denotes the first (and last) character of $$$s$$$.

        Let $$$b$$$ be the first non-$$$a$$$ character in the string. Now the string must look something like this: a...ab?...?a. The prefix a...ab is not a palindrome. If the suffix ?...?a is not a palindrome, we found a good split. Now assume the suffix is a palindrome.

        Let the position of $$$b$$$ be $$$k$$$. Now we know that $$$s[1, n]$$$ is a palindrome, and $$$s[k+1, n]$$$ is also a palindrome.

        This means that for all $$$1 \le i \le n$$$, $$$s_i = s_{n+1-i}$$$. Also, for all $$$k+1 \le i \le n$$$, $$$s_i = s_{n+k+1-i}$$$.

        Now take any $$$1 \le i \le n-k$$$. We know that $$$s_i = s_{n+1-i}$$$.

        $$$1 \le i \le n-k$$$

        $$$-1 \ge -i \ge k-n$$$

        $$$n+1-1 \ge n+1-i \ge k+1$$$

        $$$n \ge n+1-i \ge k+1$$$

        This means that $$$s_{n+1-i}$$$ is inside the palindrome $$$s[k+1, n]$$$. Thus, $$$s_i = s_{n+1-i} = s_{n+k+1-(n+1-i)} = s_{n+k+1-n-1+i} = s_{k+i}$$$.

        $$$s_i = s_{i+k}$$$ for all $$$1 \le i \le n-k$$$. Thus, the string $$$s$$$ is just $$$s[1, k]$$$ repeated until the end.

        Since the string is a palindrome, it must look like aaabaaabaaabaaabaaa.

        There are a few cases left. Let $$$x$$$ denote the number of $$$a$$$ between every $$$b$$$ ($$$x = 3$$$ in the above string). Let $$$y$$$ denote the number of $$$b$$$ in $$$s$$$ ($$$y = 4$$$ in the above string.)

        If $$$x = 1$$$, the string looks like abababababababa. Any substring of odd length is always a palindrome. Since $$$s$$$ has odd length, a split cannot contain only even length substrings. Thus, no solution exists.

        If $$$y = 1$$$, the string looks like aaaaaaabaaaaaaa. As the string is a palindrome, partition with one substring doesn't work. The string contains only one $$$b$$$, which can be contained in only one of the substrings. Any split with more than one substring must have a substring with only $$$a$$$, and thus, be palindrme. No solution exists.

        Otherwise, we can split $$$s$$$ into $$$s[1, k+1]$$$ and $$$s[k+2, n]$$$: split aaabaaabaaabaaabaaa into aaaba and aabaaabaaabaaa.

        $$$s[1, k+1]$$$ isn't a palindrome since the substring has more than one $$$a$$$ ($$$x > 1$$$), followed by a $$$b$$$, followed by an $$$a$$$.

        $$$s[k+2, n]$$$ isn't a palindrome, because the substring has at least one $$$b$$$ ($$$y > 1$$$), its prefix has $$$x-1$$$ $$$a$$$'s before the first $$$b$$$, and its suffix has $$$x$$$ $$$a$$$'s after the last $$$b$$$.

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

      I tried so hard in E with dp: dp[i] describe if we can divide in the first i position such that no partition is palindrome. Then dp[i] |= dp[j — 1] for all s[j...i] is not a palindrome. Do you think it is possible to do like that as I can't optimize

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

Is $$$O(n \log^2(n))$$$ intended to TLE on F?

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

    Basically, is this intended / close to the intended?

    • Q and Q.P are linked, so same logic as [problem:https://mirror.codeforces.com/contest/1918/problem/B], min inversions for Q = [1, 2, ..., n], max inversions for Q = [n, n — 1, ..., 1]. Additionally, any swap that increases the number of inversions in Q either increases the total number of inversions by 2 or keeps it the same.

    • Since we only increase by +2, if we increase the number of inversions in Q with a consistent algo, we will eventually reach any combined sum of inversions possible in the range.

    • So binary search on the number of inversions in Q such that combined sum of inversions $$$\geq k$$$. The inversions of Q can be built in the normal manner (place largest value possible while inversions > 0, then place remaining values in ascending order).

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

      I think this solution is wrong (although I haven’t figured out why yet) since I implemented it as well and got wrong answer test 8

      edit; the solution is right I forgot to cast to long long

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

What a "nice" round. :)

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

literally spent 2 whole hours on problem B received 14 WA rig myself looking for pref sum, segtree, ternary search, could've solved D if not

I'm going to buy a rope today.

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

    Tell me.... i also want

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

    LOL I looked for the exact same things but for C: pref sum, segtree, ternary search. I even have a O((log n)!) solution :skull:

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

    me today. In the case that K is bigger than the index of the first cow with bigger rating that our cow i didn't contemplate that it could be another cow with bigger rating than K between the first cow with rating bigger and K. it cost me 6-7 WA and ruined my contest... very sadge.

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

I guess I have been to enter an Educational Round.

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

Got reality checked so hard, spent too much time on C couldn't think of the others!! anyways will take the L.

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

I regret registering in this contest Out of my stupidity, I'll find myself a rope.

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

Damn, spent 2 hours trying to figure out why my code gives wrong answer on pretest 2 for problem D(

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

    They really threw me off with max shops as $$$60$$$ and $$$1e18$$$ in the bounds. I spent >2 hrs on the completely wrong bitmask approach.

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

Missed D, can't think about "no" case :sob:

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

Proof of C: Need to minimize the expression $$$\sum_{t=1}^{n} (\sum_{i=1}^{t-1} x_i) \cdot x_t + a_t \cdot x_t$$$ subject to $$$0 \leq x_t \leq m$$$ and $$$\sum_{i=1}^{n} x_t = k$$$. By algebraic manipulation, this can be simplified to $$$\frac{k^2}{2} + \frac{\sum a_i^2}{2} - \frac{1}{2} \sum_{t=1}^{n} (x_t-a_t)^2$$$. Note that $$$(x-1)^2+(y+1)^2 \leq x^2+y^2$$$, for any two distinct integers $$$x>y$$$. Thus greedy solution works. Sort array $$$a$$$ and choose the maximum possible quantity in each step.

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

    I think everybody pretty much did "Proof by AC" for this problem lol.

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

I did C greedily purely based on intuition and made a implementation error, then spent a hour and made 2 WAs thinking it's a logical error :/

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

2 solves for Problem I. I believe I was able to derive a solution that would run in O(k*E*log(E)) which would be 2 billion iterations in worse case, so too slow. Really curious what the approach was to that one. If k <= 10^6, it is a much easier problem.

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

I am so close to solving F. I figured out how to determine YES or NO, but I don't know how to construct the answer in less than $$$\mathcal{O}(n^2)$$$ time. Could someone give me a hint? Thanks.

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

    How do you construct a permutation of size $$$n$$$ with exactly $$$k$$$ inversions? Needed algorithm is very similar

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

      I will try to fill in all integers from $$$1$$$ to $$$n$$$. I will maintain a variable pos starting from $$$n$$$.

      If we put the current integer into pos then the number of inversions will be increased by (pos - 1) since all blanks before pos will be filled with integers larger than the current one. If (pos - 1) is too large then just decrease pos and try again.

      The problem is, in this specific scenario the number of increased inversions is kind of "continuous". You can always find a position to fill in. However in problem F it is not the case.

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

        Ok, thats another way to construct a permutation with exact number of inversions, idk maybe its possible to solve with it too? But what I did: I iterate on positions from $$$1$$$ to $$$n$$$ (not integer) and see what number do I place on this position. It's either minimum available number or maximum available number until you are in a spot when you can construct all remaining suffix easily

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

Nice set of problems, thanks!

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

A is harder than D

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

Summary of the contest

Still love the contest though lol, I think the problems are nice

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

What is the idea behind D?

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

    If n == k, then you can only have one stall with price = 1, and k > n is trivial.

    Now, you can observe that for k <= ceil(n / 2), you can always have two stalls, with the first having price n — k + 1 and the second having price 1. This lets you construct an answer for all k <= ceil(n / 2).

    Now, if k doesn't lie in either of the ranges, i.e. k > ceil(n/2) and k != n, then you can't construct an answer. Since you k < n, so you must buy k/x jewels from the first stand, where x >= 2, which leaves you with less than floor(n / 2) coins and at least one jewel and now you can buy at max floor(n/2) jewels, i.e. you have at max floor(n/2) + 1 jewels, but as k > ceil(n/2), you can never reach your goal

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

      Wow! Thanks a lot!

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

      how you are left with n/2 coins if you take amount n and first stand x as 2, coins remaining would be n % 2.. ?

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

        I wrote that x >= 2, and since k < n & k > ceil(n/2), what's the maximum reminder you can get for k in this range upon division by n/x(or k/x since you must buy at least one jewel) for x >= 2? It is floor(n/2) when k = n — 1, and x = ceil(n/2).

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

Yet another round full of constructive problems. My brain has already crashed.

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

Nice problems, surely deserves a Global Round!

Though G is somewhat technical (We can use this method for all problems of this kind), I enjoyed an unexpected cubic formula.

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

    Yeah honestly I'm still tripping myself over that comment to this day. What does he mean by "for all problems of this kind"? From my understanding maybe he means if we describe state $$$S$$$ as a sequence $$$(s_{1..n})$$$ then we can just use the potential function trick. But surely there's gotta be some additional conditions on the transitions $$$S \rightarrow S'$$$ right? How can we be sure that solving for potential functions actually gives a solution when there are a lot more equations than variables?

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

      In fact I don't perfectly understand "all problems of this kind", either, but I interpret it as: we should try to construct a potential function when we see a problem with a Markov process whose states are points in high dimensional space but the transitions are "locally". From my experience it is almost(?) always the case that $$$\sum_i s_i$$$ is constant.

      Also, there is a Japanese editorial which tries to find a nice sufficient condition for this method to be useful.

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

My solution for problem E ( But I am not sure whether it'll pass the system tests ):

I had an intuition that if the answer is yes, then you can divide it in one prefix and one suffix. Hence, I picked a random index 60 times, and checked whether a division of a prefix and suffix bordering at that index gives two non-palindromes.

Code

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

It's actually a Battle Cow. Spend more then 2 hour+.

B

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

The greatest contest i have ever participated.The examples are so strong that I could pass examples even when I misread the statements.Really love it!

btw,you see D $$$k<=60$$$,in fact $$$k\le 2$$$; you see E $$$k\le n$$$,in fact $$$k \le 2$$$.So cool,isn't it?

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

    Ough, that's big number of WAs. When I am quite sure that my solution is correct, then after the first WA I write a stress, even for first problems.

    So cool, isn't it? — yes, I don't see a problem here.

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

      In fact,each time I submit,I found a new problem.Passing examples only meant I wrote a compiled code at that night.That's really an awful experience.

      I don't think it's correct to hide the constraints of constructing steps in this way,which makes this problem's discrimination quite randomized. At least I hate it.

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

        Wait till you get to know of the old contests where writing compiled code = passing pretests.

        I dont see any issue with weak samples and wish more authors had weak samples. Its upto you to ensure that your code is right, samples imo should only be for verifying that you understood the problem right.

        I do make an exception for problems where the implementation might be difficult/tricky however, but most of cf problems arent like that, and you get wa because you are guessed.

        Personally, when i guess (and I do occasionally), i dont blame my skill issue on authors. Maybe try proving? I was completely sure of A — E when submitting

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

          Well,I could say that I was not guessing with problem BCE that night(Eventually I passed them).I just wrote,and got WA,and found the examples useless at all.

          That's also other reasons:I misread C;I solved E in a very difficult way at first; I thought about problem B with a incorrect proof. But all of these couldn't be checked by examples,and I was not patient enough,finally led to a bad result.Unlucky,but on another hand coz I'm still too weak.I posted this text because I was very unhappy and my head was totally a mess at that time,so maybe it's a bit funny.

          IMO,I think examples are used to check our ideas and common situations.If you don't want to give samples make sense,I think giving no samples could be a better choice(show the attitude to the contestants,but Codeforces seems not to allow this)

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +21 Vote: I do not like it

            "IMO,I think examples are used to check our ideas and common situations.If you don't want to give samples make sense,I think giving no samples could be a better choice(show the attitude to the contestants,but Codeforces seems not to allow this)"

            no i want samples to be there, but on problems where people will make lots of wrong guesses, i support making them weak on purpose so that guesses can be punished. Not putting any samples is too much and will lead to even more people just misunderstanding the problem.

            → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            We actually tried pretty hard to make the samples useful. For example, B's samples highlighted the harder of the two cases in the intended solution, D's samples showed that it is impossible to solve when $$$k > \lceil n / 2 \rceil$$$, and for E we showed that a palindromic string can indeed be partitioned into non-palindromic strings.

            I believe luck was just not on your side on that day :( We didn't try to manipulate the samples in any way that obstructs people, but constructing samples that counter misreading is really hard because there are 10 million ways one can misread a problem ...

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

              I could only see that I was very unlucky that night...And all in all,the problems are interesting and thanks for your effort!

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

Hmm, for last several months this is the third problem which requires checking if substring is a palindrome using hashes.

1951E - No Palindromes

1943B - Non-Palindromic Substring

ABC331F — Palindrome Query

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

    "Requires" is too strong of a word. 1943B - Non-Palindromic Substring can be solved without hashing, and my solution to 1951E - No Palindromes even uses the naive algorithm for checking if a string is a palindrome.

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

    My solution to E today was casework.

    I split into segments of consecutive characters. If even number of segments, we can just pair segment[i] to segment[i + 1] and we're done.

    Odd number of segments: if there is a position where segment[i] != segment[i + 2], we can make a segment starting from i + 1 and extend it equally as much as possible to both left and right. After that, there might be an even number of segments left which we can pair off just like above.

    Now we have alternating segments. We can look for a segment[i] where i is odd (0 indexed). If the length of segment[i] >= 2, we can break into two distinct segments, and then pair up like the even case.

    If we still have not found anything, we can look for a segment[i] where i is even and i is not the first or last segment. If the length is >= 2, then we can s into two strings [0, x] and [x + 1, n — 1] where s is somewhere in segment[i] (basically split somwhere in segment[i]).

    Now the only thing we should have left is an odd number of alternating segments of length 1. We can prove that this is impossible to split because after splitting, there is guaranteed to be at least one odd length segment but this will always be a palindrome.

    Submission: https://mirror.codeforces.com/contest/1951/submission/255365657

    Unfortunately, I did not finish this during the contest qwq.

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

Clean code for C:

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    l = list(map(int, input().split()))
    l.sort()

    ans = 0
    c = 0
    for i in l:
        ans += min(m, k) * (i + c) 
        c += min(m, k)
        k -= min(m, k)
    print(ans)
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    any proof why greedy works here?

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

      Basically, when you buy x of one ticket all the other tickets prices' will get raised by x. What this means is that you will add this x to your answer, and the order of when you add doesn't matter. So, we can greedily pick from the smallest ones, raise the prices, and continue, and this will yield the same answer as if you picked them in order. I hope that makes sense.

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

What could be the ratings of C and D??

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

Finally...finally!!!!!!!!!TAT

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

CM finally?

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

A-E probably worst set i've done since traktor round. Maybe it gets better after...

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

Does anyone know why the first submission for E is skipped? Submissions for Global Round 1951

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

How to D?

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

Is there a solution for D using $$$O(\log V)$$$ stalls? Otherwise what's the purpose for setting the limit to $$$60$$$?

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

    Mainly to subvert guessing, but also

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

      The subversion did worked, to nearly all of the fellows in my dormitory.

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

    The problem would've been way easier with a limit of $$$2$$$ imo.

    $$$60$$$ did make me wonder about $$$O(logV)$$$ solutions at first. That confusion was probably intended.

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

    You can see that $$$60$$$ is the maximum number of stalls that can actually be used (by the standard 'mod operator at least halves' argument) so effectively it is setting no limit.

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

    I guess

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

    Probably, these authors wanted to have a hand in creating April Fools Contest too

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

Thanks for amazing comeback of GR!
How to came up with problem C? It has very cute conclusion though it has very natural settings.

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

    Glad you liked it!

    Here's the lore for the problem:

    One day I randomly thought about problem A from this legendary TMW video and wondered "how could I make this problem more interesting"? Then I came up with adding the tax (note that the original only has $$$m=1$$$ so adding the tax only increases the answer by $$$\frac{k(k+1)}{2}$$$, the greedy obviously still works). Then I realized allowing to buy $$$m$$$ items per day doesn't change the strategy as well! (I then tried to have different limit for different days but it obviously didn't work)

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

D felt like an april fools problem, the main difficulty is figuring out which trick the setters are trying to pull (like putting s <= 60 and not putting n = k in the samples)

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

Thanks for the round! Though Im most likely biased I think all problems till F are very nice (and no idea about GHI) :)

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

May there be no constructive problems in heaven.

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

yo koruni top 1 sever vn i love u <3

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

I feel like my experience was quite unfortunate:

I submitted D, thought I had correct proof, WA2'd. Realized my proof was incorrect, so tried to prove for a while. Couldn't come up with a counterexample, so brute forced n and k up to 1000 and that didn't cause a counterexample. Gave up on proving, and realized that my original solution was correct if I printed long longs instead of ints, so wasted like 30mins.

E: Guessing the solution is really obvious, but I also tried to prove. Gave up on proving after a while and AC'd.

F: Really easy and free, since it's a constructive there isn't anything to prove, but wrote a slightly incorrect solution because I wasted too much time trying to prove earlier problems.

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

C was very cool!

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

I got TLE #47 on problem E because wanted to make sure that no solution of length 3 exists. My solution did approximately 50N palindrome checks with hashes and shouldn't fail. CF servers are very bad and it costed me a lot of score :(

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

    After the contest I found out that 43N checks passed in almost 2 seconds. Codeforces servers are very slow, unfortunately. Where can I found the exact hardware description of CF servers? cc: MikeMirzayanov

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

      Your code ran twice as fast on C++20 64-bit 255374818

      Replacing endl with \n also make it AC on C++17 32-bit 255375660

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

    It's not really the server's fault. The constraints here are $$$10^6$$$ (a bit higher than usual), and you're doing $$$50N$$$ checks with double hashing and checking both sides, with double modulo application for each computation. You're essentially doing $$$400N$$$ mod operations. Now if it were addition or bit operations, expecting $$$4*10^8$$$ operations in 2 seconds is reasonable, but that many MOD operations are quite slow and I'd be surprised if it's much faster for you locally.

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

After seeing the solutions of top rankers, I wanna kill myself.. Problems were so simple and elegant ,.,..

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

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

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

D won with me. GG

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

Can I ask what were your expectations when you set Problem E at that position? Were you thinking that many people would guess or rather thought, people would not guess since it is E, it can't be that easy. Just curious? (I wish I submitted D:)

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

First Div. 1 win! The second hour of this contest (solving FGH in a total of an hour after taking 52m to solve A-E) was probably one of my best-ever comebacks, up there with solving CD in the last ten minutes of Round 706 and solving five problems with my team in the fourth hour of NAC22. Very memorable contest; thanks to the authors!

Feedback on the tasks: A: Good enough as the easy problem. Samples are weak and didn't include the exactly two 1's case, which led me to take an unfortunate early penalty.

B: Good problem. It took me a while to really wrap my head around the setup, but once I did the solution works out pretty nicely.

C: Nice problem; the solution isn't immediately obvious but is relatively easy to see once you write out the price function formally.

D: Fine problem. A bit more focus on guessing than I'd like, but in fairnessonce you just try a few cases I think the approach is pretty well motivated.

E: Not my favorite problem, mostly because I suspect from post-contest discussions that most people who implemented the easiest solution (checking if any one-split approach works) didn't prove that their strategy was correct. There's also an alternative casework solution (which I implemented) where validity is easy to prove but implementation is much longer.

F: Nice problem; permutation compositions are always intimidating, but in this case looking at the number of inversions each pair (i, j) will contribute makes it a lot more clear what to do. Figuring out how to construct the permutation took me a few more minutes than I'd have liked, since the ideas I had seemed infeasible without some kind of fancy data structure, but then I realized that the construction always follows a simple pattern, after which the implementation was pretty straightforward (especially because the only data structure required is OST).

G: Very good problem--a bit on the standard end (especially for any contestants preparing for quant trading interviews?), but evidently it wasn't well-known to many participants. I hadn't seen this exact setup before, but I had seen enough very similar problems that I immediately knew how to find the probability that each marble is the last one standing and that I needed to compute the expected time until each marble is the only one left, conditional on that marble being the last one. The idea is nice enough that I really liked the problem, conditional on most contestants not having seen it before.

H: Good problem, but strangely easy for its position imo. I might have gotten a little lucky, but it felt like the first thing I tried basically worked right away. I think this is easier than G (and one could argue that the difference in solve counts is just the leaderboard effect).

F and G were my favorite problems from the round. I had to spend a bit more time on the easy problems than I would have liked due to doing casework on E and taking penalties on A/B (though both were really my fault for some pretty silly implementation errors), but the back half of the contest was very nice. Thanks for the round!

As an aside: after this month I'm starting a new job, and I expect to have significantly less time to train. Given that I've accomplished the bulk of what I've set out to do on CF, I think there's a pretty good chance I retire from rated contests at least for the time being. That being the case, I'm hoping to continue to engage with the community by regularly testing rounds, so if you're an author looking for testers for your upcoming contest, please feel free to DM me!

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

Nice round. Thanks a lot MofK Kuroni and all testers.

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

I got so many WA in B.I even use force and try to solve it but in vain.I want to swap(0..n,mycow) and calc how many matches can my cow win, and calc its max, finnaly I swap it again to recover cowList.But I got VERRRRRRRRRY many WA .How can I improve it. :(

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

I'm very unsatisfied with this "unbelievable" round

3 constructions,2 of them use k < 3 conclusion

guess guess and guess

I can't learn anything except guess from the "global" round

I'll DOWNVOTE it

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

    My thoughts exactly. I guessed C, D and E and didn't get AC on neither D nor E because I was scared to write those guesses. Judging from the comments majority of people who solved them did not even prove their solutions to either of these problems which just makes the contest experience awful.

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

    maybe try proving?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      well D is just plain bad even if the guessing is really easy to prove

      would be far better if the number of stalls are $$$\leq 2$$$ (although it may not be D anymore)

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

        I mean, we can argue about quailty of problem D, because its plain math, and someone dont like it in CP contests, sure

        would be far better if the number of stalls are $$$\leq 2$$$

        However, I really dont understand this take. I think problem would be worse? Because with $$$\leq 60$$$ I just solved problem the way it is, in the end just noticed that it takes $$$2$$$ at most, ok fine, go next. Like, I never guessed "hmm maybe $$$2$$$ is always enough?" while solving problem, and I want to believe that most participants didnt too? Because this really seems like a completely desperate out-of-nowhere guess without motivation behind it?

        If problem had $$$\leq 2$$$ in statement, that would be very weird constant which would attract attention in the first place and completely changed the line of solving a problem, making it worse

        Also $$$60$$$ is a maximum theoretical limit since $$$n \mod x \leq \frac{n}{2}$$$ for all positive $$$n, x$$$, so this exact constraint seems motivated

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          yeah, i kinda agree with your point. now that i look at it, the $$$\leq 60$$$ constraint is very much reasonable, especially seeing that the actual mechanism of how Alice spend the coins resembles the modulo operation for coins and division operation for jewels. i'm probably just mad about this constraint because of how it deceived me into thinking about bitmasks solution before even realising it's just the nature of modulo itself. still, D is overall very weird in my opinion, probably because the solution involves some guessing.

          anyways, good point. upvoted :>

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

I Just want to share my sadness:

TLE on testcase 46: https://mirror.codeforces.com/contest/1951/submission/255345491

AC: https://mirror.codeforces.com/contest/1951/submission/255365135

One code IS in C++17, while the other one is in C++20. I would get master with this ac :(

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

    Same here: https://mirror.codeforces.com/blog/entry/127943#comment-1137290 But you shared wrong link to the second submission. I think something is wrong with C++17 performance, because my solution (https://mirror.codeforces.com/contest/1951/submission/255350123) should barely exceed 1 second, definitely shouldn't even be close to 2 seconds. cc: MikeMirzayanov

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

      If in not mistaken, i think c++20 runs long long int faster than c++17, but idk why the pretests dont have a case that it is a bunch of 'l', but it is what it is

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

      I guess this is due to the difference between 32-bit and 64-bit -- long long is slow on 32-bit architecture.

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

        It is slower, but why is it so slow? At least I think there must be hardware description of CF servers somewhere.

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

          A long long does not fit in a machine register, so every operation on long longs expands to a few machine instructions (where one instruction is enough for 64-bit) -- I think this is the primary reason of slowness. Also IA-32 has very few general purpose registers, which makes values are read from or written to memory more often.

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

Thanks for the round, prove of C is beautiful, and I learn something today :)

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

Im finally Expert!!! Thank you Codeforces!

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

I've just upsolved problem E, can't believe it's AC, wow! I have no idea why E seems a lot easier than C and D.

Haskell submission

Thank you guys for an amazing contest!

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

Got the wrong answer on D because of Python. Python does not divide bigger numbers correctly. :(

from math import ceil from decimal import Decimal

def solve(): n, k = map(int, input().split())

if k > n:
    print("NO")
    return
elif k == n:
    print("YES")
    print(1)
    print(1)
elif k > ceil(Decimal(n / 2)):
    print("NO")
else:
    print("YES")
    print(2)
    print(n - k + 1, 1)

for t in range(int(input())): solve()

This is the code on which I got the wrong answer. Dont want anything but wanted to share my misery.

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

    May be ceil function is not working, try by replacing it.

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

      This works

      from math import ceil from decimal import Decimal

      def solve(): n, k = map(int, input().split())

      if k > n:
    print("NO")
    return
elif k == n:
    print("YES")
    print(1)
    print(1)
elif (k > n // 2 and n % 2 == 0) or (k > n // 2 + 1 and n % 2 == 1):
    print("NO")
else:
    print("YES")
    print(2)
    print(n - k + 1, 1)

      for t in range(int(input())): solve()

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

Guessforces

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

Felt the samples very pretty weak. Had wrong attempt in almost every question :(

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

Really good contest. D was really close to be my first AC D in div1+2. Thanks for the authors! Hope to see other contests of yours

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

Why everyone finds D ques difficult?

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

Is the song from Problem D on Spotify? I found this https://open.spotify.com/track/1TVFphEyfjzEIir70656d4?si=68360585a1254339 but this is without Jonsu :/

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

TaklaOi orz?

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

Thank you guys for an amazing contest!

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

intuitionforces

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

When you thought you could solve the problem F without a stress test :'(

Screen-Shot-2024-04-07-at-01-10-11

And also in my opinion H was a very easy problem for the position H.

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

G is absolutely beautiful!

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

hi everyone, mwah. i love yall. happy contest day! wish you good luck. mwah. (please downvote me)

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

Food and water is basic right really

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

"Xin chào" is similar to Chinese pinyin（

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

haha funny picture

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

My solution to 3rd one got skipped, but I did not cheat. I do have conclusive evidence, but my source for inspiration was this GFG link(https://www.geeksforgeeks.org/maximize-number-of-elements-from-array-with-sum-at-most-k/)

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

    Hi, even i got the mail but for problem B mentioning the people i don't even know. What should be done in this situation because the logic was quiet very basic.

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

    Please tell something what can be done

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

Hello everyone, I got a mail saying my solution is copied. Many ids are mentioned which i don't even know. I don't have any idea how it is same because i wrote it myself and also the logic was quiet very basic. I don't know now what to do in such situation please if anyone could help

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

my solution is skipped because it match with one person 3rd question was very simple so there is possibilities that many people have same approach to solve may be solution is similar pls undersand

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

Who gets t-shirts?

→ Reply