Hello!
On Apr/27/2023 17:35 (Moscow time) we will host Codeforces Round 868 (Div. 2).
The problems were written and prepared by Igor_Parfenov.
I would like to thank everyone who made this round possible:
- awoo, madlogic, _Israel_, Vectors_Master, BabaVoss, AlperenT, FzArK, Dominater069, m0t9_, rui_er, aryan12, purp4ever, MaherSefo, Shawerma, maomao90, satyam343, errorgorn, Glemhel for testing the round and providing feedback to the problems
- adedalic, for coordination of the round
- MikeMirzayanov, for Codeforces and Polygon platforms
- All participants
This round will be rated for participants with rating lower than 2100.
You will have 2 hours to solve 6 problems.
Score distribution: 500 — 1000 — 1250 — 2000 — 2000 — 2500.
Good luck!
UPD: Editorial
UPD: Congratulations to the Winners!
Div.2:
Div.1 + Div.2:
As a tester, Igor_Parfenov did his best to make sure the round is balanced and interesting. Hope you enjoy.
Your work is worthy of respect! Thank you very much for the contest!
Igor_Parfenov orz!!!
As a tester, I shall farm contribution.
PS: Hope you like the round and wish you positive rating :D
As a tester, I would recommend that you don't name yourself purp4ever, thinking that you'll be a Dominater069 of the candidates and then become an expert because your friends FzArK and MaherSefo will say awoo and make fun of ywooo. Then you would eat Shawerma out of sadness.
I know this is madlogic
As a first-time tester, I am jealous of purp4ever's as a tester skills as I can't come up with such as a tester comment (
testers are cool
Probably the GOAT of as a tester comments?
As a tester, I can't come up with any as a tester comment to post after reading this...
Thank you
Probably the shortest codeforces round announcement blog i have seen in a while
Edit: My bad I apparently can't calculate dates correctly.
Not right now it isn't.
I am unrated as I joined codeforces few days ago . I am thinking of participating in this contest . So Will I get rated after competing in this contest , or there are some conditions like you have to participate in 4-5 contests to get rated ? Please do answer .. It might be helpful for other new participants as well .
Yes, you will get rated after participating in your first contest. All the best!
Hope the problem statements would be as small as the blog :)
Yes, Plz stop making IELTS reading tests on CF, this decreases your social credit!!!
I couldn't come up with as a tester comment, that's why I don't have the right to write as a tester at the beginning of my comment.
Igor_Parfenov Orz
As a Green tester,
good luck
You too
As a gray participant, i'm not sure
A very streamlined competition announcement
"I would like to thank everyone who made this round possible"
"who" should be "that"
Wrong. In English the relative pronoun "who" is used when referring to people and "that" is used when referring to things.
now there are a problem in the server, all submissions stack in the queue, please fix it we do not want unrated contest
score distribution?
How far is purple?
Sure enough, I got further away from purple。。
It's surely not today. (sad...
There are so many submission still in queue, I'm really worried about getting stuck in the contest tonight.
Then you must call stepbro to get you unstuck from the contest.
Good Luck for all participants
The difference between C and D is massive.
See it this way:- D and E are of same points.
I will be a pupil in this night! Good Luck for everyone.
good luck
madlogic wrote As a tester, Igor_Parfenov did his best to make sure the round is balanced and interesting. Is this contest really balanced after this score distibution?
We'll see
We saw, it was unbalanced
Spoiler alert, it wasn't
NOT BALANCED ROUND AT ALL...
Since D and E are same points, I was hoping they would be of same difficulties. They are not... I started with E problem wasted more than 1 hour on that.
Have you solved D? If not, what leads you to believe it's easier than E?
I skipped D after a few minutes because I had no ideas on how to solve it, and was able to solve E.
Hope no queueforces
I wish to become an expert after this contest, please say good luck to me, thanks.
tough to get +200
Do I get some penalty for Unsuccessful hacking attempt?
Do I get some reward for Successful hacking attempt?
Yes, -50, it's written on the right side.
Thank you.
Is it me or anyone else also feels that this contest was a bit tough?
A was a bit tough than usual?
and it reduced the number of participants
Number of registrations were also low. It was around 15k only.
Yes i also felt that A was tough.
guess you tried to solve a univariate quadratic equation. actually you can just enumerate the number of $$$1$$$ because $$$n$$$ is quite small.
Your submission time between problem A and problem B is suspicious. Did you wait to submit both problem at the same time
i forgot to register, and saving A
I am convinced, not guilty!
thx, UwU
What's even funnier about this meme here is that the standard approach to solving D involves abusing a repeating sequence of "abc" (with runs of unique letters sprinkled in between).
I will probably miss the chance of becoming CM because blind me couldn't see 1e7 * 1e7 * .... * 1e7(1000 times) isn't 1e10
How did I do this exact same mistake lol
Guess it's been too long since we last multiplied
I think it's not good to comment this 15 minutes before the contest ends as others might doing the same mistake.
Yeah sorry my bad... It just completely slipped out of my mind!
This mistake costed me a lot of time :(
3 penalties man...
contest is running bruh :/
F my bad... but I doubt it'll help anyone since I didn't mention any question or something
Thank you for 5 math tasks and constructive D
For me, A was tougher than B and C.
Me too
Yep the key Idea for A is harder to catch than it is for B & C, B was simplified because of it being a permutation but still sad contest :(
Fantastic problem E. (Hint Sprague-Grandy function)
How did you find the sprague-grundy function ? I think there are edge-cases with l = 1 but i'm not sure ...
There are two different grundy values you need to calculate.
The first one is the initial condition (it's a cycle), so it will become a single path. The second one is a path, it can be divided into two paths.
Bruteforce them, and you will get a really nice table.
Submission to E Can somebody check where I got wrong? Wrong answer on test case 9
Am i true that it is Sprague-Grandy function? Mine was:
when i < l
when l<= i <=r+l-1
when r+l<=i
Taking %(r+l) yours solution becomes wrong. This pattern is easy to find if you look at the first for example 1000 sg[i], for O(n^2)
Yeah, that is the Sprague-Grandy fucntion
The explicit i < l case is not necessary
Of course Yes, i see it only after AC submission:)
Take a look at Ticket 16853 from CF Stress for a counter example.
Alice goes first, takes 1 out. Now Bob is left with {2,3,4}, if he removes one of them say 2, then Alice has got {3,4} which he removes in one go and wins. If Bob removes two of them say 2 and 3, then Alice has got {4}, removes at once and wins. Feeling dumb, what's wrong.
You're almost there. After Alice removes vertex 1, we have an L shaped graph. What happens when Bob removes the connecting point of both the perpendicular lines. Would that break the graph and force Alice to pick exactly 1 vertex in the next move?
Right. Missed that case, thanks for the effort!
I kept getting TLE on C, probably some stupid mistake, can someone give a brief solution of C?
You are creating an array of size $$$si$$$ each test case, you could just use
std::map.Please explain D
one thing to know that, n length string can produce max n palindrome.Now suppose u need 3 palindrome on a segment, then can simply print aaa.. you have to just maintain no different segment disturb others.. so take 1st 3 char abc and when you don't need more palindrome on that segment use abc cyclicly nullify extra one.
suppose on a segment, need 4 palindrome in 10 length string then u can print:
abc c abcab [3rd part for nullify]
And when x[i]<c[i] No [x[i] len string can make max x[i] palindrome]
also (x[i]-x[i-1])<(c[i]-c[i-1]) No [for same reason]
adding to this, use new character for every query. There are max 20 queries, so we can use all 26 letters of alphabet. To create new palindromes, use new character, to not create new ones, use the used ones. This can be done in O(n) time.
I was solving quadratic equation for A without seeing n <= 100 !!!
I learnt to read constraints carefully in this contest :( they can cost so much time.
Can anyone explain the logic behind C
We want the product of ai ... an to be equal to bi ... bn, Therefore their total prime factorisation should be the same (the prime factorisation of the product from ai to an). So we can keep track of the total prime factorisation (and the counts of each prime factor) of ai to an.
We also realise that p^2 where p is prime, is a strongly composite number. This is because the factorisation will then be [1, p, p^2] which is valid. Therefore it would be best to form p^2, p^2, p^2 for every prime factor in your total prime factorisation.
Now we have leftover primes, we realise again that prime * prime * prime will give you a strongly composite number. This is because the factorisation will be [1, p, q, r, pq, pr, qr, pqr], which is valid. Therefore we can group the leftover primes by groups of 3
The answer will then be:
If anyone has any alternative solutions please feel free to share! I'd like to learn as well :)
The product of all the integers in the given array is same as the product of all possible prime factors, so the condition for product is already satisfied if you break each integer into prime factor. Now to find the integers of array B(i.e strongly composite numbers) you can see that if any prime factor raised to the power 2 will always be a strongly composite number, so the necessary condition is finding prime factors that have power >= 2, now since you only require minimum (2 prime integers to make them strongly composite) you can utilize the remaining ones to help make the prime integers that aren't strongly composite i.e they exist individually. To make a strongly composite number out of different prime factors you require atleast 3 of them(like 3, 5, 7 can together form a strongly composite number). So all that if left to do is to count the prime factors % 2 and then use them later on in pairs of 3 to form a strongly composite number. Here's my way of doing it: https://codeforces.me/contest/1823/submission/203710826
Great contest, just incase someone is still struggling with Problem A, Problem B or Problem C, You can view the self made video editorial here — video solution
Thanks for the video editorial ^ ^
thanks for this great explanation
Thanks for the video editorial
Thanks for the video editorials.
Thanks for the video editorial
Thanks for the video editorial
E is really close to this https://atcoder.jp/contests/abc297/tasks/abc297_g
also D you can get it with some search https://math.stackexchange.com/questions/1926549/number-of-distinct-palindromic-sub-strings-of-a-string
:(
I think in E similarity is very surface level: statement and code are kind of similar, but actual sulutions are completely different
mehhhh, I can agree kind of the same procedure of solving thou don't you think also f(x) is really close
Yea the function is almost the same
Don't know about you, but in AtCoder problem I just thought about how mex on subsegment changes, and in E the main idea is that if $$$len \geq l + r$$$, then you don't need to think about mex at all, and the idea that otherwise answer is $$$\frac{len}{l}$$$ isn't the hardest part of the problem
how did you deduce the len/l part
Editorial is out, you can see detailed proof there
I think it depends on how you solve it. If you do not attempt to prove it, but believe in the patterns you see, you can write slow polynomial brute force, print tables for the grundy values for different values of $$$l,r$$$, find a pattern and submit it.
E: I converted the problem into pile. and search on google. but how i missed this.
How do you search? can you learn me the tricks (: -_-
Screencast with commentary
thank you :) .
Struggle is real. I was standing at 2450 rank and after resubmitting the same code i got a rank of 3800 just wow.
codeforces rul..
Hence you are a newbie lol...
If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.
i found out after i submitted another solution in the last minute just to try!
welp, RIP those of us who got cute/lazy with C and FST/TLE :P
very sad :(
Feels like the third rated contest in a row i got D within minutes of the contest ending (cus of some if i forgot), feeling cursed
A: Let there are i occurences of 1 and n-i occurences of -1, then k=i*(i-1)/2+(n-i)*(n-i-1)/2. Since n is small we can find i by brute force.
B: Let's classify indexes by i%k, then we can swap any 2 elements with adjacent indexes in the same class, so we can rearrange elements in the same class arbitrarily. Therefore, if for all i p[i]%k=i%k holds, we can sort the permutaion directly; if for at most 2 indexes p[i]%k!=i%k, we can use the preliminary exchange for them and sort the permutation.
C: We can see that "weakly composite" numbers are product of 2 different primes.
Assume n has k different prime factors. If k>=3, then n have at least 2^k factors, and at least 2^k-k-1 composite factors, and when k>=3 we have 2^k>2*k+1. If k==2 and n have square factor, then n have at least 6 factors (1, p, q, p^2, p*q, p^2*q), and 6-2-1>2. If k==2 and p!=q and n=pq, then n have 2 prime factors and 1 composite factor, so n is weakly composite.
To solve the problem, first we need to find prime factorization of prod(a[i]) by prime sieve, assume prod(a[i])=prod(p[j]^r[j]), then we check for the array r[j]. If we need to get a strongly composite number, we need a square factor or 3 different prime factors. Therefore, if max(r[j])==1 and size(r)<=2, there's no solution. Otherwise, the answer is sum(floor(r[j]/2))+floor(sum(r[j]%2)/3), first part for numbers with square factor and second part for numbers with 3 different factors.
D: First, we have p(s, m+1)<=p(s, m)+1.
Assume we add an additional char c to the end of s[1, m], and this operation creates any new palindrome. Let j be the maximal index such that s[j, m+1] is a new palindrome. Then if i<j and s[i, m+1] is a palindrome, we have s[i, i+(m+1)-j] = reverse(s[j, m+1]) = s[j, m+1], and i+(m+1)-j<=m. But since s[j, m+1] is a new palindrome, there can't be its occurence inside s[1, m]. So that's a contradiction. Therefore, s[j, m+1] is the only new palindrome created by the operation, so p(s, m+1)<=p(s, m)+1.
Therefore, if c[1]>x[1] or c[i]-c[i-1]>x[i]-x[i-1] there's no solution. Otherwise, we can construct a solution: First let s[1, 3]="abc", then p(s, 3)=3. Then we denote d[1]=c[1]-3, d[i]=c[i]-c[i-1] is the number of extra palindromes we need to create at position x[i]. Then for each i, we let s[j]=(char)('c'+i) for j in range [x[i]-d[i]+1, x[i]]. So we fill the first range by "ddddd...", second range by "eeeee..." and so on. Each range will create new palindrome equal to its size. By the condition that c[1]<=x[1], c[i]-c[i-1]<=x[i]-x[i-1] and 3<=c[1]<=c[2]<=...<=c[k] these ranges don't overlap, and by the constraint k<=20 we have 'c'+i<='z'. Finally, for all indexes i that s[i] is undetermined, we fill them by 'a', 'b', 'c' alternately, since there are no palindrome other than "a", "b", "c" in "abcabcabcabc...", they will not create any new palindrome.
E: We solve the problem by Sprague-Grundy theorem. Let's denote sg[i] as the SG number of situation of a single cycle with size i, then if i < l or i >= r+l, we have sg[i]=0, otherwise sg[i]=floor(i/l). I have idea to prove it but it's too complicated.
F: Let's forget everything of probability, and construct a path with following properties:
-Start at s, end at t.
-For each node i, the number of occurences of (i-->j) in this path is the same for every adjacent node j. We denote this number as dp[i].
Then we can get the answer by this path. Let t be the root of the tree and j be the parent of i, then the transition is dp[t]=0, dp[i]=dp[j]+1 if node i is on the simple path from s to t, dp[i]=dp[j] otherwise. That's because if i on the simple path from s to t, the number of occurences of (i-->j) will be one more than occurences of (j-->i). Finally, we have ans[i]=sum(dp[j]) if i!=s, ans[s]=sum(dp[j])+1, where sum is over all adjacent node j of i.
How about you open a yt channel ? :)
Was waiting for your editorial :D
Problem D and E should not have same score.
Problem C is the most beautiful problem i ever seen
The implementation of the special judge of Problem D seems much more difficult than the solution.
Yeah, my guess is they planned on asking if a certain string satisfied those conditions, but made the problem easier by only asking for a construction.
I think it is easily possible to check a valid answer by using palindromic tree.
Yeah when I was doing D I wondered how they are going to test it. How can we do better than O(n2)?
Fastest way is probably Palindromic Tree. But it can be done with hashing in O(nlogn), by abusing fact that there can be at most 'n' unique palindromic substrings of any string of size 'n'.
Core idea of this approach, is to consider the longest palindromes centered upon each index. For each such palindrome, insert its hash into a set and trim its outermost characters; repeat the process for each trimmed palindrome until it coincides with some palindrome in the set. The size of the set will be the answer.
I guess it can technically be reduced to O(n) if you use unordered_set and Manacher's algorithm.
I don't know why my performance is declining day by day :(
Problem E is identical to this problem
They're actually not the same. In problem E you can (after two removals) break a connected component into two separate components. You cannot do this in G. Constrained Nim 2. But it happens to be that the solutions are almost the same.
MLE on C :/
Are you precomputing the prime factors? Also, use int instead of long long for this Q coz constraints allow it.
I was using long long, this was my code, ik i have to use sieve but got mle on pretest 1 which was weird.And yes I was gonna precompute. I know i've overcomplicated it but getting mle on pretest 1 is still weird to me.
Edit: code still mle after precomputation
Don't #define int as long long.use int only
And do let me know
Hey, I solved C fair and square. I had almost one hour left, and I also refreshed in between to see for changes. How can they change the constraints after the contest, not at all fair. If I got tle before I would have corrected it with one penalty, but now my rank dropped from 2k something to 4k. I am not at all happy with this behavior.
You didn't get TLE during the contest because your code was only run on pretests. The set of pretests doesn't contain all tests and passing them does not gurantee that the solution passes the full set of system tests. No constraints were changed after the contest. You just got unlucky that your code had a mistake that wasn't covered by pretests.
his code didnt have mistakes , its just that you cant possibly say its ok to run a for till 1e7 1000 times . It was kinda obivious that it would get tle
Did I word that badly? I guess I should've said that they had a mistake in their approach, not the code. But that's not the point of the comment, I just told them why their code changed from AC to TLE.
Actually no, it runs till that last prime factor which is greater than sqrt(a[i]). Only one condition needed to be put instead of letting c increment till that last factor, we can just take the remaining value of a[i] after it reaches sqrt(a[i]). So that was the only mistake. Still it was nothing major and I could have corrected it instantly with only one penalty.
you could have used a sieve of eratosthenes
:(
I have a question, why isn't this submission giving me runtime error? (On line 43). https://codeforces.me/contest/1823/submission/203713818 Would have solved it during contest if it did.
The loop should go upto $$$k$$$, not $$$n$$$.
UPD: Sorry, misread.
I know that. I am interested in why it isn't giving me runtime error.
a great contest but if the problem D were easier the contest would be more interesting and balanced
Are there any special prerequisites needed to solve today's E?
Game theory, as mentioned in the editorial.
D was a very fun problem for me (even though i found A-C a bit boring), thanks!
gonna get to e tmr but i have an ap test monday XD and i must study
Right now it doesn't allow to make any submissions, it shows "Unexpected error". What happened?
Facing the same issue when trying to submit older problems...
Hello,
my submission 203696670 of the problem C (Strongly Composite) has been flagged as a rule violation because of it's similarities to the solutions of Aku30, stark_tony_, ek3ru8m4 and dmenezes with ids 203691212, 203691644, 203694434 and 203695366.
This is because all five of us decided to speed up factorization with a list of all prime numbers from 2 to about 3137. This list is obviously the same for each of us, as we all included the numbers in ascending order. I probaly don't need to mention this, but a list of these prime numbers has been published before the contest.
I would therefore like to appeal my disqualification, along with the disqualification of Aku30, stark_tony_, ek3ru8m4 and dmenezes, as I feel it was unjustified.
Thank you for your consideration.
The only thing common among all of our codes is the list of prime numbers rest is completely different, and you can also notice the range of prime numbers taken into consideration varies with person. Therefore, along with the other participants mentioned above I would like to appeal my disqualification.
Hello, my submission of Problem C 203692110 significantly coincides with the submission of arbalestOvO / [submission:203688479]。In our submissions, we coincidentally use the pallard-rho algorithm to decompose prime factors, and this code implementation has been made public by others before the competition. Here is the link to the code: (https://judge.yosupo.jp/submission/82101). I would therefore like to appeal my disqualification. Thank you for your consideration.
Broo.can anyone please say why i am getting tle for palindrome question-D. i am not able to find the fault.(https://codeforces.me/contest/1823/submission/208179126)