More authors = better problems (as an author) xd

I couldn't reach pupil in the last contest.. I hope I reach pupil this time. Thanks for the contest.

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.

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.

Good luck!

As a tester, I suggest you to read all the problems.

"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?"

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…

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

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.

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.

"Please note the unusual start time of the round."

Huh? What's going on with start time?

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

pakhomovee thank you

"Please note the usual start time of the round."

why postponed by 1 hour

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 >_<

Note that the round has been moved one hour later.

OK but why? Any explanation for participants maybe?

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

is it rated for all ??

If someone was wondering why the initial start time was unusual, that's because dinner in SIS starts at 18:30 Moscow time :)

The contest is postponed, probably because Mike has been playing Genshin Impact excessively.

已延丁真，鉴定为：玩原神玩的

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.

.

How to optimize memory in E2?

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.

How to solve B?

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?

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?

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. (:

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

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

A problem which is requires similar observation as problem C but slightly more interesting appeared in RUET IUPC 2022.

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?

I can not understand the second output in problem B. Can someone help me pls :(

suggest swap(rate[B],rate[C]) (MAD)