Hello, Codeforces!
mtw, naman1601 and I are glad to invite everyone to participate in Codeforces Round 825 (Div. 2), which will be held on Oct/10/2022 17:35 (Moscow time).
This Round will be rated for participants with rating lower than 2100.
You will be given 5 problems with one subtask and 2 hours to solve them
We would like to thank:
- Arpa for coordinating the round.
- KAN for help in preparation of the round.
- Everule for proposing a task that did not make it to the final problemset.
- BucketPotato, PurpleCrayon, the_hyp0cr1t3, welleyth, MagentaCobra, recurecurring, GoatTamer, udhavvarma03, 74TrAkToR, AwakeAnay, valeriu, TheScrasse, kal013, avi0000, Perpetually_Purple, codemastercpp, CoderAnshu, IceKnight1093, Dio707, hsekharsahoo, tibinyte, Vladithur, master._.mind, mejiamejia, zalak_b, Non-origination, SlavicG, manish.17, dedsec_29, Mo2men and nor for testing this round and providing feedback.
- MikeMirzayanov for great Codeforces and Polygon platforms.
The score distribution will be announced closer to the start of the round.
UPD1: Score distribution is 500 — 1000 — ( 1250 + 2000 ) — 2000 — 2500.
UPD2: Congratulations to the winners!
Overall:
Rated:
UPD3: Editorial is out.
Good luck and have fun!
As a tester, I tested because valeriu told me to.
I hope any problemsetter asked me too for testing. I wanna try testing a round so bad xd
I don't know what you are trying to imply
Nothing, just that I'd love to test some rounds but I have never been contacted for it so far
Maybe you can add my discord, I won't turn anyone down, but you have to be good friends with me before I invite you to test, it can be very difficult, you have to spend a lot of time communicating with me and making me feel like you can Trust, so it is recommended that you do not aim to test the competition, but to make friends with me.
can we be friends again?
Oh my god,aren't we already friends?
I thought we stopped being friends and I was so sad. I wish we can be friends again. Can we be friends again?
God, that's impossible. Why do you think so, let's chat on discord.
As a tester, I can assert that the problems are amazing and recommend everyone to participate in this contest!
X: doubt. UPD: I really enjoyed the contest. Problems were great. My performance was worse than usual but still I really liked the contest. Big thanks to the problem setters!
Damn, you just made the tester get a runtime error due to a failed assertion. (get the joke?)
no
Seeing green and cyan testers give me hope that the difficulty of A will be fit for its position.
Hope to see a balanced round friendly to greys.
Don't trust appearances.
Don't cover the book by its judge
cursed comment
As a tester, I think the problem is really great, and I recommend everyone to participate.
i love Mo2men <3
As a tester, I still don't know half the problems oops
Confused Unga Bunga... XD
I have a feeling that this round's quality will match the date ... 10/10 :)
agree+1
As a...
hypocrite? the problems were very nice and I wholeheartedly recommend the participation?
As...
As a tester, i forgot to farm contribution using as a tester komments.
naman1601 Sir round, can't wait to participate. Good Luck Everyone
Hoping to reach a bit closer to that green zone. Have a great contest everyone ^_^
Me too. I hope we both do it!
Lets hope A is easy this time, so that more people participate.
As a tester, the problemset is really enjoyable!
Being a tester for the first time for a CF contest, I tried to contribute and provide suggestions to the best of my ability. I would recommend everyone to participate!
Makise Kurisuu <3
As a tester, your mom
Is it funny in any meaning?
no, it is just bad humor I am honoured to be maybe the first tester to get downvotes lol
As a tester,
I want upvotes.Problems are great. You will surely enjoy the round.As a tester, I wish to solve three problems in this round
"As a tester, I wish to solve three problems"
As a participant, I think you are sus
Give me some upvote to get out of the negative contribution please ..
I hope no one will cheat in this round.
I am the biggest cheater in China OI,all people hate me.Do not do stupid things,like me!
What is meaning of subtask?
C1/C2 instead of just C
If you solve it then you will get 3250 points?
Yes
rp++!
Seems strange score distribution, C1+C2 = 3250 > E. Usually [C1,C2,D,E] is [E1,E2,C,D] in this case. I'm looking forward to see the tasks!
I am a little scared seeing the 1250+2000 distribution.
All the best @everyone. Hopefully the problems will be worth solving.
All people now looking at standings and waiting to do another things xd!
the joke about speedforces is already too hackneyed, but how can I not make a joke???
by not doing it lol
Where is the distinction? the participants can't show the difference。the problem C2 is too hard
all of these div2 testers, and none of them informed you that your round is too hard?
they can't tell the difficulty with confidence if they can't solve it though
they can say that they can't solve it tho
I would like to publicly apologize for not helping the authors well enough in this matter.
how to solve B?
C2 too hard to implement :(.
I agree.
To C2's author:The problem is good,I like it,but your examples are nearly meaningless lol
How to solve problem C1?
two pointer
Problem B really destroyed my brain ,I don't know how about 7000 solved this problem!
problem C just take 15 minutes to solve.
same here...found C1 easier than B
problem c is easier and very standard problem as its idea repeated very much in old contests.
What can be the rating of c1?
probably 1300
Same, I barely solved it in the last minutes, I think it was harder than $$$C$$$
B was literally on GFG. (Link here)
If this can generate the array $$$b$$$ and it fits the conditions, answer is $$$\text{yes}$$$. Otherwise answer is $$$\text{no}$$$.
Couldn't find the same approach in the same room, though.
It's exactly the same problem b, is this considered a stolen problem from GfG ?
Dunno. On GFG it was a constructive problem, on CF it was a decision problem. They can't deny the fact that it was solvable through a quick search on google, though.
I solved the problem now after i see its solution from gfg ,any one can cheat its solution from gfg , i don't know how is not considered cheating?
It doesn't count as cheating because everyone had access to the same source...
If it doesn't count as cheating then i will search about any problem in google during the contest.
T_T
Aaah.. I wasted 1 hour to solve B, got an AC, felt like einstein then BAM 5000 people already solved it
I think that it's cheating since this problem is exists in GFG when i saw its solution i solved it immediately after the end of the contest!
For me, it was the opposite, B in 15 min cannot solve C1. How did you solve C1.
could not solve both. wrong answer on pretest 2 for both.
Use two pointer algorithm
- for starting index find the ending index such that [start, end] is good subarray
- Since [start, end] was good, then [start+1,end] will also be good
Same :/
I think C2 is easier than B
critical-observative-forces
how to solve C2?
Let $$$b_x = x-a_x$$$, we also set $$$b_0=0$$$ and $$$b_{n+1}=n$$$ for convinience. Then if the sequence of prefix maximas is $$$b_{x_1}, b_{x_2},\ldots,b_{x_k}$$$. The answer is $$$(\sum\limits_{i=1}^{k-1} x_{i+1} \cdot (b_{x_{i+1}} - b_{x_i})) - \frac{n(n+1)}{2}$$$.
You can probably modify this blog to AC (if it works, we don't require updates to be independent). But I just bashed some stupid case work similar to prefix maximums from ICPC Gwalior-Pune Regionals 2021.
define end[i] = longest position j such that a[i..j] is good
then do casework on updates (binary search is needed)
you can try on paper how array end changes between updates
also note that update that increases a[i] should be considered differently from update that decreases it
i finished the code just now, not sure if my idea is correct
I made a vector called
start
, where start[i] indicates the lowest index that you can start a good subarray from and be able to include a[i] in the subarray. Then $$$start[i] = \max (start[i - 1], i - a_i + 1)$$$. This might look familiar if you solved C1 (though you may not have used a separate array for it).Before making any changes, the desired answer would be $$$\frac{n(n + 1)}{2} - \sum (start[i] - 1) = \frac{n(n + 1)}{2} + n - \sum start[i]$$$.
Note that $$$start[i]$$$ is basically the largest value of $$$j - a_j + 1$$$ for $$$j \leq i$$$. We can prepare another vector,
second
, where $$$second[i]$$$ is the second largest value of $$$j - a_j + 1$$$ for $$$j \leq i$$$. Note that $$$second[i]$$$ can be equal to $$$start[i]$$$ if there are two (or more) indices with the same maximum $$$j - a_j + 1$$$ value.We can prepare prefix sum arrays for both $$$start$$$ and $$$second$$$. You can probably figure out the rest from there, but if not, here are some details:
if changing $$$a_p$$$ to $$$x$$$ does not change $$$start[p]$$$, then the answer doesn't change, and you can just print $$$\frac{n(n + 1)}{2} + n - \sum start[i]$$$.
if changing $$$a_p$$$ to $$$x$$$ would cause $$$start[p]$$$ to increase to $$$newstartp$$$, then use binary search to find the next index $$$j$$$ in which $$$start[j] \geq newstartp$$$. So we use $$$newstartp$$$ for the range $$$[p, j)$$$ and use the original $$$start$$$ values for all other elements, which we can efficiently calculate totals using the prefix sums.
if changing $$$a_p$$$ to $$$x$$$ would cause $$$start[p]$$$ to decrease to $$$newstartp$$$, then use binary search to find the next index $$$j$$$ in which $$$second[j] \geq newstartp$$$ (this might be $$$p$$$ itself) and another binary search to find the next index $$$k$$$ in which $$$second[k] \geq start[p]$$$ (original $$$start[p]$$$). Then we use $$$newstartp$$$ for the range $$$[p, j)$$$ and the $$$second$$$ values for $$$[j, k)$$$ and the original $$$start$$$ values for all other elements, again, all calculated efficiently using prefix sums.
My Submission: 175446833
Wow! Very nicely explained. Also, we might get caught for plagiarism since I used
start[i]
for my array as well haha. Although I couldn't think about maintaining the second largest value as well for handling updates :(Can you explain this part please in 2nd point: when start[p] gets increased due to ap, we find j such that start[j] >= newstartp.
Are we finding a j such that j > p and whose start is beyond newstartp? How did we arrive to this conclusion that we need to find such j only?
Yes. Note that $$$start[i]$$$ is the largest value of $$$\ell - a_\ell + 1$$$ for $$$\ell \leq i$$$.
Suppose we set $$$a_p$$$ to $$$x$$$ and then recalculate all of the $$$start$$$ values. The $$$start$$$ values before index $$$p$$$ would be the same as before (no changes before index $$$p$$$). Let $$$j$$$ be the first index where the old $$$start[j]$$$ is $$$\geq newstartp$$$. Then the new $$$start$$$ values in the range $$$[p, j)$$$ would now be equal to $$$newstartp$$$, since $$$newstartp$$$ is now the new maximum value of $$$\ell - a_\ell + 1$$$ for this range.
But for index $$$j$$$ onwards, where $$$start[j] \geq newstartp$$$, we can continue using the old $$$start$$$ values, since they remain as the maximum in their ranges, despite the update to $$$newstartp$$$.
Of course, we don't actually recalculate and update all these $$$start$$$ values; we simply use prefix sums to calculate what the result would become if we were to have made such changes. The actual stored arrays are unchanged once we start reading queries.
Thanks for good explanation, really beatiful solution, but there is one thing: could you explain, what is the idea of using array second in case of decreased start[p]? Why does it work?
Note that $$$start[p]$$$ is the largest value of $$$\ell - a_\ell + 1$$$ for $$$\ell \leq p$$$.
But if $$$start[p]$$$ decreases to $$$newstartp$$$, then $$$newstartp$$$ might not be the largest such value.
Let $$$[p, k)$$$ be the range of indices such that the old $$$start$$$ values in this range all used the old $$$start[p]$$$. Then for these indices, the new $$$start$$$ value should be the new largest value (of $$$\ell - a_\ell + 1$$$), which would either be $$$newstartp$$$ or whatever used to be the second largest value, whichever is larger. We can denote $$$j$$$ as the index where the bigger of the two changes from $$$newstartp$$$ to the previously second largest.
By maintaining an array of the second largest values, we can easily find indices $$$j$$$ and $$$k$$$ through binary search, and maintaining a prefix sum array for these second largest allows us to easily compute the sum of the "new $$$start$$$ values" for the range $$$[j, k)$$$, where the new $$$start$$$ value should be the previously second largest values.
Oh wow, now it's clear. Thank you
What's the intuition behind choosing second[j] for searching?
For problem E, is there any optimal case where we need to consider the fact that after swapping an element, one of them is set to 0?
Can someone give the approach for C1?
Let's f(i) is the left-most index you can take when i is the right-most one, then f(i) >= f(i + 1).
Then, yeah, as we know, two pointers.
problem B in recent div 2 contests is being difficult for B div 2 problem
I didn't find it that hard
not anything is tough infront of baryon mode.
True XD
vote unrate
+1
I always wondered if MTBB (mean time between bricks) had a minimum bound... love getting closer to it, truly.
any idea what's the hack in B?
A lot of the hacked solves look similar and weirdly bad (to my brick-covered eyes, at least)... or they're good but messed up the indexing/bounds in some way that I'm not noticing with quick glances.
Hypothetically: weak pretests as anti-cheat would be an interesting and terrible choice...?
i went through a few hacked solutions and found people used gcd of first 2 > gcd of last 2 for all triplets which is an understandable mistake so i wouldnt conclude cheating immediately (altho im surprised it passed pretests)
about the anti cheat method, definitely sounds interesting but would need some good thinking to not make it brutal (as a sufferer of wayyy more fsts than id like)
Cheaters yet again, way too many C solves last second
how do you know it's cheating ?
YouTube videos are being leaked
Can we solve C2 without segtree?
Yes, I did it that way. Waiting to submit my solution though. BTW how to use segment tree for this? I did not find any way to update.
Yes, by using prefix sums. My submission: 175446833
I explained my approach in another comment above, because the code might be difficult to read otherwise.
huge difficulty gap after C1
Sadly, C2, D, E still too hard for me :((
Actually I think everyone had really good chances at solving Problem D, because if you have found the idea, the solution is pretty simple.
Group the numbers by pairs of 2 numbers.
Try to make each pair have both elements equal
We split the array in groups of 2 numbers. Groups with two equal elements we ignore. Groups with different elements we always chose one element in such a way, that it is alternating between 0's and 1's. If we rotate those, we will be surprised with a number like 11 00 00 11 11 00 00 11 11 00 11 11. It is easy to construct two equal subsequences, by choosing the first element of each pair.
I was very close :(
Eye opener. Was never gonna upsolve, but after seeing your post one more question done. Thanks!
Really cool idea!!! There should be one more condition to check after getting rotpos vector in your code that the size is even or odd to make sure the first and last elements are not same in the rotpos vector. i.e., if retpos size is odd then that means the first and last elements are same right? Is this condition required or this case won't happen? Could you please clarify on this. Lemme know if I'm missing something, Thankyou.
The amount will always be even. Assume it is odd. Then we have an odd number of 1's and 0's and no solution is possible, which we check beforehand.
Gave up after solving A,B,C1 and 30 minutes left. Suddenly with 10 minutes left, realized how to solve C2. Now waiting to submit it. Why do solutions strike at the last minute?
Biggest mistake -> did not see that the changes were temporary in C2
But your solution should still work (if there are no other errors)? Either you correct your solution, or you put in a dummy query after each one to reset the previous change.
Actually, I wasn't able to solve without temporary. After seeing temporary, some of the problems with a permanent change went away.
How to solve B normally?
b2 should be divisible by a1 and a2, so it is divisible by lcm(a1,a2). gcd(b1,b2)=a1, hence b1=a1. Proceeding similarly, you can have bi divisible by lcm(ai-1,ai), and bn+1 = an. For any bi not in [1,n+1], we have multiples of some number as possible inputs. You can convince yourself that taking the smallest one(that is the lcm itself) is most likely to produce a solution(taking a multiple, you only decrease the chances of gcd being whats specified). With this, you have a possible sequence bi. Just check its sanity and answer "YES" and "NO" accordingly. I hope this answers it.
I also guessed whether lcm is optimal, but I have a feeling that bigger choice spares more space for latter numbers. So that I didn't convince myself and get lost, try to find any pattern in $$$A_n$$$ is bad like "4,2,4" XD
I solved it by checking whether gcd(prev, after) divides curr or not.
If they do not for at least one number in A, then ans is No. Otherwise, yes.
Very nice observation, how did you came up with that approach?
Consider the problem for each prime number (usually useful in gcd/lcm problems)
Let $$$f_p(a)$$$ be the highest power of the prime $$$p$$$ that divides $$$a$$$. In the other words, if $$$a$$$ is divisible by $$$p^m$$$ and $$$a$$$ is not divisible by $$$p^{m+1}$$$, then $$$f_p(a)$$$ $$$=$$$ $$$m$$$.
Take any three consecutive numbers in $$$A$$$: $$$prev, curr, after$$$.
For the first two cases: $$$gcd(prev, after)$$$ divides $$$curr$$$, but this does not hold in the last case.
also the missing fourth possibility i.e when fp(prev)>=fp(curr)>=fp(after)=> okay (8,4,2)
С2 and D are too hard for normal C2 and D. And I think it`s not normal that C2 is harder than D
I don't think D is too hard, tbh. Once you realize that it's redundant for the cyclic shifts to leave any bits unchanged, i.e., there is always an optimal answer where the cyclic shift will flip all bits of the subsequence or there is no answer, then I think the solution becomes really obvious after that.
I agree that it's easier than C2, but there isn't much that could be done about that, since it wouldn't make sense to have it before C1 (since it's still harder than C1) nor should C1 and C2 be separated. I suppose it may have helped to give C2 a slightly higher score than D, to encourage participants to check D before trying C2.
Huge gap after C1, but otherwise nice contest.
Solution for C1 without two pointers or segment tree https://codeforces.me/contest/1736/submission/175446774
Could AnyBody Explain What's the logic begin taking LCM of two adjacent no and storing in another array and checking the GCD of two adjacent elements form diffrent array in Problem B and What's the logic being Problem C Because I am not figure out properly where is my test case failing and why
Since $$$a_2 = gcd(b_2, b_3)$$$, both $$$b_2$$$ and $$$b_3$$$ has to be divisible by $$$a_2$$$
Similarly both $$$b_3$$$ and $$$b_4$$$ has to be divisible by $$$a_3$$$
So the common element which has to be divisible by both $$$a_2$$$ and $$$a_3$$$ is $$$b_3$$$
That's why $$$b_3 = lcm(a_2, a_3)$$$
Now that you have $$$b_3$$$ just check if $$$gcd(b_2, b_3)$$$ is equal to $$$a_2$$$ or not. If it is not then answer is "no". Otherwise continue till $$$n$$$
Check out my precise solutions for A,B and C1: A: 175371876 B: 175384691 C1: 175422140
What Your Logic for Problem B and C1
Take an example a = {4,2,4}. Let the array b={b1,b2,b3,b4}. since gcd(b1,b2)=4, b2 is a multiple of 4 and since gcd(b3,b4)=4, b3 is a multiple of 4. Therefore the greatest common divisor of b2 and b3 will be a multiple of gcd(4,4)=4 (i.e. a[i] must be a multiple of gcd(a[i-1],a[i+1])). We cannot construct the array when it is not a multiple.
(sorry for any language mistakes :))
looks like the discord/telegram master copy fails on test case 11.
I feel second example for E was way too informative
I would've probably got 2 wrong submissions if not for it, and rightly so.
good contest!!!
When the ratings will be updated?
I loved problem E. Nice one!
Any hints, please? ^-^
Let's consider that $$$x_1$$$, $$$x_2$$$, $$$...$$$ $$$x_n$$$ are the scores that are added to your final score at each moment. Try to prove that for each $$$i$$$, $$$x_i \ne 0$$$, and also try to find some relationship between $$$x_i$$$-s.
the problem was clear and intersting thank you for the contest <3
Don't want to be too offensive, but check out wildfire032's submissions) (he is rank 13 right now in the standings) He has two different code styles for the problems A, B, and C1 compared to C2 and E. Moreover, he must have a legendary grandmaster mindset to switch problems from A, B to E and then back to C1 and C2)0)
You are so offensive, but I like it.
Well, they certainly didn't copy problem E, given that they got first solve on that problem. (3 minutes before 2nd solve and 23 minutes before 3rd solve!) Though it does seem a bit ridiculously fast, since unlike wildfire032, the 2nd and 3rd solves did not solve A and B first and they are very high ranked.
Someone might have leaked the problem with solution before the start of the contest.
I don't think so. This problem is too easy to be solved in 7 mins. It may be that somebody told him that the E problem is easy and he came to solve it.
Then, I guess, there were two people submitting from this account, one started form A and the other from E.
You are so offensive, but I like it.
For D, can someone find what's wrong here 175460824? I first create vectors v0 and v1 which store indices j where s[j]='0' and s[j]='1' respectively. My subsequence p is basically all the indices present at even positions in vectors v0 and v1 in sorted order and subsequence q is the remaining indices in sorted order. Subsequence b is all the indices j where s[p[j]]!=s[q[j]]. It fails in test 190.
Take a look at Ticket 16278 from CF Stress for a counter example.
Thanks!
I think D was not too hard. It will be of rating 1600 approx.
It can be solved by simple observation, that are:-
1) If the no. of ones are odd then answer is -1.
2) Simply divide the array in two subsequences, as per your choice. I personally have divided the array in two subsequences on the basis of parity (i.e. odd and even index)
3) Now, see if the ith index of subsequence (i.e. 2*i and 2*i+1 index of original array) are same then we can just ignore that. else you can store these pairs of index in some temporary vector.
4) You will notice that the size of that temporary array is even (because statement (1) is false).
5) Now for every "two" pair of the vector choose one '0'th index form pair 1 and '1'th index from pair 2.
6) You can notice that after the operation of right shift, all the bits will flip as the size of the array will even always. Ex- 01 01 01 -> 10 10 10.
7) In short, every two pair in temporary vector will satisfy there requirements.
8) example- Lets say pair1(1,0) and pair2(1,0) you take 0'th from pair1 and 1'th from pair2. and apply the operation then the pairs will become pair1(1,1) and pair2(0,0) and that's what we need. "NOTE- Store index in the pairs." I have used 0 or 1 for better understanding.
8) And we get our desired answer.
You can take some reference from my code :) My submission id- https://codeforces.me/contest/1736/submission/175419375
Thanks for reading it, hope this would help.
Happy coding :)
Why downvoting this?
Maybe I am unable to make them understand my solution :')
I don't think you can just choose any subsequence pair. Even and odd index works correctly, and is also what I used, because both bits in the same position of the two subsequences appear before all bits in later positions. So for each mismatching position, you can alternate between turning the 0 into a 1 and turning the 1 into a 0. Applying the cyclic shift on a subsequence where the bits alternate (consecutive bits don't match) is equivalent to flipping them all. My submission: 175422432 (note: pz means picking the 0 to add to the cyclic shift)
But if you tried to construct the subsequences differently, e.g., first half and second half, then it doesn't work. For example, consider 00001111. If you tried to match first half with second half, then there must be at least one half with 2+ indices being chosen for flipping, but then the shifting subsequence would have consecutive elements of the same bit, so the cyclic shift would NOT be equivalent to bit flipping.
Yes you are right
How were you able to think of this construction?
Where is editorial
I wonder too (cry
I think for problem c1, the answer of third test case should be 2. Can anyone explain why is it 7?
Read Problem again , for every new subarray of any size indexing will be according to new one not according to Initial Array .like one of subaarray [1,4,3] of size three is valid as per question.Hope you understand.
thank you!!!! very good and balanced contest!!! ily
175519849.Based on this submission result, i can find out whether for gcd(b[i],b[i + 1]) < a[i] I must be able to construct bi that satisfies this condition? How do you prove it?
I get it. There's no such thing. I was stupid。
My CM dream come true thanks satyam343 , mtw and naman1601
shuanq