UPD: The start time has been changed. Note that the start time is unusual.
Hi Codeforces!
Bazoka13, Toxel, and I Serval are glad to invite everyone to participate in Codeforces Round 853 (Div. 2), which will be held on Feb/25/2023 17:20 (Moscow time).
This round will be rated for participants with rating lower than 2100. We will be glad to see the participants with a higher rating to take part in our round unofficially as well!
You will be given 6 problems to solve in 2 hours. Scoring distribution will be announced later.
We would like to thank everyone that makes this round possible:
- Artyom123 for coordination of the round and help with the preparation.
- SSerxhs, skywalkert, zlc1114, foreverlasting, tiger2005, OMG_link, fried-chicken, tibinyte, _Viole_, qxforever, sleep__, valeriu, Nanako, HomuraCat, AntiLeaf, rsj, tyakennikku, qsmcgogo, Lanly, Dominater069, GGN_2015, Kumiko, StudyingFather, ClearQwQ and Ben_H for testing the round and providing valuable feedbacks.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
- You, for participating in the round.
Good luck & Have fun! :P
UPD2: Scoring distribution: 500 — 1000 — 1250 — 1750 — 2000 — 2750.
UPD3: Editorial is out. Thanks for your participation!
Congratulations to the winners!
Overall:
Div. 2:
As an author, the problems are very interesting. I wish everyone could enjoy this round and have good luck!
I respect the authors!
MakaPakka orz!..
MakaPakka orz!..
MakaPakka orz!..
MakaPakka orz!..
MakaPakka is shining, thank to MakaPakka!
MakaPakka orz!..
MakaPakka orz!..
MakaPakka orz!..
As participantes we hope the problems have short and clear statements :)
--DELETED--
You should know that codeforces contest >>>>>>>>>>>>>>>> any class. And you are already writing decent english i think you can easily skip one class. xD.
As an author, I hope you enjoy this round!
Hope to get positive delta this time. ALL the best guys!
This will be my "birthday-contest"✔️
As a tester, I hope you will enjoy the round! The problems are very interesting and educational. Good luck for everyone!
oh look who I have caught!
As a tester, I witness the great effort made by authors to make this round better. The problemset in fact changed a lot compared to the very beginning version and I believe the current version is worth participating.
As a tester, I encourage everyone to participate!
good luck QwQ
qcjj!
I hope this contest will help us to learn new things. wish everybody a good contest :)
Wish I could participate but I don't have time. I hope I can enjoy upsolving the problems!
As a chinese university student,I wish the constest be successful.
Hope this is my CM promotion contest !
Hope this is my E promotion contest!
You became an expert before me reaching CM! :(
I hope you will enjoy these interesting problems. Good luck to you!
Hey could i get some likes to remove negative contribution.
Well, just completed with implementation and basic questions of trie data structure, and I have already completed bst. Now that I have another tool in my toolkit, hoping to solve more questions this time.
I don't know if you're talking seriously but if you are trie won't get you to pupil
I never aimed for the pupil rank, at least not until I finished the basics of DSA. Earlier, I learned about stack, queue, and linked list, but they weren't useful for contests. So unknowingly, I got the assumption that maybe trees and graphs are more useful for contests. Anyhow, learning a new data structure opens up more ways to approach a problem, and even if I can't solve more questions, it is still valuable.
We will be glad to see you making your tries to solve our Bazoka13 & Serval & Toxel problems. :P
As a tester, I hope that all the participants could enjoy the contest! Good luck & have fun! I'm more than excited to say that it's the first time I took part in the management of a CodeForces contest. Thanks Serval for inviting me! QwQ
By the way, Arcaea is a nice rhythm game. You should try it!
Do you mean that there will be some problems related to Arcaea in this contest? :)
You'll see :P
What do the cases of problem E mean?
1: 1 2 4 -> ok that's simple
2: 1279 -> notes of Fracture Ray FTR
3: 344208 591000 4779956 5403429 -> scores which can be reached during Tempestissimo Beyond 11
4: 1633 1661 1741 2134 2221 -> notes of the 5 hidden songs in Arcaea 4.0, in Beyond difficulty.
Also, the calculation formula of problem E was adapted from Arcaea's MAX-Pure system.
Another Chinese Round :) Will it be hard?
Hope I can get back to expert :)
Edit: I appreciated the Paldea reference in C, but problem D is just way too hard.
I hope after this round I will stop being a prisoner of the blue
If you dont become a specialist, you will deserve a lot of dislikes.
Great perfomance in this round from you!
Does anyone know the reason for the contest time change?
I want to enjoy this contest together!
I hope I'll be able to solve problem C, Glad to learn new tips & trick apart from Practice & consistency
Hoping for a quality contest!
which is better starting with B to A or vice versa ?
D to F
Why the unusual time?
Thanks for 3 problems contest.
Please correct the blog.
You will be given 3 problems to solve in 2 hours.
Why is an O(m+n) solution giving TLE for problem C??
Read rules of participation and don't post anything about contest when contest is going on
you make a loop from 1 to 4e5 also number of testcaces is 2000. so u make 8e8 operations which is too large (8 seconds i guess)
Wonderful. But I think you meant Div 1 not 2.
Honestly, I dont think testers tested this round.
I know how to do D with $$$n + 1$$$ operators but with $$$n$$$ operators I can't. :DD
Easyforces, but tasks are still cool!
DEF are hard
How to solve E?
How solve D?
Let's define $$$a[x]$$$ as the $$$x$$$-th digit of $$$a$$$, started from zero. Also, a position $$$i$$$ is matched if and only if $$$a[i]=b[i]$$$.
Step 1: check if $$$b=0$$$. It's known that when $$$b=0$$$, the answer will only be
0or-1. Also check if $$$a=0$$$.Step 2: let $$$k = \lfloor \log b \rfloor$$$, make $$$a[0...k]$$$ the same as $$$b[0...k]$$$. As $$$a$$$ is not zero, you can move the highest
1of $$$a$$$ to the highest unmatched position $$$i$$$ such that $$$i \leq k$$$, and after the XOR operation, the position $$$i$$$ is matched. This might takes at most $$$k+1$$$ operation(s).Step 3: make $$$a[k+1...n-1]$$$ equal to zero. This time we can move the lowest digit of $$$a$$$ to the lowest unmatched position $$$j$$$ such that $$$j > k$$$, and after the XOR operation, the position $$$j$$$ is matched. This might takes at most $$$n-1-k$$$ operation(s).
Finally, you get the solution with at most $$$n$$$ operation(s).
Excuse me I'm a bit confused, what is complexity of this? I think i read once it was O(n) but my and offical solution is O(n^2).
There are at most $$$n$$$ operation(s), and in each operation, you need to simulate the XOR process, which takes $$$O(n)$$$ operations either, so the complexity is $$$O(n^2)$$$.
This contest gives me some Chinese amazing!
Translate: We will give them some little Chinese amazing
This round is 6 stages of grief
Can Anyone help how to solve C problem?
HINT-> Just think of how much a number from range 1->n+m would contribe to the answer.
It was a really cool question just try to solve it using this HINT if you still can't solve see the editorial as it would be available soon I guess.
Hope you solve the question by seeing the hint yourself :)
Just think in terms of contribution of each value when u form pairs. we need to know in how many arrays out of m+1 total , does a particular value occur. Then apply simple PnC for the arrays it appears in and for the arrays it doesn't appear in
WHY is TL on E so tight???
Edit: It turns out that my solution could be greatly optimized. It got AC in 1.7sec.
Edit2: My slow solution without optimizations works in under 3s. If the authors set TL to 4s, it would pass...
maybe O(S)
Maybe. But I think I saw some other $$$O(s_n*ln(s_n))$$$ solutions which passed.
Try to avoid multiple long arrays. Due to the memory system, the pointer transferring would be slow if so.
Yeah. I have already optimized my code(by avoiding useless calculations). Anyways it's a little bit sad:(
https://codeforces.net/contest/1789/submission/194977514
Here's my solution when testing the round, which runs below 1.5 seconds per test. Actually, as I use
Z(modulo class), it should be slower than usual.D is too hard,why
How to solve E? I've thought long and hard about how to optimize the complexity of my approach,which was $$$O(n \sqrt{s_n})$$$
Mine $$$O(s_n*ln(s_n))$$$ solution got TLE 5....
ABC were good problems overall.
I just feel a bit dumb for missunderstanding C and solving it when you concatenate Ai, A(i+1)...Aj...
It is a pretty interesting problem though
please explain your approach
For which problem ? The missunderstood version or the C?
not the misunderstood
also please explain this part of the problem the number of distinct elements of the concatenation of Ai _ and Aj_
OK so basically, let's consider the contribution each integer gives to the answer.
Let's consider a pair (i,j) and an integer x. For x to contribute +1 to the value of (i,j), x must be in Ai or Aj. So you will first need to find, for each integer, the number of array it is in (you can do this by simply simulating the process and remembering at what point in time you last added the integer in the array).
Then for each integer, either you chose (i,j) such that x is in Ai and Aj, either you chose (i,j) such that x is in Ai and not in Aj (or in Aj and not in Ai).
Code: 194973423
Let me know if something is unclear
Edit: so for what you've asked, it means that you consider an array B(i,j) consisting of the integers of Ai and Aj and you then consider the number of distinct integers in this array B(i,j)
wait, wasn’t it the point of the C problem? Or am I misunderstanding it too
Nop. In C you consider the concatenation of Ai and Aj only, not of Ai, A(i+1)...till Aj.
Worst contest I have ever seen. I could not see the update in the start time :( (But problems were good.)
Div2 problems: A-B-C- E -E-F
read "not need to minimize the number of operations"
did not read "no more than n operations"
sadge :(
cp is hard
people from rank 200 to 2000 (in official standings) solved only three problems. problem set in unbalanced.
Indeed. I would've risen by at least 100 rankings if I had solved C a half hour earlier (I solved it towards the very end)
A very hard contest..
My solution to E was very cancerous and prone to random errors (no idea). My solution works in $$$\mathcal O(s_n \log s_n + n)$$$ per test case with somewhat large constant factors (there are a couple of linear passes). Is there a faster solution? I didn't find a way to reduce to $$$s_n \log n$$$. You could always precompute sieve earlier instead of doing it implicitly in the computation from $$$x = 1$$$ to $$$s_n$$$ but I for some reason thought it would to be too slow and wouldn't work. In particular, I feel like $$$s_n$$$ plays a very big role in deciding the complexity, $$$n$$$ doesn't even matter. Is it possible to get $$$s_n \log \log s_n$$$?
[EDIT: OKAY, it passed at 1200ms, so I guess $$$s_n \log s_n$$$ implemented with a somewhat not large constant factor does pass.]
Again I'm Unable to solve problem C ಠ╭╮ಠ feeling sad,but I'll not give up Let's see how long it will take.
By the way problem C is very good.
How to solve D
worst D ever
If I've consumed 10 minutes less on problem D, I could have solved E. So unfortunate!
TLE5 say hello friend
What you do in years, I do in a day. We are not the same.
Can anyone please explain what is pi and qi in problem E?
It doesn't matter at all, this is a hint:
Separate the question into two parts:
I finally understood the problem statement. It could have been formulated in a much better way (f(x) is defined as the number of i (1 <= i <= n) for which there exists at least one pair of non-negative integers x and y that satisfy si = x * .. + y * ..).
i think you should find more candidate master, expert, specialist, pupil and newbie to test the round, instead of most of the testers' rating are > 2100.
Agree
how testers are found is : they make a announcement in the cf testing discord server
And since, there is a direct correspondence with interest and strength, the testers are more likely to be higher rated.
If a lower rated guy asked to test, he would be allowed to. Coordinators cant really go around Dming random people.
:C
Am I correct to think that D is in fact just super easy construction?
When I look at the problem D today(I didn't participate yesterday), I think it's no harder than before, or even easier than common D.
This is how I solved F
The solution is the same as the writer's one. Congratulations!
But I noticed that there are some solutions with <100ms time limit, and I'm curious about it.
194988517 this one runs in 171ms.
We can just try all subsets of $$$|S|/5$$$ size partitions of S, we do not need $$$|S|-|S|/5$$$ partitions, slightly non-trivial observation but it can be proved via pigeonhole principle.
ok I know why. During the calculation of LCS3, a small trick is used: when the last digits of the first 2 parts of the string are not the same, then the case is not optimized and we can pass it. By carefully arranging the condition order, it could be fast.
that's a cool solution and quite easy to understand, thanks for sharing
For D, is't there an O(n) solution?
How to solve E, when sn % x != 0.
I think I got the problem down to counting numbers from the array that are in ranges of the form $$$\left[ k \cdot \lfloor \frac{s_n}{x} \rfloor, k \cdot \lfloor \frac{s_n}{x} \rfloor + k \right]$$$ for any $$$k$$$. I believe this should be $$$O(s_n \cdot \log{s_n})$$$ if done correctly, but I got TLE.
Your solution is correct. Maybe you need to speed up your implementation.
It's quite simple when $$$x \mid s_{n}$$$. Let see how to count the answer when $$$x \nmid s_{n}$$$.
Define $$$\lfloor \dfrac{s_{n}}{x} \rfloor = K$$$, we have: $$$s_{i} = p_{i}\times K + q_{i} \times (K+1) = (p_{i} + q_{i}) \times K + q_{i}$$$.
Thus, $$$s_{i}$$$ satisfy the equation if and only if $$$\lfloor \frac{s_{i}}{K} \rfloor \geq s_{i} \operatorname{mod} K$$$. As $$$\lfloor \frac{s_{i}}{K} \rfloor$$$ can be large, but $$$s_{i} \operatorname{mod} K < K$$$, let's count the number of invalid $$$s_{i}$$$ instead.
Enumerate $$$K$$$, then for $$$\lfloor \frac{s_{i}}{K} \rfloor = C$$$, we have $$$C < s_{i} \operatorname{mod} K < K$$$, so the invalid numbers form a range, and we can calculate it quickly by preparing the prefix sum of the count array of $$$s_{i}$$$. After calculating the number of valid $$${s_{i}}$$$, as all possible $$$x$$$ here also form a range, we can calculate $$$\sum x$$$ easily, and get the contribution when $$$\lfloor \dfrac{s_{n}}{x} \rfloor = K$$$.
For each $$$K$$$, we need to run $$$O(K)$$$ operations. Preparing the prefix sum takes $$$O(n + s_{n})$$$ operations. As $$$\sum K \leq \sum_{i=1}^{\sqrt{s_{n}}} \dfrac{s_{n}}{i} + \sum_{i=1}^{\sqrt{s_{n}}}i \leq s_{n} \log s_{n} + 2 \times s_{n}$$$, we can say that the solution is $$$O(n + s_{n} \log s_{n})$$$, which is enough to pass the problem.
I stucked at A for an hour just because I thought that O(T*N^2) will result TLE...turns out that it don't
A good heuristic is that you can do about 1e9 operations per second, so O(T * N * N), which would result in max 500 * 100 * 100 = 5e6, will easily pass. This can often be helpful when thinking about time complexities :)
So we can actually run a for loop from 1 to 10^9 in a contest with TLE?? Something new learned. Thanks
10% situations that u can do it with pragma
90% is usually 1e8
What Tima9 said and also depends on what and how many O(1) operations you do inside the for-loop.
You should also keep in mind that finding gcd takes O(log n) operations, so, in the worst case, it is 500*100*100*20 = 1e8, which, as for me, is a bit too much for the first problem
screencast with commentary
Also nice problem F. But gifting arrays is cancer.
Any hints for D apart from the "obvious" observation below?
Left $$$k$$$ shifts leave the right $$$k$$$ elements unchanged, right $$$k$$$ shifts leave the left $$$k$$$ elements unchanged...
Explanation for D:
If a and b are both all-zero, we don't need any operation. If a is all-zero, we can't change a by operation, so if b is not all-zero, there's no solution. Also if b is all-zero but a is not, there's no solution because shift(a, k) must be different from a since k!=0, so a^shift(a, k) can't be zero. Therefore, we can assume there are some 1 in a and b.
Let min_a = the minimum position that a[pos]=1, min_b = the mininum position that b[pos]=1. We solve the problem by different situations:
--min_a<min_b. If we right-shift by k, we will flip a[min_a+k] and leave a[1...min_a+k-1] unchanged, so we can use right-shift (n-min_a) times to make a and b same on range [min_a+1, n]. Then let max_a = the maximum position that a[pos]=1. because min_a<min_b, we have max_a>min_a, so we can use left-shift min_a times to make a and b same on range [1, min_a].
--min_a==min_b. We still can let a[min_a+1...n]==b[min_a+1...n] first. Because min_a==min_b, we have a[min_a]==b[min_a]==1, so we can use left-shift (min_a-1) times to let a[1...min_a-1]==b[1...min_a-1].
--min_a>min_b. Now we need to left-shift a[max_a] to make a[1...max_a-1]==b[1...max_a-1], and then right-shift a[min_a] to make a[max_a...n]==b[max_a...n].
Explanation for E:
First, we find maximal blocks [l, r] such that floor(s[n]/x) is same for x in range [l, r]. Let a=floor(s[n]/l), then for x in [l, r-1], we have ceil(s[n]/x)=a+1. Let's check how many s[i] can be represented as sum of several a and (a+1). In fact, only numbers in these ranges satisfy the condition: [a, a+1], [2*a, 2*a+2], [3*a, 3*a+3], ..., [(a-1)*a, (a-1)*a+(a-1)], [a*a, s[n]]. We can use prefix-sum to count them, and multiply it by sum[l, r-1]=(l+r-1)*(r-l)/2. Then for x==r, if ceil(s[n]/r)=a+1, we just change sum[l, r-1] to sum[l, r]. If ceil(s[n]/r)=a, we need to check how many s[i] can be represented as sum of a: we just need to check all multiples of a. (My upsolve submission for E: 194975227)
When can we expect rating changes to occur?
great F
Why can you come up with problem E during playing music games? Is there any story-like problem statement?
yaa , problems are really good
It seems that the difficulties of some constructive problems like D are often underestimated.
What is the edge case in problem D that gives this many fst??
The data of question C is weak. Someone
memsetin every test case and he got accepted.memsetfor the array with a length of 400000. It's wrong at all.It's normal, even though
memsetis $$$\mathcal{O}(n)$$$ in theory, it's very fast in practice. Doing $$$t = 10^4$$$ memset over array of length $$$n = 2 \cdot 10^5$$$ is fast enough.I know. I used to be able to hack such code, so I usually thought the data was not strong enough. If the data is very strong and can't hack it, then I'm sorry for my excited remarks.
Started the contest late because you thought it will start at 20:05(IST) gang:(
I started at 20:00 IST, 10 mins late
me frfr
You can find the editorial video for the problem C on my channel.
Problem C: https://www.youtube.com/watch?v=7nYE42FZzN4
wishing positive deltas to everyone :)
What is the expected rating for C?
1500 or 1600
Вопрос по задаче А. Что я не так делаю? Отсортировал массив, нашел для всех префиксов ноды. Потом иду по массиву нодов и смотрю если нод больше длины, то ответ нет. Если для всего массива условие выполняется то ответ да. Конкретно на примере: есть массив 1 4 2 6 сортирую его получается массив 1 2 4 6 для его строю массив нодов 1 1 1 1. Каждый текущий нод меньше текущей длины значит массив хороший. Может кто подскажет контрпример. Вылетает на 231 тесте, а его невидно.
Непонятно, зачем тут нужно сортировка? Ты же понимаешь, что у тебя для 7 14 15 будет ответ "no", а если переставить как 7 15 14 то будет "yes"
7 14 15 нод 7 и 14 равен 7 и это больше двух значит массив плохой. Я ещё проверяю и для реверсированого массива 15 14 7 здесь ноды 1 1 1. И это ответ yes
Ладно, я привел плохой пример, но понятно что нет причины сортировать числа.
То если Вас не затруднит объясните принцип решения задачи. Спасибо. Почему все берут нод двух элементов массива и проверяют чтоб он был меньше или равен двум. Спасибо.
если есть пара с нодом <= 2, то ставим ее в начало, тогда нод на любом префикс <= 2, победа. иначе, какие-бы мы два числа на первое место не поставили, условие ломается для префикса длины два
7 14 15 20
How are you supposed to find the solution of problems such as C in a reasonable amount of time? I participated in a lot of contests (this is a new account), and my weakest point has always been spotting these small "tricks" and "observations" that these problems require in order to be solved.
Before saying the "duuh, just practice!", I want to say that I tried practicing a lot, trying to understand the solution of the problems and the whole process of finding it, but for me it's still so hard to see the solutions of problems like these.
I couldn't find it during contest, it took me like 2 hours after that to see the solution is that you must know at the end how many times does each element appear throughout the whole transformations over all arrays, and from that you can calculate the solution. But the thing is, I just stumbled upon this randomly, because I tried different ideas that didn't work, it wasn't because there was some heavy thought to it. I find it frustrating that after years of trying (again, this is a new account, I used to be 'expert' rating) sometimes I can't even solve C problems, while other participants who are newer to this just finish it in like 20-30 mins (or even less).
Am I too stupid for this?
As a CM, I even couldn't solve some problems between B-D for several times (and that's why I've dropped from master). I think everyone will perform badly at some times, so cheer up please.
Man I feel this so much, and honestly, I don't know any better advice than to practice more and don't look at tutorials :/
The trick is to break down the problem, first into any solution then optimize it. Here, I will perform it on problem C.
We need to transform into a palindrome, right? We need to change a segment so that our thing becomes a palindrome. Obviously, we could just check every possible change in O(n^3) complexity but that's too slow. Here, we can make use of something that we know — the symmetry. A palindrome is, by definition, symmetrical so we can notice that changing the same segment in the first half or its mirrored counterpart in the other is virtually the same for the purpose of the solution. That also means that we will only ever change something on one of the halves (because if we were to start our segment in the first half and end somewhere in the second one, we might just as well not change the middle parts and reduce the operation to changing only in one half. So here we are, we reduced it only to a half. What does that mean? That means that we need to change every single bit that isn't equal to the mirrored counterpart in the other half. Now, when is that possible? When all of those form a single segment and checking that is really easy.
That's B, not C
oh, ye, my bad
Anyways, for C then. Obviously, we can just try and merge every 2 arrays and count the distinct numbers but the complexity would be O(n^2 * m) which we cannot afford. Even if we had a magical box that would merge arrays in O(1), we would still have an O(nm) solution. That means that we need a much different approach than testing all combinations. We can see that the arrays change by one number at a time and for every number that appears during the whole thing we can denote when it appears and disappears (we can do that as numbers are pairwise distinct). Using that information, we can see in how many arrays the number appears. That allows us to count the score for each number (there are max n + m distinct numbers) and then conunting in how many combinations the number appears (that's just combinatronics, you can do it many ways)
the general idea is that you try and find every single, even useless consistency you can and note them down until you find something that is useful
Well, you just move from one idea to another until it works
Had 6 WA's because I missed one return statement :(
Anyways, got AC on D 2 min before the contest ends :)
It's good to be cyan :)
Ratings updated preliminary, it will be recalculated after removing the cheaters.
became cyan today!!
O-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I-E-A- JO-ooo-oo-oo-oo EEEEO-A-AAA-AAAA
Can someone please explain why these 2 solution differ only in one operation that is theoretically the same in both cases but one gives wrong answer ?
correct one: https://codeforces.net/contest/1789/submission/194991180
wrong one: https://codeforces.net/contest/1789/submission/194991257
ps: the difference is where I initialized ans
Your wrong one has parenthesis around ((m + 1) * m), which evaluates the inside first using 32-bit integer, and hence it overflowed. Your correct one evaluates from left to right and using 64-bit integers, which will not overflow.
Thank you very very much!!! So if I understand correctly if I will always write like that : 1ll * (int variable from expresion) it should always work ?
Yes, or you can just use long long for all your variables, because usually you would have enough memory to do so.
For problem D, I use boost/dynamic bitset to allocate dynamic size. But it's not accepting on cf compiler. What can I do? Here is my code https://codeforces.net/contest/1789/submission/197297649