Hi!
This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students, Moscow Open Olympiad in Informatics (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829, 852, 857).
We are happy to announce Codeforces Round 879 (Div. 2) based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Jun/18/2023 11:05 (Moscow time). Please notice the unusual time. You will have 6 problems and 2 hours to solve them.
We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of All-Russian olympiad in the name of Keldysh (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.
Problems of this competition were prepared by grphil, Mangooste, sevlll777, Siberian, TeaTime, teraqqq, Ziware, TheEvilBird, Ormlis, Alexdat2000, vaaven, Mikhango, Artyom123 guided by Ormlis, grphil and Helen Andreeva.
Thanks to Artyom123 for the round coordination, and also thanks to MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.
Great thanks to the testers of the round: PurpleCrayon, He_Ren, feecIe6418, penguinhacker, ix35, Dominater069, MagicalFlower, tzc_wk, gyh20, ezraft, Kieray, AquaMoon, satori_____, njupt_lyy, Mike4235, ak2006, Lavine, Ritwin, xiaossr, turmax, fastmath, Kapt, Kirill22, Be_dos, Olerinskiy, gmusya, blyat, vsinitsynav, orz, TheGoodest, playerr17, lesssia.
UPD1: Scoring distribution:
500 – 1000 – 1250 – 1750 — 2500 – 3000
Good luck everybody!
UPD2: Editorial
UPD3: Winners!
Official:
Unofficial:
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?
It means that there is an on-site olympiad contest in Russia which has the same problems as this Codeforces round. The problems were originally prepared for the olympiad, and they just reuse the problems here on codeforces.
Do the contests usually happen at the same time as the onsite?
yes
Oh thx. Got it.
Good luck everyone! wish I turn purple!
My daydream is shattered T_T. L_Wave
When will scoring distribution come out?
edit: got it.
When the olympiad will begin, I guess
I hope the round will be better than the previous one and I will become a master!
I hope I will pass 1500 rating
I hop I will pass 1400 rating
Can you make the pretests stronger?
Will this be rated?
Yes. But you could've just read the title.
Two contests in one day, cool!
I'm confused why comments like "Good luck" sometimes get downvotes but sometimes get upvotes
two rounds in one day??
confused..which one to attend , 879 or 880
Both! ;)
is it ununsual to have 2 rounds happening so close to each other? never in the Codeforces have i ever seen this coming
Because these to rounds are not "regular", they are based on two olympiads (Russian and Polish), which are at the same time. A funniest joke it that there is Atcoder Regular contest between two CF rounds:)
it is unusual, but it has happened, in fact, round #829 and #830 had only a 15 minute break between them!
Super Sunday tomorrow! CF 879 > ARC 162 > CF 880
Before cf 879 there is leetcode weekly round also
who gives leetcode lol !!
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 :).
Rating for first round will get updated before second one.
not really , last time two back to back contests happens in one day , and both rating updates happens after end of both rounds accordingly
Who is Keldysh?
+
It's great to see AquaMoon as tester
Thanks for your support! Tasks are nice and wish you good luck (〃'▽'〃)o
Be ready with Math Problems :)
Russian kids eat div.2 problems for lunch （￣︶￣）↗
I hope there's no DDOS,I just have a bad ABC.
I was wrong :3
Is this round rated?
Read the Blog title carefully :D
Sure, Bob, whatcha gonna do about it?
Nice contest. First time to solve only A & D.
how did you solved D.
For every i-th segment I found the segment that difference with i-th segment maximum possible. Let x be the r_i — l_i + 1, y be number of common points. Difference will be 2 * (x — y)
Yes I know this..but how to find that segment with the maximum difference or minimum overlap
There are only three cases, Compare with 1) segment with largest l 2) smallest r 3) smallest size
can you explain it's proof.
for the 3rd one, you need it to be included in the ith segment. How to do that efficiently?
Not really. If the smallest interval is not included, the height difference only gets better and you would have covered it in cases 1) or 2).
For i-th segment if there is a segment that doesn't have common points you must choose it and difference is 2 * x. Otherwise you must check with segments which have minimum length, wich have minimum r[j] that l[i] <= r[j], which have maximum l[k] that l[k] <= r[i]. NOTE: I used set for finding r[j] & l[k]
Suppose student i's hand is the highest at the end. Then Zinaida should ask li to ri to obtain maximum height difference.
To get the max difference of heights, there should exist a pair of segments such that one gets +1 increments and other gets -1. Iterate on all increment segments and find the best decrement segment to maximize the ans, there will be 3 cases:
1. consider the segment with rightmost start.
2. consider the segment with leftmost end.
3. consider the segment fully overlapping with least length.
1 and 2 are easy to achieve by sorting, for 3rd case iterate on segments in increasing order of start points and maintain a multiset of segments sorted by lengths that have start points greater than or equal to current segment
For 3rd case we can sort according to ending point and keep track for minimum length segment. You can Check my submission 210074389
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.
This is how it is intended to be, it's not a bug. In Div.1 or Div.2, if you submit multiple times with "pretests passed" to a single problem, only the last submission will count and all previous ones will be regarded the same as previous incorrect submissions.
In other words, you get -50 for each previous submission, and you get time penalty according to the last "pretests passed" submission. I actually don't know if submitting a "wrong answer" submission after "pretests passed" gives any penalty, though.
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$$$!
Was being braindead sorry.
There are $$$O(n)$$$ prime numbers in range $$$[1,n \cdot logn]$$$. So you can consider your upper bound of answer to be around $$$n \cdot logn$$$.
We can show that the answer doesn't exceed $$$10^7$$$.
Consider the subarrays $$$[i;i], [i;i+1], \dots, [i;n]$$$ (i.e. subarrays with a fixed left point) and their LCM's. If we go through these in order from left to right, the next segment's LCM must be a multiple of the previous one. This means that if the value changes, it must at least double. This means that within these segments starting at $$$i$$$, there can only be $$$\left\lceil\log_2 10^7\right\rceil = 24$$$ different values $$$\le 10^7$$$. This means that within all subarrays over all leftpoints $$$i$$$, there can be at most $$$n \cdot \left\lceil\log_2 10^7\right\rceil = 3 \cdot 10^5 \cdot 24 = 7.2 \cdot 10^6$$$ distinct values $$$\le 10^7$$$. Since this number is less than $$$10^7$$$, some values $$$\le 10^7$$$ must be missing, and the answer is thus $$$\le 10^7$$$.
Can someone explain problems D and E to me? I solved problem ABC quickly, but I couldn't solve any of the others.
D: Just take every pair. now you will to call all from x[i] to y[i]. then if you find a r> y[i] || l<x[i] then current contribution is (y[i]-x[i]+1)*2. If not then check with the minimum length segment.. the last check is check is intersected pair with ith pair.. find the max l[i] as l[i]<=r also find lowest r[i] as if r[i]>=x[i].
link
thanks for your great explanation:D
I might have overcomplicated myself but notice that there are only three possible candidates for the range $$$[l_i, r_i]$$$:
The range $$$[l_j, r_j]$$$ with the minimum $$$r_j$$$.
The range $$$[l_j, r_j]$$$ with the maximum $$$l_j$$$.
The range $$$[l_j, r_j]$$$ with the minimum length such that $$$l_i <= l_j, r_j <= r_i$$$.
Case 3 can easily be checked with a dynamic segment tree.
Actually, for the third case, a segment tree is not needed. Consider the minimum overlap for Cases 1 and 2 as X;
Then iterate through an array sorted based on the lengths of the segments until the current subsegment length exceeds X.
My submission.
Thank you both:))
Any hints for solving problem C ?
Think of parity of the operations bob can make
Calculate the cost of making S == T and S == Rev(T)
min of them is answer ?
Yes, since Alice wants to minimize the duration of the game.
i missed the exception when alice does not need to make any meaningful move and just wait for string to get reversed .
Oh yeah, that's an annoying edge case
ikr , thanks though . tryna upsolve d before next round
Luckily the edge case was present in the sample test case. It was a good edge case.
You should also consider Bob's movements. If you make 17 Alice movements, to make S == T then after 17 movements Bob reversed T and S and you should add 1 more Bob's (for example)
main hints is if bob reverse the S or T affect are same.
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.
How did you solve B? I'm gonna lose 150 rank in this contest because of that stupid problem aaaaaaaaaaaaaaaaaaaaaaaaaaaaaah
It's simple once you read it correctly. First, make them equal by padding 0s. Then, find the first index from the left where digits differ. Let's say x in L and y in R.
Now, we can construct two numbers like,
.......y00....00
.......x99....99
It can be proved this is optimal.
Amazing Contest! Can anyone tell the difficulty rating of A,B,C please? Also how to solve D?
The difficulties probably are 800,1000,1200
For D, my main observation is that we can always get the answer by choosing two segments and calling all the numbers in the larger one. This will give us a maximum difference of $$$2$$$ times the length of the larger segment minus $$$2$$$ times the intersection length. Now if we can come up with a way to choose the best segment to pair a given segment with, we can iterate over all segments and take the maximum answer we get.
what I did was to keep track of the shortest leftmost segment, shortest rightmost segment, and the shortest segment overall. Let those be $$$[l_l, r_l], [l_r, r_r]$$$ and $$$[l_s, r_s]$$$ respectively. Now for each other segment, if $$$l_i > r_l$$$ or $$$r_i < l_r$$$, we choose this segment and that boundary segment which doesn't intersect it. If the current segment intersects both boundary segments, we have 3 choices:
We consider the current segment and the left boundary
We consider the current segment and the right boundary
We consider the current segment and the shortest segment overall
We can simply check what we get for all these choices and update the answer as we go. Finally, we have to check what answer we can get if we choose the right and left boundary segments themselves.
What does the 'shortest leftmost segment' mean? on what basis did you sort them?
I primarily sorted to minimize the $$$r_i$$$ (thus 'leftmost') and secondarily to maximize $$$l_i$$$(giving the 'shortest' part).
Similarly for the rightmost shortest segment I primarily sorted to maximize $$$l_i$$$ and secondarily to minimize $$$r_i$$$.
get it, thanks!
Do you sort the $$$[l_i, r_i]$$$ first on the basis of length and then run this algo? I mean how are you handling the case when the current segment is contained in any of the segments which have been already processed? I'm talking about the case when any of the processed segment could contain whole of the current segment.
No, I process the ranges in the same order given. However I find the overall shortest, leftmost and rightmost ranges before processing. I don't understand what you mean by the processed segment containing the whole of the current segment.
For problem D, a naive solution is to iterate over all pairs of students, then try to raise the first one's hand as high as possible and the second's hand as low as possible. Using greedy algorithm can easily determine the best strategy to ask the topics and update the answer. The time complexity is $$$O(n^2)$$$.
A key observation is: let i, j, k be the students with the smallest r, the one with the biggest l and the one with the smallest r-l, respectively. We can make the second student be either i, j or k, which can be proved right with simple caseworks.
video editorial for D survey in class
@Astroflexx
problem D is nice!
I think tests were very weak
weak tests better than FST
what's FST?
failed system test
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
0999 2000 gives 29 (:
whenever you encounter a digit in string b that is bigger than a, you don't have to check the rest as you can force them to be 0 and 9 , so the ans here is 2+9*3 which is 29
0999 2000 it will give 29
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
Same
video editorial for D survey in class
Frogmaster _Gawd_
Question about problem B: seems like for a following test
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).
09999 10000
Oh, I see, I guess this makes sense then, thanks!
You can do 10099 and 9900 which adds the "1" you are missing
10000 and 9999 gives 37
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?
I commented this already elsewhere, just copied from there:
We can show that the answer doesn't exceed $$$10^7$$$.
Consider the subarrays $$$[i;i], [i;i+1], \dots, [i;n]$$$ (i.e. subarrays with a fixed left point) and their LCM's. If we go through these in order from left to right, the next segment's LCM must be a multiple of the previous one. This means that if the value changes, it must at least double. This means that within these segments starting at $$$i$$$, there can only be $$$\left\lceil\log_2 10^7\right\rceil = 24$$$ different values $$$\le 10^7$$$. This means that within all subarrays over all leftpoints $$$i$$$, there can be at most $$$n \cdot \left\lceil\log_2 10^7\right\rceil = 3 \cdot 10^5 \cdot 24 = 7.2 \cdot 10^6$$$ distinct values $$$\le 10^7$$$. Since this number is less than $$$10^7$$$, some values $$$\le 10^7$$$ must be missing, and the answer is thus $$$\le 10^7$$$.
I was kind of looking for a tighter limit $$$10^6$$$ works for me and I don't think the answer would exceed that number.
Also, I think the actual limit is smaller think about it this way you need a position for each power of a prime plus you need to kind of have some weird configuration of the array to get all values.
For each i there's at most one value of lcm in a range [L, i] for each [2^j, 2^(j+1)). Let's take x being the minimum integer such that 2^x > N. Then in the range [2^x, 2^(x+1)) there's at most N values that appear as lcm of subranges, but since the range has size greater than N there must be a missing value. This proves a bound of 3 * N + 1.
Edit: even stronger is realizing that we can generalize the observation from [2^j, 2^(j+1)) to [X, 2X). Then, for the range [N+1, 2(N+1)) there are at most N values that appear, so there's one missing and it can be at most 2N+1.
Oh, this is really nice, thanks.
Can you please label what does i, j, L indicate in accordance to the array?
Fixing a position i in the array, considering every value of lcms of values in ranges [L, i] of the array that end at position i, there's at most one unique value of lcm that has value in range [X, 2X) for any positive X.
It's obvious that the answer doesn't exceed $$$10^9 + 7$$$, as this number never occurs. So, we don't care about LCMs greater than this number.
Let's choose three indices
$$$1 \leq l \leq a < b \leq n$$$
if $$$LCM(l, a) \neq LCM(l, b)$$$ then $$$LCM(l, a) \cdot 2 \leq LCM(l, b)$$$
So, for a fixed leftpoint, the number of different LCMs doesn't exceed $$$\log(1e9 + 7)$$$
We can say that 5e6 is an upper bound since there are at least 3e5 prime numbers less than 5e6
Such a fast rating update.
probably because there's another contest today
what is the idea of B ?
Brute force on prefix where you place all 9s in a number and 0s in another number
is it always possible ?
Well it worked but idk proof
Could you explain me idea of problem D?
video editorial for D survey in class
@Halym2007
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.net/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.
F: You can do it in $$$O(N)$$$ using prefix sums 210079002
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.
Please any hint for problem D
VERY SIMPLE SOLUTION FOR PROBLEM D, by killer_god ,
Linear time solution.
I was implementing sorting and then segment tree and got lost in implementation, and he solved in just 7 minutes.
https://codeforces.net/contest/1834/submission/210057660
Consider what the maximum answer is if you have only 2 students.
For each student, can you find an efficient way to find the optimal otherstudent to get the maximum answer? Maybe using extremes?
video editorial for D survey in class
@L_7
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!
You could make a graph on letters where an edge between x and y means that all occurences letters x and y must become the same letter.
This means that for each string, the answer would be (total number of characters — number of connected components). There also might be an edge case where there are no characters that are in both strings from current component so you would have to add 1 for each of these.
Rest is the same as C, solve for odd/even separately
I became Master in this round!
Congrats! I earned -120 this round though..
Thank you! And I'm sorry to hear that your rating dropped.
Congrats!
Thank you!
Specialist for me
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
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)
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)
the other student partially overlaps, and is the maximum, in this case, we take the student with the farthest endpoint.
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)
What is the meaning of statement "Your solution ... have been uphacked". Is it means that my solution was hacked?
It means that someone hacked your solution after contest. But notice that this a div.2 contest, which does not have an open hacking phase after the contest (you can only hack during the contest in your room for score). Since the hacking was done after the contest, you don't lose score. But this shows that systests were not strong enough to catch all wrong solutions.
@Ormlis, I got this mail today morning. Your solution 210063237 for the problem 1834C significantly coincides with solutions sanjaydwk/210063237, tandj_24/210066622.
But there was no such submission by tandj_24. In fact, I saw his/her profile and he/she have not solved any question in this contest. Please look into this matter asap.
Thank You!
Today I received a message saying that my solution for problem B and C of Codeforces Round #884 coincides with the solution of a codeforces user named AbdulRahman_Salah. [cut] I was really confused why this has happened. But then I saw that a particular design is present in both of our codes.
Problem B -
Mine || AbdulRahman_Salah
Problem C -
Mine || AbdulRahman_Salah
I've been using this template for so many previous contests and I've no idea why this has happened. Moreover, I have given around 26 contests and I have a very clean record. I am not a cheater.
I would request MikeMirzayanov to look into this matter as clearly there is no fault of mine in all this. Please help me. Codeforces, please look into this matter. I don't want to lose my expert tag. I've got it after so much hard-work.
Moreover, see this blog for more.