errorgorn's blog

By errorgorn, history, 3 years ago, In English

Hello again Codeforces!

errorgorn, oolimry and iLoveIOI are glad to invite you to participate in Codeforces Round 723 (Div. 2) which will be held at May/28/2021 17:05 (Moscow time). The round will be rated for the participants with a rating lower than 2100. Participants from the first division are also welcomed to take part in the competition but it will be unrated for them.

You will be given 2 hours and 30 minutes to solve 6 questions. One of the puzzles is interactive, please read the guide of interactive problems before the contest.

We would like to thank:

We hope you find the bugaboos interesting and fun! Wish you high rating!

Here is scoring distribution because you guys deserve it <3

  • 500 — 1000 — (750+1000) — 2250 — 2500 — 3500

Btw, remember to downvote all testers who writes stupid comments to beg for likes.

UPD: editorial released

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

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

stupid comments to beg for likes

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

As a participant of the testing contest, sir antontrygubO_o has barred us to post "as a tester" comments. So following his order, Enjoy another consecutive contest under lord Anton ! The authors did a great job with the problems ! Wish you high rating. !

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

    True, as a participant of the testing contest, I will not be writing 'as a tester' comments since Anton sir told us not to.

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

'Btw, remember to downvote all testers who writes stupid comments to beg for likes.'

The testers right now:

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

    How can we forget this torture to us :/

    Screenshot-20210525173114-1920x1080

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

Smart comment

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

Jokes apart, the problems are really nice and errorgorn sir doesn't like long problem statements so it's going to be a nice contest.

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

    I guess the statements are so short that the author decided to call them questions.

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

Is it ok for non-testers to ask for upvotes?

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

    Yes ofcourse. You have mine :)

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

      I've never seen a man work so hard for contribution++

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

        civil war

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

        Unfortunately, T1duS is done with his quota of comments on this blog, and now is crying in front of us all others on testers grp that he can't reply to you.

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

The last round had very nice problems!! Expecting even more nicer problems this time!!

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

    Glad to hear that you liked the tasks,

    If you are mad at anyone, you should be mad at me or the other setters. As a coordinator Anton did the best he could/was humanly possible.

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

Thanks to the last round, I can be rated this round :D

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

.

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

Div 1.5 on it's way :(

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

Which problem is an Interactive Problem? It should not be anyone one of A, B and C. :(

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

    I guess may be C will be interactive. As it is also divided in two significantly easy questions.

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

      Why does that indicate interactivity?

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

        Maybe some number of queries based.
        Easy one — at most N queries.
        Hard one — at most N/3 queries.

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

        If not interactive then it must be a brainteasers or why would c will be divided into similar difficulty of A and B?

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

          Looks like you haven't participated in many contests having subproblems. It always has been this way.

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

          Because C has been split for non-interactive problems before? What's so special about interactivity?

          Also in all likelihood, solving C2 (i.e. both parts of C) will be harder than B. It is just that it has an easy subtask.

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

Don't forgot to consider the UNUSUAL START TIME

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

    is't it unusual start time ??

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

      It is unusual , I don't know the reason of you getting so many downvotes , Maybe I will also get some now :/

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

    I was surely going to miss this round. Thanks :)

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

..2 hours and 30 minutes to solve 6 "questions"

Radewoosh triggered

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

It will be my first div2 round. Just do it!

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

How do you fix contest duration?

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

    We have testers to virtual the problemset and they give feedback on whether the contest should be longer or shorter. And we kinda agreed that 2 hours 30 minutes was good.

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

Ignore.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +89 Vote: I do not like it
    • We hope you find the bugaboos interesting and fun! Wish you high rating!

    Please read annoucement more clearly next time

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

Can anyone tell me, how does this "750+1000" scoring works?

I hope the contest overload Codeforces server with great participation just like now when I am reading this announcement :)

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

    It means there will be C1 and C2 bugaboos, with C1 being easier, therefore scored 750.

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

Race to specialist begin ...

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

I came looking for bugaboos, I WAS NOT DISAPPOINTED

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

nice contest

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

Can a tester say the round was bad for once please :D

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

    We do all the time, but only to the authors/coordinators. This is because we like to watch contestants suffer, so we have every motivation to avoid telling if the round is bad. And we might even lie and tell that it is good when it's not.

    (Anyway, this round is good.)

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

      So, should i trust that the round is good as you said "anyway, this round is good" or not as you said "And we might even lie and tell that it is good when it"s not".

      My mind gave many errors on reading your comment XD

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

    I will, when I test a round (sad face) :(

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

Why are we not using bugaboos instead of questions?

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

Just couldn't resist more.

Codeforces Round #753 Memeset

The following memeset is divided into 5 memes, one of which has two parts, so basically 6 memes. You will have 30 seconds to waste on it.

I sincerely hope you all enjoy it.

Odd Bugaboo

A

Bugaboo Ragnarok

B

Arei Syndrome

C

Bugaboo Apocalypse

D

A no namer cyan posting memes, meanwhile THE red coder-

E1

Close up Rade-vieew-shh:

E2

Thanks and don't wait for editorial.

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

I am damn Sure that Binary Search will be Used in One of the Problem in this Contest.


How?
Smartly Written Post!

Upvote if you Found it Helpful !

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

    I think it's a trap. They are misleading the harmless contestants to just walk into the world of Binary Search.

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

    Not just any one of the problems. I bet it will be the interactive problem. And most importantly, it's not even surprising.

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

CF never disappoints us. Bugabooset

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

now that cf changed problemset to bugabooset, i can happily tell, i cant wait to solve more bugaboos in this round with you all!

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

I hope there will be short tasks.

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

Hope I reach Pupil today. Wishing high rating to everyone:)

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

pretests || system tests

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

Bugabooforces

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

C score distribution is 1750?why it is in brackets?

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

    There will be 2 sub bugaboos C1 and C2 with C1 be easier as compared to C2.

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

      2 different tasks with c1 different and c2 different like B1 and B2 in 721#Div2 ?

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

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

Wish I would be able to solve at least 2 bugaboos in this contest

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

iLoveIOI What happened to you after 2018?

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

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

Hope the question statements will be short and clear

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

zadgavgava.

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

    hahaha.. people trying hard to create memes to get some upvotes.

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

2 hours and 30 minutes for 6 problems? This one is going to be tough

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

hope this contest will be the one to break my negative rating streak :D

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

.

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

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

Problems were very Interesting!! Thanks to the setters.

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

    How are these problems interesting? Just speedforces from A — C2.

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

I literally hate 1111.

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

Now, we all hate 1111

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

    After watching solution you will hate yourself (for some time) xD

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

My Health gone negative today.

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

lmao ‎‎‎‎‎‎‎‎‎‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎

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

Gave my best, but this contest was too hard. Solved 0 out of submissions for a, b and c. Have to improve my intuition.

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

E is just this paper. Did authors know about this? It was a bit too easy to find.

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

    I think we really did not know about this. So sorry about that.

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

    I am very sorry, I will try to research more next time.

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

Had a very bad contest. Was C some sort of greedy?

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

    Yes. C1 could be done by DP though.

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

    yes , tbh i found it easier than B. In C you just need to remove most negative element when overall sum becomes less than 0 . Let's hope it passes pretest .

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

    Yeah. You maintain a value h (health), ans (longest sequence), and Q (a priority queue of used potions), and at each element, if h + a[i] >= 0 you increment h += a[i], ans++, and add a[i] to Q. If h + a[i] < 0, then check whether we can improve h at that index by swapping the smallest used value in Q for the current value of a[i].

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

      Got it. This was too easy, well, I was thinking in some other direction entirely. Thanks to everybody for the help.

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

    Yeah it is kinda greedy. For every i from 1 to n let's say ps = (sum of positive integers till i) and ns = -(sum of negative integers till i) and also you maintain all negative elements in a priority queue. So you will remove the least elements until ns<=ps for every i and update answer by counting i-(number of removals).

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

    You can solve it also using a segment tree.

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

      I love how you always cover your code with comments regarding your thought process

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

      Can we solve this without segment tree ? We can keep on removing it ( negative taken a[i]) from previous positive values (of a[i] ) , and if we can remove it , we add it to ans . Here we take the negative number with min abs(a[i]) first ,similar to your idea. spookywooky . Please help i tried this way, getting wrong maybe impletation error.

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

Out of curiosity, is it possible to compute the optimal swapping cost in problem D for two arbitrary strings in less than O(n ^ 2)?

After realizing the answer was always made up of contiguous blocks, I bricked on this subproblem for an hour before realizing I could calculate it in O(n * characters) as long as one string had that property.

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

      The level of ooof given I got AC on this problem during the contest...

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

    It's the inversion count

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

    Let x be the first character of A. We can always say that the first occurrence of x in B will be the character that will go to the first slot in B(otherwise we can see that for any other occurrence of x should swap with the first occurrence of x and by doing that we are swapping two same characters which is not optimal). So now whe have the following algorithm: Take first character in A — x. Find the first occurrence of x in B. Move x to the first slot. Remove both xs from A and B and repeat until there are no characters left. You can store the list of position of each character in B and using Fenwick tree you can efficiently calculate the position of x.

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

      Yeah this is exactly what I was trying for an hour, including using the Fenwick Tree as a difference array to see how much I had to "adjust" the original position of the x to get its actual position. Couldn't figure out the exact details of what to add / subtract to adjust it in the case where a character gets shifted right multiple times.

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

Some one please tell me about approach of B

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

    If x > 11 * 111 — 11 — 111 (frobenius coin problem), answer is YES. Otherwise, answer is yes if x is obtainable by combination of 11 and 111.

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

    I thought of it this way. If you add 111 to any multiple of 11, you are basically adding 1 mod 11. So if your given number is >= x*111 , you can shift the mod by x times. It's easy to see that if x>=10, any number is possible.

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

What's your approach to Kill Anton?

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

every random logic passed first pretest on problem D but failed on second. What was story behind putting "ok You are epic!" in pretest 1 of D ?

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

    The first pretest is just the sample test from the statement. And the OK message is probably the same for all test cases (in this contest at least), but obviously the system won't show more testcases before the end of the contest.

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

I love Anton Sir very much. (:

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

problem statement for D was quite entertaining and funny loved it ♥

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

    How to solve it ? I summed the position at which each character is occurring and then put those characters whose sum is lowest in last.

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

      I applied brute force , grouped all same characters together and solved for each permutation of ANTO and it worked

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

        Thanks. Can any one provide intuition or proof why it will be correct (grouping similar characters together) ?

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

The title of problem B is giving a clue for solving the question

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

What the hell was problem B! Spent almost the entire contest thinking on it!!!!

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

    Is just looking mod11, it can be done in O(1) per query with 11 if

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

    If n >= 11*111, you are guaranteed yes, because you can subtract values of 111 until you get a multiple of 11.

    Then we know we are only concerned with 1111, 111 and 11. We can brute force every combination of these that doesn't take us over 11*111, and update an answer array with YES for each found value (default is NO). Precompute this to avoid TLE.

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

      How can we be very sure that we will always end up getting multiple of 11 by substracting 111 repeatedly for n>=11*111

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

        111 is congruent to 1 mod 11, so 111*n is congruent to n mod11, so you can get a number with any rest mod11

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

        11 and 111 are coprime. Suppose n % 11 = k, 0 <= k < 11. 111 % 11 = 1. If we subtract 111*k, we have reached a multiple of 11. Since k < 11, n is still positive.

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

        The mathematical answer is that 111 is 1 modulo 11, but if you're not familiar with modular arithmetic, I can explain it differently.

        Every number $$$x$$$ can be expressed as $$$a×11 + b$$$, where b is between 1 and 10, inclusive. For example, $$$111 = 10×11 + 1$$$, or $$$12345 = 1122×11 + 3$$$. (Another way to write this is that a = x / 11, and b = x % 11, where / is integer division, and % is the remainder after division.)

        That means:

        1×111 = 111 = 10×11 + 1.
        2×111 = 222 = 20×11 + 2.
        3×111 = 333 = 30×11 + 3.
        4×111 = 444 = 40×11 + 4.
        5×111 = 555 = 50×11 + 5.
        6×111 = 666 = 60×11 + 6.
        7×111 = 777 = 70×11 + 7.
        8×111 = 888 = 80×11 + 8.
        9×111 = 999 = 90×11 + 9.
        10×111 = 1110 = 100×11 + 10.

        Since every remainder between 1 and 11 occurs exactly once, we can turn any number greater than 11×111 into a multiple of 11 by subtracting the appropriate multiple of 111 to reduce the remainder to 0.

        For example, $$$1234 = 112*11 + 2$$$, so we can subtract $$$2×111 = 222$$$, to end up with a multiple of 11: $$$1234 - 222 = 1012 = 92 × 11$$$.

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

      You can make it a bit more optimal. $$$x=11$$$ and $$$y=111$$$ are coprime, so every number can be expressed as a linear combination of them. I guess you can check what this linear combination is and check if both are positive, or you can brute force up to $$$11*111-11-111=1099$$$ which would be the maximum number not expressible with positive coefficients.

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

        Indeed. Really the question amounts to

        ans = (n >= (111)*(n%11) ? "YES" : "NO")

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

      You can avoid precomputing just by noticing that the conditional if(x%11==i&&x>=111*i) must be true for some i between 0 and 10 if the answer is YES

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

        Yep. A few ways to do this. Quite a nice question.

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

    Every number with even number of ones is a multiple of 11, and every number with odd numbers of ones is 111 + a multiple of 11. So the answer is 11x + 111y. Floor(n / 11) should be >= (n mod 11) * 10 to have an answer, i.e., trying to take every 1 in the mod with 10 elevens to form 111.

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

    While testing, current problem B used to be A. We were made to solve it as A :notlikeduck:

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

I got RE#5 of problem D, can anyone help me? Thanks!

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

:(

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

as a first AC, you are late AC.

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

From problem C I saw the real power of Priority Queue! Good contest :)

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

    Actually there are few cases at each index(from left to right). If current value is negative and reduces the total current sum to < 0, then just check minimum element from priority queue(of negative numbers which have seen and added to the sum until this step during the iterations) if this value is less than it, just ignore this step and go to the next, otherwise just pop priority queue and push this value into it, also change current sum. Note that 1) We need all the positive numbers, it's not the problem of course. 2) If current value is bad to choose this time, it's also bad idea to pop pq twice or more, it's much better to skip this value only(or swap with minimum negative to improve current sum). If current value isn't bad, then just increase total amount and change current sum too(also if this value is negative, push it into our pq of negative numbers).

    // Below see code

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    int main() { ios::sync_with_stdio(false);

    int n;
    cin >> n;
    
    vector<ll> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    
    ll res = 0;
    
    priority_queue<ll> pq;
    ll cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur + vec[i] < 0) {
            if (!pq.empty() && cur - (-pq.top()) + vec[i] >= 0) {
                if (-vec[i] > pq.top()) {
                    // don't need do anything, if this value doesn't improve sum
                }else {
                    cur = cur - (-pq.top()) + vec[i];
                    pq.pop();
                    pq.push(-vec[i]);
                }
            }
        }else {
            if (vec[i] < 0) pq.push(-vec[i]);
            cur += vec[i];
            res++;
        }
    }
    
    cout << res << endl;

    }

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

How many of you are getting bad rank because you came 30 minutes late because of your carelessness. It happened to me as well. :(

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

It was a very strange round for me.

A) No idea, let's random shuffle
B) Spent some time, maybe 5-10 mins wandering whether my solution will pass and why it passed and whether I should optimize it just because thought that 500 * 10000 amounts to billions
C1&C2) Made some stupid mistakes and got -150 for incorrect submissions
D) Immediately got what the answer should look like. Spent an hour googling how to find inversions and copy pasting some functions from stackoverflow until it worked.

After which surprisingly found that I am quite at the top and left the contest because knew that I wouldn't be able to solve E even for an entire hour

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

Thank you for the round. I really liked these problems, but due to my low level i couldn`t solve all of them. Waiting for more rounds from you :)

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

.Pics-Art-05-28-10-35-34

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

    The place under the picture should be mine

    Cause I still don't know how to solve A constructively, just random shuffled it

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

      I did the same after noticing that the upper limit for n was laughably small. Also having no idea how to solve problem A constructively made me finally switch from Ruby to D programming language. Because a 20x-100x speedup surely increases chances for a non-optimal solution to be accepted.

      It's interesting that there were two persons using D and only one person using Ruby among more than 10k contestants today.

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

Today's contest was shit for me

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

    How come? You haven't even participated

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

      Are you sure about this ?

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

        If you haven't tried to submit any solution, then the system assumes that you haven't participated at all. Just being online and reading problem descriptions isn't enough.

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

MikeMirzayanov When will you update the rating ?

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

 ok Nice! (Bugaboo A)

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

It was a nice contest with understandable problem statement. I loved doing this contest thanks for the contest

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

Thanks for the fun bugaboos! Here's a link to my screencast. (An HD version will be ready within the next few hours.)

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

Codeforces these days is coming with tricky and tough questions to think upon in contests..isnt it ?

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

Can someone share more problems based upon Chicken Mcnugget Theorem .

Thanks in advance .

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

I solved problem C1 in the last minute, but got so excited that forgot to submit C2 :(

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

Is the next Codeforces Round for DIV2 going to be in 2 weeks?? If yes then why such a long wait?

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

    A DIV1+DIV2 contest is in two days and you are eligible to participate in it. Also more DIV2 contests are likely to show up in the schedule. Many of them are announced with just a few days notice.

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

Problem C is a known problem. 11 days old blog link . Similar problem link.

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

After the contest i was assigned to a room.What does that mean actually?

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

    You can only hack those people who are in the same room with you (after locking the problems).

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

What is wrong in this solution for question c2 ?

include <bits/stdc++.h>

define ll long long

define ld long double

define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const ll MOD = 1e9 + 7; const ll N = 2e5 + 5;

ll n, a[N], sum = 0, ans = 0;

int main() { IOS;

cin >> n;

set<ll>s;

for(ll i = 1; i <= n; i++)
    cin >> a[i];

for(ll i = 1; i <= n; i++)
{
    sum += a[i];
    ans++;
    s.insert(a[i]);
    if(sum < 0)
    {
       ll x = *s.begin();
       sum -= x;
       s.erase(s.begin());
       ans--;
    }
}

cout << ans << endl;
return 0;

}

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

    Use any data structure other than set because set does not allow storing duplicate values.