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

Автор errorgorn, история, 3 недели назад, По-английски

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

 
 
 
 
  • Проголосовать: нравится
  • +923
  • Проголосовать: не нравится

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

stupid comments to beg for likes

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

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 недели назад, # ^ |
      Проголосовать: нравится +57 Проголосовать: не нравится

    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 недели назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

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

The testers right now:

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

Smart comment

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

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.

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

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

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

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

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

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

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

    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 недели назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

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

.

»
3 недели назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится
»
3 недели назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Div 1.5 on it's way :(

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

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

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

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

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

      Why does that indicate interactivity?

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

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

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

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

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

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

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

          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 недели назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Don't forgot to consider the UNUSUAL START TIME

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

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

Radewoosh triggered

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

Hope for strong pretests of bugaboos

not like this
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck everyone :)

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

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

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

How do you fix contest duration?

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

    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 недели назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

Ignore.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +89 Проголосовать: не нравится
    • We hope you find the bugaboos interesting and fun! Wish you high rating!

    Please read annoucement more clearly next time

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

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 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Race to specialist begin ...

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

I came looking for bugaboos, I WAS NOT DISAPPOINTED

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

nice contest

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

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

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

    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.)

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

      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

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

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

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

Hope those Bugaboobs dont destroy my rating.

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

Why are we not using bugaboos instead of questions?

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

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.

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

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 !

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

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

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

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

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

CF never disappoints us. Bugabooset

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

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

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

I hope there will be short tasks.

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

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

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

pretests || system tests

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

Bugabooforces

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

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

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

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

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

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

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

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

iLoveIOI What happened to you after 2018?

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

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

One problem is interactive means that 1 out of 6 will be interactive or c1&C2 will be interactive???

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

Hope the question statements will be short and clear

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

zadgavgava.

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

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

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

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

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

.

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

Friendly advice to cin cout users. Use

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

I suffered a lot because of this in the last contest.

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

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

I forget to register can anyone say how I can register now?

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

Problems were very Interesting!! Thanks to the setters.

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

I literally hate 1111.

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

Now, we all hate 1111

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

My Health gone negative today.

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

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

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

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

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

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

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

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

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

    I was also thinking about only dp for C

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

      Yes, parse the array, put -1*values in a heap,whenever sum goes below 0 start adding the values from heap, simultaneously maintaining the maxcount.

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

    Yes. C1 could be done by DP though.

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

    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 .

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

    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].

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

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

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

    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).

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

    Yes, I did it greedy way.
    Approach — traverse the array and keep on taking all potions as long as your health is non negative. Also keep adding negative elements into the heap as you will need it.

    If you encounter a negative potion which on adding will make your health negative then see if it is greater than the min element of heap in your heap of -ve numbers, if yes then remove the min number from heap and add the current potion (this step will increase your health keeping the number of potions same).

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

    You can solve it also using a segment tree.

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

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

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

      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.

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

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.

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

    It's the inversion count

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

    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.

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

      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.

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

Some one please tell me about approach of B

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

    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.

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

    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.

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

    You have to notice that 11 and 111 can actually make the remaining 1s(say 11111 = 11*1000 + 111). Then notice that 111 = 11*10 +1. It means that we could first always use 11. If the remainder is say 3, we change thirty 11 into three 111. Then it is divisible. So if we have thirty 11, then it is divisible, otherwise no. Therefore, we have this equation:

    remainder <= (quo/10)

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

I got rekt ;(

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

how the gell to do B ?

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

What's your approach to Kill Anton?

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

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 ?

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

    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.

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

I love Anton Sir very much. (:

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

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

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

    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.

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

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

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

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

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

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

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

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

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

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

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

    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.

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

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

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

        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

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

        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.

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

        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$$$.

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

      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.

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

        Indeed. Really the question amounts to

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

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

      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

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

    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.

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

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

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

I didn't do so hot...

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

Can anyone hack my recursive solution for B.

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

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

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

:(

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

Very good round.! Thanks for this round. I tried for 2 hours to solve (B) but, I couldn't. If it's possible to give the hint option with the editorial then it will be helpful for beginners like me.

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

After 10 attempts I was able to passed the test of B in the very last minute of the contest. how did i miss that stupid observation :/

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

as a first AC, you are late AC.

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

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

  • »
    »
    2 недели назад, # ^ |
    Rev. 9   Проголосовать: нравится -19 Проголосовать: не нравится

    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;

    }

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

    but i have done this question without using priority queue

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

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

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

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

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

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 :)

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

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

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

    The place under the picture should be mine

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

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

      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.

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

    "How to solve A?"

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

Today's contest was shit for me

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

    How come? You haven't even participated

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

      Are you sure about this ?

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

        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.

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

          In short, forget. Who will understand he will understand I handed over shorter

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

MikeMirzayanov When will you update the rating ?

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

 ok Nice! (Bugaboo A)

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

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

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

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

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

https://codeforces.com/contest/1526/submission/117690554

Can somebody help me out I am getting RTE on test 17 in C2

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

CAN ANY BODY HELP ME CONVERT THIS CODE IN TO MEMO OR DP PROBLEM C GETTING TLE public static void main(String[] args) { // TODO Auto-generated method stub FastReader s=new FastReader(); int n=s.nextInt(); long[] arr=new long[n]; for(int i=0;i<n;i++)arr[i]=s.nextInt(); long ans=solver(arr,0,0); System.out.println(ans); } private static long solver(long[] arr, int i,long sum) { // TODO Auto-generated method stub long ans1=0; long ans2=0; if(i>=arr.length)return 0; if(sum+arr[i]>=0)ans1=Math.max(1+solver(arr,i+1,sum+arr[i]),solver(arr,i+1,sum)); else ans2=solver(arr,i+1,sum); return Math.max(ans1, ans2);

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

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

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

117662221 PLEASE HELP TO CONVERT THIS CODE IN DP OR MEMO THANKS U I ALREADY WRITE THE RECURSIVE SOLUTION

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

    I don't think that this problem can be solved with dp since the constraint on health is way to high .I tried doing the same during the contest and got TLE only . But now I have solved it you can checkout my approach here

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

Can someone share more problems based upon Chicken Mcnugget Theorem .

Thanks in advance .

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

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

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

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

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

    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.

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

      Ohh thanks for the information. I recently started participating in the contest so didn't know about it.

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

This is my dp function.

Your code here...
int longarr(int *a,int n, int **dp, int cur,int energy,int k){
    if(cur==n-1){
        if(energy+a[cur]>=0)
            return 1;
        else
            return 0;
    }
    if(dp[cur][k]>-1)
        return dp[cur][k];
    int t1=energy+a[cur];
    int g2=longarr(a,n,dp,cur+1,energy,k);
    int g1=-1;
    if(t1>=0){
        g1=1+longarr(a,n,dp,cur+1,t1,k+1);
    }
    dp[cur][k]=max(g1,g2);
    return dp[cur][k];
}

I am simply caling it using longarr(a,n,dp,0,0,0). It is showing WA on Test Case 3 and I am not able to understand why. Can Someone please help?

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

I liked the test but the question was really hard:((((

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

errorgorn and the testers are madlads for having this as a test case for 1526A - Mean Inequality.

ORZ, ORZ, ORZ

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

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

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

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

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

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

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

In Codeforces Round #723 (Div. 2) K_I_E_N_1_8_2_0_0_5 is my sub account, i have submitted the solution from main account to sub account, can you add me points to kien_1_8_2005 and subtract only from K_I_E_N_1_8_2_0_0_5

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

/

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

Hey guys, My idea for C2 is to greedily take elements in descending order until total_sum becomes negative, also while taking an element, check if the prefix till here plus current element is positive. code. Couldn't figure out where it's failing. could anyone help

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

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;

}

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

can anyone please help me why i am getting error in the C question

include<bits/stdc++.h>

include

include

using namespace std; int main() { int n; cin>>n; int arr[n];  priority_queue <int, vector, greater > pq; int s=0; int c=0; for(int i=0;i<n;i++) { cin>>arr[i]; pq.push(arr[i]); s+=arr[i]; while(s<0) { s=s-(pq.top()); pq.pop(); c++; } } cout<<(n-c)<<endl;

}

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

someone add me as friend and make my Friends of users count 59 to 60.I hate the digit '9' at the end of any number

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

tourister is great programmer