Hello, Codeforces!
I am very excited to invite you to our contest Codeforces Round 1054 (Div. 3), which starts on . You will be given 7 problems and 2 hours and 15 minutes to solve them.
The problems were authored by me and __rose and soullless to solve and alter them.
The round will be hosted by the rules of educational rounds (extended ICPC). Thus, all solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After the open hack phase, all accepted solutions will be rejudged on successful hacks. Also, note that there is no score distribution — rank will be determined by number of problems solved, followed by penalty; wrong submissions will incur the usual penalty of 10 minutes, following the rules of educational rounds.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
take part in at least five rated rounds (and solve at least one problem in each of them)
do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
We would like to thank:
Wansur and abc864197532 for red testing.
ImDMka, Aldk and Away_in_the_heavens for orange testing.
Hagry for purple testing
1BR444H1M, Batyi-A-019-28, HorridBear, Romakolesn and kartikchauhan189 for cyan testing.
Erbolat-R-019-28, Yozhik and Fadlallah for green testing.
MikeMirzayanov and KAN for the great platforms.
Vinton Cerf, and Robert Kahn for inventing the internet.
Nagi for not giving up football.
You for participating!
UPD : the editorial is out.
first comment!!
nice
why is my solution for 3rd problem wa on test 2??? :sob:
Nagi proving once again that being a lazy genius is still genius enough for CF
__baozii__ really wants to Reach igm
I guess I can regain my streak soon.
.
I am so jealous of your college syllabus
I don't think they'll review or anything.. they too busy and there are too many accounts making AI submissions.. Just make a diff account.
As a blue tester, I am not a blue tester.
Codeforces x Bluelock?
Specialists preparing for tomorrows contest:
As an orange tester, I am purple
As an green tester, i have no idea XD
Nice Image
^_^
100% goated round
Blue Lock mentionedddeddd!!!!! Goated round
:D
As a tester, I encourage you to participate in the round. Nice problems.
GOATED ROUND BLUE LOCK MENTIONED
Anything the authors can do to help with the crawling bans during the hacking round would be greatly appreciated.
And I've been banned for crawling...
Why are you hacking problems if you're not participating in the contest? Maybe you should go outside, touch the grass, and breathe some fresh air?
Why are you saying I wasn’t in the contest?
Because it wasn't rated for you, why hack other people's solutions if you don't get points for them? It seems like you really have nothing better to do.
A 12 hour hacking session is actually a great practice area to get better at hacking for div1/2 rounds. In those rounds, you are under time pressure, and there is a penalty for a failed hack. Are you suggesting I learn how to hack with my rating on the line and with bigger downsides, both in time to solve other problems + the negative points for a failed hack?
In terms of the net effect on you from my activities, you would have been hacked anyway. My efforts simply notified you sooner of the outcome + you can see the full test case that specifically hacked your code. If you had TLE on the final test set instead (other people were also doing hashmap hacks), it would take much greater effort to figure out what that hack generating code was.
It seems in general your concern is that you submitted code, it passed, and then it failed later. That possibility occurs because of the rules set up by codeforces, and this possibility is in all rounds (div1 through div4). My view on hacking rounds is the following: It's already a lot of work to create good problems, and hacking rounds lower the burden on problem authors for generating great contests.
Sorry if I'm missing something obvious, but can't seem to find how long the contest is. 2 hours? 2:15? 3:00 (unlikely)?
I don't know how they missed it in the announcements but you can find it in the length column on the https://codeforces.me/contests page. It's 2:15.
Ahh yes, that's one way of finding it out. Thanks. They should've mentioned in the announcement, though.
Me to div3 when i was a struggling cyan
As a participant,I'll do my best to solve all problems of this contest
As a participant, i hope to AK the round!
Hope to have a good contest
Hope to reach expert :)
Congratulation
Thank you:)
Blue lock x codeforces?!
Can wait for Rin destroyer mode to destroy me (╯˘ -˘ )╯
fire!
I am doing this contest in the airport as my flight has been delayed. I hope my flight is delayed longer so that I can get more submits.
Wish to AC 4 questions
Finally, i solved 5 problem , Sleep zzz:)
What questions you are solving for practice. Your growth is incredible. Please help.
Btw congrats on +ve delta
thx honestly, the rating gain was partly luck. I regularly participate in ABC and write editorials for post-contest review. Wishing you great progress and a huge +ve delta soon!
Codeforces is really fast and smooth today. How can you achieve this?
It’s fast and smooth because we are there , monitoring every cheater, scaring them, and we built strong tests.
This was the weirdest contest I have done in my life. great work !!
very fun problems
I am considering reading blue lock now
I have been delaying it for a long long time
How to solve 2149E - Hidden Knowledge of the Ancients ?
I hope G isn't intended to be solved with randomization
I solved G with random because of very simple realization, but I also believe that solution which uses kth-stat on the interval to get possible values, is able to get AC
You can also overkill with MO's
Really neat idea with kth statistics! 10 lines of implementation for online, generalizable, fast solution: 340616457
And harder version as well: 340601606
Works in $$$O(\frac{n}{k} \log(n))$$$ per query for getting all the numbers that appear at least $$$k$$$ times in the segment.
my solution to problem G does not rely on randomization.
it is based on the observation that for a given query the length of the interval can either be less than sqrt(n) or more than sqrt(n).
in this case we'll just go over the whole interval, store occurrences and print answer.
in this case we can notice that the good elements must occur more than sqrt(n) / 3 times in the interval. this implies they occur more than sqrt(n) / 3 times in the whole array. it is now obvious that the total candidates (for all queries of this case) are all the elements that occur more than sqrt(n) / 3 times in whole array, which are at most 3 * sqrt(n). to solve this case we can precalculate prefix occurences for the candidates (elements that appear at least sqrt(n) / 3 times in the whole array) and check them during each query.
the complexity i achieve using maps is O(q * sqrt(n) * log(sqrt(n)) + n * log(n)). since the TL is 4.5 seconds i think this is the intended one, but who knows.
edit: this got hacked, its correct but it's not good enough
It can be solved using extended boyer moore's algorithm with segment tree.
Each node will store 2 potential candidates — {(candidate_1, votes_1), (candidate_2, votes_2)} as there can be at max be 2 candidates only. In simpler words, the segment tree will store the result of extended boyer moore's algorithm on the range [l,r].
Merging Logic — 1. If a candidate from the right matches an existing one, then their votes are added. 2. If a slot is open, the new candidate fills it. 3. If all candidates are different, they cancel each other by reducing their vote counts.
For each of the two candidates returned by the query, you must calculate its true frequency within the range [l, r]. This can be done quickly by pre-calculating the indices of all numbers and then using binary search. If the true frequency is strictly greater than ⌊(r — l + 1) / 3⌋, then it is a valid answer.
i solve with randomiztion but got wa so i use boyer moore
This problem and 840D — Destiny look like G
G is not original, infact it has appeared on codeforces itself. 840D - Destiny
Is 840-D doable by Randomized algorithm ?
very nice contest, loved F. couldn't find how to optimize G.
Please tell me E was sliding window
Correct
Yes, but with a little trick, exactlyK(k, [l, r]) =
countAtMost(k,r) -
( countAtMost(k,l−1)+(countAtMost(k−1,r)+countAtMost(k−1,l−1)) )
where, countAtMost(k,x): answer of k distinct element and length at most x
how to solve F?
Fantastic round. Njoyed D a lot:)
nice balanced round !! Appreciate it
Is G solvable with Mo's algorithm? I can't eliminate the O(logN) part when updating.
https://codeforces.me/contest/840/submission/302962076, it uses random tho. But it's very unhackable.
Oh, so we need random anyways. Thanks
what is meant by random here ?
use randomization, like for a segment we can try 100 times, if none of them hit the elements with a frequency larger than L / 3, the probability is $$$(\frac{2}{3})^{100}$$$ which is negligible.
it's not Mo, but we have other sqrt solutions 340447922 too.
Wow, glad to know this. really stunning.
Here's the Mo code for it
340514285
This was a stupid question.
Initially I used Mo's as well which obviously TLEd. But it is still solvable in sqrt(n) per query by precalculating for elements having frequency > sqrt(n) and brute force for queries with length < 3 * sqrt(n).
You can use rollback Mo to avoid the logN part.
Yes it is. Not sure if it is Mo's Algorithm, but it is sqrt decomposition. You can see my commented submission — 340516275
If you want in c++, you can see this direct translation — 340513734
Both of these use a hashmap so they are prone to getting hacked. You can use a map instead — 340519043
Yeah you can, but to eliminate the O(logN) part you can use coordinate compression 340514285
My thought process for $$$F$$$ was as follows:
the range for $$$x$$$ is $$$0 \le x \le 10^9$$$ ($$$x = 10^9$$$ when $$$d = 10^9$$$ and $$$h = 2$$$) (is this range correct?)
Is my approach even remotely correct lol?
your idea is correct
let $$$d = p \cdot (x+1) + q$$$ $$$(q \lt x + 1)$$$ then we can prove that an optimal answer for the problem is $$$i_1 = ... = i_q = p + 1, i_{q+1} = ... = i_{x+1} = p$$$ using exchange argument, which we can calculate in $$$O(1)$$$
As I passed the problem just now with your construction,will you mind being pointed out a mistake that for $$$ i_1 $$$ to $$$ i_q $$$, they shoule be $$$ p + 1 $$$ ,and for other $$$ i $$$,they should be $$$ p $$$.
i'm sorry for the typo
What is exchange argument ?
It's like a method of proving by exchanging some arguments
For example: in this problem if there exist $$$a, b$$$ such that $$$i_a - i_b \ge 2$$$ then we can prove that if we make $$$i_a := i_a - 1, i_b := i_b + 1$$$ then the value that we need to check is smaller. So we know that the optimal solution guarantees that $$$|i_a - i_b| \le 1$$$ which is only true when array $$$i$$$ is a permutation of what i've said
Yes,i have same idea but I used x-1 not x ,and then you can make bin-search on x,because best I values are d/x and d%x values +1 this can be calculated in O(1). My approach : 340527265
Thanks for posting , I liked the mathematical thought process
You're welcome :) It still hurts that I was this close to solving the problem but I couldn't get the trivial solution of $$$p$$$ and $$$p + 1$$$ :(
yeah , I am also pondering about how to think these things during contest.
but good reveal of patterns and maths
Is E need persistent segment tree or it is simpler than this ?
maintaining two sliding window is enough
now I get it, I feel bad about myself :(
ts was ass icl
not only was there a complete lack of problem solving in this contest up to including e (probably later problems as well if i had to guess)
half of these were knowledge checks or leetcode ah problems
when its very obvious how to solve the problem, and it takes the entire later part of the contest to implement... hint hint, probably not a fun problem, we use this site for problem solving, go set on leetcode if you think these are good tasks
oh and a side effect of it being very standard!!!!!! a lot of indians will be solving it! theyre very good at standard implementations huh?????
anyways tldr: tspmosmicl
update: I was doing binsearch on BIT for e, turns out spamming pdbs is easier, but my argument about it being too standard still stands.
E was a 1 line modification of this and just f(k) — f(k-1). Usually I am very good at leetcode style problems, but I did this on D so I am losing 60 yippee
Overall great contest
For the problem G, WHY NO -1 IN THE SAMPLE CASE ??????????????????????????????????????????????????????????????????????????????????????????????????????
I believe the reason behind this is to not confuse answers for different queries with each other, in case you suggest to output nothing if there is no suitable values
I got a wrong answer because of it and the sorting It would have been more convenient if they have used a custom checker.
GPT passed G with Mo's Aglo. Link
Can someone check if its hackable or not?
At first I thought, “Wow, the Kazakhs organized a contest, the problems must be great.” While participating, I found problems A–C quite good, but the rest felt kind of strange. On top of that, with AI one could easily AK this contest.
Every div 3 is AKable with AI tho?
Can you please provide a hint to solve D?
Calculate for a and b. Take the minimum.you have to take the median of a for the lowest cost of consecutive a and same for b. And at last just compare and print the minimum cost. If n<=2 then it will always be 0 and if a or b is already consecutive then it will be zero.
I solved A-E in around 45 minutes, official ranking was 300, and then so many people solved F and G using LLM and I dropped to 1300. (A problem similar to G already exist on CF and is rated 2500 but there is no way low rated people knew it).
F was standard binary search , the solve rate does not seem too high. (Not sure — I was not in the contest)
I think the time limit is so tight, here 340510152 I was compressing the array using a set and a map but it didn't pass. But when I compressed using sort and binary search instead it passed. 340511269 I understant that it should be a bit faster but they are still the same time complexity O(n * log n).
can anyone hack my cheese in D? I only find the "stick spot" around the average index +- 100
340513009
Bro, we got specialist curse
It's specialist life atp, just enjoy.
I made it with sample like this: aaaaa...aaaabababab...abababbbbbb....bbbbb
Thanks, it will strengthen the systest. (my main idea is to use median tho)
I noticed that today’s Div. 3 Problem G feels very similar to 840D — Destiny . I know Codeforces usually avoids repeating problems, so I was a bit surprised. It doesn’t seem entirely fair, since people who have already solved 840D might have an advantage in today’s contest.
But that is a 2500 problem. If a rated Div3 participant has already solved that problem; I think he / she deserves that advantage..
Anyways, I agree with your point that the statement was also same (just k was restricted to 3) and we had to get all elements (at most 2) rather than the minimum element and the setters could make it a bit indirect inspiration from problem 840D.
1800 max its just an old problem
Can someone explain that why we should calculate the operations from median on question D?
to minimize the cost. If we take the middle one then the left ones and right ones will give the lowest cost by swapping. If we take any random a or b then the opposite side will not give the lowest cost that's why median is the answer.
The answer can be calculated by accumulating the elements to a particular position i. For such a i, if it moves one position to the right, the answer will increase by rcnt — lcnt, where lcnt represents the elements with positions less than or equal to the i, and rcnt represents the elements with positions greater than the current position. Then for any i, moving towards the median position, the answer must be decreasing, so we have to consider the median.
DEEPWOKEN MENTIONED
A lot of newbies in top 100 .They literally are not letting us to know our real level !!
is f greedily make as many consecutive moves as possible and restore 1 hp if needed?
unfortunately no
Proud to present screencast again
I only plan to link on codefocres rounds which I got #1, Apologize for seeing my screencast comment again, but I am happy and proud to have gotten another #1 for the third time in a row.
The initial intention of the channel is to just show to everyone the performance/speed/consistency was achieved without AI assistance. But maybe I will try to take it in different directions.
Crazy E . Felt like dp problem looking at first
__rose and soulless, there are some unexpected verdicts on problem G that need to be resolved. Thanks
^^ I think this means my test case hacked the official solver. :)
Should we use lambda function in questions involving mo's algo
as it is very common to create insert , remove function in lambda , however such problems are usually along with high constraints and lambda function have additional overhead as compared to normal functions declared globally
so should we adapt y-combinater
, so is the risk valid?
Tutorial when ? Really interest about last problem -> majority elements for multiple query !!
I made $$$O(n \sqrt{n} \log{n})$$$ pass with this Mo's order, lol.
4.1s (very close to 4.5s) but it counts :D
But to 'really' solve this, I'd suspect you'd use something like random sampling ($$$1/3$$$ probability per attempt) coupled with the fact that there can only be $$$2$$$ elements to maybe get $$$\log^2$$$ per query.
$$$O(\log{n})$$$ per query is possible, using segment tree that keeps the top elements.
How would you combine nodes efficiently? As far as I know, there's always been problems with segment trees when you try to combine for any case $$$ \gt \frac{r-l}{2}$$$. Maybe a merge sort tree would work (to update counts on merge) but otherwise I'm not sure how you'd use a segment tree.
Got stuck on F for 1.5 hours during the contest and another 2 hours after it. Then carefully translated the problem on paper into another one: find min(k) such that there exists a set of natural numbers xi with x1+…+xk = d and h+k-1 > Σ(xi(xi+1)/2). Output d+k-1. The last approach took 20 minutes and no need to debug. Submission
Nice Div But it was full of CHEATERS --_--
Agreed. Managed to clear all the python3 submissions on E with hacks, and a lot of the code looked very similar.
Check out my video solution to G!
People are still hacking using Python hash collisions. Didn't we agree to stop that already?
Good job using an array to count items for problem C!
More Blue lock themed Questions!!!!!
16 times submit on problem G. What's a nightmare :(
please quick editorial otherwise problem C will haunt me for days
Try to solve some mex questions then you will get it eventually
For people who solved G using randomized algorithm, what is the lower bound on the number of indices you search per query and is there any way to derive it for a specific n?
Let's assume the worst-case: r-l+1 = 2 mod 3, and there are 2 numbers which occur (r-l+2)/3 times. The probablity of not getting a correct answer with k iterations is approximately (2/3)^k*2, let's denote it as p. We can choose k to be 50 to make this probability roughly 3*10^(-9). Since we didn't use n in our calculations, there are no bounds on n. k that we choose depends on the total number of queries. Math. expectation of the number of queries needed to get the first wrong answer is 1/p and we want it to be much more than the total number of queries.
Codeforces Round 1054 (Div. 3) , this was my first contest in this platform , I registered for it beforehand but it is showing as an unrated contest , I did not get any rating from this contest. Can anyone explain me why ?
After the open hacking phase, all submissions are rejudged with the tests submitted as hacks. After that you will get your rating. This process takes some time for Div. 3 competitions.
It seems that problem G can be simply solved by Mo's Algorithm without thinking.
Can someone please check why my solution for D is wrong?
this my code
for the string "baabbabb", your code is giving answer as 3, but the correct answer is 2 (swap 'a' at index 5 two times with b).
Whoa!! A round that wasn't tested by __baozii__
Great problems either way, tho I couldn't participate
When the editorial will be released ?
Hello, my handle is ShashS02. I am a new user and I participated in this round. I registered more than 24 hours before the contest started, but my participation was marked as unofficial and I did not receive a rating. Could you please look into this? Thank you.
you are not a trusted participant
Because using AI in contests is very bad. I think you'll be banned soon.
Codeforces AI detector is kinda bad nowadays Just seen a guy that is like in the 4th consecutive round using full gpt answers and didnt get caught yet
The questions are interesting (and relatively simple; I like this round),but I need the editorial TAT
After a long time a proper div 3 contest, problems were balanced according to div 3 and also I achieved expert :)
same, but i still feel hard in div.2 or div.1 + div.2
thanks for this wonderful round!
Yay im specialist now
Hii can anyone help me here, Why is my solution to Problem C giving TLE on 7th test case Submission Details
According to my understanding this is still O(n) or max O(nlogn) I'm all ears, It's been a while since i started CP again, maybe I'm missing something Thank you in advance
You would normally be correct that this should be O(n) average time complexity; and the sum of all n is 2*10^5 so this should pass. However, since you are using python, you should know that sets in python are unordered, which means they have O(1) insert on average but O(n) worst case; in the very worst case your code takes O(n^2) to run after inserting n elements each in O(n) time.
This is opposed to c++'s set which is ordered (and does doesn't fall to this issue but instead runs in O(n log n)). The alternative solution to this problem that works in python would've been instead to not use a set to check if an element is present but use a frequency array; a list that counts how many times a number has been seen (e.g. a list named frequency has frequency[2] count how many times 2 has been seen among all numbers in the input).
Alternatively, see https://codeforces.me/blog/entry/101817 for how to make set not immediately break on standard test cases; to put it simply using this class makes it so set becomes much harder to force into the O(n^2) worst case and instead your performance becomes closer to the O(n) average case.
Ain't using unordered_map anymore....F hash collisions :)
well done, good contest. but i can't understand problem G till now, what a dispiriting problem.
340744591 why is my solution wrong cant think of a test case where this would go wrong please lmk o/w
1 5 abaaa
Your code tries to claim you need to swap once (to baaaa), but all the b's are already together and no swaps are actually needed.
I have received a notification that my submission for problem 2149E (https://codeforces.me/contest/2149/submission/340450859) has been flagged for similarity. I would like to clarify that this is a misunderstanding.
This problem is essentially a standard sliding window (two pointers) template problem. There is a very similar problem on LeetCode with the same core idea:
https://leetcode.cn/problems/subarrays-with-k-different-integers/
The solution approach is well-known and widely shared in public resources long before this contest. Many participants likely used the same standard technique independently.
I confirm that I did not share my code with anyone, nor did I view or copy anyone else's code during the contest. The similarity arises solely from the fact that this is a classical algorithmic pattern with a natural and common implementation.
I kindly request a re-evaluation of this case. Thank you for your understanding and fair judgment.
Hello Codeforces, I have received a notification that my submission for problem 2149E (https://codeforces.me/contest/2149/submission/340465979) has been flagged.
The question is basically the most commonly found pattern questions based on the sliding window, which can be found on leetcode. So since I am used to this pattern, implementation in the way that I had done, was the most intuitive, and I was used to it. The following are the leetcode questions: https://leetcode.com/problems/subarrays-with-k-different-integers/description/ https://leetcode.com/problems/binary-subarrays-with-sum/description/ https://leetcode.com/problems/count-number-of-nice-subarrays/description/ https://leetcode.com/problems/number-of-subarrays-with-and-value-of-k/description/ and many more Basically, the technique of using sliding window, but for finding at most k, and then at most k-1 and then subtracting to get exactly k. This algorithm is pretty common, so similarity is based upon mere coincidences, and re-evaluation should be done to give a fair judgment.
I ensure that I have never copied or used any unfair means to write any code. The similarity is all because of its too basic, standard algorithmic nature.
I kindly request you to re-evaluate and give a suitable judgment regarding the same
Thanking you, Solandra
Hello Codeforces team, During the contest I submitted three different solutions. Two of them got Wrong Answer and only the last one was accepted, which shows that I was trying to solve the problem myself.
First submission (WA): [https://codeforces.me/contest/2149/submission/340427928]
Second submission (WA): [https://codeforces.me/contest/2149/submission/340477792]
Final submission (Accepted): [https://codeforces.me/contest/2149/submission/340479653]
I kindly ask you to understand my situation and review my case. Thank you.
Obvious AI
Hello,
I usually work on one file and when I move from one problem to another, I just delete the old code and write the new one. For this problem, I submitted three times.
In my second submission I handled freq[k] with a separate +1 condition, which was not correct, because it could overcount or undercount depending on the test case. In the final submission I fixed this by using ans = max(missing, freq[k]), which correctly balances between the missing numbers below k and the occurrences of k. That’s why the third submission was accepted. Best regards, Mohamed
That's not even why it is so obviously AI
Ok, what should I do? I was just trying to solve the problem, but you’re not trying to help me.
Stop using AI
Subject: Appeal re plagiarism flag — submission [340485399] for [Problem 2149E] Dear Codeforces team and round coordinators, An automated message was sent to me that my submission [34048539] for [2149E] has considerable concordance with submissions with the IDs (beardly/340475079, Skylight_ 422/340481158, IamKeviN69/340481986, Vimlendu2003/340485399, AdelO_mcc/340502599), although one of the Id among them is mine itself as Vimlendu2003, cited in the notice. I would like to put forth an explanation and request some leniency on blocking my account. The problem was solved by me in the actual contest. While testing on an online compiler/paste service, I accidentally left my code public. Now, I do realize that this was a violation because code exposure can lead to a sudden presence in the realm of other contestants. So to be clear: I never intended to share the code with anyone, nor was it handed over to me by anyone. This was my slip-up, and I take full responsibility for the accidental leakage. The following measures have been adopted in order to ensure that such an incident never occurs again: 1. I will not be using any paste/online judge service for contest code. 2. My tools have been set by me for only private/local testing by default; 3. I have gone through the Codeforces rules (blog entry 8790) for a better understanding. I accept fully any penalties given by the jury in accordance with the rules (e.g., disqualification of submission/rating rollback), and I respectfully request that my account not be blocked as the action was unintentional and the cause has been eliminated. Codeforces means much to me, and I want to stay fair and continue learning in future rounds.
Thank you for your time and consideration.
Vimlendu Sharma/Vimlendu2003