Блог пользователя maomao90

Автор maomao90, история, 11 месяцев назад, По-английски

Hello Codeforces,

We are very glad to invite you to participate in Hello 2024, which will start on Jan/06/2024 17:35 (Moscow time). You will be given 8 problems and 2.5 hours to solve them. One of the problems will be divided into two subtasks. The round will be rated for everyone. There will be at most 2024 interactive problems, so please read the guide for interactive problems before the contest.

All the problems are written and prepared by me.

Spoiler

We would like to give our sincere thanks to:

The score distribution is $$$250 - 500 - 1000 - 1500 - 2250 - (1500 + 1500) - 4000 - 5000$$$.

Hope everyone will enjoy the round!

Congratulations to the winners!

  1. ecnerwala
  2. ksun48
  3. VivaciousAubergine
  4. gamegame
  5. cnnfls_csy
  6. maroonrk
  7. tourist
  8. Geothermal
  9. kmjp
  10. yosupo

Congratulations to the first solves as well!

UPD: Editorial

Анонс Hello 2024
  • Проголосовать: нравится
  • +2422
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится +157 Проголосовать: не нравится

As a tester I went from expert to specialist during the making of this round

»
11 месяцев назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

as a tester, I can happily tell you that this round is surely one of the rounds of all time.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Congratulations to everyone on the first competition of 2024! YAY!

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    I'm 1330. Is this round too difficult? Don't wanan lose morale in the beginning of the year xD

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      Bruh, rating doesn't matter, I'm also 1330, And even if I lose 1100 rating I Would be happy bcuz of the experience I've gained, it's all about learning nothing more

      just enjoy the problems and chill, rating doesn't matter

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why do you care about rating ? If you care about rating so much you can't improve in long run , see my graph I have lost expert but giving contests will only allow me to improve faster than people who are camping in certain rank

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what does this mean, will it be harder than usual ?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I wouldn't normally expect that from a round but this is surprising truly amazing work guys.

»
11 месяцев назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Please open our correspondence

»
11 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hope to have fun in $$$1^{st}$$$ contest of $$$2024$$$.

»
11 месяцев назад, # |
  Проголосовать: нравится +365 Проголосовать: не нравится

as a tester

Screenshot-2024-01-02-191045

»
11 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

waiting for this contest...

»
11 месяцев назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

My last wish for Goodbye turned out true, so purely trying my luck, hope to become IM!

»
11 месяцев назад, # |
  Проголосовать: нравится +198 Проголосовать: не нравится

Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶

»
11 месяцев назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

This is my first "Hello Year" contest.

I promise to solve at least 3 problems!

»
11 месяцев назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

As a tester, I can guarantee that this will be the best round of the first week of 2024

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lol, I can confirm that as it's the ONLY round in the first week of 2024.

»
11 месяцев назад, # |
  Проголосовать: нравится +267 Проголосовать: не нравится

I was forced to test.

»
11 месяцев назад, # |
  Проголосовать: нравится +172 Проголосовать: не нравится

As a tester, there is a non-negative number of problems in the problemset, and at least one person will win the contest.

»
11 месяцев назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится

As a iLoveIOI, peepeepoopoo

»
11 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hope this contest will be good, unlike last contest :)

»
11 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Scoring distribution?

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Hopefully there won't be any more googleable or oeisable problems in this round

»
11 месяцев назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Please, don't be mathforces this time

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

    But math is fun...

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится -64 Проголосовать: не нравится

      Using algorithms is more interesting than doing math

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Sry to tell you but the fact is you can't be a good algorithmic programmer without being good at math

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится +78 Проголосовать: не нравится

          Best problems are when math, algorithms, data structure and implementation are in balance. When it's overly biased like OEIS lookup of single number input it's not fun.

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          talkig of maths, I want to ask about the last contest"bye bye 2023", problem B.

          In the case whereb%a=0, why did we assume that the lowest divisor of b is equale to the lowest divisor of x ?

          • »
            »
            »
            »
            »
            »
            11 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            yep , i do also have the same doubt. someone please help bruh..

          • »
            »
            »
            »
            »
            »
            11 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            When b % a = 0, you'd know that b = a p, where p is the smallest prime in x. Why? Let's assume that p was not the smallest prime in x, then a (b/p) would not be the second largest divisor as you'd be able to choose a smaller prime. Anyway, b is only missing this one prime, so x = b p. p = b / a, so x = b * b / a.

          • »
            »
            »
            »
            »
            »
            11 месяцев назад, # ^ |
              Проголосовать: нравится -6 Проголосовать: не нравится

            you will find the best answer here after min 13 https://www.youtube.com/watch?v=6vbL_jd5Ghw

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        Algorithms are math

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        But math is also a algorithm,right?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Math is Life

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Tfw yet another genfuc question shows up in Div1.

»
11 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Interactive problems are awesome!!!

»
11 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

3amy Amrharb <3

»
11 месяцев назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Guys remember to not upvote the blog before the contest.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hope this will be better than "Goodbye 2023"

»
11 месяцев назад, # |
Rev. 4   Проголосовать: нравится +26 Проголосовать: не нравится

Hope Hello 2024 != Good Bye 2023

»
11 месяцев назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

Hoping this contest brings the coordination back on TrAK

»
11 месяцев назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

I ran some code and managed to optimise the upper bound on the number of interactive problems to $$$7$$$ from $$$2024$$$.

I'll write a formal proof of my algorithm later and edit that into this post.

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I hope this round is better than before.

»
11 месяцев назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

Fun fact: 2024 is divisible by 11 and 23

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hope that we'll have $$$\mathtt{fun}$$$

»
11 месяцев назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится
Spoiler

Sounds more promising than Goodbye 2023.

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I hope to kick off 2024 by becoming Pupil after this round.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Same

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится -18 Проголосовать: не нравится

        You can submit 10 WAs on A and then resubmit it 100 times.

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Fortunately, WA penalty doesn't do anything unless you get ac, and you can't get less than 30% of the points for a problem no matter the penalty.

          Submitting 1234567891 wrong hacks should work though :))

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

18o3 sir as a tester orz...:)

»
11 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Let's have fun in the first contest of 2024! Wishing everyone a positive delta!

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    It's annoying how every blog announcement has like 5 of these "positive delta" wishes, even though it is impossible for everyone to get a positive delta

    Ahem, back to troll content: Good luck eveyrone! Hope you all get +200 delta in contest and reach new rank in contest!!1!!1 Hope i can reach my dream rating of 800

»
11 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

the last contest was "good bye rate" ... this contest going to be "hello rate" what do you think ?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

goodbye 2100, hello 2000

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

We hope this will be better than the previous one

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

18o3 orz

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello 2024

»
11 месяцев назад, # |
  Проголосовать: нравится -65 Проголосовать: не нравится

Clashing with LeetCode Biweekly. Skipping this one.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +150 Проголосовать: не нравится

    For the 69'th time, its not clashing with leetcode biweekly, leetcode biweekly is clashing with it

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      This is what happens when an unstoppable force meets an immovable object.

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится -91 Проголосовать: не нравится

      LC Biweekly always happens on the same day. CF contest happens randomly any day so you are wrong

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +56 Проголосовать: не нравится

        Consistency of timings is not a measure of quality, if anything it is the reverse since the round nust happen even if the problems are not up to the mark

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          "codechef starters = bad" ~ codechef admin

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится -64 Проголосовать: не нравится

          I feel like LC has better quality questions than CF. Most of CF rounds are Mathforces af like Good Bye 2023

          • »
            »
            »
            »
            »
            »
            11 месяцев назад, # ^ |
              Проголосовать: нравится +20 Проголосовать: не нравится

            you are delusional, LC has the worst questions known to mankind, practically every single problem is stupid and standard and well known

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      This has 69 upvotes. It's too perfect.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just solve LeetCode Biweekly in 5 minutes

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

18o3 orz tester

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

There will be at most 2024 interactive problems — what does it mean?

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

As-Salaam-Alaikum 2024

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully, I was able to solve first 4 problems!

»
11 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

as a noob ,I hope I can solve problem 1 within 1 minute and not get hacked

»
11 месяцев назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

As a tester problems are good...but I'm not a tester

»
11 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

moo

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится -149 Проголосовать: не нравится

Do not be a second 74TrAkToR or marzipan again!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How humorous! I am looking forword to participating in this round!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hyped up by the blog !

»
11 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Please provide scoring distribution

»
11 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

I wish 2.5 hours were 2 hours 50 minutes

»
11 месяцев назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

I feel the contest will not be very good

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could a beginner participate this contest ?

»
11 месяцев назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Can the Python be used while solving in here?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can solve with any language that can be used to solve a problem in the problemset (Including python).

    But I wouldn't recommend using it as it's much slower than c++, you may need to further optimize your solutions in order to pass the tests.

    If you are planning to use Python submit using PyPy instead of Python which is usually much faster.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For very early problems definitely. In harder problems, especially with more complex implementation, you can run into TLE, but at that point learning to code in a suitable language isn't the hardest part.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a newbie i tried the sample interactive problem but solution was incorrect and i cannot see correct solutions of other people. Can someone please help me with this one

»
11 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hope it can make me excited instead of the frustrating "Good Bye 2023".

»
11 месяцев назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

74TrAkToR won't be the coordinator of this contest. Yay!

»
11 месяцев назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Guys, I am a complete beginner to programming. I have started learning basics of C++ from sololearn.com. If there is anyone who is hearing me, who is candidate master or master. Please can you help me? I want guidance for CP.

I want to dedicate 1 year for doing CP full time. I want to utilize this time to get maximum output.

Thank you.

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i can not wait to start it!!!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope this contest has the opposite number of votes as Goodbye 2023.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve the first 3 problems

»
11 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

will we see "happy new year" instead of "accepted" in this round?
MikeMirzayanov

»
11 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

omg mao zedong round orz orz orz

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't usually love contests with 500 point for problem B

»
11 месяцев назад, # |
  Проголосовать: нравится -72 Проголосовать: не нравится

can someone help me with this question

A brave Knight "A" has an array of monsters to face, and will use a combination of might and magic to defeat as many as possible. In this challenge we'd like to know if the knight is successful at defeating them all, and if not, how many monsters are defeated. A can see the monsters and their order ahead of time. Despite being evil monsters they will politely queue and challenge A in the current order. Knowing this, A can plan what to do so that it is optimal.

The first monster will always be defeated by A's squires while A prepares for battle For each other monster there are two possibilities :

1.If the current monster is weaker than the previous one (i.e. monsters[current] < monsters[current-1]), The enemy surrenders — what goblin would face someone who has just defeated a dragon?

2.If the current monster is stronger than the previous one (i.e. monsters[current] > monsters[current-1]), then A has two options :

2.1) Might! A fights the monster taking damage (reducing hit points by the difference between the current and the previous monster). 2.2) Magic! A can drink an invulnerability potion, defeating the monster without taking damage.

Write a function that takes as initial parameters A list of monsters in order of how A will face them, with their strength as values; A’s initial hit points; A’s amount of invulnerability potions. And returns The 0-based index of the last monster A defeated.

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hope this time I can finish at least 5 problems.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to become CM this round!!!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope for a positive delta

»
11 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I wish it's somehow better than Gb2023 lol

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +69 Проголосовать: не нравится

    That bar is so low you could use it to play limbo.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    IMO first ever CF round would have been better that Gb2023. At least people might have learnt about maybe Dijktra or knapsack rather than just coding math operations without understanding significance.

»
11 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Wish a good perf and an enjoyable round.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a not tester, i can tell u this round it's much better than Goodbye2023

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Happy new year frands .

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how does score of questions related to our rating

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Geothermal will win codeforces round Hello 2024

»
11 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Will OEIS will be helpful in this round also? :P

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope, 2024 will better perform than 2023.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have deregistered even , I had registered for the contest

»
11 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

ImbalanceForces

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is time limit for C too tight ?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if not, please share the approach after the completion of the round.

    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Greedily considering this problem. We set the last number in sets $$$a$$$ and $$$b$$$ to $$$x$$$, $$$y$$$ (where $$$x$$$ and $$$y$$$ are the maximum values initially).

      Assuming we add the number $$$z$$$ to the set:

      1. $$$x>z, y>z$$$: Add $$$z$$$ to the set represented by the smaller number in $$$x$$$ and $$$y$$$.

      2. $$$x>z, y<z$$$: Add $$$z$$$ to the set represented by numbers greater than $$$z$$$ in $$$x$$$ and $$$y$$$.

      3. $$$x<z, y<z$$$: Add $$$z$$$ to the set represented by the smaller number in $$$x$$$ and $$$y$$$.

      Then we solved the problem within the complexity of $$$O(n)$$$.

      submission link

»
11 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

kringe round it was too bad!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unable to solve C,i better not be a retard

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится -25 Проголосовать: не нравится

    Every contest should be unrated when "YOU" can't solve problem C.

    Nice JOKE.

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I think that its about calculating the longest ( non increasing subsequence) but I couldn't figure out an approach except for the n^2 one

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      There's an nlogn way to find LIS, but it's not required for the problem. I solved this by greedy

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      C is not about LIS. But LIS is solvable in o(NlogN). I tried really hard though, to prove LIS way of solving C, but i can't. This sort of problem is really pain in the ass i gotta say.

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I made a mistake I meant to say (Longest Non-Increasing Subsequence) not LIS

        did you try to calculate that and it gives you WA too ?

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I don't think calculating the longest non increasing subsequence is the right approach as there are multiple possible such sequences and it is not necessary that all of them will give the same penalty

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    apologies.

»
11 месяцев назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Prove_with_ACforce

»
11 месяцев назад, # |
  Проголосовать: нравится +119 Проголосовать: не нравится

I've participated in codeforces contests for 7 years, and I still can't solve Div2C. I don't know how much I've progressed in past 3-4 years. Maybe its time for me to quit this game now.

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

C was nice. I love it when I prove a solution during the contest

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    it was about finding the ( Longest Non-Increasing Subsequence) right ?

    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      No, just try to start with the end. Then, you can compare each new item with the last added item in each of the two subsequences

      The rest is casework

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        ok thanks, but can it be solved if we found the longest non-increasing subsequence?

        the (Longest Non-Increasing Subsequence) penalty will be 0 and then we calculate the penalty of the remaining numbers in the set. do you think that this is a valid Solution?

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          You mean the longest non-increasing subsequese which will give us penality 0, right?

          • »
            »
            »
            »
            »
            »
            11 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            yes , I'm sorry

            • »
              »
              »
              »
              »
              »
              »
              11 месяцев назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              No worries!

              The longest non-increasing subsequence will not work

              Consider this test case:

              10

              7 4 1 6 2 3 5 8 1 9

              If we take the first subsequence as the longest non-increasing subsequence it can be

              7 6 5 1

              The other will be

              4 1 2 3 8 9

              Which has penality of 4

              But consider this solution wich have penality of 3 only

              1 6 3 9 8

              7 4 2 5 1

              The first has penality of 2 and the second has penality of 3

              which is less than the (longest non-increasing) solution

              • »
                »
                »
                »
                »
                »
                »
                »
                11 месяцев назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                thanks, some comments on the editorial section are talking about the correctness of this approach you can place this counter example there too

              • »
                »
                »
                »
                »
                »
                »
                »
                11 месяцев назад, # ^ |
                Rev. 10   Проголосовать: нравится 0 Проголосовать: не нравится

                No it will be 7 6 5 1

                4 1 2 3 9 8 This will have penatly 3.

                u interchanged them.

                I know LDS wont work because you can take this sequence :

                27 28 29 100 99 98 97 96 20 19 18 30 27

                When by LDS

                100 99 98 97 20 19 18

                27 28 29 30 27

                The penalty :3

                The better would be 100 99 98 97 96 30 27

                27 28 29 20 19 18

                Penalty :2

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 месяцев назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Yes, you are correct I changed the two numbers while testing

                  Thanks for clarifying

»
11 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Goodbye, 2024.

»
11 месяцев назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

I tried so hard to solve C. I tried varies of approaches to deal with it, but still failed. But I didn't give up. I tried to drew a lot of examples, tried to use dp, binary search, ternary search, graph, extended euclidean, ford fulkerson algorithm, .... And finally, I realised that I still unable to solve C.

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    Kind of the same... Sent 2.5 different solutions and tried maybe 5 approaches and all WA 2

    UPD: actually I had correct idea but just initialised arrays wrong... Now I am specialist for the first time since 2014...

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    problem C reminded me of my skill issue

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same goes with me ,First I tried with LDS(using binary search) then soon realised the question might not be that much complex.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think the solution will be greedy, the basic argument is every element will either go array a or b

»
11 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

wow what IS d? new year, new pain

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I found out that if x is the biggest element must have a brother that's equal to x-1 (both leaves). From that i think you can delete those two elements from the array and substitute them with their father (that has value of x-1) and solve again. I tried this with some data structures (double linked list and priority queues, very ugly) but got WA on pretest 2. I spent like 1.5 h on this :(

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      "I found out that if x is the biggest element must have a brother that's equal to x-1 (both leaves)."

      I guess, not "x is the biggest", but x is the deepest.

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        if x is biggest, then it won't have children. Though this doesn't mean it will have a leaf brother, at least one maximum should have a brother that's a leaf. Maybe it becomes a problem if there's two possible brothers, i'm not sure if both choices lead to a tree or not

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I saw that too, but what if X has both neighbors equal to X-1? Which one do you merge it with? What if it has one or both neighbors equal to X? I didn't really see any breakthrough in this line of thought

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        WOW I fucking misread the statement. I thought we could freely color the edges 0 or 1, turns out one edge HAS to be 0, and one edge HAS to be 1 for each non-leaf. I'm going to kms

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        If you do this until you can't:

        • Choose an inner node
        • merge it with its child with 0 edge

        The result will be a tree, not necessarily binary. The Dfs over leaves is now equivalent to dfs in tree, but with one tweak. We need to decide after which children (or it's possible at the beginning) we insert the inner node into dfs_order. Everything is possible, which means if (e.g.) choose the root, then there will some subtrees dfs_order concatenated on the left, and some subtrees dfs_order concatenated on the right. This can be checked with RMQ and recursion, but instead of deciding where to break the concatenated blocks in the root, we will decide them in the children. So at the end we need to check if the root is unique.

        240558002

        (oh i see you misread but maybe this will be helpful to someone else)

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        In that case if you have [... x-1, x, x-1, ...], then you merge any neighbor to x and always get [... x-1, x-1, ...]. Anyways this is the editorial sol

    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      i did exact same thing and 5 minutes after the contest i realised, that there must stay only 1 element and it must be equal to 0, otherwise it's a "NO".

      240601323

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

CCCCCCCCCCCCCCC!help!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is problem c dp?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is D DSU?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yea, I did a DSU based solution; however, something like linked lists might be easier to implement

»
11 месяцев назад, # |
  Проголосовать: нравится +89 Проголосовать: не нравится
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wow, I came up with the same solution without realizing that the complexity becomes linear if done recursively.

»
11 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Really nice problem D! A bit hard for its position though?

»
11 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

What's the idea for D?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Firstly, there must be only one $$$0$$$ in a valid sequence. Next, give some examples on the draft paper. You will find that if $$$x (x>0)$$$ appears in the sequence, then $$$x-1$$$ must have appeared.

    Let $$$x$$$ be at position $$$t$$$. Combined with the drawing, it can be found that $$$t$$$ must be within a interval $$$(l, r)$$$, satisfying the conditions of $$$\forall i \in (l, t) \cup (t, r), a_ i>=x$$$, and $$$a_l=x-1 \vee a_r=x-1$$$.

    I'm not very good at expressing its proof in words, sorry!

    Finally, we use dfs and binary search to solve this problem. Pass three parameters $$$l, r, x$$$ into the dfs function, representing the current interval $$$[l, r]$$$ and the value $$$x$$$. Record the position of each value in the array $$$t$$$, find the value $$$x-1$$$ in the interval $$$[l, r]$$$, split the entire interval into several small intervals, and recursively solve the problem.

    Happy New Year!

    Here are some examples as a reference:

    5
    6
    1 0 3 2 3 1
    6
    1 0 3 3 3 1
    5
    1 0 3 2 1
    5
    0 1 0 1 1
    7
    0 1 2 3 4 5 2
    
    Yes
    No
    Yes
    No
    Yes
    
    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Additionally, if you use bfs instead of dfs, some optimizations can achieve $$$O(n)$$$ complexity!

»
11 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

The webpage lag 15 minutes after the start of the competition caused me a lot of trouble.

Anyway, the problems all look interesting, thanks!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Today contest: Problems A & B is which ratings predict plz..? problem C question is kinda hard for me, I mean understanding the concept! what should I do to resolve this? also C: predict ratings? how much...

»
11 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

problem d is interesting but so hard, didn't solve :(

»
11 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

$$$\frac{Div. 3 \ + \ Div. 1}{2} \neq Div. 2$$$

»
11 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

great contest but did not manage to perform as expected !!

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

How to practice for problems like C (guessable but not trivial greedy problems)?

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Practicing Greedy problems might help.
    Practice reasoning based on "Proof by contradiction"

»
11 месяцев назад, # |
  Проголосовать: нравится +81 Проголосовать: не нравится

Accidentally submitted F2 to F1 & got -350 score...

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great contest! Thanks.

Hello 2024 != Good bye 2023

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Wow, it was such quickforces. My last accepted submission was on 0:11 .

My ideas to D:

  1. DFS. Assume we are on vertice. We remember what is above in stack. Either sum on path is $$$a_i$$$, so we calculated it, leave the leaf; or it is inner vertice, do exactly two dfs-s. If we are out, and array $$$a$$$ is no used fully, append one vertice above and start from it with only one dfs call. Incorrect.
  2. Greedy. Go from left to right. When we are on some position, we can do $$$-1$$$ on segment with this position as left border, and all different right positions. Use maximum right border every time. Incorrect model.
  3. Stress. Try to find pattern. Could not find.
  4. Split array on $$$0$$$-s to components. Size of each component is at least 2^max on compoment. What is next?
  5. Go from small values to big values. For all segment of values at least x its length has to be at least 2^length. Incorrect.
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Im failure after taking this contest :(

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Even though I couldn't solve the problems, I liked the problems as they are short and nice.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Interesting contest, third problem was as easy, as it was hard.

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

Accepted/Tried

How brutal the C test is. (The pretest btw)

»
11 месяцев назад, # |
  Проголосовать: нравится +109 Проголосовать: не нравится

cloudflare is SHIT

»
11 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Now I know how difficult to welcome the new year is.

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I wonder how many people proved solution of C.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    welcome to codeforces

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

    In my opinion, high-level coders will prove this because they can demonstrate it almost instantly.

    The proof of this problem is a typical one. Consider iterating from 1 to n. Suppose the current two subsequences end with a and b, assuming a <= b. Suppose the current number is x. Consider two cases:

    1. You put x after a number greater than or equal to it. In this case, if both a and b are greater than x, choose a. Otherwise, choose b.

    2. You put x after a smaller number. In this case, it will choose to put x after a.

    We consider that if we can make two choices in the current step, it must hold a < x <= b. If we choose 2, it becomes x, b, and penalty++. If we choose 1, it becomes x, a. We can imagine that the penalty is like a free ticket, which can change any number into INF at any time (including changing a into INF instantly), so 'a' with one less penalty is strictly better than 'b' with one more penalty.

    I don't know how others did this problem, but I only realized the answer to this problem after the proof.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Proof by AC is the most powerful method

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Didn't really prove it, but my reasoning went kind of like this. There's no real reason to take a penalty if not strictly necessary. If i raise one of the two sequences when not required I might also have done this later for the same cost. Then I just thought about how to keep a good state and figured out the best greedy moves after some tries. Then i proved by AC.

    Proof is a big word, but having an idea what you're doing is good enough usually

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

More and more vegetables,what should I do?

»
11 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

First two problems were satisfying. Solutions are short and pretty

»
11 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Is F1 difference + segment tree?

»
11 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

E seems classic, but I can't solve it. How to solve E? QAQ ~

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

240509224 240515600

Identified and rectified a discrepancy in Problem A submissions; both versions passed the pretests and shared the same logic. However, there was a point reduction of 50 points. :"(

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone Kindly share the solution of A using recursion. Thanks.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    u can just solve it through if a + b is an odd or not

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah. Missed that simple observation :(.I am trying to understand how recursion works. Confused how to implement this as there can be 6 cases I think?

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you don't need recursion observe that in every turn total coins will decreased by 1. when will it become 0 ?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Deserves the first contest of 2024. I really enjoyed it. :) Plus, thanks for the flash-fast editorials.

»
11 месяцев назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

C was the hardest problem of all time

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Why do I perform well in shxt rounds and brick the good rounds, weird

spent 1h writing F for nothing

»
11 месяцев назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

For every non-leaf vertex, one of the edges to its children has weight 0 while the other edge has weight 1.

I forgot about this restriction while solving D, a sample in which this makes any difference would have helped so much :(

»
11 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

2024 is already ruined for me after this contest. 2025 will be my year!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great problems, enjoyed a lot! kudos to the author(s)

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +127 Проголосовать: не нравится

Feedback on the round:

A: Fine easy problem.

B: Good problem conceptually. I personally would have preferred for the entire sentence "Note that there are no constraints on the sum of n over all test cases." to be bolded, which would have made the fact that O(n^2) solutions are not intended to pass more obvious.

C: Good problem; I've seen the general greedy strategy used as part of other problems before, but it serves reasonably well as a standalone C.

D: Nice problem; simple idea and the implementation isn't too bad.

E: I don't think this problem is objectively bad, but stylistically it isn't my favorite. Most of time time I spent solving it involved working out details rather than coming up with the general idea. Also, a (somewhat harder) version appeared as ARC 146 E (thanks to AC server for pointing this out).

F: Good problem. I prefer DS problems like this one where the data structures part can be handled mostly by copying a standard template, but writing the merge function itself requires a little more thought. Amusingly, I didn't come up with the idea for F1 before solving F2 and I didn't think about the flow idea given in the editorial while solving F2.

G: Great problem. This problem particularly improved my contest experience because it's the kind of problem where even if you don't end up at a solution, you can at least make reasonable progress throughout the time you have left in the round. In my case, I think I was very close to a solution, but unfortunately I hadn't finished working out all the edge cases or implementing the XOR hashing idea.

H: Didn't seriously attempt.

Aside from the fact that problem E had been used before (which empirically didn't seem to affect the standings much, if at all, and would have been hard to Google anyway), the round seemed very successful--the problems were interesting and the contest was prepared well (there seemed to be very few FSTs, there were minimal server issues during the round, and systesting started/the editorial was posted quickly after the end of the round). Thanks to the author and the coordinator!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for the contest.

Ended with positive delta, now starting with positive.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2300, recorded.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really great contest enjoyed it altough solved till C but got me to specialist Nice

special thanks to the testers and coordinators for creating such an amazing contest

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wish I could have solved D and F1.

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Awesome problems

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really an amazing starting of 2024

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks a lot to all the staffs ! i had fun this round . Wish i was able to complete C haha

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

@maomao90 Thank you for the great contest!! Enjoyed it a lot. Lots of DSA involved. LinkedList, Priority Queue, DP, Segment tree, Flow, Min Cut, Segment tree.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem C is too greed!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It was actually a wonderful contest, i enjoyed attending it virtually. :)

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm not able to open editorial page. It says "You are not allowed to view the requested page." Any ideas on this?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I became a specialist after that contest

»
11 месяцев назад, # |
Rev. 4   Проголосовать: нравится -9 Проголосовать: не нравится

Bad contest.... AB are quite good, but D's conclusion is too hard to think(the implementation is easy, though). Also, C's greedy is hard to prove. The other problems are not bad, but there's no time for me to solve them as ABCD cost me the whole time.

And, why editorial isn't available now?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tree LGM -> Three LGM

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

yar bhai lagta expert ka spna spna hi rh jayega

»
11 месяцев назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

dis this comment pls

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am green now. Thank you Hello 2024

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

goodbye 2023 turned into "good riddance 2023"

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I keep getting WA3 in F1 using a segment tree. Can anyone please advise, what might be the problem? code here Thanks :)

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why H is only 2000?

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice contest, loved it.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great round