### errorgorn's blog

By errorgorn, history, 3 weeks ago,

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.

• +923

 » 3 weeks ago, # |   +456 stupid comments to beg for likes
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   -102 Everyone after seeing disliked comment..Lets Dislike it more
•  » » » 3 weeks ago, # ^ |   -42 Spoiler...n
 » 3 weeks ago, # | ← 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 weeks ago, # ^ |   +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 weeks ago, # |   +96 'Btw, remember to downvote all testers who writes stupid comments to beg for likes.'The testers right now:
•  » » 3 weeks ago, # ^ |   +142 How can we forget this torture to us :/
 » 3 weeks ago, # |   +132 Smart comment
 » 3 weeks ago, # |   +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.
•  » » 3 weeks ago, # ^ |   +54 I guess the statements are so short that the author decided to call them questions.
 » 3 weeks ago, # |   +23 Is it ok for non-testers to ask for upvotes?
•  » » 3 weeks ago, # ^ |   +4 Yes ofcourse. You have mine :)
•  » » » 3 weeks ago, # ^ |   +10 I've never seen a man work so hard for contribution++
•  » » » » 3 weeks ago, # ^ |   +46 civil war
•  » » » » 3 weeks ago, # ^ |   +9 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 weeks ago, # ^ |   +13 This is how a champion works bro:Tune in on 6th June to learn more!https://www.youtube.com/watch?v=FTcgA2eQ1XE
•  » » » » » » 3 weeks ago, # ^ |   0 ngl, when I read "give me some ideas", I thoughts its a shot from a telegram cheating grp lol. But apart from jokes, yeah, he is :orz:
 » 3 weeks ago, # | ← Rev. 2 →   -6 The last round had very nice problems!! Expecting even more nicer problems this time!!
•  » » 3 weeks ago, # ^ | ← 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 weeks ago, # ^ |   0 I'm not mad at anyone, you all did your best and we enjoyed trying the problems!
•  » » » 3 weeks ago, # ^ |   -7 Problems were nice.. any failure is a part of the contestant's fault.
•  » » » » 3 weeks ago, # ^ |   0 Agree 100%
 » 3 weeks ago, # | ← Rev. 2 →   +6 Thanks to the last round, I can be rated this round :D
 » 3 weeks ago, # | ← Rev. 3 →   -23 .
 » 3 weeks ago, # |   -52
 » 3 weeks ago, # |   +4 Div 1.5 on it's way :(
•  » » 3 weeks ago, # ^ |   +2 Will the contest be difficult? Scoring looks fine tho
•  » » 3 weeks ago, # ^ |   +9 Is it a trap again? :)
•  » » » 3 weeks ago, # ^ |   +23 nastia and scam? :)
•  » » » 3 weeks ago, # ^ |   +1 Lets hope this round will be as good as yours, and not a trap.
•  » » » » 3 weeks ago, # ^ |   +11 But I can already see its_Atrap
•  » » » » » 3 weeks ago, # ^ |   0 Now, we can be perfectly sure that it indeed was a trap. Feel free to blame its_Atrap
 » 3 weeks ago, # |   -23 Which problem is an Interactive Problem? It should not be anyone one of A, B and C. :(
•  » » 3 weeks ago, # ^ |   0 I guess may be C will be interactive. As it is also divided in two significantly easy questions.
•  » » » 3 weeks ago, # ^ |   +9 Why does that indicate interactivity?
•  » » » » 3 weeks ago, # ^ |   +32 Maybe some number of queries based. Easy one — at most N queries. Hard one — at most N/3 queries. SpoilerPrerequisite : Binary Search. Time Complexity : N_LogN
•  » » » » 3 weeks ago, # ^ |   +1 If not interactive then it must be a brainteasers or why would c will be divided into similar difficulty of A and B?
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +8 Looks like you haven't participated in many contests having subproblems. It always has been this way.
•  » » » » » 3 weeks ago, # ^ |   +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 weeks ago, # |   +18 Don't forgot to consider the UNUSUAL START TIME
•  » » 3 weeks ago, # ^ |   +43 is't it unusual start time ??
•  » » » 3 weeks ago, # ^ |   +13 It is unusual , I don't know the reason of you getting so many downvotes , Maybe I will also get some now :/
•  » » 3 weeks ago, # ^ |   +3 I was surely going to miss this round. Thanks :)
 » 3 weeks ago, # |   +42 Spoiler
•  » » 3 weeks ago, # ^ |   0 It doesn't necessarily have to be a binary search problem, it can either be a segment tree problem or even not a certain tag.
•  » » » 3 weeks ago, # ^ |   +1
 » 3 weeks ago, # | ← Rev. 2 →   +206 ..2 hours and 30 minutes to solve 6 "questions"Radewoosh triggered
•  » » 2 weeks ago, # ^ |   0 Exactly xD
 » 3 weeks ago, # | ← Rev. 4 →   0 Hope for strong pretests of bugaboos not like this...
 » 3 weeks ago, # |   0 Good luck everyone :)
 » 3 weeks ago, # |   +5 It will be my first div2 round. Just do it!
 » 3 weeks ago, # |   +1 How do you fix contest duration?
•  » » 3 weeks ago, # ^ |   +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 weeks ago, # | ← Rev. 2 →   -18 Ignore.
•  » » 3 weeks ago, # ^ |   +89 We hope you find the bugaboos interesting and fun! Wish you high rating! Please read annoucement more clearly next time
 » 3 weeks ago, # |   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 weeks ago, # ^ | ← Rev. 2 →   +19 It means there will be C1 and C2 bugaboos, with C1 being easier, therefore scored 750.
 » 3 weeks ago, # |   +5 Race to specialist begin ...
 » 3 weeks ago, # |   0 I came looking for bugaboos, I WAS NOT DISAPPOINTED
 » 3 weeks ago, # |   0 nice contest
 » 3 weeks ago, # |   +14 Can a tester say the round was bad for once please :D
•  » » 3 weeks ago, # ^ |   +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.)
•  » » » 3 weeks ago, # ^ |   +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
•  » » » » 3 weeks ago, # ^ |   +4 spy tf2
•  » » » » 3 weeks ago, # ^ |   0 If we eliminate the impossible, whatever remains, however improbable, must be the truth!!!
•  » » 3 weeks ago, # ^ |   0 I will, when I test a round (sad face) :(
 » 3 weeks ago, # |   0 Hope those Bugaboobs dont destroy my rating.
 » 3 weeks ago, # |   0 Why are we not using bugaboos instead of questions?
•  » » 3 weeks ago, # ^ |   -8 bugabooset Done
»
3 weeks ago, # |
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

E2

Thanks and don't wait for editorial.

 » 3 weeks ago, # |   +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 !
•  » » 3 weeks ago, # ^ |   +11 I think it's a trap. They are misleading the harmless contestants to just walk into the world of Binary Search.
•  » » 3 weeks ago, # ^ |   +4 Not just any one of the problems. I bet it will be the interactive problem. And most importantly, it's not even surprising.
 » 3 weeks ago, # |   +4 CF never disappoints us. Bugabooset
 » 3 weeks ago, # |   +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!
 » 3 weeks ago, # |   +1 I hope there will be short tasks.
 » 3 weeks ago, # |   +1 Hope I reach Pupil today. Wishing high rating to everyone:)
 » 3 weeks ago, # | ← Rev. 3 →   +5 pretests || system tests
 » 3 weeks ago, # |   +5 Bugabooforces
 » 3 weeks ago, # |   +1 C score distribution is 1750?why it is in brackets?
•  » » 3 weeks ago, # ^ |   -7 There will be 2 sub bugaboos C1 and C2 with C1 be easier as compared to C2.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 2 different tasks with c1 different and c2 different like B1 and B2 in 721#Div2 ?
 » 3 weeks ago, # |   +24
 » 3 weeks ago, # |   +11 Wish I would be able to solve at least 2 bugaboos in this contest
 » 3 weeks ago, # |   +2 iLoveIOI What happened to you after 2018?
•  » » 3 weeks ago, # ^ |   +5 cyberphobia, I guess !!
•  » » 2 weeks ago, # ^ |   0 :eyes:
 » 3 weeks ago, # |   +32
 » 3 weeks ago, # |   0 One problem is interactive means that 1 out of 6 will be interactive or c1&C2 will be interactive???
 » 3 weeks ago, # |   +3 Hope the question statements will be short and clear
•  » » 3 weeks ago, # ^ |   +1 You mean bugaboo statements?
 » 3 weeks ago, # |   +66 .
•  » » 3 weeks ago, # ^ |   +3 hahaha.. people trying hard to create memes to get some upvotes.
 » 3 weeks ago, # |   +5 2 hours and 30 minutes for 6 problems? This one is going to be tough
 » 3 weeks ago, # |   0 hope this contest will be the one to break my negative rating streak :D
•  » » 3 weeks ago, # ^ |   +5 Your current streak is just 1.
 » 3 weeks ago, # | ← Rev. 2 →   -14 .
 » 3 weeks ago, # |   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.
 » 3 weeks ago, # |   +24
 » 3 weeks ago, # |   0 I forget to register can anyone say how I can register now?
 » 3 weeks ago, # |   -6 Problems were very Interesting!! Thanks to the setters.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +4 How are these problems interesting? Just speedforces from A — C2.
 » 3 weeks ago, # |   +21 I literally hate 1111.
•  » » 3 weeks ago, # ^ |   +1 Such a shitty problem!!
•  » » 2 weeks ago, # ^ |   0 i simply did recursive backtrack.
 » 3 weeks ago, # |   0 Now, we all hate 1111
•  » » 3 weeks ago, # ^ |   +10 After watching solution you will hate yourself (for some time) xD
 » 3 weeks ago, # |   +4 My Health gone negative today.
 » 3 weeks ago, # |   +10 ‎‎‎‎‎‎‎‎‎‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎
•  » » 3 weeks ago, # ^ |   +14 Weird flex but okay.
 » 3 weeks ago, # |   +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.
 » 3 weeks ago, # |   +14 E is just this paper. Did authors know about this? It was a bit too easy to find.
•  » » 3 weeks ago, # ^ |   0 I think we really did not know about this. So sorry about that.
•  » » 2 weeks ago, # ^ |   0 I am very sorry, I will try to research more next time.
 » 3 weeks ago, # | ← Rev. 2 →   +14 Had a very bad contest. Was C some sort of greedy?
•  » » 3 weeks ago, # ^ |   0 I was also thinking about only dp for C
•  » » » 3 weeks ago, # ^ |   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.
•  » » 3 weeks ago, # ^ |   0 Yes. C1 could be done by DP though.
•  » » 3 weeks ago, # ^ |   +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 .
•  » » 3 weeks ago, # ^ | ← 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].
•  » » » 3 weeks ago, # ^ |   0 Got it. This was too easy, well, I was thinking in some other direction entirely. Thanks to everybody for the help.
•  » » 3 weeks ago, # ^ | ← 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).
•  » » 3 weeks ago, # ^ | ← 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).
•  » » 3 weeks ago, # ^ |   +8 You can solve it also using a segment tree.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +8 I love how you always cover your code with comments regarding your thought process
•  » » » 2 weeks ago, # ^ | ← 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 weeks ago, # ^ |   +1 One way how to do it without segtree is above, see link
 » 3 weeks ago, # |   +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.
•  » » 3 weeks ago, # ^ |   +3
•  » » » 3 weeks ago, # ^ |   0 The level of ooof given I got AC on this problem during the contest...
•  » » 3 weeks ago, # ^ |   +3 It's the inversion count
•  » » 3 weeks ago, # ^ | ← 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.
•  » » » 3 weeks ago, # ^ | ← 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.
 » 3 weeks ago, # |   0 Some one please tell me about approach of B
•  » » 3 weeks ago, # ^ | ← 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.
•  » » 3 weeks ago, # ^ | ← 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.
•  » » 3 weeks ago, # ^ |   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)
 » 3 weeks ago, # |   0 I got rekt ;(
 » 3 weeks ago, # |   0 how the gell to do B ?
 » 3 weeks ago, # |   0 What's your approach to Kill Anton?
•  » » 3 weeks ago, # ^ |   +3 Making his DNA beautiful.
 » 3 weeks ago, # | ← 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 ?
•  » » 3 weeks ago, # ^ |   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.
 » 3 weeks ago, # |   +50 I love Anton Sir very much. (: Spoiler
 » 3 weeks ago, # |   +5 problem statement for D was quite entertaining and funny loved it ♥
•  » » 3 weeks ago, # ^ |   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.
•  » » » 3 weeks ago, # ^ |   +3 I applied brute force , grouped all same characters together and solved for each permutation of ANTO and it worked
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 Thanks. Can any one provide intuition or proof why it will be correct (grouping similar characters together) ?
 » 3 weeks ago, # |   +13 The title of problem B is giving a clue for solving the question SpoilerThe title of the problem is "I hate 1111" . This is important because you will see that all numbers greater than and including 1111 in the series 11, 111 ,1111 , 11111 ,... can be expressed as the sum of 11 and 111. Example 1111=11*100+11 11111=111*100+11Thus the problem subsequently breaks down to finding out if a solution to the following linear equation exists a*111 + b*11 =n (Here n is the number we have to represent.
 » 3 weeks ago, # |   +6 What the hell was problem B! Spent almost the entire contest thinking on it!!!!
•  » » 3 weeks ago, # ^ |   -8 Is just looking mod11, it can be done in O(1) per query with 11 if
•  » » 3 weeks ago, # ^ |   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.
•  » » » 3 weeks ago, # ^ |   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
•  » » » » 3 weeks ago, # ^ |   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
•  » » » » 3 weeks ago, # ^ |   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.
•  » » » » 3 weeks ago, # ^ |   0
•  » » » » 3 weeks ago, # ^ | ← 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$.
•  » » » 3 weeks ago, # ^ | ← 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.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +12 Indeed. Really the question amounts toans = (n >= (111)*(n%11) ? "YES" : "NO")
•  » » » 3 weeks ago, # ^ |   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
•  » » » » 3 weeks ago, # ^ |   +3 Yep. A few ways to do this. Quite a nice question.
•  » » 3 weeks ago, # ^ | ← 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.
•  » » 3 weeks ago, # ^ |   0 While testing, current problem B used to be A. We were made to solve it as A :notlikeduck:
•  » » » 3 weeks ago, # ^ |   0 A is hardest problem from A-C
 » 3 weeks ago, # |   0 I didn't do so hot...
 » 3 weeks ago, # |   0 Can anyone hack my recursive solution for B.
 » 3 weeks ago, # |   0 I got RE#5 of problem D, can anyone help me? Thanks! Code... #include using namespace std; #define int long long #define fi first #define se second #define pii pair #define mp make_pair #define pb push_back int n; vector a; int f(char ch) { if(ch=='A') return 1; if(ch=='N') return 2; if(ch=='T') return 3; if(ch=='O') return 4; } char F(int ch) { if(ch==1) return 'A'; if(ch==2) return 'N'; if(ch==3) return 'T'; if(ch==4) return 'O'; } void solve() { string s; cin>>s; n=s.size(); a.clear(); for(int i=0;imaxx) { maxx=now; for(int i=0;i<4;i++) maxp[i]=p[i]; } }while(next_permutation(p,p+4)); int cnt[5]; memset(cnt,0,sizeof(cnt)); for(int i=0;i>_; while(_--) solve(); return 0; } 
 » 3 weeks ago, # |   +3 :(
 » 3 weeks ago, # |   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.
 » 3 weeks ago, # |   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 :/
 » 3 weeks ago, # |   -6 as a first AC, you are late AC.
 » 3 weeks ago, # |   +4 From problem C I saw the real power of Priority Queue! Good contest :)
• »
»
3 weeks ago, # ^ |
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;

}

•  » » 3 weeks ago, # ^ |   0 but i have done this question without using priority queue
 » 3 weeks ago, # |   +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. :(
 » 3 weeks ago, # | ← Rev. 5 →   0 It was a very strange round for me. A) No idea, let's random shuffleB) 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 billionsC1&C2) Made some stupid mistakes and got -150 for incorrect submissionsD) 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 weeks ago, # |   0 Thank you for the round. I really liked these problems, but due to my low level i couldnt solve all of them. Waiting for more rounds from you :)
 » 3 weeks ago, # |   +19 .
•  » » 3 weeks ago, # ^ | ← 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
•  » » » 3 weeks ago, # ^ |   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.
•  » » 3 weeks ago, # ^ |   0 "How to solve A?"
 » 3 weeks ago, # |   0 Today's contest was shit for me
•  » » 3 weeks ago, # ^ |   +1 How come? You haven't even participated
•  » » » 3 weeks ago, # ^ |   0 Are you sure about this ?
•  » » » » 3 weeks ago, # ^ |   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.
•  » » » » » 3 weeks ago, # ^ |   0 In short, forget. Who will understand he will understand I handed over shorter
 » 3 weeks ago, # | ← Rev. 2 →   +39 MikeMirzayanov When will you update the rating ?
 » 3 weeks ago, # |   +1 ok Nice! (Bugaboo A)
 » 3 weeks ago, # |   0 It was a nice contest with understandable problem statement. I loved doing this contest thanks for the contest
 » 3 weeks ago, # |   +8 Thanks for the fun bugaboos! Here's a link to my screencast. (An HD version will be ready within the next few hours.)
 » 3 weeks ago, # |   -10 https://codeforces.cc/contest/1526/submission/117690554Can somebody help me out I am getting RTE on test 17 in C2
 » 3 weeks ago, # |   -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=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);
 » 3 weeks ago, # |   +2 Codeforces these days is coming with tricky and tough questions to think upon in contests..isnt it ?
 » 3 weeks ago, # |   -15 117662221 PLEASE HELP TO CONVERT THIS CODE IN DP OR MEMO THANKS U I ALREADY WRITE THE RECURSIVE SOLUTION
•  » » 3 weeks ago, # ^ |   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
 » 3 weeks ago, # |   +3 Can someone share more problems based upon Chicken Mcnugget Theorem . Thanks in advance .
 » 3 weeks ago, # |   0 I solved problem C1 in the last minute, but got so excited that forgot to submit C2 :(
 » 2 weeks ago, # |   0 Is the next Codeforces Round for DIV2 going to be in 2 weeks?? If yes then why such a long wait?
•  » » 2 weeks ago, # ^ |   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 weeks ago, # ^ |   0 Ohh thanks for the information. I recently started participating in the contest so didn't know about it.
 » 2 weeks ago, # | ← 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 weeks ago, # |   0 I liked the test but the question was really hard:((((
 » 2 weeks ago, # |   0 errorgorn and the testers are madlads for having this as a test case for 1526A - Mean Inequality.ORZ, ORZ, ORZ
 » 2 weeks ago, # |   +14 Problem C is a known problem. 11 days old blog link . Similar problem link.
 » 2 weeks ago, # |   0 After the contest i was assigned to a room.What does that mean actually?
•  » » 2 weeks ago, # ^ |   0 You can only hack those people who are in the same room with you (after locking the problems).
 » 2 weeks ago, # | ← 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 weeks ago, # |   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 weeks ago, # |
0

What is wrong in this solution for question c2 ?

# 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 weeks ago, # ^ |   0 Use any data structure other than set because set does not allow storing duplicate values.
•  » » » 2 weeks ago, # ^ |   0 Thanks :)
»
2 weeks ago, # |
0