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:
- Our lord and saviour antontrygubO_o for amazing coordination and rejecting our poopoo tasks
- dantoh and tqbfjotld for roasting our enigmas and testing them before they were prepared
- our many testers balbit, kshitij_sodani, Monogon, T1duS, icypiggy,user14767553, maomao90, Starlight-Sailor, wxhtzdy, Jellyman102, ETK. and jamessngg for bricking on bamboozlers and destroying our testcases
- MikeMirzayanov for Codeforces and Polygon platforms
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
stupid comments to beg for likesAs 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. !
True, as a participant of the testing contest, I will not be writing 'as a tester' comments since Anton sir told us not to.
'Btw, remember to downvote all testers who writes stupid comments to beg for likes.'
The testers right now:
How can we forget this torture to us :/
Smart comment
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.
I guess the statements are so short that the author decided to call them questions.
Is it ok for non-testers to ask for upvotes?
Yes ofcourse. You have mine :)
I've never seen a man work so hard for contribution++
civil war
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.
This is how a champion works bro:
Tune in on 6th June to learn more!
https://www.youtube.com/watch?v=FTcgA2eQ1XE
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:
The last round had very nice problems!! Expecting even more nicer problems this time!!
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.
Problems were nice.. any failure is a part of the contestant's fault.
Thanks to the last round, I can be rated this round :D
.
Div 1.5 on it's way :(
Will the contest be difficult? Scoring looks fine tho
Is it a trap again? :)
nastia and scam? :)
Lets hope this round will be as good as yours, and not a trap.
But I can already see its_Atrap
Now, we can be perfectly sure that it indeed was a trap. Feel free to blame its_Atrap
Which problem is an Interactive Problem? It should not be anyone one of A, B and C. :(
I guess may be C will be interactive. As it is also divided in two significantly easy questions.
Why does that indicate interactivity?
Maybe some number of queries based.
Easy one — at most N queries.
Hard one — at most N/3 queries.
Prerequisite : Binary Search.
Time Complexity : N_LogN
If not interactive then it must be a brainteasers or why would c will be divided into similar difficulty of A and B?
Looks like you haven't participated in many contests having subproblems. It always has been this way.
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.
Don't forgot to consider the UNUSUAL START TIME
is't it unusual start time ??
It is unusual , I don't know the reason of you getting so many downvotes , Maybe I will also get some now :/
I was surely going to miss this round. Thanks :)
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.
https://codeforces.me/blog/entry/91090?#comment-796399
..2 hours and 30 minutes to solve 6 "questions"
Radewoosh triggered
Exactly xD
It will be my first div2 round. Just do it!
How do you fix contest duration?
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.
Ignore.
Please read annoucement more clearly next time
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 :)
It means there will be C1 and C2 bugaboos, with C1 being easier, therefore scored 750.
Race to specialist begin ...
I came looking for bugaboos, I WAS NOT DISAPPOINTED
nice contest
Can a tester say the round was bad for once please :D
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.)
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
spy tf2
I will, when I test a round (sad face) :(
Why are we not using bugaboos instead of questions?
bugabooset Done
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
Bugaboo Ragnarok
Arei Syndrome
Bugaboo Apocalypse
A no namer cyan posting memes, meanwhile THE red coder-
Close up Rade-vieew-shh:
Thanks and don't wait for editorial.
I am damn Sure that Binary Search will be Used in One of the Problem in this Contest.
Upvoteif you Found it Helpful !I think it's a trap. They are misleading the harmless contestants to just walk into the world of Binary Search.
Not just any one of the problems. I bet it will be the interactive problem. And most importantly, it's not even surprising.
CF never disappoints us. Bugabooset
now that cf changed problemset to bugabooset, i can happily tell, i cant wait to solve more bugaboos in this round with you all!
I hope there will be short tasks.
Hope I reach Pupil today. Wishing high rating to everyone:)
pretests || system tests
Bugabooforces
C score distribution is 1750?why it is in brackets?
There will be 2 sub bugaboos C1 and C2 with C1 be easier as compared to C2.
2 different tasks with c1 different and c2 different like B1 and B2 in 721#Div2 ?
Wish I would be able to solve at least 2 bugaboos in this contest
iLoveIOI What happened to you after 2018?
cyberphobia, I guess !!
:eyes:
Hope the question statements will be short and clear
You mean bugaboo statements?
hahaha.. people trying hard to create memes to get some upvotes.
2 hours and 30 minutes for 6 problems? This one is going to be tough
hope this contest will be the one to break my negative rating streak :D
Your current streak is just 1.
.
Problems were very Interesting!! Thanks to the setters.
How are these problems interesting? Just speedforces from A — C2.
I literally hate 1111.
Such a shitty problem!!
Now, we all hate 1111
After watching solution you will hate yourself (for some time) xD
My Health gone negative today.
Weird flex but okay.
Gave my best, but this contest was too hard. Solved 0 out of submissions for a, b and c. Have to improve my intuition.
E is just this paper. Did authors know about this? It was a bit too easy to find.
I think we really did not know about this. So sorry about that.
I am very sorry, I will try to research more next time.
Had a very bad contest. Was C some sort of greedy?
Yes. C1 could be done by DP though.
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 .
Yeah. You maintain a value
h(health),ans(longest sequence), andQ(a priority queue of used potions), and at each element, ifh + a[i] >= 0you incrementh += a[i],ans++, and adda[i]to Q. Ifh + a[i] < 0, then check whether we can improvehat that index by swapping the smallest used value inQfor the current value ofa[i].Got it. This was too easy, well, I was thinking in some other direction entirely. Thanks to everybody for the help.
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).
You can solve it also using a segment tree.
I love how you always cover your code with comments regarding your thought process
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.
One way how to do it without segtree is above, see link
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.
1430E - String Reversal
The level of ooof given I got AC on this problem during the contest...
It's the inversion count
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.
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.
Some one please tell me about approach of B
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.
I thought of it this way. If you add
111to any multiple of11, you are basically adding1 mod 11. So if your given number is>= x*111, you can shift the mod byxtimes. It's easy to see that ifx>=10, any number is possible.What's your approach to Kill Anton?
Making his DNA beautiful.
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 ?
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.
I love Anton Sir very much. (:
problem statement for D was quite entertaining and funny loved 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.
I applied brute force , grouped all same characters together and solved for each permutation of ANTO and it worked
Thanks. Can any one provide intuition or proof why it will be correct (grouping similar characters together) ?
The title of problem B is giving a clue for solving the question
The 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+11
Thus 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.
What the hell was problem B! Spent almost the entire contest thinking on it!!!!
Is just looking mod11, it can be done in O(1) per query with 11 if
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.
How can we be very sure that we will always end up getting multiple of 11 by substracting 111 repeatedly for n>=11*111
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
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.
https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
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$$$.
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.
Indeed. Really the question amounts to
ans = (n >= (111)*(n%11) ? "YES" : "NO")
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
Yep. A few ways to do this. Quite a nice question.
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.
While testing, current problem B used to be A. We were made to solve it as A :notlikeduck:
A is hardest problem from A-C
I got RE#5 of problem D, can anyone help me? Thanks!
...
:(
as a first AC, you are late AC.
From problem C I saw the real power of Priority Queue! Good contest :)
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;}
How many of you are getting bad rank because you came 30 minutes late because of your carelessness. It happened to me as well. :(
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
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 :)
.
The place under the picture should be mine
Cause I still don't know how to solve A constructively, just random shuffled it
I did the same after noticing that the upper limit for
nwas 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.
Today's contest was shit for me
How come? You haven't even participated
Are you sure about this ?
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.
MikeMirzayanov When will you update the rating ?
It was a nice contest with understandable problem statement. I loved doing this contest thanks for the contest
Thanks for the fun bugaboos! Here's a link to my screencast. (An HD version will be ready within the next few hours.)
Codeforces these days is coming with tricky and tough questions to think upon in contests..isnt it ?
Can someone share more problems based upon Chicken Mcnugget Theorem .
Thanks in advance .
I solved problem C1 in the last minute, but got so excited that forgot to submit C2 :(
Is the next Codeforces Round for DIV2 going to be in 2 weeks?? If yes then why such a long wait?
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.
errorgorn and the testers are madlads for having this as a test case for 1526A - Mean Inequality.
ORZ, ORZ, ORZ
Problem C is a known problem. 11 days old blog link . Similar problem link.
After the contest i was assigned to a room.What does that mean actually?
You can only hack those people who are in the same room with you (after locking the problems).
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;}
Use any data structure other than set because set does not allow storing duplicate values.
Thanks :)