diskoteka's blog

Codeforces Round #894 (Div.3)
By diskoteka, 5 weeks ago, translation, In English

☀ ☀ ☀ Hey Codeforces ☀ ☀ ☀

Summer is ending, but my team and I are happy to invite you to participate in Codeforces Round 894 (Div. 3). The round will take place on Aug/24/2023 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by: diskoteka, pavlekn, playerr17. Ivang helped us with the idea of one of the tasks.

We would like to thank:

  1. Vladosiya for coordinating the round

  2. MikeMirzayanov for great Polygon and Codeforces platforms

  3. feeder1, Xellos for red testing

  4. michao, induk_v_tsiane, Phantom_Performer, vladmart, dmkozyrev_thinks_slowly, LordVoIdebug, vrintle for yellow testing

  5. kzyKT, celin for purple testing

  6. ZiXeL, egorsa, MADE_IN_HEAVEN, Thost, Nafis, mewnya, natalina, Serik2003 for blue testing

  7. i_love_penguins, tnaito, akwa_blue, Zeyad_Hekal, NgJaBach for cyan testing

  8. mkshh, myav for green testing

We wish you all good luck and a high rating!

UPD: Editorial published

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

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

As a tester, I really liked the problems. I wish you good luck and have a nice day!

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

As a participant I will participate and be pupil again: : : : :

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

do not have a point of 1900 or higher in the rating.

Should it be 1600?

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

    idk why, but it was always 1900

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

    no

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

    I guess you don't understand what that part means. First, you should probably read the last paragraph of this blog.

    From the blog:

    -- We will exclude from the official standings of Div. 3 rounds and put in a separate rooms all those who can’t be reliably called to be a real participant. Accounts that materially participated in less than 2 rating rounds (materially means solved at least one problem there) before the start of the Div. 3 rounds, and those who have ever gained 1900 or more rating units will not get into the official standings and will be assigned to separate rooms. However, this does not mean that there is no rating recalculation for them. Thus, the rating will be updated for all users whose rating is strictly less than 1600 at the time of the start of a round.--

    In short, everyone who has $$$< 1600$$$ rating will receive rating change after the round, but only some of these participants will be shown in the "official standings". Namely,

    • People who have participated in less than $$$5$$$ rated contests (originally $$$2$$$ as you can see) are excluded from the official standings.
    • People who have reached $$$\ge 1900$$$ rating, and later dropped back to $$$< 1600$$$ rating are excluded from the official standings.

    These rules are in place to try to make sure that everyone in the "official standings" is actually at Div.3 skill level and not someone much better just having low rating. I think it is more fair to make this rating upper bound at $$$1900$$$ than $$$1600$$$, since reaching $$$\ge 1600$$$ rating doesn't mean you are actually that good (you could've gotten lucky).

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

as a tester i will you all good luck >.<

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

As a tester, I demand my name in the blue testing list and can assure that problemset is very well balanced and no problem is a cakewalk and wish everyone good luck and recommend to read all the problems

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

    But your name isn't on blue testers within the blog ?

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

      lol people thought I am fraud and downvoted me heavily haha

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

        The list is now updated and yes it has your name in it ><

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

What about Vika from your last contest

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

Wishing for this round will be the great round of Div.3. Best of luck to all contestants :)

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

I am also excited for this round...

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

wow , I am so excited to be involved , and hope I move on to pupil

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

I have the impression that the contest would take place on 8/26 (Sat.) Has it really been moved up, or did I get the date wrong?

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

I hope I can reach Master AFTER this round :v

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

    XD

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

    hi,i'm from vietnam too.probably i'm younger than you.can i chat with you about solutions,idea and ways to deal with problem?

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

      It's alright, I will provide support in my freetime. However if you want to discuss more actively, I suggest you joining Vietnamese Olympiad in Informatics (VNOI) community. At the moment, they are available on Facebook, Discord, ... There are many experts in CP so that you can ask for help

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

As a participant I will participate hoping to be an expert XD

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

Sauce for artwork

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

Wish to be blue !!!

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

    I'm really grateful for the opportunity this contest gave me to reach the blue！

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

I hope to be blue after this contest.

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

Fingers crossed that this time around, the problems are easy to understand unlike your previous round.

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

Is that the girl in the blog Vika, which you mentioned in your last contest? Whoes stories were hard to decode >_<

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

Thanks for this round and good luck for everyone!

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

Let's go !! ORZ .

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

Ohh Shit Is this the sunflower round??

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

How is it going with Vika

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

No offense, but pls no Vika in this round

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

I am crying because of interactive problem will be in contest.

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

    Where is it written that there will be ?

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

      The post must've been edited for some reason, I'm also pretty sure that at first it said there was going to be an interactive problem.

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

hope I'll regain blue soon...

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

ohh shitt..VIKA againnn

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

that's not yellow it's orange sir.

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

No offense, but pls no Vika in this round.

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

What does red/green/etc. testing mean? I thought, tests are the same for everybody

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

Hoping for great div3 contest__

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

Yall will like the problems.

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

waiting..............................

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

Hoping to cross 1300 mark

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

.

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

    Did you even read the announcement?

    If your rating is less than 1600, then the round will be rated for you.

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

I suffer Tle mostly....What will i do??

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

Hope my color will change after this round . Lets go !

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

    It will...... .......................................... .......................................... ............................ ............................ ............................ ...................... be green hh

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

    Just missing with you. You can do it.

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

Really hope to reach pupil this time!

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

good luck for everyone :)

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

:(

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

I can't wait, I'm so excited about Div 3

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

So many Yellow and Blue testers for a cyan, green & grey round

→ Reply
»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it
Hope to Solve 3 Problems
→ Reply
»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

diskoteka how is your vika now ? after reading last contest's problem statements

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

Expert round?

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

I hope to learn many different concepts and ideas in this round. But yeah surely I want to increase my rating :)

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

As a particpant , i hope to be cyan again.

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

May Lord Krishna bless you all with +ive rating.

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

35k participants

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

why 'custom invocation' not working ? (: diskoteka

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

    he can't control that , even mike can't , it's not working as it is contest time and too much pressure on the judge

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

Good contest, enjoyed it !!

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

when it's bout div.3, diskoteka never disappoint us.

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

gg, this was my first contest and i didnt know what to expect from it. The questions were great, but my solutions aren’t(had to scour over StackOverflow for a few places...). but congratz!

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

For some reason my solution to A got all different outputs than what I got when I ran it on my PC, lost 2 hours because of that, is that normal during contests or was that some kind of bug? I switched to C#, wrote the exact same code and it got accepted...

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

    Your uzeli array is uninitialised so has random undefined contents on each run.

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

      then why did it always work on my PC? So basically I had to set all values of that array to false?

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

        You got lucky I guess (different compiler / optimisation settings may produce different results). It isn't worth trying to work out why it works sometimes when you have undefined behaviour, just fix the undefined part and it'll work everywhere.

        if you declare it as bool uzeli[m]{}; instead of bool uzeli[m]; it will be default initialized (which for bools is all false).

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

          Yeah i get you, i did do that in C# because i experienced problems before in C# due to that mistake its just that it never happened to me in C++ so yes it probably is because of the compiler, anyways what a shit way to lose that much time and rating, especially when C and D werent that hard... : Thanks for helping

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

Having spent lots of time for E because of the third test case, that's really confuse because of the note. I got AC because of predicting the actual problem LOL.

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

    1，3，5，6 ? 2，3，5，6 ? I was totally confused during the contest :D

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

      Yes, it really pissed me off.

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

      3rd question , my good God . what was that even . I just couldn't understand . I spent my entire time trying to break down that question .

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

what is error in this code For Problem F https://codeforces.com/contest/1862/submission/220289269

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

mid=(lo+hi)/2 forces

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

    Yes solved the problem D with quadratic and got WA, and I know it time to use bi-search

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

      D can be solved without binary search.

      Here's my submission — 220221455

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

        can you please explain you solution. thanks in advance :)

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

          If you observe carefully there is a pattern in the solution — 2,3,3,4,5,4,5,6,7,5... So it is like -

          2,3

          3,4,5

          4,5,6,7

          5,6,7,8,9

          and so on

          If you solve the equation nC2=r, where r=required number of different ice creams, you will get n = (1+sqrt(1+8r))/2, so just calculate this value if it is an integer it will be your answer, and if not, then it will be the first number of the row in which your answer is present so just add the diff between r and the value for which you got the answer which you can find by simply putting it back in the formula nC2 and that will be your answer.

          Sorry if I was not clear, but the main thing is finding the pattern and the quadratic then you can solve this question.

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

            bro but in sample test case 4 for 179 why do we need 27 , by nc2 it can be wo also right because 20 c2 is 190 more than 179

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

              In question D. it is given that exactly n type of ice-cream has to be made, not greater than that not less than that. for test case 4 answer is 27 because you need 19 unique ice-cream flavor and 8 repeating flavor. e.g. 1,1,2,2,3,3,..

              19c2 = 171.

              since you have repeated 8 flavor you can make 8 unique combinations of (1,1),(2,2) ....

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

                yea understood, thanks a lot

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

              That’s what I thought too. I spent like half an hour tryna understand until the general announcement then got AC right away

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

I cannot get the test details in E, can you help me what wrong with my code ? This is my code

:(( I know I cannot get more rating after this contest :(

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

    Do you fully understand the statement, that's confuse. If you are, the problem is just maintaining a priority queue to keep track of the largest value, and maintain the size of queue to be less than or equal to m.

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

    I think the problem is that d*i can give overflow , when you're calculating res

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

Thank you Geothermal for this trick while using bitset.

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

I don't know if problem C was actually confusing or maybe I'm dumb enough not to understand it.

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

    I also found it very coufusing.

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

    It's simple Range sum query, but very confusing

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

    I simulated what the final array would be and compared both arrays in the end.

    Solution

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

    It is basically a prefix sum kinda problem where we are generating the tilted array with respect to the diagonal line and comparing both arrays

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

Can someone hack this F solution for the case when water and fire > 1e5? https://codeforces.com/contest/1862/submission/220284156

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

for D i noticed it's . find the nearest lowest X for X choose 2 then add n-(X choose 2) . but since it failed on the last test since it's a very big number so is my logic correct and bad implementation? Edit: ok nvm i was an idiot and made r in the binary search n not 1e9 :).

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

    find X: X * (X — 1) <= 2*n < X * (X + 1).

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

    It works. Just to avoid getting hacked I used Python lol

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

Solving problems are way easier than reading them!

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

nice problemset and hoping for positive delta! almost got WA for F but luckly after brief reviewing, i did manage to solve it in the last 4 minutes.

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

Good problems!Thank you! And I want to know is there any brute force ways for F?I got wa using my brute force way :(

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

Problem D:

I used binary search on k, trying k choose 2. If I found kc2 == n, answer is k.

If such a k does not exist (for example, n = 7), I found the greatest k such that kc2 < n, and then added duplicate balls. So for 7, 4 choose 2 is 6, add 1 duplicate ball (e.g. {1, 1, 2, 3, 4}) to get 5 as the answer.

This strategy worked for test 1 but not test 2. During the contest I believed it was a binary search bug but now I wonder if this strategy is valid.

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

220284619 how is this wrong? can anyone tell?

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

Just got F a moment after the contest ...

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

Here is my Live Screencast of solving problems [A -> F] (with commentary in HINDI).

PS: Don't judge me by my current rating :(

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

Nice problemset. Thanks for listening to the feedback on last round and made your contests better . Loved D

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

can you guys tell me logic for [problem:C] and [problem:D]?

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

    C: I try to flip the fence, and compare with the input

    D: you should find the value X, where X * (X — 1) <= 2n < X* (X + 1). Because you get X * (X — 1) distinct pair (2,3) or (1,2), and some same pair (1,1) or (4,4)

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

Can someone hack my F. 220282299

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

How could problem E be approached? What I observed is that we optimally must select the shortest continuous subarray starting at 0 because we will always remove -d * len(a), where a is that subarray. Then we can pick maximum $$$m$$$ positive values, but how to determine the length of that subarray? Would a priority queue work and at each index check the maximum m values + -d * i?

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

    You don't need the shortest continuous subarray. The answer is maximum of: for each position sum of the greatest m positive elements to the left minus the position multiplied by d. If you get more than m positive elements to the left, you just erase the minimum of the set or the priority queue and update the sum.

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

F is an interesting dp problem. Unfortunately, I was not able to solve it for the limited time.

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

My F solution was Iterative dp with memory optimisation

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

lognforces

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

220296987

What is making my solution slow for G? (time limit exceeded) I would want to hear some advices on how to use sets and what to avoid to not get tle in the future.

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

    I had a similar solution, mine was segmentation error (I believe to be memory exceeded)

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

Problem C solution using binary search Link

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

As someone who's new to this stuff, I got slammed by the 3rd problem

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

Nice problemset.

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

Most confusing problem "D" :) && Besides lots of announcement increases the confusion level further except clearing.. ConfusingForces

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

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

    Hey Cheater, why have you inserted unnecessarily string/char etc. in your code of D.

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

      Could you point out the unnecessary string/chars you saw in his code? If you are referring to blank lines, they don't matter anyway. Could you clarify what part of the code made you believe the person you accused a cheater is actually a cheater?

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

        Nvm. Very my fault for commenting without checking the problem of the solution. Thought it was this Contest's D.

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

          I am not sure if you and the accuser are the same person. But accusing someone a cheater is not something we should take lightly. Your reasoning of accusing someone cheater because you thought the code was for this contest is not only unacceptable but also unforgivable. At least check the problem ID before calling out someone a cheater. Anyway, I hope you have learnt from your mistake and would take this seriously in future.

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

            I didn't accuse him. I literally specified it in the previous version that I neither accuse nor defend.

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

              If "Hey Cheater" is not accusing someone a cheater then I don't know what does accusing means. Anyway, I am not quite sure why are you replying? Are you and ccpp same person or distant cousins?

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

                I have no idea who he is, but I didn't say "hey cheater" in any of my comments, in the CF history of this account.

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

                  My bad then, I think you should have replied in the separate thread. Cause, my question was specifically to ccpp. And I did not get any answer. Your comment confused me.

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

                  Sorry, Actually I went to saw Sol of D in his profile (submissions) then I saw this soln. I did not realize that the soln was od another contest and presumed that he had done it to pass plagrasims. I am extremely sorry to have created this confusion.

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

      i knew that grays dont have brains. i was unaware that they cant even see properly

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

        I can see properly. I can clearly see your color is RED.

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

    Extremely sorry bro, I mistakenly thought you cheated. Sorry please forgive me. Sorry Again.

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

      It's Ok bro.. Understanding the coding aspect is enough.

      That's actually not unnecessary strings/char. That's called template. We mainly use it for writing code faster in contest time, Cause you already know your coding speed will impact your contest performance

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

        Actually I thought that the code was of this contest, but that was of some past contest. I thought that strings are unnecessary (due to my Assumption(wrong) that code was of this contest) even without looking at full code. Sorry Bro once again. Actually since there are a lot of cheaters, I get so angry at cheaters.

        But sorry you are NOT a cheater. Good luck

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

My solution for F is slight different from others, I binary searched on time, and got amount of fire and water. Now if any of these is greater than sum, this time works. Else, I try to fill knapsack of fire in most optimal way, (by optimal I mean, filling it in such a way that it has least remaining space possible) and check if remaining sum can be filled in water knapsack. Similarly, tried to fill water knapsack in most optimal way and check if remaining can be filled in fire knapsack.

Here is link to submission

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

    if((sum-dp[F]<=W)||(sum-dp[W]<=F))

    You only need to check one of these. Suppose sum-dp[F] <= W is true:

    dp[F] is the sum of a subset of monsters sum - dp[F] is the sum of the remaining set of monsters

    Since sum - dp[F] <= W, we can kill the remaining set of monsters with W. In other words, sum - dp[F] <= dp[W].

    Therefore, sum - dp[W] <= dp[F] <= F and the second statement is true as well.

    The same argument applies if you want to prove the second statement implies the first.

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

    i did the same

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

Hello, can someone provide a hint for problem E

Thanks :pray:.

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

    Lol i thought it was question F nvm mb

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

    Have a good day!

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

worst div3 contest

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

Video editorial for problems A&B&C&D: https://youtu.be/aEB8NXX-lxA

Thought would be useful

IN ENGLISH

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

Great problems, D and F were really interesting, and E was also nice. Hope to get to expert after the rating changes :)

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

In problem F, I've seen many solutions that use this bitset idea, but I'm just lost at what it does.

Can someone explain what it's supposed to be happening here?

bitset<1000001> dp;
dp.set(0);
for (int j = 0; j < n; j++){
    dp |= dp << s[j];
}
→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +25 Vote: I do not like it

    this is the equivalent of

    for i from 1 -> n:

    for j from sum -> a[i]:

    dp[j] |= dp[j — a[i]]

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

    generates all subset sum which are possible.

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

    OK, I think I got it!

    For the interested:

    dp[amount] should be $$$1$$$ when we can form amount by summing some elements of s together, and $$$0$$$ when we cannot.

    Therefore dp should have enough size to store all possible different amounts. In this case, from $$$0$$$ to $$$10^6$$$.

    Initially dp will have all values set to $$$0$$$ (we don't know yet which values we can form), except for the $$$0$$$-th bit (we always can sum up to $$$0$$$, just choose no elements from the set).

    The line that sets the $$$0$$$-th bit to 1 is: dp.set(0).

    Then we iterate over all elements of our set. Say that our set s is {3, 2}.

    In the first iteration of the for, we know that we can form s[0] — that is, when we choose only the first element to form our sum — so we should set the s[0]-th bit of dp to $$$1$$$.

    After the first iteration, the $$$3$$$-rd (and $$$0$$$-th) bit of the bitset will be $$$1$$$:

    dp equals 00000 ... 0001001.

    In the second iteration, when considering s[1], we know that for each value we already know we can form, we can also form that value + s[1]. Since each bit already set in dp represents a value we know we can form, by left shifting each bit $$$1$$$ of dp by s[1], we get all new values we can form.

    In the example, since s[1] is $$$2$$$, by shifting all bits of dp by $$$2$$$, we have:

    dp << 2 equals 00000 ... 0100100 (now we know we can form 2 and 5).

    By using | between dp and dp << 2, we join all the values we already knew we could form and these new values we just learned we can form: dp |= dp << s[1].

    dp |= dp << 2 equals 00000 ... 0101101 (we can form 0, 2, 3 and 5).

    The same idea for s[1] is valid for any s[i] that comes after, and after the for, we know all values from $$$0$$$ to $$$10^6$$$ that can be formed, since they're set to $$$1$$$ in the bitset.

    There are probably better and shorter explanations elsewhere, but since this is a Div3, I think it means no harm putting mine here.

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

It's very unlikely that 1000 people will solve F during contest, I think heavy cheating is going on maybe those Unofficial Experts , CM, M.. provide these fellow cheaters the solution :(

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

    F wasn't that hard to be honest. I needed around 30 minutes to solve it(spent 10/15 minutes on E after solving C). I immediately had the binary search plus knapsack idea. But wasn't really sure if it would pass(I was thinking about normal knapsack not the bitset one). Then I was able to reduce it to only knapsack without the binary search.

    I participated virtually though!

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

      What's the t.c. of bitset idea? Is it O(sum + n)

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

        O((n * 1e6) / 32 + n)

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

          can you explain it please.

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

            performing an operation bitset has a time complexity of n / 32 or n / 64 depending on your computer, but in codeforces it seems like it is 32.

            we iterate through every number, then we take the whole bitset and we perform OR operation with (bs << val), this takes O(ceil(SIZE / 32)), SIZE in this case being sum which is 1e6.

            we do this n times, which gives us the total time complexity of O(n * ceil(SIZE / 32)) or O(n * 1e6 / 32)

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

              I think you meant OR operation. Anyway, thanks for the explanation.

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

    True :)

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

    I was also surprised

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

Python users, for Problem G anyone knows the source of this SortedList template 220199018? (huangxw, yuki_keshiki)

I was getting TLE with the PyRival implementation.

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

    I copy the SortedList template from someone's submission in Atcoder contest，it is crazy fast，prefect to solve this problem.

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

White spaces and endl seem no difference to checker. 220288316

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

    yeah , I never use " " , I always use "\n" and never had a problem.

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

      Cool! I knew that trailing spaces do not count. But never knew that new line is also fine. No more space handling from now, then.

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

Can problem E be somehow solved using binarysearch?

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

Hey everyone, I'm a newbie. I want to ask why this round is not rated for me. Thanks.

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

the observation, maximum difference between adjacent elements of the array for problem G is damn cool !!

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

Why are the rating changes not out yet, hacking is over right

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

    There is always the daunting 2-3 hour wait after system tests before rating updates. Hoping to get pupil, I’m at 1199 right now!

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

      That’s great congrats

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

        And I just noticed that you’re two points away from specialist. Congrats to you too!

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

nice contest i like it , F problem is so goood

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

crazy queue

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

Is system testing done?

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

where is the systerm test?

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

    when will this queue end, I am facing this issue since last 4 to 5 hours

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

Can E be done using sliding window?

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

    But you need to kill all monsters, not just a subset

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

Hope to reach pupil after this contest. Solved 4 problems

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

Why don't start system test immediately ?

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

Why don't start system test immediately!!!!!

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

Why don't start system test immediately ?

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

I am a python user but I dont know what is the alternative of multiset of C++ in python?

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

    I guess you can use heapq as an alternative

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

Good round in total, but problem A is very boring, problem D and F are a little boring, the others are interesting!

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

Now i have become expert the destroyer of division 3.

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

The solution of D — only 3 rows. https://codeforces.com/contest/1862/submission/220453243

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

commented on a wrong round sorry

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

When do editorials of contests usually release? I am new here.

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

    they are released, check the last line of annoucement(this post)

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

      Thanks. I also want to know the approximate time frame for all contests

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

Lmao I binary searched on F and created a dp table every time not realizing I could've just created a big one to start. Oops.

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

Attention!

Your solution 220250441 for the problem 1862E significantly coincides with solutions wont_give_srsly/220246281, manvendrasinghshekhawat/220250441, bdyby11/220257824, pmqwerty/220262992, Swarupa/220264041, pranavkumarreddy567/220268055, DarkDreamin/220269225, nitiksharma/220269800, jvamshi36/220271912, jolly_79/220273460, Tintintani/220275635, absolute_07/220277807, jkoushik_iiitn/220278018, abhay5a/220278945, anjan_reddy/220279911, kunaltelangi/220280520, Mobbbbb/220281738, i_decided/220284890, Adityaraj834/220285184. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code).

I recently received this mail stating that I was accused of plagiarism for a problem 1862E. I didn’t know any of these people nor did I share my code with anyone or use any online ide. I am 100% sure that this violation has not happened from my end.

I have personally looked at all the other submissions and none of them match exactly with mine other than using ‘multiset’ and the problem logic. I request you to please check again MikeMirzayanov.

My Submission: 220250441

Other Submissions:

220246281 220257824 220262992 220264041 220268055 220269225 220269800 220271912 220273460 220275635 220277807 220278018 220278945 220279911 220280520 220280520 220281738 220284890 220285184

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

I hope you are doing well and reading this. In relation to my most recent Codeforces entries, I'm writing to discuss a worrying problem. The resemblance in my replies to those of other participants is simply coincidental, I tell you. I have not cheated in any manner.

I am entirely committed to following the platform's standards because I recognize how crucial it is to keep it honest. I take the responsibility for my Codeforces account and reputation very seriously, and I would never act dishonestly. I think the similarities in the solutions can be traced to the nature of the issues and the typical approaches taken by participants. For clearly stated situations, it is not unusual for numerous people to come to the same conclusion independently.

Please evaluate my submissions and give my justification some thought. Please don't hesitate to get in touch with me if you have any further questions or concerns so that I may provide clarification or more details. I am more than prepared to help and offer any proof required to prove my innocence.

I respect the Codeforces community and its dedication to fair play, and I look forward to finding a solution that preserves these values.

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

I recently received this mail stating that I was accused of plagiarism. I didn’t know any of these people nor did I share my code with anyone or use any online ide. I am 100% sure that this violation has not happened from my end.

I have personally looked at all the other submissions and none of them match exactly with mine other than the problem logic. I request you to please check again.

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

Attention! Your solution 220205849 for the problem 1862C significantly coincides with solutions Team1_QuangDat/220205849, Lo_Mid_Hi/220259007. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. I recently received this mail stating that I was accused of plagiarism for a problem 1862C. I read the code from the Lo_Mid_Hi account and it is 100% identical to my code and I do not know this person. It can be seen that this account copied code from many different people in the contest. He copied my code, he didn't even delete the comment at the top of my code. I request you to please check again MikeMirzayanov. My submission: 220205849 His submission: 220259007

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

please update the problem ratings, it has been more than 20 days since the contest is finished and yet problem ratings are not updated.

→ Reply