When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By errorgorn, 3 years ago, In English

Hello, Codeforces!

Welcome to the Codeforces Raif Round 1 (Div. 1 + Div. 2) supported by Raiffeisenbank, that will start on Oct/17/2020 16:05 (Moscow time). It will be a combined rated round for both divisions. Note that the start time is unusual.

All problems were authored and prepared by bensonlzl, oolimry, errorgorn, dvdg6566, shenxy13.

Ari gato to:

You will be given 8 problems, one of which would be divided into easy and hard versions, and 150 minutes to solve them.

We hope that statements are short and pretests are strong and that you find the problems interesting! Good luck, have fun and we wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

Thanks to Raiffeisenbank, winners will get awesome swag:

  • 1st-3rd place = Bluetooth speaker

  • 4th-10th place = Bumbag

  • 11th-20th place = Power Bank

3HCumg.md.png

Random 50 participants outside of top-20, who solved at least one problem will receive:

  • Thermos Mugs

  • Raiffeisenbank t-shirt

About Algorithmic Trading team in Raiffeisenbank

We develop a high-frequency trading (HFT) system for equity, currency and derivative markets. Our business edge is in technology. The main goal is to create a top-notch platform based on fundamental and statistical models and machine learning, with low latency and high throughput. The efficiency and scalability of our code give us a competitive advantage. We are passionate about code quality and strive for highest standards in product development.

If you are interested in internship and employment opportunities in the Raiffeisenbank algo-trading team Capital Markets, or want to get in touch with the bank's recruitment , fill out a form below.

FILL OUT FORM →

UPD: Scoring distribution: 500 — 1000 — 1000 — 1500 — 1750 — 1750 — (2250+750) — 4000

UPD2: Editorial out!

UPD 3: First ACs and winners

First ACs

A: 300iq

B: icecuber

C: Not-Afraid

D: Radewoosh

E: Errichto

F: fmota

G: Radewoosh

H: Radewoosh

Top 5

  1. Radewoosh

  2. Um_nik

  3. kczno1

  4. ecnerwala

  5. littlelittlehorse

Congratulations to everyone!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +1164 Vote: I do not like it

As a tester, make sure to stay hydrated!

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

    if you get more upvotes than blog i will swallow a battery

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +199 Vote: I do not like it

      go swallow your battery

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

      Would you like recipes?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +102 Vote: I do not like it

      I'll press charges.

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

        Please, some things are not good to joke about

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

          The press charges is an involuntary good joke though. Because battery.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Check the previous edition of the comment.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I'm aware, not a good topic to joke about haphazardly. Just saying there was a decent involuntary joke in there.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +33 Vote: I do not like it

      Blog: 20 upvotes Comment by Monogon: 28 upvotes!

      errorgorn, I think it's happening because of your reply to the comment.

      Good Luck :) Let's see who wins xD

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +2 Vote: I do not like it

        Well I upvoted the blog because of his comment. Haha no t didn't. I expected atleast one upvote from errorgorn

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

          Did you also downvote Monogon's comment?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +110 Vote: I do not like it

      Videos or it didn't happen

      (Please don't actually swallow batteries)

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

      You can swallow potato battery, lemon battery, etc

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

        ohya i think you can use potatoes / lemons to charge phones / be used as a weak electricity source (i think it might have something to do with electrolytes?). So they are batteries in that sense.errorgorn Just swallow a cherry or smth.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Also apple battery, grape battery can be the better choice

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Err......I don't think so. Because once the potatoes or the lemons are used as battery,it will be filled with heavy metal ions.So it will still be harmful.

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

      Swallowing batteries is pretty dangerous, right? (like what happens then it's in your stomach?)

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

        You must be very fun to have around at parties.

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

      I believe Monogon asked you to comment. Truly wonderful the mind of monogon is. The way you harvest upvotes is simply brilliant.

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

      Monogon is a record holder, and I think you said so because you are a master at swallowing batteries

      GL

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      Actually, fruit can be used as batteries.

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

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

      I believe that the real purpose of errorgorn's comment is to help Monogon hit 200 contribution.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You actually won the bet against the almighty Monogon!

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

    Monogon's Masterplan to hit 200 contribution with just one comment

»
3 years ago, # |
  Vote: I like it +90 Vote: I do not like it

Absolutely strange prizes distribution, but ok. Waiting for nice contest!

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

All the author are from Singapore zoo. Why zoo?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    Will be answered in task description (implicitly or explicitly)

    Don't worry though, statements will still (hopefully) be short.

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

    Firstly finish your drink then we would talk about it.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Please don't upvote the above comment. It is aesthetically pleasing as of now.

»
3 years ago, # |
  Vote: I like it -30 Vote: I do not like it


But unfortunately it will reward us a big negative delta :'(

»
3 years ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Ok it's not funny my bad

»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I just want T-shirt

»
3 years ago, # |
Rev. 4   Vote: I like it +349 Vote: I do not like it

Guys, list of participants looks weird.. There are lots of unrated users with the strange handles..

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

    Very interesting, there is probably just one person behind them all.

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

    Should tag MikeMirzayanov, I don't think setters can do much about it.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +146 Vote: I do not like it

      What if they change the rules a little bit so only rated participant can receive the prizes?

      Untitled.png
      any many more

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

        Yeah, rules should be changed.Prizes should be only for rated participant.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For which the participation of accounts seemingly would be much more. Mainly the submission of problem A can be huge with copied code in different account

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

    If all these accounts are created by a single person, I wonder how can someone remember so ugly handle names!!

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

      His browser will remember it with password.

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

      Microsoft UI Automation can certainly do some nasty stuff.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Looks like now these accounts have disappeared from the registrants list.

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

    what if new users will not write this round? (I think everyone wants T-shirts from legendary codeforces.)

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

    Fixed it.

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

None of the japanese coders here have noticed the Arigato pun in the statement :(

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

    I think they're trying their hardest to forget it :)

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

CF has really given us a variety of rounds this year :o

We've had a polish round, indian round, russian round, chinese round, japanese round and now we're being blessed with a singapore round followed by a romanian round.

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

Hope none of the duplicate account get prizes.. Not because I am envious it's just that it would be undeserving... (And now don't downvote me from your duplicate account else I will understand this world is doomed).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just curious about the facts on score distribution, I don't know--- what is the basis of scoring distribution? Why is scoring distribution announced before the round, and not before that? Also, do the rounds get tested without scoring distribution?

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

    We haven't announced scoring distribution because we're still discussing it :) I'm not sure about other round authors. Usually scoring will have some basis in difficulty, since we want to make sure that solves are rewarded fairly. As a result, obviously rounds must be tested without scoring distribution, since we get difficulty feedback (and thus basis for scoring) from testers.

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

It clashes with COCI can you delay the contest?

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

    These weekends: Codeforces Raif Round 1, SRM, COCI, AGC, Kickstart, CF Div2, Cook Off. Pls tell how to fit everything without intersections.

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

      Sounds like a problem statement

      There are multiple number of rounds these weekends, and coordinator antontrygubO_o needs to schedule the contests so that there will be no intersections! Please help poor antontrygubO_o figure out how to reschedule the contests! The first line contains N, the number of contests. For the next N lines, two inputs A and B, respectively the starting and end time of the contests will be given. Print the optimal number of...

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

      I think you missed today's ABC xD

»
3 years ago, # |
  Vote: I like it +92 Vote: I do not like it

Just like last week, I will go live just after the round ends to discuss my solutions https://www.twitch.tv/errichto

Also, that's the ugliest bluetooth speaker I've ever seen.

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

    Is that an excuse for not coming in top 3?

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

      Yes. Prizes in top20 aren't interesting so I will aim for 21st place. Or around 300th again, just like in last contest just to avoid getting unnecessary stuff. True story.

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

        Try not solving a problem. Who knows you might get the random one :D

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

        Seems like, you'll have to do with the unnecessary power bank now :p

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should always follow "True story" with "Yeah yeah"

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

    UPD: going live now!

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Google Translate told me that swag means goods that be stolen. How funny it is :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope this contest will be a good contest UwU

»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Hey, I'm flattered! Can't skip this one now

»
3 years ago, # |
  Vote: I like it +64 Vote: I do not like it

[memem.jpg

»
3 years ago, # |
  Vote: I like it -117 Vote: I do not like it

Is contest rated ?

»
3 years ago, # |
  Vote: I like it +114 Vote: I do not like it

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

    Codeforces ain't perfect, but when you compare it to other sites like codechef, it's considerably better imo.

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

    Is this supposed to mean that Mike does a bad job?

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

      I suppose not

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you believe world's best boss was bad at his work? That's offensive.

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

        i guess you got it wrong. my context was, after getting the same compliment for so many time, that will be Mike's reaction if this handshake happen in real right now

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

      I don't think being imperfect means you are doing a bad job. Every system will always have its faults, but codeforces is comparatively far better than anything else that is available.

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

        You went philosophical there. I'm just asking about the meaning of this meme. Michael in pic doesn't seem to know what he's doing.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there remote jobs at Raiffeisenbank?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    There is a form to join them at the end of the blog

»
3 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Another global round!!

»
3 years ago, # |
  Vote: I like it -32 Vote: I do not like it

I hope to solve all of problems

»
3 years ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

[Deleted]

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

    answered in annoucement (implictly or explictly)

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

      Sorry,that was sent by my classmate. I owe you an apology for not looking after this matter.

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

I remember I read short statements XD

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to hack a problem i locked?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Go to room tab at the top. Click on some submission. Read his/her code. If you believe you have a counter case, click on the Hack! button below.

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

      But why submissions is unclickable?

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

        maybe you are trying hack submissions of people not in your room, click on room on the dashboard and then try clicking on submissions of the people in there

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to delete an accepted submission? I got C accepted at 00:24, and then I thought I would test another solution, and it turns out the system only counts the last submission even if all of them are accepted. Please tell me why this is a thing, so annoying going down 2k places for something that doesn't make any sense

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

    Passing pretests during the contest does not mean it is correct. Therefore, sometimes a contestant may want to resubmit their solution which the pretests may not have caught their bug. This is why the rules are designed this way.

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

Did I choose wrong problem?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest!!

Amazing problem D!

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

    What was amazing about D? Seemed like mindless implementation to me. Unless there is some elegant way of solving it?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      Of course there is a elegant way!

      Code
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 4 in D ??

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

    well you can send your code to figure out where is your problem : ) (and dont send your submission link because ig seeing others code is unavailable rn)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      my code

      also, I think my code isn't clear enough to read :) so this is my solution

      spoiler
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        well you can match the number 3 with 3 type of things. 1) the ones who is not match with any 2(free one). 2) all of the columns with number 2 -> just put a higher mark on top of the last one and another one with the same height. 3) with another 3.

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

        You can match a 3 with a 2.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably
    3
    3 2 1

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what the fuck is pretest 3 of E

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do E?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Let's consider you converted the first part into x1 part, the second one into the x2 part ...

    find out how much you can reduce from the final answer if you cut the i_th part another time(convert it from x_i part to x_i + 1 part)

    put the values inside a priority queue and do the best option each time

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

how to do b?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's first iterate over the string and check if we have any cw or acw paths. Now, everytime we encounter an off path, we can mark it as a good path. If we encounter a cw path, we need to make sure that there are no other acw paths and vice versa. Also, another case is when the previous or the next path (leading to and from a node/snake) is off, we can mark this node as good.

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Isn't E just about always taking the maximum number m and separating it into p = m / 2 and q = m - p for all maximums, which can be implemented by priority queue? If not, could someone explain why?

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

    1 3 8 you way : 4 2 2 the better answer : 3 3 2

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

      Hi my logic gives correct answer for this case...but i got WA on test 4.

      Submission

      My logic : https://codeforces.com/blog/entry/83730?#comment-710946

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

        n = 2, k = 2, array = {1, 9}, your answer : 50, the real answer 82.

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

    4 8
    2 4 5 8

    You algo give answer 49 (2, 2 2, 2 3, 2 2 4)
    But correct answer is 47 (2, 2 2, 2 3, 2 3 3)

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

    It isn't always an optimal option. For example for input $$$[2, 4, 10, 5]$$$ your algorithm would divide $$$[10, 5]$$$ into $$$[2, 3, 5, 5]$$$ while an optimal division would be $$$[3, 3, 4, 5]$$$.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, crap, I didn't realise we were allowed to do that. RIP my problem reading skills. I'll leave trying to become better at problem solving and go and start learning primary school english.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For E, to generate k carrots with minimum eating time, I derived that the $$$a[i]$$$ carrot should be split into $$$\frac{a[i]}{\sum_ia[i]} * k$$$ parts. But since each carrot should contribute to atleast 1 piece, I could not incorporate this fact into that. Can anyone provide insight on this?-

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

    Any final split is equivalent to splitting $$$a_i$$$ into $$$j$$$ pieces, which can be optimally solved by for any $$$j$$$. The final answer will be the smallest that has a total of $$$K$$$ times. The function for the difference between $$$j$$$ and $$$j+1$$$ is nondecreasing, so it's optimal to maintain the sorted list of current changes for each $$$i$$$ using a priorityqueue/set.

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

one stupid bug made me submit WA on E if my solution is correct I'll throw myself from the window

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

    I just corrected my code for both E and F less than 5 minutes from the end of the contest... I think :(

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

    Go ahead, don't hesitate.

    At least you would stop crying in the comments.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      nah it's probably wrong I won't suicide unluckily for you

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

        check it after the testing

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

        u can do it now

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did it's WA it seemed correct to me Idk why it's wrong but I'm not that good to solve E so it's not a surprise

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

I got an idea for E : Was trying to make all k numbers as close as possible to give the minimum sum of squares. This follows directly from the well known QM>=AM>=GM>=HM inequalities.

Take QM>=AM Here QM is sqrt((L1^2 + L2^2 + ...... + LK^2)/K) WHERE Li is the length of carrot we give to ith rabbit.

Also AM is = (L1+L2+L3+....LK)/K.

Now L1+L2+.......+LK is equal to sum of lengths of all carrots.

From here we can see the minimum value is [(sum of all carrots)/k].

I was trying to implement a similiar approach on these lines but got WA on pretest 4 what am I missing ? Also I saw Errichto solve it in the first 15 minutes after (in addition to solving A,B,C obviously) and knew it was some clever problem.

My submission
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We cannot combine the lengths of 2 carrots.. hence i guess your approach is wrong.

    CASE:

    4 4

    1 1 1 9

    The answer is 84

    but you will print 36

    which is wrong. I hope i have not read the question wrong xD

»
3 years ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it
»
3 years ago, # |
Rev. 2   Vote: I like it +45 Vote: I do not like it

Lol, F is a "segment-tree-beats" problem. https://codeforces.com/blog/entry/57319

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +43 Vote: I do not like it

    F has linear time solution. We relaxed it to logarithmic due to tester feedback.

    Actually, if I remember correctly, errorgorn discovered segment tree beats solution quite early on, and we spent some time trying to kill it.

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

      In fact, majority FSTs were caused by testdata that was meant to kill segment tree beats (sorry!)

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

        My solution works (982ms), so I enjoyed the contest :)

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

      Even $$$O(n^{\frac32})$$$ works! On worst case locally it works 0.2s for me, on systests it worked in 62ms ;)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did a O($$$n^{\frac{3}{2}}$$$) solution but it did not pass test 48 :/ can you share your submission please?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Mine is pretty lightweight. https://codeforces.com/contest/1428/submission/95782858

          I add characters one by one and compute contribution of all substrings ending at each character. When doing that I am interested in intervals of ones of growing lengths when looking from (current) end to beginning. There can be at most $$$O(\sqrt{n})$$$ of them, so I can iterate over all of them. This solution can be easily changed into linear, but it was easier to leave it as it is and it was fast enough.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact, you can set them to 0 using brute force.

    It's also a $$$O(n \log n)$$$ solution, but i don't know if it will FST.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved F with normal segment tree though. The idea is to iterate l from high to low and maintain the lowest r such that f(l,r)>=k for each k.

    Submission: 95806181

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution was O(n)

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I spent most of my time trying to solve D. I thought my construction was perfect, however, the judge didn't think so. T_T

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hey, is there anyway to solve Problem 'E' using Binary Search ? I tried to solve 'E' using Binary Search, but could not pass pretest 3 link to my code : https://codeforces.com/contest/1428/submission/95803093

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Didn't you forget to call fans.clear()?

    And I think it's just a wrong solution.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I passed pretests for Problem C. But forgot to lock it. Does that count?

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

fastest editorial I've ever seen

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we've had fast editorials in most recent contests. It's a great improvement for codeforces i think!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish i could know what is the test case 4 of problem E....

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I am so sad that my solution to problem D was wrong just because the grid numbering started from top. Couldn't change it as it was in last minutes of the contest.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For E is there a fault in logic if I try to binary search for the max height of the carrot such that the total number of carrots is K. then evenly divide the carrot heights and find the answer??

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

    Yes. Consider the case where you cannot actually evenly divide things, for eg

    4 5 100 100 10 1

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

    Yes, the optimum set of lengths might not be the one with the minimum maximum length. Consider the case n = 2 k = 5 and initial lengths 235683 and 675850 (sorry for the big numbers).

    The optimum lengths are 235683, 168962, 168962, 168963, 168963.

    However it is possible to get to 117842, 117841, 225284, 225283, 225283. And the maximum value of this sequence is smaller than the optimum one.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Yes totally makes sense.. I know the other solution using priority_queue (didn't click during contest tho) but i couldn't find why this wouldn't work... bad dayyyy.. But good round!! Thanks for the help!! :D

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

Sample test cases in E were literally useless

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

    I think the samples were fine. They should just be there to make sure that you understand the problem properly. Creating your own nontrivial samples to test on and see if your algorithm works is something that's important and should be done by the contestant.

»
3 years ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

https://www.youtube.com/watch?v=g22-5e5xAGA

Watch Video Editorial of all problems

Also do watch , cp experiences of IIT Madras students

https://www.youtube.com/watch?v=8n12sCm0VUI

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round!!! Fun Fun Fun!

P.S. Problem D 122+ system tests? O_o

»
3 years ago, # |
  Vote: I like it -32 Vote: I do not like it

https://www.youtube.com/watch?v=VI5bL7Csc7w

Video Editorial of all Problems

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the contest. :)

I really liked problem D!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

errorgorn, will there be a list of t-shirt recipients?

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

    i have no idea how the ppl getting shirts are selected

»
3 years ago, # |
  Vote: I like it +119 Vote: I do not like it

When your last attempt of saving your rating in last 10 seconds of contest got rejected by a semicolon

(It got accepted after fixing the semicolon)

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Was log^2 with segtree intended to pass in F? I got TLE on recursive version and accepted (<500ms) on iterative one. If log^2 complexity can easily pass why not set the limit to 4s?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where we can know who is winner ?

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

    The most important question for many of the CF users who gave round today. xd

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a human, I'm going to die without becoming a Grandmaster :"

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Enjoyed This Round clear problems statements !!

»
3 years ago, # |
Rev. 3   Vote: I like it +61 Vote: I do not like it

Here's my solution to H:

Firstly for each ring choose a random number from $$$[-20, 20]$$$ and move it by such shift to make sure that nothing very bad will happen.

Now consider the rings in random order. Let's take some ring $$$i$$$. Move it clockwise and stop and the moment when the result decreases for the first time. After this, shift this ring counter-clockwise by one.

After such a phase all arcs are grouped. By grouped I mean that every two arcs either share their exact position or don't touch each other at all and the size of each group is at least $$$2$$$.

The number of groups is ofc $$$\leq 50$$$, but it'll be a bit less in average. Now it'd be nice to discover how the indexes are grouped. To do this, initialize a set of groups, initialy empty and consider all the rings (again in random order). When we consider ring $$$i$$$, then move it by one clockwise. Nextly, loop over all the existing groups, and for each of them take its representative and move it once clockwise and once counter-clockwise. It's possible to know to which group ring $$$i$$$ belongs (or if it's in a new group). Then shift ring $$$i$$$ counter-clockwise by one to fix the situation.

So we know how the rings are grouped, but we need to know their order (and distances). Take one group and it's representative. Let's move it clockwise and stop when it bumps into another group. In this moment iterate over all other groups, for each of them take one representative, move it once counter-clockwise and once clockwise. It's possible to know if we bumped into this group (and ofc we know the travelled distance). Then move the ring back to its group.

After this we know everything.

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

    fun fact: When code forces ran your solution during contests on systests, it gave "runtime error on test case 21" from too many queries.

    In the end, it ended with 14848/15000 queries, what a clutch rng!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does the random shifting in the first step stop very bad things from happening WHP?

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

      Imagine having the results $$$0$$$ at the beginning. Wouldn't we need $$$O(n \cdot m \cdot \log(n))$$$ moves to move the arcs to the groups (even with an optimal order)?

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

        Not sure what you're asking. There's a one-parameter family of test cases of the form 0 (k times), 20 (k times), 40 (k times), ..., 20*ceil(100/k) (100%k times), and variants with distributions more skewed to the one end than the other.

        You're randomising the order in your "move clockwise until gap" phase to avoid a quadratic blowup when k is small. When k=1, for instance, each iteration of "move clockwise until gap" creates a new gap, giving you an expected O(mn log(mn)) moves or so. When k >= 2, though, the new gaps take a while to form. In particular, the first sqrt(n)-ish iterations won't create a new gap.

        Numerically, when k=2, I get a mean of 13060 steps and a standard deviation of 2500 steps just in the "move clockwise until gap" phase.

        I can imagine a tight arithmetic progression being bad too. Intuitively, random jitter shouldn't change the nature of an arithmetic progression instance too much. Why does the initial randomisation step help with this dynamic?

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

          I didn't say that it's a correct solution.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How much time does it take to update ratings?

»
3 years ago, # |
  Vote: I like it +79 Vote: I do not like it

Congratulations to prize winners!

Bluetooth speaker:

List place Contest Rank Name
1 1428 1 Radewoosh
2 1428 2 Um_nik
3 1428 3 kczno1

Bumbag:

List place Contest Rank Name
4 1428 4 ecnerwala
5 1428 5 littlelittlehorse
6 1428 6 300iq
7 1428 7 gop2024
8 1428 8 ksun48
9 1428 9 neal
10 1428 10 maroonrk

Power Bank:

List place Contest Rank Name
11 1428 11 Benq
12 1428 12 Endagorion
13 1428 13 Errichto
14 1428 14 yosupo
15 1428 15 zeronumber
16 1428 16 Kilani
17 1428 17 Muffinhead
18 1428 18 244mhq
19 1428 19 Worteltje
20 1428 20 tfg

Thermos Mugs & Raiffeisenbank t-shirt:

List place Contest Rank Name
57 1428 57 UnstoppableChillMachine
184 1428 184 Yousef_Salama
305 1428 305 LJC00118
526 1428 525 yuusanlondon
747 1428 746 reiracofage
804 1428 804 VivekUchiha
1126 1428 1126 siddhant1
1654 1428 1654 sh_mug
1841 1428 1838 sahilshelangia
1934 1428 1934 sojisan
1967 1428 1962 _radioactive_
2107 1428 2105 kansal_2106
2625 1428 2625 Igorbunov
2762 1428 2757 sandeepkumar
2885 1428 2876 aniket_lakhotia
3063 1428 3058 ab_dtu
3165 1428 3164 the_traveler_
3424 1428 3416 akash_garg
3735 1428 3732 gxy001
3894 1428 3893 adimiclaus15
4225 1428 4224 rsgt24
4226 1428 4226 agarwala2512
4418 1428 4418 NOT_PRO
4532 1428 4532 hritik_456
4549 1428 4548 aky121
4761 1428 4760 suresh_babu
5010 1428 5010 joker2
5176 1428 5175 avinashrao
5241 1428 5240 sauraviiitp
5311 1428 5311 pako1609
5321 1428 5321 coder_rohit_r
5431 1428 5430 FatemaKapadia
5459 1428 5459 _Vishwa
5589 1428 5586 evilbegin
5795 1428 5794 Mohamed_El-sayed
6020 1428 6018 Min_Young
6866 1428 6866 KaoYanGou007
7055 1428 7055 Moaaz-Mahmoud
7104 1428 7104 youcef
7216 1428 7216 viven0525
7410 1428 7402 1600-1700
7644 1428 7595 brytnispiers
7861 1428 7861 B1GGersnow
7898 1428 7861 Palak_8840
8055 1428 8050 Khalid_ibn_al_Walid
8131 1428 8112 biswa_990
8475 1428 8466 srinidhi21
8551 1428 8533 mr.saylander
8813 1428 8813 phoenix_1402
9351 1428 9340 Liniou

Note that it is possible that some cheaters will be removed, but we will not recompute prizes unless one of them is a cheater.

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

    Congratulations to the Lucky 50!

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

    Thanks for the contest! Can I request a power bank instead of a bumbag? :)

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

      I'll check if it's possible.

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

    Damn it feels good when your friend is in the list...

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

    My rating has dropped by 100, but I won the T-shirt and Thermos! Should I be pleased? Or should I be sad?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lol

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When will we receive the gifts?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In a week or two you will be contacted by System or someone with bold black handle to check your address and they'll provide you further info.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I didn't receive my t-shirt yet. Will it take some more time to reach?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Job ! =)))))))

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this get WA in E ?

Input
Output
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Your output is

    X..X
    .XX.
    ..XX
    ....
    

    which would translate to 5 3 2 1 instead of your input.

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Does someone know how to download full test cases for a problem? My C attempt gave WA at the second test set's case #92, but couldn't see what it is.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nope..no way bro

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

      Ah that's sad.

      Essentially I tried to find a counterexample for my WA attempt, in which I consider the input string as "(some_number_of_B)(start with A and end with B)(some_number_of_A)". The middle part (start with A and end with B) is then reduced to contain only As or Bs, so the string is further reduced to (some_number_of_B)(some_number_of_A). I know the editorial solution is correct and simpler but struggled to find the counterexample for the idea above.

      Any suggestion is really appreciated!

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

The contest was very well prepared and I actually had fun competing, so thanks to the organizer. But I have a doubt.

I am not sure this kind of contests should be rated for "strong contestants" (let's say IGM). Problems E and F were quite standard, and also G was just a variation on the knapsack-problem (it was not easy to understand the details of the associated knapsack-problem, but it was pretty clear that it shall be stated as a knapsack). I think this kind of problems are a bit too standard to play a role in the rating of high-rated contestants. Once again, I am not saying that this contest was not good, I am sure it was interesting and pleasant for 99,9% of the participants and therefore it was a very good contest (clear statements, nice problems, good pretests and good tests... high-quality overall). I am wondering whether it would be better to make it clear in some way (before the round) how original the problems are (adjusting accordingly the rating range).

I am implicitly suggesting that a system similar to the AtCoder one (only AGCs are rated for strong contestants) might be beneficial also for Codeforces. In general, I feel that what I consider interesting is quite different from what a contestant with rating 1910 considers interesting (and I guess that this difference is even bigger for contestants stronger than me) so it is strange that we have exactly the same set of rated contests. The main reason is that there are many nice problems (for example E and F of this round) that are incredibly cool for a candidate master but quite standard for an IGM (in the same way that sorting an array in $$$O(n\log(n))$$$ is incredibly cool for a novice, but standard for anyone who knows a bit of stuff).

I would like to hear the opinion of some strong contestants... maybe I am the only one with this opinion (and maybe noone will ever read this late comment).

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

    Hi, thanks for the feedback!

    I'm not exactly a strong contestant but I do agree largely with your comments. I'd say the problems E and F are kind of classic at higher levels, and that the contest is easier than what you'd expect from a normal div1.

    About problem G, I didn't think that it was that standard when I set it. That's probably because I found the observation about 0,3,6,9 the hardest part of the question. So while the knapsack part is classic, I found the hardest part of the question the ad hoc observation at the start. Also interestingly no tester solved G during contest time (although some almost solved it).

    About differentiating "original" and "classic" contests, I think it'll be a good idea. However, I'm not sure about the feasibility since usually problem setters don't have much flexibility in choosing the type of problems since we don't have enough good problems to play around with the style of the contest.

    An idea is to look at the problems after they're proposed and then decide which category it falls under? Random thought I had: what if combined rounds are more of the classic type and have a rating cap. Rounds which are div1 + div2 (5/6 problems each) be more of the original type (at least for div1), and possibly harder now.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree that problem G was less standard than E, F; I mentioned it because if G had been very original it would have made the whole contest original. Regarding "no tester solved G during contest time". I am not claiming that G is easy, in fact it is not. But originality and difficulty are almost orthogonal properties.

      Regarding your proposals and comments on how to solve the issue... I simply have no opinion. I don't know whether combined rounds should be capped, or if separated rounds should be capped (or if the capping should be independent of the type of round) or if the threshold for div1 should be raised.

»
3 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Is anybody able to access the editorial right now? It was available an hour ago but now when I click on the link to editorial, it says "You are not allowed to view the requested page" and redirects me to the last opened page on codeforces. Please confirm if you are facing the same problem.

Upd: Fixed Now, Thanks

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

errorgorn I guess there is a glitch with the editorial, It says the editorial is not accessable. Please check once

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help wanted :
For problem E, I binary searched on the length and found out the maximum possible length in which the carrots may be divided. It'll be great if someone can explain me why its wrong.

https://codeforces.com/contest/1428/submission/95793574

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

    Who's this cutie pie muah muah

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider splitting 100 into three slices.

    When you take a cut of size 33, you split it into 3 '33' length cuts and 1 length '1' cut.

    33 33 33 1, and hence you say this is suboptimal and you proceed to 34, which results in this splitting: 34 34 32 which you falsely claim optimal. (Your answer will print sigma square of this array)

    However, you could have split it as 33 33 34, which is a case your code doesn't test. (Turns out this is the most optimal split)

    i.e it is not optimal to always take arr[i]/mid portions along with arr[i]%mid extra. sometimes merging arr[i]%mid with another is more optimal.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    ..