Hello Codech....err i mean Codeforces!
I invite you to participate in Codeforces Round 934 (Div. 1) and Codeforces Round 934 (Div. 2) which will start on Mar/16/2024 17:35 (Moscow time).
You will be given 6 problems and 2 hours 15 minutes to solve them in both divisions. Division 1 has $$$\textbf{2 subtasks}$$$, and Division 2 has $$$\textbf{1 subtask}$$$.
Joining us on the problem setting panel are:
Coordinator: Ashley errorgorn Khoo.
Authors: Satyam satyam343 Kumar Roy, Aditya Everule Jain, Shreyan Dominater069 Ray.
Russian Translation: Alexey Alexdat2000 Datskovskiy.
Red Testers: Kostia kostia244 Savchuk, Jeroen jeroenodb Op De Beek, Andrei andrei_boaca Boaca, Luan LipArcanjo Arcanjo, Fernando ffao Fonseca, Alexander teraqqq Babin, Aleksei Vercingetorix Esin, Zixuan RDDCCD Yan, Aws Kaitokid Issa, hyforces.
Yellow Testers: Naveen evenvalue Kulkarni, Kaio MvKaio Vieira, pavement, penguin133, zengminghao, Irmuun irmuun Chinbat, Jared malachi_toney_goat Goff, James jamessngg Sng, Sergey Kniaz Kniazevskiy, Chien-Yi -1e11 Chien, camc, Hriday the_hyp0cr1t3 G, Aryan aryan12 Maskara, Thomas oursaco, Weobe, Leonardo defnotmee Valente Nascimento.
Purple Testers: Milind milind0110 Gupta, straw berr y.
Blue Testers: Matthew chromate00 Roh, Ahmad Ahmad45123 Elwasefi, Kirill Mox_Taest3r Kobets, Ivan peshkoff Peshkov, Yi Xiang Tyx2019 Tey, June cjc Chen, Kirill AbsurdMan Petrov, ExpensiveAC, Elyes ElyesChaabouni Chaabouni, Ianlsam, Non-origination, nsqrtlog
Cyan Testers: Vyacheslav Kirito.LVL99 Komarov, Harsh Codula Sharma.
Gray Testers: Sergey ansergeyg An.
Negative Rated Testers: Cozma tibinyte2006 Tiberiu-Stefan.
I would like to thank MikeMirzayanov for platforms Codeforces and Polygon.
Please do read a few problems in advance at the very least. Especially with all the subtasks, it is strictly in your benefit to read and choose the problems you want to try. Good luck. We hope you enjoy the problemset.
Score Distribution will be posted soon.
$$$\textbf{UPD}$$$ : Score Distribution :
Div2 : 500 + 1000 + 1500 + 2250 + 2250 + (2250 + 2750).
Div1 : 500 + 1250 + 1250 + (1250 + 2000) + (2000 + 1500) + 4500.
$$$\textbf{UPD2}$$$ : Sorry for the issue with the queue towards the end. Hope you enjoyed the round.
$$$\textbf{UPD3}$$$ :
Div2 :
1) WanYuanShenWanDe
2) solar_tree
3) kcodex
4) zhukau
5) Oinng123
Div1 :
1) tourist
2) jiangly
3) gyh20
4) Benq
5) ecnerwala
$$$\textbf{UPD4}$$$ : Editorial is out.
As a tester, I would like to know when the next cookoff will be.
Maybe in python it's float("inf")
As a tester, I recommend to break your fast on this meal.
satyam343,Dominater069,Everule orz
As a tester, Dominater069, Everule and satyam343 orz
As a tester, C++20 when?
As a tester, good luck to all participants.
As a tester, lunchtime when
Cringe announcement
I understand if you don't like it, it is slightly different, but calling it cringe without any feedback isn't very nice, don't you think? :)
I only talked about the announcement, not about the round!
Of course Dominater069's rounds are great!
What is a subtask? Are there any prior examples to try it?
Subtask means the problem will be divided into two parts, one will be easier with lower constraints and one will be harder with higher constraints.
Thanks. I thought it's something special that deserved highlighting in announcement
As a participant, i will participate
Congrats, Dominater069 on your first codeforces round!
So many testers !
I was really excited to do this contest but now i discovered that I'm a tester D:
As a tester, the problemsetters cooked.
I'm sorry, but Div.1 is very important, so why not take the option of postponing it?
It is a bit sudden, considering that changes in the available C++ compilers have made some libraries effectively unusable or slowed down (if you make heavy use of long longs).
I think the most important issue is that both C++14 and C++17 (32 bit) don't support __int128.
I wonder why no one has mentioned it before, at least on CF.
Agree.It's very inconvenient.
you guys using __int128 somewhere outside pollard / miller_rabin?
I and some Japanese often rely on ACL ( https://github.com/atcoder/ac-library ). If we want to use modint, fenwick_tree or convolution, we need int128.
fenwick_treeO_ook, I see atcoder/fenwicktree calls
to_unsignedand its requires__int128_t. but why it is converts T to unsigned?I mentioned it 4 days ago. Really sad.
Congratulations on your first contest, Dominater069
And also Good Luck for every parcipicant!!!!!
Dominater069 orz
Umm... Why is the eligibility range for Div. 2 from 0 to 1899?
If there is a corresponding Div. 1 round, then you belong to Div. 1
Dominater069 rounds gotta be one of my favourite genders
Arre Pogi, tum yaha??
kaho to clear kardu tumhe?
what do you mean by subtasks? can somebody explain please
Versions of tasks with different sub-conditions.
For example:
D1 and D2 from https://mirror.codeforces.com/contest/1934/standings
D1 and D2 from https://mirror.codeforces.com/contest/1903/standings
Ohh got it. Thankyou
Negative rated testers tho :)
problem in div 2 is subtask 1 in div 1 ??
downvoteforces
As a tester, the problems are really good and I would recommend the participants to read all of them.
I did the round yesterday thinking that I would get to 1900 and get to compete in Div 1 this round. But the rating changes have not come through yet. Anyone know if I'll get to 1900 before the contest?
Is the mean of "subtask" like 1939D - Big Persimmon (one problem but have partial points), or like D1/D2 (two problems without partial points)?
two problems without partial points
Since so many LGM's demanding C++20, can someone elaborate what's the difference between C++14,17,20 etc...
Again Clashing with LC Biweekly, have to skip
i put contest specifically in lc biweekly time so i can get a high rank after a long time
ohh
nahh...i'd code
That's why Dominater069 orz.
2250 for div2D is too high.
it became speedforces
BCD1 with the same score, looks interesting
orz, I hope to reach Specialist soon. Good luck to all participants!!!
Ah yes! A negative rating tester!
4500? Serious?
Dominater069 Great to see you as the author on CodeForces Contest!!
So many subtasks. Is it possible to make a 5-hour IOI rated contest?
What is penalty time ?
Amazing problems haha, Dominater069 rounds are always so fun, This one had a codechef taste (Bitwise and Game thoery), loved it.
newbie here i come
SAFE!
In queue.
how to approach B ?
Hint:
First consider the 2*n size array where, in first half all elements from 1 to n are present and in the remaining half all elements from 1 to n are present {these two half will have same xor}.
then, try to think what will happen if we swap some of the elements.
imagine submiting your code in the last 10 minute and get long queue, then it give you a WA verdict after contest
There's a bunch of submissions in queue. Will the round be extended?
my code is not submitting from last 10 minutes, its stuck on pretest 1??
It's just that the codeforces is lagging
U
The examples seem a little simple so that I have a lot score penalty. qwq
These 2250 are slightly eazier than average.
Trash sample.
I'm back, GM.
What was the catch in the problem C? Alice has to pick numbers in increasing order. Bob will remove minimum x such that cnt[x]<=x. Right?
Can someone provide a counter-test-case for my solution?
The second smallest element with frequency 1 is the answer.
If I'm not mistaken, the answer is second smallest element with frequency 1. Once we pick the first number, we can just react to what bob is doing. He will never be able to remove a number from us, unless it's value is 1.
Yes, sorry, I actually meant frequency 1, don't know why I typed unique frequency. Updated. Thanks.
0 0 1 1 2
Answer is 3
I sorted the array and found the MEX of elements in odd positions. Can someone provide some counter case? It failed.
0 0 0 1
You say the answer is 1 but it is 2. Alice can pick up the 1 then a 0. If you index from 0 then just add another 0 in the front (have the 2 in an even position)
Your algorithm would work (I think) if you had at most 2 of each number.
0 0 1.
Alice picks 1. Bob picks 0. Alice picks 0. Mex is 2.
0 1 1 2 2
Actual answer : 3 Your answer. : 2
I love problem div2D.
How did you solved it ?
My solution for D looks like shit
gameforces!
Ok, can somone please tell me whats wrong with my solution? 251789210
I ran stress test but nothing came up ...
EDIT: Nevermind ... got it
Man, I'm stress testing with actual AC codes rn and nothing's coming up. What the actuall fuck
Can you share the test case?
Edit: Nvm, system tests are over
Hello , I took a look at your solution , you only subtract 3 when the sequence is alternating ababababa, but it's actually you need to remove all the odd values, 3 5 7 ...
Yeah that's the issue .. Thanks for the response :)
Can anyone here pls explain D to me?
If you have a palindrome, say
abcddcba, and you append a characterxat the end. Under what condition will it remain a palindrome?How to check if the given substring itself is a palindrome, I wasn't able to check that without getting a TLE.
My approach was if its 2-good, then it is k-good for all even numbers k, less than the string length. Similarly, if it is 3-good, then it is k-good for all odd numbers k, less than string length. But in this case, I was required to check additionally if the given substring was a palindrome. I wasn't able to think of an efficient way to do this. Can someone help?
You will need to use string hashing.
Thank you.
You can do Manacher. It's little bit annoying to handle the index though.
did you use it in your solution?
yes
gotcha, ty broski
I think it wasn't a nice decision to decide to extend the round at the last minute.
there was a long queue (~10mins) towards the end of the contest, its the only fair decision
No, the only fair decision is to make the round unrated (I mean, it might be a valid argument that the "unfairness" was allowable, though...).
I received the notification of the extension only after the extra time. I was lucky to notice it at some point, but the site was too unstable and I just spent almost-offline time...
thanks
Same, I left before the round was finished.
Fully agreed. Also, no announcement was sent to Div1 contestants before the scheduled end time.
But never give up until the last moment, right? Leaving early is not the right approach.
The problem is, When there were 20 minutes left, I decided to go with problem F, which is harder but with less code. As long as I solve it, I can quickly write it in 5 minutes. But If I know I have 30 minutes, I will go with problem E, since I already solved it, but I don't have enough time to code. Extension at the last minute is useless for me, I can't do anything with C and E.
I apologize that the original announcement of extension has not reached the Div1 participants. Normally, it is sent simultaneously to both contests, however, I can see that this time it has only been sent to Div2. I guess either I misclicked, or the system malfunctioned.
Did not get the notice of the extension and hence did not submit D2 which was a couple minutes of debug away. :(
My solution of B using randomisation
https://mirror.codeforces.com/contest/1944/submission/251722044
How to solve Div2D
If the substring has all identical characters, the answer is zero. If the substring contains alternating characters such as
ababab, the answer is summataion of all even $$$k$$$. Otherwise, all $$$k \geq 2$$$ contribute the answer, except the original substring, which will contribute only if it is not a palindrome.The crucial idea is : If you have a palindrome, and you append a character at the end, there are a very limited set of scenarios in which the new string would also remain palindrome (that's where the motivation for alternating string comes in).
Thanks!
wrong
Fuck me , i thought problem B was finding non intersecting subarrays with equal XOR, and my Solutin passed the first test , i'm so fucking blind man
1C is MUCH easier than 1B.
Can you share it's solution.
Is always choosing the node which has largest number of elements at farthest distance and eliminating these farthest element nodes correct?
Let the diameter of the tree be $$$d$$$.
When $$$d$$$ is odd or $$$\lfloor \frac{d+1}{2} \rfloor$$$ is odd, select the node in the middle of the diameter for operation.
When $$$\lfloor \frac{d+1}{2} \rfloor$$$ is even, let the middle two nodes of the diameter be $$$x, y$$$, and then operate on $$$(x, 1) (y, 1) (x, 3) (y, 3) \dots$$$
I didn't carefully prove it, but it looks very correct and passed all the pretests :)
Proving this is quite simple, use the fact that any operation turns at most 2 nodes of the diameter black. Since the diameter must be made black you get a lower bound of $$$\frac{len + 1}{2} + 1$$$ operations. The case when $$$len \equiv 3 \mod 4$$$ you can do the 2 center nodes tactic. To prove that you cannot do better when $$$len \equiv 1 \mod 4$$$ you can just arrange the diameter nodes in a row. Any operation that colors 2 nodes will color 2 nodes with the same index parity. But there are $$$\frac{len + 1}{2}$$$ nodes with each parity. The number is odd, thus you cannot match the last 2 nodes together and need to do them separately. This is no better than the "Take one node and all the distances" tactic.
No. I don't actually know, why is $$$n \le 2000$$$, when I could solve it in $$$O(n)$$$. Probably, it is hard to create checker in $$$O(n)$$$.
Find any diameter. Let its length is $$$D$$$ (the number of vertices on it is $$$D + 1$$$). There are two cases:
Case 1: $$$(D + 1) \mod 4 \neq 3$$$ (not 3, 7, 11, etc.). Then we have to find one vertice on center on diameter and simply do $$$d = 0, d = 1, d = 2, \dots$$$.
Case 2: $$$(D + 1) \mod 4 = 3$$$. In this case we can optimize one operation. Look at examples:
The upper horizontal line is a found diameter. We can take vertices $$$a$$$ and $$$b$$$ and do operations $$$(a, 1)$$$ and $$$(b, 1)$$$. Using algorithm from first case we could find following operations: $$$(a, 0)$$$, $$$(a, 1)$$$ and $$$(a, 2)$$$, which is worse.
We can do operations $$$(a, 1)$$$, $$$(a, 2)$$$, $$$(a, 3)$$$, $$$(b, 1)$$$, $$$(b, 2)$$$, $$$(b, 3)$$$.
So, in this case we use two vertices on the center of the diameter.
"Probably, it is hard to create checker in O(n)." — Absolutely right. That was the reason :)
I think you forgot to say that for even $$$k$$$ we can skip $$$(a, k)$$$ and $$$(b, k)$$$, so on the last example we only need to perform 4 operations $$$(a, 1)$$$, $$$(a, 3)$$$, $$$(b, 1)$$$, $$$(b, 3)$$$
I couldn't stick this solution (which you described) in during testing. I tried very hard to do it :)
You might be surprised to hear that it was actually placed at 2F(1D) when I tested
Well done, Amazing performance Kevin114514. It was a nice comeback, indeed!!! 🔥🔥
Is problem D related to hashing?
At least I used it, hope it will pass systests
i did using hashing
For me this round is very Bad
Very weak samples propably on purpose
Ideas in div1B and div1C are really easy to get but corner cases are really easy to miss
Maybe its me but i really hate such rounds
Try random DP approach for F1 but still can't do it :((
Dforces
I did this in div1 problem B. Is this an intended solution?
There are three cases.
Case 1: There is only one character in a string: $$$aa \dots aa$$$. In this case the answer is $$$0$$$.
Case 2: The string is of form $$$ababab \dots aba$$$, and its length modulo $$$2$$$ doesn't matter. In this case the answer is $$$2 + 4 + 6 + 8 + \dots$$$ and if a string itself is not a palindrome, then additionally $$$+ length(s)$$$.
Case 3: Else the answer is $$$2 + 3 + 4 + 5 + \dots$$$ and if a string itself is not a palindrome, then additionally $$$+ length(s)$$$.
To check the form $$$aa \dots aa$$$ or $$$abab \dots abab$$$ of a string I used prefix sums for all characters.
To check, if a substring is a palindrome, I used polynomial hashes with segment tree.
Yes, this should be correct. By the way, since we are already using polynomial hashes, can't we just compare substring hash with its reverse for equality?
Checking whether the substring is a palindrome or not within the given constraints was the most difficult part for me
For polynomial hashes of a substring, you can use some sort of prefix sums, instead of a segment tree, because there are no updates.
I think that for checking if given substring in a string is a palindrome, we can use Manacher (but I also did it with hashes)
Did exactly same, still getting WA on test 2, maybe some edge case, disappointing contest for me.
You can also use manacher algorithm for checking palindrome. It's O(n).Manacher
Can someone help me what's wrong with my B solution?
try this case n = 5, k = 2, 1 2 3 4 4 1 2 3 5 5
thanks
I am so mad at myself atp, because I missed not in 1B, and I was trying to solve it the whole time >:(
How to do div2D (shortest way)
For even: if k < full_length_substring, good = all characters are same
For odd length: if k < full_length_substring, good = all even position characters are same & all odd position characters are same.
full length needs to be calculated manually, I used manacher algorithm.
The king is back in the game...
is there any other way to solve Div2 D without using Manacher algorithm(tourist 251709195 used it) but it seems a bit tricky Anyone with any other approach
tourist #1 jiangly #2 what a beautiful sight to see
A picture that everyone likes except jiangly
balance is restored
Can someone explain what is wrong with this solution for C problem of div2:
251791328 Div2-D why this submissions RE？It run ok in my computer.
Problem E, found centroid and then just dfs'd out as far as possible and printed unique distances... what case does it WA? https://mirror.codeforces.com/contest/1944/submission/251783755
Two operations are enough.
In div2D, how do you check if a substring is a palindrome or not in constant time?? I implemented the rest of it completely but just didn't know how to get through this part. It was incredibly frustrating ffs.
You can use rolling hash (aka. Rabin-Karp) or Manacher's algorithm.
You can use string hashing. If you're afraid of implementing string hashing by yourself, you can use this mini library provided by USACO guide.
Using this library, the code is as simple as
My Submission
I solve div2E as follow first i try every node as starting then i try every adj pair as starting the operation and take the best out of all why it didn't pass any countr example??
What's wrong with my solution 251724861 for Div 2 1944B - Equal XOR?
Edit: Got it
nice balanced round, good job, guys
Test case : 9 1 0 7 7 7 6 1 2 0 Output must be 3 but its 2 as if Alice choose 0 then Bob would choose 2
Think what if Alice instead of taking 0 initially she took 2 and then Bob if goes for 0/1 there will still be 0/1 left to take.
For Div1E, why is the answer 3 here?
If you try to get mex=4, Alice chooses 2, Bob removes 2 copies of 3, 2 copies of 1 and 1 copy of 0, Alice chooses 0(or 1, it doesn't matter), Bob removes 2 copies of 1 and 3 copies of 3, Alice removes 1(or 3, it doesn't matter), Bob removes 5 copies of 3, loss for Alice.
Nice Round. Upsolved Div2 D after the Round. Learnt How to check s(l...r) is palindrome or not in constant time using Hashing by converting to Integer in base 26.
One doubt , I stored these hashed values mod 1e9 + 7 , it passed the cases but Isn't it possible that two string might give same hashed values mod 1e9 + 7 ? If yes how to avoid such cases ?
possible, but very unlikely
you should do double hashing to make sure it doesnt happen in the future
You can store two hashes with different constants to almost completely eradicate this possibility. I got hacked during the competition because I used only one hash, fortunately I managed to add another hash in time. This is my submission. There is also a good paragraph about reducing collisions on cp-algo.
or you could use manacher's algo which will give you the longest palindromic substring at every center. Its much easier as code is available at gfg.
Big gap between 2C and 2D, and IMO 2B was harder than 2C. Problems were good.
Anyone has any hint how to go from 1D1 to 1D2 ? Thanks
The Inclusion-Exclusion Principle.
We can solve it by just modifying the solution of 1D1 too, we just need to observe that transitions from states of index to the next are like range arithmetic-progression add updates, which can be processed in $$$O(k)$$$ per index. Since there are $$$O(n)$$$ indices, we have an $$$O(nk)$$$ solution.
251801445
Can you explain, what are the conditions for the array to be good?
You need for every i , $$$a[i] \lt = a[i-1] + a[i+1]$$$
For Div2 Problem B Equal XOR I have the following submission https://mirror.codeforces.com/contest/1944/submission/251835494 but it gives
wrong answer l is not subset of a[1, n] (test case 37)for test 2 and I have 0 idea why. I sorted the indices in l and r so this shouldn't happen unless l contains elements which are not in [1..n] (or [0..n-1] as I have them 0-indexed in my program). Does anyone have at least an example for which my solution fails?1
3 1
1 2 2 1 3 3
Your solution greedily takes the value. So when it encounters the first 1 it immediately insert it into the first array .As a result the output contains 1 less element
Yes, it's tourist ranking first, finally! Hope tourist can get back to the rating leader again!
received WA 15 times on pretest 2 for problem 2C/1A
discovered that there was no output on one test case
1 0fixed and immediately got AC 🤡
Trash D1 AB, and Terrible samples
When will the ratings be updated?
Congratulations,jiangly goes back to the first rating.
Winner of Div. 2 is called WanYuanShenWanDe??? Why Genshin Impact ("YuanShen") is everywhere, even in Codeforces?
"Yuanshen" is translated directly in China,and gradually becomes a meme because of its popularity.
Good problems,thx.
So when will the ratings be updated?
As a tester, good luck to all participants.
I hope there is no queue at the end of contest .
haha，me too
When will the ratings be updated? Why is the rating updated so slowly this time?
in problem 3 of div2 9 1 0 7 7 7 6 1 2 0 let this be the test case, i think here answer should be two but it's three
explaination->in first turn alice choose 0, then bob choose 1, then alice choose 1,then bob choose 2 and thus by any next turn alice will not get two and mex will be two
what if Alice chooses 2 at the very first move?
oh yes,thanks
the contest is rated or unrated
When the rating will update ?? It's taking a lots of time
please provide an update on when the rating will be updated?
When will the ratings be updated? On some div1/2 contests, it is as immediate as lightning once the round ends, rating updates. On other hand, for other contests, it delays. This delayed lot.
i got WA on D because someone found strings with the same reverse hash. with this, you can hack anyones code. is this fair?
Yes
maybe you can try to user manacher?
there was a discussion between the contest writer Dominater069 and LGM's regarding that all of Div1 participants did not receive the message. convo I guess they might be checking manually the number of affected Div1 participants so they can get their round unrated as it happened in the last round where 18 people were manually addressed.
Finally became a Expert haha
my actual rank in this round is 1192 and its showing in common standings but in my recent contests its showing my rank is 4811 and i got a 106 negative .. can someone address my problem ?
Valid concern. You should put up a blog or mail MikeMirzayanov
negative/xia
Check 4th test of problem A
wrong output format Unexpected end of file — int32 expected (test case 200)
what does this error mean?
Can someone give an example test case where single hash might fail on Div2D?
I submitted a single hash solution which got AC, but someone in the comments said that their single hash solution got hacked.
Here you go, I hacked you to illustrate.
The point is you can somewhat easily find collissions for single-hashes if you know the modulo/base, so you should default to double hashes usually.
too easy C.too hard D.
Wow, I arrived slightly late in this contest just to discover there isn't a single question in the 1300-2000 difficulty range. Welcome to speedforces, and I already lost before it even had began
Can someone suggest what is wrong in my submission for div2 C problem.
251924677
My idea was that Alice and Bob will always pick up the smallest available element that occurs once in the array. What is wrong in that?
My submission failsin 363rd test case.
Imagine such testcase:
What will be the answer and what is your code answer?
My code answer will be 1. First Alice will pick 0 and then Bob picks 1, so final answer becomes 1.
C9rrect answer will also be 1
I have run your code, it gives 0.
oh ya got my mistake, thanks a lot[user:mihajlovskijr]
You're welcome
In my opinion the score of Div. 1 E should be 1250 + 2250 instead of 2000 + 1500...
Ended up getting wrong ans in D due to hash collision, changing the value of p worked.
Incorrect submission-https://mirror.codeforces.com/contest/1944/submission/251985522
Accepted-https://mirror.codeforces.com/contest/1944/submission/251985606
It didnt work, it just didnt get hacked yet. Why not just pick a base randomly? (Or mod works too but you have to make it prime)
Thanks, got hacked so used a random generator now
For those of you still waiting on some editorials, this may be of slight help. My editorial on Div2 A to D (the last two being Div1 A, B): https://www.youtube.com/watch?v=fZK7hiemXOE&t=10s
For Div2 C / Div1 A
for the test case 9 1 0 7 7 7 6 1 2 0
how the output is 3 ? First Alice removes 0, then Bob removes 1 then, Alice removes the second 1, now Bob removes the 2 and now Alice cannot get a 2 and cannot make MEX equals to 3
Kindly help me understand this
Alice removes 2 first.
Can you please explain the optima strategy and how it works ?
Alice picks 2.
If Bob picks 0, Alice picks 0 in the next move.
If Bob picks 1, Alice picks 1 in the next move.
If Bob picks something else, Alice can just pick whatever.
With this strategy, Alice can always pick 0, 1 and 2.
tourist is back
hi