By awoo, history, 6 months ago, translation, In English

Hello Codeforces!

On Dec/27/2021 17:35 (Moscow time) Educational Codeforces Round 120 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

»
6 months ago, # |
  Vote: I like it -87 Vote: I do not like it

It's rare that an official blog was posted 36 minutes ago and there are no upvotes.

»
6 months ago, # |
  Vote: I like it -65 Vote: I do not like it

I've pretended to be expert. But still I have ambition to be expert and never lose hope. Wishes to positive delta.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -44 Vote: I do not like it

    I've pretended to be specialist. But still I have ambition to be specialist and never lose hope. Wishes to positive delta.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -75 Vote: I do not like it

      Never possible on behalf of you, cause you're already master. But Thanks to codeforces to meet our expectation for a short time.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it -74 Vote: I do not like it

      You are candidate master, aren't you ?

      UPD : Please don't downvote me x)

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

      .

»
6 months ago, # |
  Vote: I like it -60 Vote: I do not like it

Last educational round in year, makes me feel nervous ...

»
6 months ago, # |
  Vote: I like it -53 Vote: I do not like it

I hope this last Educational round makes me PUPIL in 2022!

»
6 months ago, # |
  Vote: I like it -64 Vote: I do not like it

Is it last educational round in 2021? or we will be surprised with another one!

»
6 months ago, # |
  Vote: I like it -62 Vote: I do not like it

19 educational rounds this year. We hope more in 2022 INSHAALLAH.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    "INSHAALLAH" get your religion out of codeforces. If not, then here you go, I just made a religion I follow. It's total opposite of yours and I'm gonna shout its catchphrase. FUCKALLAH.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      "Inshaallah" is an arabic word, even arabic people of other religion speaks it too. But man "Astagfirullah" you're abusing god, you cannot be a good human being. I can say a lot but i don't wanna create any kind of controversy, the purpose of codeforces is different. To maintain the decorum please don't reply on this comment, whatever you want to say you can messege me.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      MikeMirzayanov, please remove his comment if possible.

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

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

        Right I said that. THAT was exactly for the inshallah and whatever the fuck the comment I replied to was saying. Now I know you religious cunts won't stop with your shit, so I better give it to you the same trashy way you do here.

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

          orrrrrrr you can go and solve some problems and focus on getting better at cp since ur just wasting ur time and offending other people at the same time. time to grow up g

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

            Just like you don't need permission to scream ALLAHALLAHALLAH anywhere, I don't need permission to do what I wanna do as well. Is it that hard to get, g?

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

              nobody is telling u what u can and can't do. ig u can say were teaching u the manners which muslims learn at the age of 6.

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

              screaming that probably needs permission, its not even permitted in islam because it could possibly bother the surrounding people. does it make u happy to make anonymous accounts and look ignorant, or do u show these comments to someone seeking their approval cuz its real sad either way <3

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

                Seeking approval? No It's just that no religious bs should be here on cf. Not a single word.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      Request to all the people which trust in God (aka Allah), please downvote him !!

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

      notice how u just attacked our religion in the worst possible way and all the muslim commenters replied with respect. u can learn a thing or two from us. allah yahdeek

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -50 Vote: I do not like it

    All comments under this blog have more downvotes than upvotes

»
6 months ago, # |
  Vote: I like it -42 Vote: I do not like it

if (Comment section == Downvote section) return ("get a life")

»
6 months ago, # |
  Vote: I like it -44 Vote: I do not like it
lighthearted meme
»
6 months ago, # |
  Vote: I like it -34 Vote: I do not like it

last educational codeforces round for this year .

»
6 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Raining Of Downvotes . hahahaha !!

»
6 months ago, # |
Rev. 2   Vote: I like it -32 Vote: I do not like it

hello community

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    For you — yes, it is

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      What's the bullying? Let's upvote him! Use all your fake accounts for this good deed.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it -20 Vote: I do not like it

        Agree. It`s time to do something good before the New year comes

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    Thanks for changing your question! I just answered on is it rated or not... And the biggest thank for my contribution...

»
6 months ago, # |
  Vote: I like it -35 Vote: I do not like it

I want to be in this rare moment, down vote me too!

»
6 months ago, # |
  Vote: I like it -42 Vote: I do not like it

1 upvote = $1 for poor kids in africa

»
6 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Bye bye educational 2021... And down vote starts X(

»
6 months ago, # |
  Vote: I like it -25 Vote: I do not like it

HAHA downvote me too, i want to be part of this rarest chain XD

»
6 months ago, # |
  Vote: I like it -18 Vote: I do not like it

why edu round?

»
6 months ago, # |
  Vote: I like it -55 Vote: I do not like it

Segment tree is very indian

»
6 months ago, # |
  Vote: I like it -32 Vote: I do not like it

WTF Downvoteforces??

»
6 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Expecting a good contest. :3

»
6 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Who let the downvotes out? I promise this is not a rickroll

»
6 months ago, # |
  Vote: I like it -15 Vote: I do not like it

My first round as a red coder

»
6 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Not a single comment (votes > 0).

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

    a kid is spamming downvotes from fake accounts, i wonder how lonely he is and how he is enjoying this

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov Can we do something about this kid that is spamming down votes from fake accounts on every single comment? I wonder how he is enjoying this. go get a life man!

»
6 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Instead of downvoting, do programming !

»
6 months ago, # |
  Vote: I like it -34 Vote: I do not like it

Why So Negative??

»
6 months ago, # |
  Vote: I like it -39 Vote: I do not like it

lol why so many dislikes

»
6 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Why EDU Rounds Are More Difficult Than Normal Div2 ?

»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Downvotes, Downvotes everywhere

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

Enjoyed problem C, very interesting. But It took me 3 tries to accept this porblem, but anyway I love it

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

OHHH! GOD ! I will become Master ??!! It only took two contests to go from expert to Master(maybe)and that's CRAZY!!!

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

    So why you guys want to downvote evry comment? Ok, that's fine.

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

    congratulation!! hopefully one day i will become green :')

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

    Great, congratulations, i'm still trying really hard to reach specialist.

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

    You didn't become Master finally ...

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yep. I'm getting so frustrated now. 2095 what the fuck

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

        Hope next time you will reach it ...

»
6 months ago, # |
  Vote: I like it +35 Vote: I do not like it

What about the idea that every upvote's or downvote's value is function of current rating, contribution and account creation date?

May be it is non-democratic..

»
6 months ago, # |
  Vote: I like it -16 Vote: I do not like it

It's strange how you don't do any significant change in the code and still expect it to get accepted each time.

6 wrong submission on C.

Wrong on pretest 2 forces ;)

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

    I initialized my answer as 1e9 instead of 1e18 (because I had my INF defined at 1e9) and it gave wrong answer on test 4. Checked my algorithm 4 times but never ever thought of checking the value of INF. After checking tourist, did I find out that my algorithm was exactly the same as his and then I noticed his INF then I changed mine and boom Happy New Year! Damn, this sucks man, no more this small of a mistake may make my delta negative. No more 1e9s. You live, you learn I guess.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi, I looked at tourist solution as well but I don't understand one part. May I ask why do we calculate the extra decrement step as follow?

      cur += (diff + t) / (t + 1)

      I get the diff / (t + 1) part but what does the t / (t + 1) represent?

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

      Hey i was struggling with the C..and i gone through your comment and i have did the same kind of error..now its accepted

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone give a hint on task D please?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Find number of strings where first position where it differs from original string is ith

    and last such position is jth.

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

    My solution to the problem D. https://codeforces.com/blog/entry/98410

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

      Could you have a look at my code? I think I've done something similar.

      If it's not too much trouble. Thanks

      Spoiler
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem C be solved with binary search on number of moves??

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

    That's right.

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

      i was not able to implement parity function successfully :( Thanks

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

        It can be done without binary search in O(n). You can look at my 2nd submission. The idea is that we can reduce the smallest number by 1 x times and make the largest b numbers equal to that smallest number (after reduction) such that the total sum is less than k. We can iterate over b from 0 to n — 1 and find out x in constant time (with some precomputation of a prefix sum array) so that it follows the Sum <= k rule. And then just take the minimum of all such b + x.

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

          i think i got it. thanks.

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

          Since the input has to be sorted it is O(nlogn)

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

            Ohh yes. I dont know how I missed that. Thanks for correcting me.

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

          Can you exactly tell me what is X for ? If you don't mind..

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

            X is the number of times we perform the first operation. It can be shown that it is best if we perform it only on the smallest element.

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

    Yes. I did it this way. See my solution

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

    Yeah but you should make some observations at first.

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

      that's what i am saying to myself after not getting AC i should have spend more time on my notebook rather than trying to implement it quickly Thanks

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

        some number X of I operation only for smallest element, second operations for Y of biggest numbers. so iterate on Y from 0 to n-1 and find minimal X with binary search.

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

          You can find minimal X in constant time (if you precompute the prefix sums array) using a simple formula. I did it so.

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

            ll X = max((a[0] * b + a[0] + b + (r — k)) / (b + 1), 0LL); why you add b before (r-k)? because in division you round up?

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Same doubt, and how diving it by b+1 gives us the moves required ?

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

                a[0] is the smallest element which is now a[0] and I am changing b largest elements to be a[0]-x as well and r here is the some of all the other n-b-1 elements. So we want (a[0]-x) + b*(a[0]-x) + r <= k. I took the smallest value of x that satisfies this relation.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  ll X = max((a[0] * b + a[0] + b + (r - k)) / (b + 1), 0LL);

                  Why do you have to do max here with 0LL why we can't just calculate the whole eqn and store it into x?

                  Awesome solution though!!!!!!!

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

                  Thankyou so much

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

                  Because this expression can be negative but X cannot be negative as that would mean adding ones to the smallest element |X| number of times, which is NOT one of the permitted operations. Dry run it for the second test i.e 2 69 6 9 and you will understand.

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

              Yes to round it up.

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

          i think i have tried in the same way. i will check my code tomorrow. Thanks for your help

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

    I solved it using binary search .

    But after the contest :(

    https://codeforces.com/contest/1622/submission/140825675

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

My solution to the problem D. https://codeforces.com/blog/entry/98410

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Loved the E! chef's kiss

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C

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

    Binary search

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

    Actually it works also without binary search. Observe that there are at most n-1 copy steps, and all decrease comes before the copies.

    Then we can iterate the number of copy steps from n-1..0, and foreach one calc the number of needed decreases in O(1).

    Looks like O(n), but since we first need to sort the input it is O(nlogn)

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

      Actually my solution is the same. I just use binsry search to calculate the decreases(though I know that it can be abtained in O(1))

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

      Nicely Explained bro...thnx for comments in yur code. Helped a lot

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

Why do div1 players in official standings?

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for short and clear statements!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tried Problem C using binary search but got wrong answer on test 6(really sucks). Can anyone help me understand why

code
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understanding what I did wrong in solution C? 140802492

I made chances array which indicates chances that will be required by decreasing small element by some amount and changing all elements from i to n — 1 for i in [1, n) and took minimum of them.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. set a4=a3=1;//step = 1;

    2. decrease a4 by one, and get a4=0. //step = 1+1=2

    3.choose a7 and decrease in by one** 3 time**; //prev step = 2+3=5

    4.choose 4 elements a6,a8,a9,a10 and equal them a7; // here isn't 4 steps? prev 5+ this 4?

    as in every step we can choose just 2, ai and aj? so according to their explanation, the answer is 9. but how did they come up with 7?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      We try to decrease lowest element and flip highest elements. For given case after sorting we get 1 1 1 2 2 3 6 6 8 10 and required value is 1. One solution is -2 1 1 2 2 3 -2 -2 -2 -2 and get sum as -1. Here we decreased first element by 1 3 times and changed last four elements to -2 using first value so 7 operations

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

    Your submission gives -2 when I used the following input:

    1
    6 25
    2 2 2 2 9 9
    
    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh thanks for clarifying should have used max with 0 when I finding chances. Thanks for taking time to find the issue. It is accepted now[submission:140828937]

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one tell me why am i getting wrong answer for problem B,here is my solution link 140812830 140812830

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

    Not able to understand your code bro...please explain your approach

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Just curious , why the constraints were set for a O(n^2) or maybe O(n*k) solution for D? Is there any solution that relies on this small constraints (like maybe a dp)? I could only come up with O(n) solution.

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

    can you please elaborate your solution for problem D.

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

    I did in the following way, not exactly dp but combinatorics. Let i and j be two indices I want to find the number of string which exist such that prefix upto i and suffix upto j is same as that of the original string, then s[i+1] can not be equal to the original value, and s[j-1] can not be equal to the original value. so s[i+1] and s[j-1] remain fixed and number of 1 between i+1 and j-1 has to be <=k. then we need to shuffle (j-1)-(i+1)+1-2 characters in the usual combinatorics fashion and add the answer for all i and j.

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

      Great explanation Got it thanks:).

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

      The number of 1 between i+1 and j-1 has to be equal to k right ? So that we can shuffle the substring. Why <=k?

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

        if you have a string containing k ones... you can always shuffle a substring of it containing less than k ones... then also we can pretend we have shuffled that substring with k ones. Actually, if you use exactly equal to k, you will not consider the above case and will undercount.

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

      What exactly are the roles played by s[i+1] & s[j-1], I am unable to understand.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Yeah there is straightforward soln to it in $$$O(n^{2})$$$

    Spoiler
»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

KOVAL_ IS A CHEATER!!!!!!!!!

140792053 140792490

please reject his submissions MikeMirzayanov

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    yeah KOVAL been doing this for so long with others, but some of his old submisson got skipped i think this ones will get skipped to

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

    Alien-level coding skills

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C using binary search?

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

    Suppose that you have to complete x operations. How this operations will look? Firstly you decreases minimal value, secondly all remain operations you spend for replacing maximal values by new minimal value. We can sort all elements, then you decreases begin and replace some suffix. You can try different suffix length from 0 to min(x,n-1) and for all possible length calculate sum in O(1). 140781854

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

      Thanks a lot.I was having exact same idea but couldn't implement it during the contest.Seems like binary search wasn't a intended solution for this problem

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I had the same binary search idea. The thing is: if you fix the number X of operations of the first type (decrease min value), in O(1) with math you can find how many replace operations you will need to have the sum <= k. I actually coded the binary search, but something was wrong. Then I realized this idea which leads to an O(n) solution.

        The code: https://codeforces.com/contest/1622/submission/140778410

        PS: the if inside the main loop is the number of 2nd type operations needed.

»
6 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Can someone give me a counter-example for my approach to C?

1) Sort the array

2) For every index $$$i$$$, we will copy the value of the smallest member i.e $$$arr[1]$$$ from $$$i+1$$$ to $$$n$$$, but before copying we will find the minimum decrements, $$$d_i$$$ in $$$arr[1]$$$ that are needed so the constraint of sum $$$ \le k$$$ is satisfied

To be precise, let $$$m$$$ be the smallest member, then for every index $$$1\le i\le n$$$ we find smallest non-negative $$$d_i$$$ such that-

$$$prefixsum[i]-d_i + (n-i)*(m-d_i) \le k$$$

where $$$prefixsum[i]$$$ is the sum from $$$1$$$ to $$$i$$$ in the original sorted array

Overall, the answer will be minimum of all the $$$d_i + n - i$$$ over all $$$i$$$ because we do $$$d_i$$$ decrements and $$$n-i$$$ copy steps.

Here is my submission. Gives WA on test 2.

EDIT:

I found the error, int x = -1/2 will give x=0 and not x=-1. I had an implementation bug. My code failed for the following case-

5 6

1 4 1 1 1

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

    Your submission sounds quite close to mine. I also WA on test 2 before I added ans = min(ans, sum-k), where you only do decrements and no copy steps.

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

    If we solve this equation di can never be zero.

    So the case where di is zero i.e no decrement operation and all set operations is not covered?

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

    Counter example:

    1
    5 10
    1 999 999 999 999
    

    Your solution gives 3, but I think the correct answer is 4.

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

      Thanks bro ur a genius.

      After 7 wrong submissions finally got to see Happy new Year

»
6 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I solved C without binary search (more of like greedy approach)

First of all the main observation is we should always decrease the smallest element and then make some greater elements of array equal to the smallest element.

Now simply brute force over the total number of values which you will make equal to the smallest element (suppose it is x) and the smallest element is decreased to a value y

then,

we know

sum of remaining elements + x*y <=k

calculate sum of remaining elements using 2 pointer or prefix sum (your choice)

and brute force over all values of x from 0 to n-1

and take minimum over all values

for more clarity look at the submission 140822105

»
6 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Here are my solutions for Problems A-D, you can check it out, since edu editorials take time, they come after hacking phase usually.

»
6 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

when I pressed sumbit for problem D, notification of contest end appears then I couldn't submit and get contest is over.

I got pretest passed on 18:36 UTC+2 :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to know what is wrong with my approach for problem c

submissionYour text to link here...

My approach:-

  1. sort the array

  2. taking subarray from index 1 to $$$i$$$.

  3. finding then how much should $$$ar[0]$$$ be decremented so that after replacing $$$i+1$$$ to $$$n-1$$$ index with the decremented number the sum is $$$<=k$$$

for this I used following equation Let $$$S$$$ denote the sum of number from index 1 to $$$i$$$

then $$$S + (n-i)*x<=K$$$ where x is the number to which all the remaining numbers will be changed into.

Found optimum $$$x$$$ from the above inequality and got the number of moves to do the said changes. Took minimum of all.

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

    I've posted almost the same comment, I got WA on test 2 with this approach as well

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

      yup saw just now.

      If you get yours resolved please ping me

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

        If we solve this equation x can never be zero.

        So the case where x is zero i.e no decrement operation and all set operations is not covered?

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

          $$$X$$$ from above inequality floor($$$(K-S)/(n-i)$$$) therefore it can become 0.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I found the error, int x = -1/2 will give x=0 and not x=-1. I had an implementation bug. My code failed for the following case-

        5 6

        1 4 1 1 1

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

          in my code I took care of that.

          I handled the negative separately.

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hey, can anyone look at my submission for C and tell me why my code fails. It fails on some testcase number 2571 so I can't see the testcase, but I can't figure out what's wrong with my approach.

Code

Approach: Sort array a. Take l = LLONG_MIN, h = a[0]. Then binary search on the values that I need to decrease the smallest number to. So my countMoves() function counts the moves if I transform a[0] to mid and then assign the new value to the largest numbers from the end until sum > k. If the number of moves are better than previous best, I increase l to mid + 1, else I decrease h to mid — 1.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks man, was able to rectify the mistakes, and made some progress, but unfortunately now I'm getting WA on test 6 fml

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Because the function countMoves() for value between the range is not monotonically increasing or decreasing. Instead it is [ decreasing -> increasing ]. So you need to modify your.binary search accordingly.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Unsure why my binary search solution for C isn't working. Could someone please take a look?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can you give me some hints about how to solve problem 1622E - Math Test?

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

    Maximizing the absolute value is kinda hard, so let's use the fact that there are at most $$$10$$$ students. For each student, there are two ways to evaluate the absolute value in their contribution to the answer: either $$$x_i - r_i$$$, or $$$r_i - x_i$$$. You can iterate on $$$2^n$$$ different ways to evaluate the absolute values, and then maximizing the answer without absolute values becomes much easier (use Contribution to the Sum technique).

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

      Thank you! Solved with your hint 140833798

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

      how to prove that this will correspond to a valid answer (for the max answer atleast) because for some permutations to maximize the sum even though you "force" a student to score lower than expected from the bitmask, you might still assign a permutation that makes the student score higher than expected or vice versa

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

        You don't actually "force" that to happen; you suggest it. $$$x_i>r_i$$$ is fine even if the bitmask says $$$|r_i-x_i|$$$ is the $$$i$$$th term. The purpose of the bitmask is to find the best $$$p$$$ (for that bitmask). After that, you can calculate the total sum with the given formula.

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

        I'm not able to figure out full proof, but maybe proof is based on statement that if we can't get answer for this algorithm, which provide maximum possible answer, then we can't get any other answer. Looks like need to assume that we can get correct answer for permutation with less result, which satisfies constrains for module expansion. Then with several number of swaps of two elements in permutation we can get maximum answer — contradiction.

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

        For some bitmasks it's true that final setup may not correspond to the definition of that bitmask. But it will give some value, which is less than or equal to one of the valid setups for the bitmask, which is equal to current bitmask with its invalid bits flipped. Let's say based on the value of bitmask, we assumed that for some student, X contributes positively and question scores contribute negatively. But we ended up with X <= score(1) + ... + score(M). But since, X — (score(1) + ... + score(M)) <= 0 <= (score(1) + ... + score(M)) — X, if we will flip all such invalid bits, we will end up with some larger or equal value which corresponds to one of the correct solutions of flipped bitmask.

        Now let's say maximum value occurs with some bitmask in a valid way. When we process that bitmask, we generate maximum possible answer, due to X's are fixed and if we distribute scores according to sorted list of correctly answered questions. Our distribution itself may be invalid, but since we know that mathematically this is the largest possible answer according to our formula, and it is less than or equal to some valid answer. This means that we will find our maximum value when we will process the bitmask which results in that maximum value.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Deleted.

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Hello everyone! I've come across someone whom I believe has cheated. How do I report the case?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C: I couldn't get where is the bug, can anyone help with this? http://codeforces.com/contest/1622/submission/140813410

»
6 months ago, # |
Rev. 2   Vote: I like it +89 Vote: I do not like it

Thanks to everybody who joined the stream! Specifically, thanks to TimmyThinMints for streaming with me, to BledDest and tourist for helping us with F, and everybody else for joining in! I very much enjoyed the problems, especially working with everybody to figure out F.

Update: link to stream: https://www.youtube.com/watch?v=RM96b68TPv8

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

    I used the idea you shared in your stream to solve C, but got stuck on test case 2. This is my submission with some comments : 140832114. Can you help to point out where the error is? Thanks!

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

      Try

      1
      3 8
      9 1 3 
      

      The optimal move is to convert 9 to 1 in one move, making the sum as $$$(1 + 1 + 3 \leq 8)$$$ but your output is 5.

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

        Oh, I think I see what went wrong now. When fixing the number of largest elements to be replaced, call it T, the correct approach is that we first replace the T largest elements with a[0] (the smallest) without modifying a[0]. We should do the replacement first because it is possible that we do not even need to decrease a[0], just like your counter example.

        What I did in my incorrect solution was to decrease a[0] first, then do the replacement.

        Thanks! This counter example really helped:)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

finally will be expert.thanks for the contest

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

If anyone is looking for video Solutions,Here they are(for A-D)

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please tell me what am I doing wrong here?

Code for C
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Are you unhappy about something? Giving credit to the original author (rather than stripping out this information) was surely the right thing to do and I don't see anything wrong with that.

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

      I would be happy but I know they did this so someone would hack the solution and then they would use that hack against me.

»
6 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

.

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

    Here is my guess of your code:

    • cnt is the number of 'big numbers' you want to set to a small value.
    • cnt+1 means the 'big numbers' and the minimum number in the array. All of the 'cnt+1' numbers will have the same value of the minimum number after the 'set' operation.
    • total is the total sum of the unchanged numbers.
    • (total-k) is the reduction amount needed to satisfy the requirement of the final sum of the array being <= k.
    • (total-k)/(cnt+1) is the reduction amount per element, element which changed.
    • (total-k+cnt)/(cnt+1) is the rounding up of the above division.
    • cnt + (total-k)/(cnt+1) is the total number of operations needed. The first term accounts for the number of 'big numbers' being set to the value of the new minimum. Each 'big number' requires one operation. The second term is the number of operations required for bringing down the minimum element into an even lower minimum if necessary.
»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

140835874 Can someone tell me what im doing wrong for problem C. The above code fails in the 4th test case(It's too large so can't paste it here ,sry ).

My approach is for every prefix of the array(sorted in decreasing order), what is the maximum value, the smallest number can be reduced to and then assign it to all the numbers in the prefix so that the sum becomes less than or equal to k. Of all such values im finding the one with min operations. Thanks :)

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

    You might want to research whether

    ll sum = accumulate(arr.begin(), arr.end(), 0);
    

    does what you intend it to do.

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

    use

    ll sum = accumulate(arr.begin(), arr.end(), 0ll);
    

    not

    ll sum = accumulate(arr.begin(), arr.end(), 0);
    
»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Binary Search Complete Code Explained . I have explained in best way possible. For anyone looking for solution using binary search.

»
6 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

If anyone would like a solution for problem C, here it is :

Solution for **C. Set or Decrease** https://codeforces.com/contest/1622/problem/C
»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone give me some advice please?

I could finish A,B,C in 30 minutes, however I could not work out problem D.

Maybe I can not solve such math problems,

could you please share some blogs or documents for me?

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

    Solve problems in Archive with difficulty >= 1800 with tags "Math" and "Combinatorics"

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

KOVAL_ IS A CHEATER!!!!!!!!!

140792053 140792490

please reject his submissions MikeMirzayanov__

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey! why my O(n*log^2(n)) solution for B is getting TLE? link:- https://codeforces.com/contest/1622/submission/140858246

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

    I'm not getting what you have done! But, this could be easily solvable by assigning numbers from 1 to x to the non-decreasing sorted order of disliked song and x+ 1 to n the non-decreasing sorted order of liked songs.

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

      yeah that can be done but why TLE? O(n*logn) should pass

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

        lower_bound(set) is slower than set.lower_bound try to fix it

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

          lol got ac by using set.lower_bound() link:-https://codeforces.com/contest/1622/submission/140871249 Thanks will always remember it!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how can correct output of any testcase be 0 for problem D, I have seen some testcases in hacks and couldn't figure out why the correct output is 0.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how D can be done in O(n^2), they are checking for cnt[1] <= k and also what is the relation with the boundary elements to be 1 or 0?

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

    For any substring to be shuffled, if the boundary element of this substring(right most) is not changed, no matter how much we shuffle all other elements, all the resulting substrings have been already counted during shuffling of substring which occured before(if current substring is not the first one to be shuffled). Therefore for generation of new strings boundary element must be changed. But this is O(N) solution using two pointers. I still don't get how to solve this in O(N^2).

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

      Can you give me an example please if you don't mind ?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D changed (x — y) % MOD, to (x — y + MOD * MOD) % MOD, and got AC. What a stupid mistake

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't solve problem F by thinking for a long time. I hope fast editorial.

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

I joined a few days back and participated in yesterday's round 120 and solved one question with successful submission but my rating has not increased. Could someone please tell the reason as I am joined just a few days back.

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

It's confusing that $$$n$$$ in problem D is only $$$5000$$$, for there is an obvious $$$O(n)$$$ solution using simple inclusion and exclusion.

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

    Maybe the purpose of that is to confuse contestants.

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

    It was an educational round for the participants rated lower than 2100. Their opinion about what is "obvious" and "simple" may naturally differ from yours. I would check the official editorial to see what was supposed to be the intended solution.

    Moreover, with a 12 hours hacking stage, there's always a risk that somebody may come up with a very evil hack, exploiting cache misses or branch mispredictions to significantly reduce performance. So setting excessively tight time limits and/or constraints for any problem is dangerous in this contest format.

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

      I agree with the first one. However, $$$n=5000$$$ is obvious not for $$$O(n)$$$ but for $$$O(n^2)$$$.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    O(n)? What about n choose r? It is at least O(n log n) right? Am I missing something?

    PS: just saw your code, you just used one fast exponentiation for the precalculations, forgot about this idea, it is actually O(n)

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

      Ah, you can calculate the factorials and their inversions in $$$O(n+\log\mathit{mod})$$$ time. You can see my submission 140805732.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

When will the editorial be available? Also, how can the answer be 0 in problem D? I don't undestand... please, help!

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

    We have to print answer % 998244353. So if the actual answer is a multiple of 998244353, then the printed answer will be 0.

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

    It happens when the actual solution is a multiple of MOD.

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

Is the editorial out?? If not when can we expect it? Thank you.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi I am avinash204, and I received a message today that someone has copied my code and it has resulted in getting a penalty ,however, I have no clue how someone else has the same code like me as I wrote it all by myself. What about my ratings will I get it or not?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Educational Codeforces Round is Always hard for me :( how to overcome this situation?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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