Hoping this time, the contest to be balanced with better pretests, unlike the previous few editions :)

All the best everyone!

Sorry if this is a stupid question but what does it mean that the round is based on the russian olympiad? I read something like that on codeforces sometimes, also in other posts. Can somebody explain?

Good luck everyone! wish I turn purple!

gl hf y'all

When will scoring distribution come out?

edit: got it.

I hope the round will be better than the previous one and I will become a master!

I hope this contest is going to be better than previous contests. I kindly ask authors and testers to balance the pretests of problems, as it affects to the contestant's performance.

All the best everyone!

Can you make the pretests stronger?

Will this be rated?

Two contests in one day, cool!

I'm confused why comments like "Good luck" sometimes get downvotes but sometimes get upvotes

I hope this contest is going to be better than previous contests. I kindly ask authors and testers to balance the pretests of problems, as it effects to the contestant's performance

two rounds in one day??

confused..which one to attend , 879 or 880

is it ununsual to have 2 rounds happening so close to each other? never in the Codeforces have i ever seen this coming

Best of luck everyone. Excited for this!

Super Sunday tomorrow! CF 879 > ARC 162 > CF 880

I have a question. How manage Codeforces rating changes if I participate in both rounds? My new rating will be calculated using my rating before compete in the first round or after my first contest rating changes? I ask that because I wanna do both contest :).

This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh

Who is Keldysh?

+

It's great to see AquaMoon as tester

Do we need to register for this round? Becz I can't see the link for registration

Be ready with Math Problems :)

If you complete the first dev, you will be in the best condition, and you will participate in the dev at 5:35 I think everyone will do this and sleep well today

Russian kids eat div.2 problems for lunch （￣︶￣）↗　

A lot of red and yellow testers, I hope this contest will be great.

All the best everyone.Curious to face a new challenge.

I hope there's no DDOS,I just have a bad ABC.

I was wrong :3

Is this round rated?

I submitted D two times out of FST paranoia and the second time I submitted my code I lost about 100 points. Is this intended? I thought only the first accepted was the one that counted.

Bob's goal is to maximize the duration of the game

Sure, Bob, whatcha gonna do about it?

Nice contest. First time to solve only A & D.

I submitted my code for D 2 times out of FST paranoia and approximately lost 100 points on the second submission. Is this intended? I thought that only the first accepted counted for scoring.

Problem E is so nice. The answer cannot exceed $$$max(a_{i})+n^2$$$, so $$$ans \leq 10^{10}$$$. Now imagine function $$$nxt(i, x)$$$ which tells you the smallest index $$$j>i$$$ such that $$$a[j] \nmid x$$$. Then, to find MEX, we can just use the $$$nxt(i, x)$$$ atmost $$$log_2(max(a_{i})+n^2)$$$ starting from each $$$i$$$!

Can someone explain problems D and E to me? I solved problem ABC quickly, but I couldn't solve any of the others.

Any hints for solving problem C ?

Could you please put a link to the contest in the announcement?

Anyone else so dumb that they confused statement of B like this:

Find a number X in [L, R] such that the strength of X and R is maximum. I wasted an hour just to realize the correct statement, and then it was just a matter of a couple of minutes.

Amazing Contest! Can anyone tell the difficulty rating of A,B,C please? Also how to solve D?

problem D is nice!

problem B

accepted code give output 29 for this input.( 88 2588) but i guess this should be 28. please recheck.

I think tests were very weak

problem B

accepted code give output 29 for this input.( 88 2588) but i guess this should be 28. please make me understand.

upd: ok understood

I threw hard this contest and didn't solve C in contest. I solved it after tho with a somewhat unique idea. I simulated the optimal strategy for Bob to make the game last as long as possible. In order to keep it relatively fast, I also kept a reverse of the string so that I wouldn't have to keep reversing it after Bob's move. 210083837

Solved ABC in 30 minutes and then struggled with D. Interesting task, I was quickly able to reduce the problem to finding two segments with the largest exclusive area and was trying to transform it in a useful way but failed. Waiting for the editorial

Question about problem B: seems like for a following test

1
11 11299

according to the correct solution the answer is 37, but isn't it only 36, because in the best case we can get these two numbers: 99 and 9900 (I dont see how it is possible to get a sum any higher than this).

cool contest, problems D and E require at most 30 lines of code if you got the right idea

Any kind of proof for the upper bound of LCM in E?

Such a fast rating update.

what is the idea of B ?

Could you explain me idea of problem D?

problem E has really weak system tests.
Just hacked an accepted solution with this test:
1
100000
6 8 6 8 ... 6 8
https://codeforces.com/contest/1834/submission/210074338

A: The number of occurences of -1 should be even and not greater than n/2.

B: From the first different digit of L and R from the highest digit. Let L=a1*10^m+a2 and R=b1*10^m+b2 where a2,b2<10^m, we can let 0-th to (m-1)-th digits of L become 9, and corresponding digits of R become 0. Then the answer will be at least abs(a1-b1)+9*m. We can see this is also the upperbound of the answer.

C: We can see that for Bob, reversing S and reversing T are equivalent, so Alice only need to make S==T or S==reverse(T). If Alice make k changes to transform S into T, the game will end at (2*k-1+(k+1)%2)-th turn, and if Alice make k changes to transform S into reverse(T), the game will end at (2*k-(k+1)%2)-th turn — but there's a special case: if k==0 the game will end at 2nd turn.

D: Define f(i,j) be the size of [l[i], r[i]][l[j], r[j]] (which denotes the set of numbers contained in [l[i], r[i]] but not in [l[j], r[j]]), then for any two students i, j, the difference of there height will be not greater than 2*max(f(i, j), f(j, i)). Therefore, we need to calculate max(f(i, j)) over all pairs of (i, j). We need to consider 2 cases: range i is contained inside range j, and otherwise. For the first case, we need to sort all ranges by their left-end, and for 1<=i<=n checking max(r[j]-l[j]) where l[j]<=l[i], and calculate (r[j]-l[j])-(r[i]-l[i]). For the second case, we need to check min(r[j]) where r[j]<=r[i], and calculate r[i]-max(l[i]-1, r[j]).

E: Note if p is a prime number or 1, and p is in the set of lcm, p must occur in a[i], so the answer will be at most p[n] (the n-th prime number). And for each i, the number of different values of lcm(a[j], a[j+1], ..., a[i]) below p[n] is at most log(p[n]), so we can check these values by maintaining the set L[i]={lcm(a[j], a[j+1], ..., a[i]) : 1<=j<i} in O(p[n]+n*(log(p[n]))^2) for checking n*log(p[n]) values and calculating lcm in O(log(p[n])).

F: The answer of a single query is the number of indexes i such that p[i]<i. Since there are at most 2*n different status of the array (n shifts of a[i] and n shifts of reverse(a[i])), we can pre-calculate all of them using fenwick tree.

A: Many straightforward approaches. What I did was count the number of +1s and the number of -1s. Make the number of -1s even (making a change if needed). After that, you can only change two -1s at a time to preserve parity, resulting in a +4 difference, so the final answer is $$$2 \left\lceil \frac{\max (0, minus - plus)}{4}\right\rceil + (minus \% 2)$$$

B: Find the first digit position in which $$$L$$$ and $$$R$$$ differ. Change all digits after this point to 9 for $$$L$$$ and 0 for $$$R$$$, resulting in a total strength of (difference at first change) + 9 * (number of digits after the first change)

C: It makes no difference whether Bob reverses $$$S$$$ or $$$T$$$, so Alice simply needs to make sure either $$$S == T$$$ or $$$S == rev (T)$$$. Count how many operations Alice needs for each of them, and pick the smaller, then count how many total operations are needed (including whether it ends on Alice's turn or Bob's "turn"). The problemsetter was very kind to place the edge-cases of $$$S == T$$$ and $$$S == rev (T)$$$ in the sample input (I legit missed both of them when I first thought I completed my code).

D: We only care about the highest hand and the lowest hand, so we basically need to find the maximum pairwise set difference between all intervals. My observation was the student with the lowest hand would have to be either: (a) the student whose interval ends the earliest, and if there are any ties, then this student has the shortest interval among them, (b) starts the latest, with shorter interval breaking ties, (c) shortest interval, with early end breaking ties, (d) shortest interval, with latest start breaking ties.

Proof Sketch: consider all cases how lowest hand interacts with highest hand: either they overlap on the left, or they overlap on the right, or the former is a subset of the latter, and in all three cases, we can see that violating all four conditions guarantees the existence of another student that would achieve a lower or equal hand (for the same choice of highest hand).

Once I found these four students, I checked all $$$n$$$ students as candidates for highest hand against each of these four students, and picked the one with the largest set difference. I'm not even sure if it's necessary to check all four, but I couldn't complete the proof for fewer than 4 low-hand candidates, so I stuck with the safe choice of checking all four.

During the contest, I misread the statement of problem C and thought that In turn, Alice chooses an integer i between 1 to n one of the strings S or T and any lower-case Latin letter c and replaces all occurrences of i -in the chosen string with the character c . If so, how can this problem be solved? I've tried a lot but haven't found the answer, I'm stuck and can't generate a solution, so any help would be greatly appreciated!

Please any hint for problem D

During the contest, I misread the statement of problem C and thought that In turn, Alice chooses an integer i between 1 to n one of the strings S or T and any lower-case Latin letter c and replaces all occurrences of the i -th symbol in the chosen string with the character c. If so, how can this problem be solved? I've tried a lot but haven't found the answer, I'm stuck and can't generate a solution, so any help would be greatly appreciated!

I became Master in this round!

https://www.youtube.com/watch?v=qq1D83Mj4TY My solution for D

I fixed the 'ith' student to be one of the maximum/minima. and then checked for 4 cases

1. the other student is disjoint with the ith student. In that case, the answer is the max(2*size(i),2*size(k)) for all 'k' segments disjoint with i. (which can be found using binary search and maintaining suffix maximum)

2. the other student partially overlaps, in this case, we will take the student with the farthest start point out of all the overlapping segments ( we assume that the other student is the minima)

3. the other student partially overlaps, and is the maximum, in this case, we take the student with the farthest endpoint.

4. the other student is fully overlapped by the ith range, for that we will take (size(i) — minimum size of any segment which is partially/fully overlapping with the ith segment)

Почему в задаче С, s сводится только к t или rev(t), разве не может быть случая когда стоит взять некоторые символы из s другие из t чтобы в итоге получился палиндром и точно не потребовалось ждать ещё одного реверса от Боба?

Интересные задачи, спасибо за контест! 2-ая и 3-я особенно понравились, добавил в избранное)

What is the meaning of statement "Your solution ... have been uphacked". Is it means that my solution was hacked?