Hello, Codeforces!
We are glad to invite everyone to participate in Codeforces Round 893 (Div. 2), which will be held on Aug/15/2023 17:35 (Moscow time).
Please note the unusual start time of the round. This round will be rated for the participants with rating lower than 2100.
Our round is completely set by SIS (Summer Informatics School) students. We did our best to prepare interesting and creative problems. You can check out some of the previous rounds prepared by SIS students: Codeforces Round 816 (Div. 2), Codeforces Round 815 (Div. 2),Codeforces Round #694,Codeforces Round #612,Codeforces Round #530.
Task authors and developers: Daria arbuzick Grekova, Petr green_gold_dog Losev, Yaroslav 555105 Semenyuk, Artem ArtAlex Alexeev, Anton NToneE Egorov, Fedor FedShat Shatokhin, Timofey IzhitskiyTimofey Izhitskyi, Egor salyg1n Salygin, Vladimir plagues Gerasikov under the guidance of Evgenii pakhomovee Pakhomov
We are very thankful to
teachers who contributed to the round creation: Kirill kirill.kligunov Kligunov, Alexey allvik66 Vasiliev, Anton stepanov.aa Stepanov and Fedor fastmath Ushakov
testers for good advice and important feedback: KseniaShk, AndreyPavlov, glebustim, Semen07, Ooops_no, WrongAnswerOnTest3, Sweezy, NToneE, mir, DanilaOdesser, maomao90, Nikitun, a.stepanov281005, i_love_penguins, Kayot, LeoPro, dope, SomethingNew, AndrewPav, Dart-Xeyter, lgswdn
Gimran bashkort Abdullin for reviewing all of the tasks and giving us valuable advice, which helped us improve the contest
our coordinator IgorI for valuable advice and patience
KAN for the help during preparation of the contest
MikeMirzayanov and geranazavr555 for codeforces and polygon platforms
You will have 5 tasks and 2 hours to solve them. We recommend you read all the problems. The contest may contain interactive problems! Make sure to read this post.
The scoring distribution is $$$500-1250-1500-2000-(1750+1000)$$$
Note that the round has been moved one hour later. The contest start time is Aug/15/2023 17:35 (Moscow time)
We hope that you will enjoy our tasks!
Good luck!
UPD: Editorial
UPD 2: Congratulations to the winners!
Div. 2:
Div. 1:
First solves:
A. ball_of_wool
B. ecnerwala
C. nigus
D. jiangly
E1. grass8sheep
E2. yydtq
More authors = better problems (as an author) xd
this didn't age well. to be fair, most of the problems were interesting, but B and C were definitely ordered incorrectly
Problem B should be a literary comprehension problem, not a coding problem.
It just doesn't fit the style of Codeforces problems. Good problems should be hard to solve instead of being hard to understand.
Fully agree. I spent most of time to understanding what to do and then very little time to coding.
I couldn't reach pupil in the last contest.. I hope I reach pupil this time. Thanks for the contest.
So do I.
If so many people with a high rating came up with tasks, then there is a high probability of high-quality tasks
As an author, I love phonk.
Our taste matches :)
As an average phonk enjoyer, here is a recommendation
As an average phonk enjoyer, here's a recommendation
As a person who reviewed all of the tasks and gave the authors valuable advice, which helped them to improve the contest, I encourage you to participate and enjoy the problems!
The contest may contain interactive problems. This statement is enough to make you worried.why?interactive prblms are fun
How to do interactive problems? I don't know anything about it
https://mirror.codeforces.com/blog/entry/45307
binary search
I feel you :)
"may"
Good luck!
why the hell am i getting so many downvotes ????
As a tester, I suggest you to read all the problems.
As a not tester I suggest everyone to listen to you.
As a tester, I love you.
As a competitive programming expert (literally), I think OAleksa learned stack on 5th of July 2023.
"In the recent contest, i have noticed a significantly larger number of contestants solving problems A, B, and C compared to previous contests. Are the problems easier, or are the contestants more intelligent in your opinion?"
last contest c was easy compared to other div2 C
lol today's C was even more easier
As a regular codeforces user, I will take part in this round!
as a tester, i wish you good luck, problems are good
omg , independence day contest
This time is just right because it’ll start at 21:35 in China and when it ends at 23:35 I’ll just sleep.
UPD: Postponed to 22:35…
Why u guys sleep so early? You can study late night too.
Not anymore :|
this is the best contest that i have done before :vvvvv
as a tester, i wish you good luck, problems are good
Is it necessary to use faster languages for this contest?
OMG 5 problems with so many authors. That would be a great round :)
wssb
A very good starting time for us Chinese.
As a participant, I hope i cna learn something new in this competition and hope everyone can get good results.
Only 5 problems? then 5th one could be 2400+ :( This might lead to other probs being harder than usual too
Considering that one of the authors of the tasks is green_gold_dog, chinese users are advised to refrain from writing this competition...
orz plagues
Good luck！
Worried about the interactive problem
Wish to become Master. Just a bit below it :)
Congrats!!
Scoring distribution?
Hopefully there won't be any down site moments again during the contest :)
delayed :l
1 refresh cost me 1 hour
Please note the usual start time of the round. This round will be rated for the participants with rating lower than 2100.
OMG I will have to sleep one hour later...
Why is the contest postponed by an hour, which makes my sleep worrying.
Oh no.
Time not unusual now...
It was probably delayed because the site kept going down.
Why u delay an hour? As we can see, CodeForces is going very well.
For we Chinese Coder, we have to stay up for another one hour.
Agree
Oh sorry, I'm sorry to hear that there was a power outage in the city today. Hope a good round!
"Please note the unusual start time of the round."
Huh? What's going on with start time?
Please start some professionalism and if you want to delay the start of the contest, do it earlier than 5-10 minutes before :)
delayed?-_-
Score distribution not updated yet.
Why did the contest be postponed?
I woke up early, just for it to get delayed. rip hopefully it will still be a good contest
You woke up from grave??
pakhomovee thank you
Is this really needed? All you need to do is just solve problems
Scoring distribution gives some idea about problem difficulty (in case you haven't figured this out yet)
Ok but you always see scoring distribution while contest
posted it as soon as I found out that Codeforces is up!
"Please note the usual start time of the round."
why postponed by 1 hour
From codeforces telegram:
Unfortunately, there was a power outage in the city today, which caused a disruption in Codeforces' operation. At this moment, Polygon and other services are already operational, and Codeforces is close to being up and running. We estimate that the start will happen in about 15-20 minutes. Considering that the "Codeforces Round 893 (Div. 2)" was expected to start around this time, we have decided to postpone the start of the round by 1 hour. Therefore, the round will begin at 14:35 (UTC) / 17:35 (MSK).
tldr: site were down for like an hour and started working ~10 mins before contest were about to start so codeforces decided to postpone
Unusual time + Unusual delay = Usual time
For now the start time of the round is usual again xD
in the end, it's amusingly held at the usual time again >_<
I never understood why some rounds happen at unusual time in the first place.
Actually, participating in contests at the 'usual time' can be a bit tough for participants from East Asian countries, who might have to stay up late to take part. I think it would be nice to schedule a contest at an 'unusual time' once in a while:) Maybe Codeforces are thinking about this too, considering people from all around the globe
Note that the round has been moved one hour later.
OK but why? Any explanation for participants maybe?
`
Hello.
Unfortunately, there was a power outage in the city today, which caused a disruption in Codeforces' operation. At this moment, Polygon and other services are already operational, and Codeforces is close to being up and running. We estimate that the start will happen in about 15-20 minutes.
`
Authors: note the unusual time of the contest
(probably) Server issues: Let me fix that for you.
Hmm I guess that the interactive problem will be divided into 2 subtasks :))
"Please note the usual start time of the round."
"That's magic! No sooner had I written the previous message than Codeforces started working. Hooray!"
is it rated for all ??
Yes, if the rating is between (-∞,2100)
If someone was wondering why the initial start time was unusual, that's because dinner in SIS starts at 18:30 Moscow time :)
If someone was wondering why the contest got postponed, that's because the authors were trying to come up with problems B and C in the last 10 minutes (they have failed miserably).
xD
The contest is postponed, probably because Mike has been playing Genshin Impact excessively.
已延丁真，鉴定为：玩原神玩的
Do you play Genshin aswell?! 你也玩原神？！ Genshin！
Wow
译言丁真，鉴定为：文盲
swap(problem B,Problem C)
abomination of a contest
my code for e1 should pass in every way, shape, or form but why mle so low when stuff can be up to 10^6???
I don't understand with so many authors no one noticed that they should swap B and C. Current C is an easy B at most
C<B
I miss +ve $$$\Delta$$$
A<C<<B . C was easier than B.
The problem statement of B was quite tricky. First, I couldn't notice that I must remove exactly one cookie seller.
.
lol
If so, then some troll people may want to leak the sol to problem during every contest .
How to optimize memory in E2?
I used it as a good chance to learn about bit padding in C++ struct.
b was very tricky , i loved the problem but according to contest , it doest not fit for B
AK'ed in 82min. The memory limit of E2 might be too tight for me.
A: Obviously two players will press buttons which can be pressed by both players if possible. So we can assume the 1st player has a+ceil(c/2) buttons and the 2nd player has b+floor(c/2) buttons.
B: The problem statement is unclear: "the number of cookie sellers, such that..." can be considered as "the index of the optimal seller to be removed" instead of "how many sellers can be removed to minimize the number of cookies". Back to the solution: For 2 adjacent sellers s[i] and s[i+1], petya will eat ceil((s[i+1]-s[i])/d) cookies from position s[i] to s[i+1]-1. Therefore, if we add 2 unremovable sellers s[0]=1 and s[m+1]=n+1, the number of cookies will be sum(1<=i<=m+1)(ceil((s[i+1]-s[i])/d)), then we can brute force for every removable seller.
C: The maximum score is floor(n/2), which means (1, 2, ..., floor(n/2)) can be values of gcd(a[i], a[i+1]), because if t>floor(n/2), then 2*t>n, but if a[i]!=a[i+1] and gcd(a[i], a[i+1])=t, WLOG assume a[i]<a[i+1], then a[i]>=t and a[i+1]>=2*t, which is a contradiction. On the otherside, the permutation (1, 2, 4, 8, ..., 3, 6, 12, ..., 5, 10, ..., 2*k+1, 2*(2*k+1), 4*(2*k+1), ...) can reach this upper bound.
D: We need to find following values:
pre[t][i]: the maximum size of consecutive block of '1' in the substring s[1, i] if we can flip at most t values.
suf[t][i]: the maximum size of consecutive block of '1' in the substring s[i, n] if we can flip at most t values.
They can be found by two pointers (keeping index i, j and make sure that the number of occurence of '0' in the substring s[i, j] is no more than t). Then for every pair (i, j) such that i<=j, we can take s[i, j] as the maximum consecutive block of '0', let cnt = the occurence of '1' in s[i, j], then L0=j-i+1 and L1=max(pre[k-cnt][i-1], suf[k-cnt][j+1]). We can get a valid pair of (L0, L1) for every pair (i, j), but for each L0 we only need to keep the maximum corresponding L1. Then we can get at most (n+1) different functions f(a)=L0*a+L1, then we can evaluate the maximum values on [1, n] by brute force in O(n*2).
E1: At first we create a tree with only a root node and no value, and a stack containing this root node. Then we can translate queries like this:
"+ x": Create a new node with value x, let the node on the stack top be it's parent. Push this new node into the stack.
"- k": Push the k-th ancestor of the node on the stack top into the stack.
"!": Pop the top node from the stack.
"?": Find the number of distinct values on the path from the root to the node on the stack top.
Using binary lifting we can find the k-th ancestor in O(log(k)), then we can build the tree and get the list of queried nodes in O(q*log(q)), and using dfs to find the answer for all nodes. Then we can solve the problem offline.
E2: To solve the problem online, we need to use persistent segment tree to do update and queries on the history version of an array. However, because the low memory limit of this problem, when using 12 bytes (3 int32 variables for value, left child and right child) for a node of segment tree (there can be O(q*log(X_MAX)) = 2e7 nodes in total), I got MLE for several times. But we can make some observation:
--- Once a tree node has been created, the answer corresponding to this node will not change. So we only need to find answers when doing "+ x" operation.
--- If value x is on the path from root to the parent of new node, the answer will be increased by 1, otherwise remain the same. So we only need to check the existence of a single value, instead of checking the sum on any certain range.
Therefore, we only need to keep 2 pointers to left child and right child (we use -1 as null pointer, which means there's no value exists in the subtree), and the space for a single node of segment tree will be 8 bytes, which fit the memory limit.
Wow! Fast Editorial. Thanks
Orz
For E actually there is a kinda simple solution that just uses sets which I ACed after contest. You just need to maintain a records array and a pointer.
The idea is that everything to the right of ur pointer may not be valid currently, while everything before is accurate. Then, in your records you can store (is this x 'useful' (contribute to distinct count), x, how many 'useful'). Then, to handle -k, you just jump the ptr to k before, to handle ?, just find how many 'useful' ptr is at, and to handle + x, its abit tricky, but you just need to keep track of the indices of useful x, and make sure there is one useful x before the ptr, so u can use another set to do it. Then you override the current record to the new record, (but make sure to store the change to handle rollback). Then rollback can be done with a stack.
The key is to notice that suppose you delete and then add stuff, you must rollback the added stuff before rollbacking the delete so by doing that and restoring the records after rollbacking add, you are sure that your records are correct before rollbacking the delete.
Submission: https://mirror.codeforces.com/contest/1858/submission/219002981
Graphical Approach for Problem C
For problem C, I modelled it using trees with an edge between every number n and its n/spf(smallest possible factor). After making the tree, I ran a normal dfs for the required array.
Here's my submission: My Contest Submission
Thanks for E1 solution!
How to solve B?
Don't
Got you
Think of calculating the answer without removing any element for all the prefixes and suffixes. Then you can compute the answer corresponding to the removal of ith element in constant time
i got stuck on B for almost an hour and needed 10' to finish D. spent 15' coding problem B and 40' to try to understand what the problem wants me to output.
why can't the author just cut the bullshit on problem statement? B problem statement is horrendous and confusing and open to different interpretations.
"The number of cookie sellers...." omg, just simplify it next time please.
The problem itself asks to get the count of cookie removals that result in the minimum cookie to be eaten. Just why? this is just to trip on the test case where 1 is in the input.
B number problem are defficult than C
This contest went so well for me! I solved the first 3 problems (my best performance yet). Also, B was harder than C, which was kind of funny
Balanced...
there's a reason i save my vote till the end :)
B is one of those problems that is simple if you have the author's intended implementation in mind and torturous if you don't.
Why is B>C :/
Any one got WA on pretest 5 on E1/E2? can you please kindly tell me what went wrong?
upd: i found reason
Are you sure you f**king passed English IV?
support you
Please open the practice as fast as possible, for I failed to submit my code in the last minute due to network jam :(
zero balance
Statement for problem B was so bad.
Thank you so much for making E2 interactive instead of xor lastans.
My online algorithm get TLE on E2 but passed E1, because I thought can not use std::cin and ios::sync_with_stdio(false) in an interactive problem:(
Worst Problem B statement I have ever seen.
B is unclear.
Had really high hopes.
Second and third problem should be swapped. I almost fell asleep while reading the statement. Bad problem for B.
I don't understand why none of the testers realized that positions B and C must be changed
Anyone else overkill D with CHT?
I did with li chao
What a shit statement of B. Fully ruin my entire life.
I can't understand Problem B. Statements are not clear and a lot of information makes me panic.
I just hate problems like B.
Especially if given at position B.
(may be i just dont like A or B having big statements.)
But its completely non obvious why suddenly ask count? I just assumed index and coded already.
And the statement was bit ambiguous too.
Why would anybody set strict ML in problem with persistent segment tree?
UPD: My bad, model solution doesn't require it
What the tight memory limit on E? My submission for E got MLE since it use only 300MB.
so many authors and testers in this round yet we have B much harder than C with terrible problem statement
One of the biggest mistakes of my entire life is upvoted this blog before start of the contest. (:
Don't be dramatic bruh
How the fu*k is it drama? I was trying to CM hardly. Today I solved A/C too fast. You can't deny that B statement was shit (: also, when I read D in last 30 min, it was clearly solvable for me if I can manage 1 hours. But still if i can't solve D. I didn't get negative at least.
you must be getting negative bro, as b has more than 4k submissions and you are 1870 :/
Hello, sir. My guess ability is too low to understand that near means zero distance.
B was just crap problem. Phrasing was very confusing, for example why do you say a seller is "near" a bench instead of at a bench. Can a seller be "near" multiple benches? And in what world does the whole story even make any sense? Why would you eat a cookie where a cookie seller is if you already have unlimited cookies. And why would you even buy a cookie in the first place if you already have unlimited cookies. Why not just say: You eat a cookie at position 1, after walking for $$$d$$$ units without having eaten a cookie and whenever there is a bench, where the benches have positions on the coordinate axis.
Also $$$m$$$ was only bounded by $$$n$$$ (which was fixed after 30min), so you either tried to solve the problem for $$$m \le 10^9$$$ or saw that the sum of $$$m$$$ is bounded by $$$10^5$$$.
are writers just trolled us by B?
a < c < d < e < b
:/
Sorry, it's my mistake. Please don't click the dislike button again, I'm sorry! (I mistook C as an existing problem)
(Comment before modification) //This game has an existing problem https://www.luogu.com.cn/problem/P9345
It's shameful for the person who wrote the original question
This problem requires finding a permutation with score exactly equals to k, instead of the maximum possible score.
I think it's even easier than the original question
We also had the same problem asking for a permutation with score equal to k but then decided to ask for the max answer.
What is the output of the second number in B question, I haven’t understood it yet. :(
It's exactly the same as question C.
https://www.luogu.com.cn/problem/P9345
Codeforces Round 893 (Div. 2) Problem C looks the same as Luogu: https://www.luogu.com.cn/problem/P9345. Should th contest be unrated?
How to Solve Problem B
create 2 arrays first array (let's name it a) to store the number of cookies eaten by Petya at seller[i]'s bench second array (let's name it b) to store the number of cookies eaten by Petya at seller[i]'s bench if seller[i-1] was removed a[0] = b[0] = 1 + floor the distance between seller[0] and 1 divided by d for the rest of the array, a[i] = a[i — 1] + floor the distance between s[i] and s[i — 1] divided by d (+ 1 if the distance isn't divisible by n). b[i] = a[i — 2] + floor the distance between s[i] and s[i — 2] divided by d (+ 1 if the distance isn't divisible by n) now you find the max difference between a[i] and b[i] which is the difference resulted by removing s[i — 1] and count how many times did this difference occur. the answer is the difference between the number of cookies eaten if no sellers are removed and the max difference then the count of the max difference. here's how I solved it 219009908
A problem which is requires similar observation as problem C but slightly more interesting appeared in RUET IUPC 2022.
It's quite interesting, and I figured out only when min(u,v)==gcd(u,v) can edge(u,v) be useful. So the number of edges is not big.
B and C should've been swapped
Question about problem B.
Why is the answer for this test case 6, 4 instead of 6, 3?
30 5 8
6 8 15 24 29
Removing cookie sellers at 8 or 24 won't give the minimum, right?
Removing 24 will give minimum as, if we consider the points where petya eats cookies in range [15 ,29]. Before removing 24 will be 15 — 23 — 24 — 29. After removing 24 will be 15 — 23 — 29
You can remove 6, 15, 24, 29 for minimum
I can not understand the second output in problem B. Can someone help me pls :(
The second output is the count of people that (if he's removed, the least cookies are consumed)
e.g
Remove People#1, Cookie Count=3
Remove People#2, Cookie Count=4
Remove People#3, Cookie Count=5
Remove People#4, Cookie Count=3
And the output should be
3 2because there are 2 people that can lead to least cookie counts(people #1,#4)
thank u sm
suggest swap(rate[B],rate[C]) (MAD)
true, problem B is a good example of what problems to be avoided to be a part of round
suppose
C is the same problem from other OJ, and E1&E2 r 2ez and trivial.
I don't think this round should be rated, whether in terms of quality or difficulty.
unrated for me better(MAD)
I'm still waiting for RiOI round 3, and u r blaming codeforces problems :(
Linear solution for E1 (Edit: Seemingly linear, actually quadratic):
We construct history tree of additions (or persistent linked list if you will) then dfs it, storing how many uniq values we have.
Query processing:
+Add a node to history tree and move to that node. Store it to history.-Move to a father k-times, store final node to history. (We can do this, cause we will not move up more times, then we added nodes)!Load last but one node from history and delete last.?Mark this node for an answerDfs — we store counts of all items in array and total unique ones:
- Add value stored in current node.
- Answer all questions marked here.
- Dfs all sons.
- Remove the value stored in this node.
Seems to me this is O(N) but did not pass (218993624). Did this happen to anyone else?
Not true with
!queries. Consider adding many values then repeatedly doing-and!.Fix to this problem is to do binary jumping.
Makes sense, thanks.
It's because the queries can repeatedely go back k times and then rollback which goes forward k times. Its pretty easy to see how the number of operations would blow up in that case.
What's your explanation of the number of people who passed C is 3 times of who passed B, and why did you use a widely known problem witch had appeared in Chinese as C?
C was kinda easy , B was kinda of a corner cases thing
I think it partly has to do with problem B being very hard to read especially for those whose first language is not english.
Yes! I spent at least 15 minutes to get to know what B tells.
can anyone help me with this solution for problem c? Getting WA 218998257. I don't know which case is failing.
Your proposal only has 5 distinct numbers. There is no number six.
Sorry, Didn't get you.
The wrong test case is when n=12. The expected permutation should have 6 different numbers, but yours only have 5
No way you guys have just pulled the contest announcement from the front page. That's just a little bit silly, don't you think?
UPD. It's back, now I am not worried for all of the work that went into this contest
UPD 3: The contest will be unrated
Ratings updated preliminary, it will be recalculated after removing the cheaters.
Video Editorial For Problem A,B,C and D.
https://youtu.be/CeFlJ-pX3kw
Please find the solution of problems A and B on the channel: https://www.youtube.com/channel/UCLQtLtFcxXAd7366G3iCadw
Problem A Link: https://youtu.be/fKhvK6TfRXA Problem B Link: https://youtu.be/fZQQedImGNw
rest in peace atomicenergy
https://www.douglassfh.com/obituary/zachary-polansky
Good problems, bad round I guess. But B's problem statement gives me a headache:(
Also, after solving A~C, I saw that E1's score is lower than D, so I thought it would be easier, but in fact it seems like I'm terribly wrong. I solved D in the last 20 minutes, but got penalty on E1 for like 10 times. Maybe I'm just bad at data structures bruh
why my first submission of problem A was skipped? but it is right.
Because you made another submission on A later on, thus the first one got omitted.
I think problem B can be rephrase into something like :
Given $$$N$$$ points from $$$1, 2, ..., N$$$. There are also $$$M$$$ benches numbered $$$1, 2, ..., M$$$. Bench number $$$i$$$ is located at point $$$s_i$$$
You start at point $$$1$$$ and go all the way up to point $$$N$$$ by moving $$$1$$$ unit per second. Then you start by eating a cookie ay point $$$1$$$. Along the way, you can eat cookie at any integer point $$$p$$$ when at least one of the following condition is fulfilled :
You want to remove exactly one bench so that after the removal of the bench, the number of cookie you eat in the end is minimal
Determine :
15 authors and we have the problem B with more 5000 Accepted and problem C with more 13000 Accepted :)
i hate the problem B :(
B > C > A
So, 15 authors couldn't see that B > C > A ?
Unfortunately, that is true :( We are really sad about it, because we were worried that B might be of the same difficulty as C based on the round testing (it took people around the same amount of time to solve them), and we tried to fix this by giving them almost equal score.. It is really hard to predict the difficulty of a particular problem for round participants, and we are disappointed that we couldn't sort it out properly. However, based on the little information we had, it might have turned out the other way as well if we did swap them. We are truly sorry for misjudging problems' difficulties!
Can someone tell what's wrong in 219096582 solution for D?
.