Привет, Codeforces!
Команда ТГ канала @KogutIvanTutoring рада позвать вас принять участие в Codeforces Round 1016 (Div. 3) во Apr/08/2025 17:35 (Moscow time) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов, после её завершения все успешные попытки будут перетестированы на успешных взломах. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи были придуманы и подготовлены частью нашей команды: fstilus, EzikBro, _icy_, Boodoochai, pskobx, gravitsapa
Также большое спасибо:
MikeMirzayanov за системы Polygon и Codeforces.
Vladosiya за координацию раунда.
a.stepanov281005, reshke, Pagode_Paiva, AC_sahER за оранжевое тестирование раунда.
Alexbrii за фиолетовое тестирование раунда.
Friendiks, Wileyne, margothequeen, Tainel, darysani, Pistol_Engineer, CarlosS48 за синее тестирование раунда.
im_sad_now, veliak, harpreet1237 за бирюзовое тестирование раунда.
NeNichiy, alice19, Telyatnikov_Mikhail за зелёное тестирование раунда.
Всем удачи!
UPD. Разбор выложен!
As a tester, problems are very interesting!
As a tester, I can assure you that the problemset is interesting, and the round will be enjoyable.
As a participant, I do not trust the testers
I am a big fan of those testers
cry disappeared
As a tester, you will enjoy solving the problems..
why isn't there any grey(gray) testing of the round considering its div3?
Finally
YEAH! YEAH! YEAH!
Although unrated, i still hope i will enjoy this round
Saving this—hopefully, I'll need it in the near future! :)
Good Luck for every specialist contestants to reach expert
Finally excited for my first unrated contest
Yes, I’m ready to be back to CYAN, inshaAllah!
400 contest is insane. mad respect!
Thanks a lot, brother.
I'll try imitate rainboy in this round.
As a tester, problems are very interesting!
As a tester, problems are very interesting!
hopefully my journey of ending failure will start from this contest
I am excited to participate with my new monitor set-up today..!
Why did this dude TrinhTranPhuongTuan banned? Cause he got top 1???
Cuz he chichtranxongtron =))
In G are the sample testcases correct?
first time ak div3! ヾ(^∀^)ﾉ
this was my first div3 AK as well. funnily enough i spent the most time on D lol
nvm my E got hacked LMFAO
Perfecto
Perfecto
I am never writing a div3 or div4 again.
Why?
Although i didn't participate in this round, i've read the problems and i think it is one of the best div3s i remember
There were better Div3's ig
I believe, but i didn't say "the best" and i didn't say "among all div3s"
Yes Div3s by cry are top-notch.
vovuh's Div 3 is the best
The hardest div3 I have ever seen(for me)... can't solve G, get plenty on C E and F stuck on B for 10min, F for 1 hour, I'm too weak :(
So can anyone tell me how to solve G?
UPD: now I know why I can't solve G.
Well, I now know why I couldn't solve G. I was stuck on calculating the maximal dissimilarity group and kept thinking about the following:
maintains a ds such that it supports the following operations:
But really, you just need to two pointer scan the array, and then deal with the contribution to the answer from the element currently pointed to by the right pointer, which is a classic 01-Trie problem. Regardless, the quality of the questions in this game was very high and I love it very much!
I think perception makes a big difference. Specifically, I would probably normally spend more time than I did on F if my speed were on par. But I solved A-E very slowly because of mistakes and thus knew I had to get F quickly, so I did in 20 mins.
To solve G, we use a trie to get the max xor, then iterate over l and find the nearest r to get that max xor value.
Thank you very much 111
Can you suggest some resources for learning this data structure pls
cf edu seciton teaches tries and segtree -- that's where I learned this application of tries. the edu section is not very big, but the topics it does cover are very well taught.
https://mirror.codeforces.com/blog/entry/123404
Is O(N * M * M) solution feasible in problem F ?? This is equivalent to 1e8 operations. One of the codes passed the TCs but I doubt about strength of TCs.
Expected solution is in $$$O(n*m)$$$. Actually, F was easier than D, E, and even C in my opinion, because there is no edge case.
yes.
I overkilled F in O(n*m*m) although couldn't solve in contest courtesy to D.
Good quality problems. I made so many stupid mistakes lol and so I didn't get time for G, but I knew immediately that we can just use a trie to get the max XOR, then iterate over l and find the nearest r such that a[l]^a[r] = max_xor.
I do have one contention though -- tries in div 3 problems. It's not that tries are too difficult for div 3, but rather there are much better alternatives, like some graph problem or something. This is probably the third time I've seen a trie in div 3.
Why does it have to be ==max_xor ? Maybe their xor is < max_xor but >=k ?
Oh yeah, my bad. It's been that kind of day where I just delete parts of the problem statement from memory lol.
D was very wrong placed , i spend my entire time on d why there are lots of ac in d ??
there are too many cheaters ...i looked at the number of submissions while i was solving c,i was dumbfounded -_-
yes, you need some serious practice to solve d fast because there is very large scope of errors and i wonder people solving it very dammm fast
although i couldnt solve D ,but a lot of people solved E before D , so i think the position of the problem wasn't right...and yeah people just solving the probs damn fast
i just chatgpt it after the contest and solve it on first go without hints :\
D is actually an easy problem, but i didn't want to write a dfs so i skipped it first, but i didn't realize the binary research at first so i wrote D 40 min later and then go to E. /Cry/
Why my 314649703 for E — Min Max MEX TLE?
I haven't looked specifically at your code, but I got TLE 2 times before realizing that we should ensure we are only ever checking the predicate for mex values <= n/k, which will ensure a O(k*mex_val) predicate is O(n) at most.
check my way of knowing mex till now -> intialize set and intialize mex with 0 and just do while(set.count(mex))mex++; and as u go left to right just add elements in set
I wonder, don’t you have any testers to tell you that this contest is bad? I’d like to know what you were thinking when you included problems C and D. Problem E was much easier, except for the text of problem F. Are we here so you can test our ability to read English?
This contest was a waste of time.
When I’m not good at something, I leave it to someone else.
fr wasted too much time on d and e was simple bs and just bcs of d, could not solve E
The order is incorrect and the problems are bad.
understood we dont need to blank all incorrect pos we can just do it one by one thanks
b a k A4 timesd s D twith $$$j=2$$$d s D ta X b Ywith $$$j=1$$$a X b YSet all c to the network 5 (u, s, k, J) => 4 ops
Replace j = 1 (*, s, k, J) => 1
Select network 3 (a, s, k, J) => 1
Replace j = 4 (a, s, k, *) => 1
Select network 2 (a, s, k, A) => 1
total = 4 + 1 + 1 + 1 + 1 = 8
i am retarded
sorry for my bad presentation on my explaination :((
nah ur explaination was good I was just thinking Why I couldnt understand this during contest , this testcase is itself solution ig
wtf was D bro I wasted 1.5hrs on it. I should have solved E before it was simple binary search
I feel like my solution for E is hackable because I used sets instead of arrays to track which elements have been filled so far. More than 1000ms in C++ is not good news...
Link to my submission
Hacks appreciated
E was easier than B
lmao, I got like 5 WA's cuz of forgetting to check the power of the primes in the prime factorization.
u must have mistaken my E for C
yes I did. cough cough.
bro I got WAs from forgetting 11 is prime lmao
and I was counting 1 as prime got 4 WA
I got no WAs on B and C both...and i knew that we have to use BS on E but how to actually do it can you plz share the code and approach for E and for D i had no clue
just go to my submissions from profile
remember what you say(*ˉ︶ˉ*)
i submit your code twice，oneAC，one TLE18，so possiblely it will fail on retest
oh no ;(, I should have improved sol
you guess what，my code is as same as you(^з^)
Please say that again now xddd !! So many TLEs.. Generally, majority of us (myself included) are habitual of using set to track elements but that additional logarithmic factor caused problems I guess, so the Setters probably intended us to use a boolean array. So yes in that sense, E is suitably placed.
But yes, original Tests should not be that weak as this is unfair for the participants to not even getting the chance to optimise their approach further..
It was more of a div4 than a div3.
Why the authors in recent div3's have removed the notes section from problem statement $$$?$$$ In today's contest, there were no notes except for task $$$D$$$.
What is the corner case in G? I'm creating a trie of all seen numbers and searching as follows:
if k has this bit 0 and we can make this bit 1, then simply return the max index of any number seen so far that does so, otherwise continue down the tree.
if k has bit 1, make sure to take the branch which makes this bit 1, if there is no such branch, then return -1. If we reach end of the tree then return the max idx as we must have atleast matched the value of k.
Lets say you are in position i currently, and looking for the j-th bit of v[i]. Assume that j-th bit of k is 0, then there is a chance to get xor value bigger than k. But in that case your program immediately returns biggest such position p1. Maybe there is index j2 < j, where j2-th bit of k is also zero and you have a chance to make xor bigger than k as well, and there is a position p2 > p1 which satisfies this conditoin. In that case you miss better answer of i-p2+1, and take just i-p1+1.
Thanks a lot. That makes sense. Now I wonder how to handle this case since I cannot do the search for both children. Maybe I can precompute as k is fixed and not a part of the query.
You do not need to search for both children. I updated your code and it passed 314663898.
Thanks, that's so kind of you!
I read this probelm is very intersting but i found some cheater in this contest. How can report them?
In problem c, is there exist any prime number greater than 1000? someone pls help...:(
yes
???
Problem D is litteraly to toxic to put in a D div 3 i think even G is more straight forward and easier than D (although i didn't solve G cause i ran out of time)
We can swap D and F basically..
So true, F was so baddddddddd. I dont know what were the authors high on while keeping F at F
I gave up after getting WA on test 2 for 1 hour =))
I used binary search and tests were not passed just because 1 << N... (it has to be 1LL << N). Studying always hits us...
Why the problems dont have notes to explain the example test
nice Codeforces round!!!
A: Usaco dirt forces
B: Codeforces ig
C: bro took some inspiration from that one educational round
D: where is suhas nagar in the credits
E: should be C
F: reading comprehension forces
G: idk not strong enough prob some ds lets be real
I completely flop another div. 3 again...
orz Lever.
Was problem $$$G$$$ solvable using Trie and two-pointers ?
Solved using Trie without 2ptr: 314650347
Page is temporarily blocked by administrator. Why codeforces is not allowing to view solutions of other users.
Can you share the solution in pastebin
Trie is enough, no need for two pointers: 314637977
Today's G was so similar to this problem: https://oj.uz/problem/view/IZhO12_xor
Here is my screencast of this contest along with the solution ideas and thought process: https://youtu.be/6suW6LZyYtY
I am planning to do more of these videos if my schedule allows it.
orz
Lol this absolute bruteforce passed for C
what is the possibility that using unordered_map in E causes hack?
do not use umap or uset in CF because it can be O（n） if hacker read STL code to hack you
We have numerous "unexpected verdict" E hacks, which usually indicates std also fails lmao
It's more likely that one of the testers' solution failed. It happens when anything that's marked as correct on Polygon fails, not just the main solution.
Hope to reach pupil after rating changes.
Hi friends, it was a good contest, thanks to all friends
Hoping to reach pupil after rating changes. Wasted too much time debugging D.
While it is obvious that a basic and direct bruteforce applying k <= 7 would not pass, the reason it is not higher is because of multiple edge cases. See below for extra details, in case you want to try to find the edge cases first.
(Hint 1: try googling) (Hint 2: At least one example exists in k <= 100).
The repunit primes (primes of the form 111...111) are all edge cases. 11 is simple enough to find in contest, but n = 1, k = 19 or k = 23 would be a nightmare to find, especially without doing googleforces in contest.
Relevant wikipedia/OEIS:
https://en.wikipedia.org/wiki/Repunit#Decimal_repunit_primes
https://oeis.org/A004023
This is exactly what I found during the contest as well as I thought there must be some corner cases with n = 1. Fortunately, I later saw that k is restricted to just 7 and I could just use the naive is_prime routine for all cases.
bruteforce
This is why I specifically mentioned "basic and direct bruteforce".
This manages to run in polynomial time relative to the length of the number, rather than the expected exponential for the intended solution (which uses the fact that the number does not have to be iterated over.)
I'm not sure if those bases alone are enough to catch the edge cases (since the solution is actually probabilistic in nature and is only guaranteed to work because of the usual compprog bounds) but this solution would in theory be able to catch the edge cases I mentioned. If k instead allows for the 4th edge case to happen (see the sequence for what k this is), you might need a slight improvement in the code to get this to work (or they need to set t <= 10). Either way, this version of the problem would be around Div3F because you either need to googleforces or run this optimized bruteforce.
Here's a list of valid k's with x = 1
Please make Div3 and Div4 contests unrated. Today, most of the D problem solvers used AI, and on the other hand, G was also solved by AI. With this rising amount of piracy, most of the noobs are just rushing for ratings.Or use some ide so that copying statement becomes impossible.
Yeah, I tried it with claude after the contest got over. It solved the problem in one go.314662411
D is a pure implementation problem, why would it have more AI usage than the other problems? G is also a very classic problem, you really don't need much to solve it (just knowing that pairwise xor problems sometimes can be solved using a trie is enough).
I cannot understand arguments like this. Should we unrate div1 and div2s as well? LLMs can usually solve problems A through E in a div2, which is more than enough to carry anyone to master.
I didn't mean to support the argument to unrate the div3 and div4, I was just agreeing on the part that D was solved by AI. I don't think we can do much about cheaters, we just can enjoy solving problems.
One of the best div3s <3
wdym you really think F was worth F?
the writers of problems can't get the time complexity right and exclude wrong solution, but let others hack the accepted codes after contest, this is so rediculous
I mean, I am doing ACM, not OI. If my solution is completely wrong in time complexity, I get penalty, not first "Accepted" but then "solved -1". Try to imagine that if a question tells you to calculate a * b, but you mistakenly put a + b. However all of tests of "a b" are "2 2" or "0 0", and you got accepted and didn't notice the mistake. Then after the contest, you code is hacked. Of course it's partly my own fault, but don't you think that's a little bit irresponsible?
how the hell did this submission get hacked? Isn't it n(logn)(logn) Link
maybe not TLE but WA
the hack verdict says tle
There are a lot of solutions using
std::set<>orstd::map<>getting hacked.Not sure what the case is exactly. The slowest case I can think of is $$$n=2×10^5$$$, $$$k=1$$$, $$$a = [0, 1, 2, 3, ..., n-1]$$$ but if I run your code locally it only takes like 800 ms.
Maybe the CodeForces judging machines are especially slow when it comes to dynamic memory allocation or something like that.
Yes exactly, at worst there are n elements in the map taking logn time and the binary search adds another log factor. 2×10⁵×(log(2×10⁵))²~~10⁷. Are the machines this slow?
creating multiple sets requires more overhead space(setup cost is higher) as compared to creating single one storing it all, also using unordered_set was a much better choice over given n and max value of a[i].
I just made a single map for each search, I can understand it is a bit inefficient but I looked at the boundaries and did not much care about these little things. Looking at the number of hacks in E, something seems wrong
For reference, here is a similar submission but in python look at the difference in execution time
While practicing problems on Codeforces, I’ve noticed that in some cases, especially when there are many duplicates, using set & map often gives better TC than unordered_set & unordered_map, so I’ve generally preferred them. However, in this contest's E, my solution got a TLE on test case 67 during internal testing, possibly due to test cases added through hacks. After system testing, I tried replacing set with unordered_set, and surprisingly, it got accepted. It felt a bit odd, and I’m still not entirely sure why that happened.
std::unordered_set<>andstd::unordered_map<>are backed by hashtables so insertion and deletion take $$$O(1)$$$ time on average, which is faster thanstd::set<>andstd::map<>, which are backed by balanced binary search trees, which take $$$O(\log n)$$$ time on average.Usually the unordered variants are also faster in practice. However, the unordered versions are vulnerable to hacking due to hash collisions, see e.g. this blog post: https://mirror.codeforces.com/blog/entry/62393
For this particular problem it's not really a concern, because the attack requires inserting elements that are a multiple of the bucket count, while in this problem, the elements of the set are smaller than the maximum size of the set, so the attacker cannot create many collision.
However, in general, it's best to avoid using plain
std::unordered_set<>andstd::unordered_map<>in contests that allow hacking. (Or at least harden them with randomization as explained in the blog post.)Python doesn't suffer from this because its hash tables have randomization built in. Java's hash tables revert to using balanced search trees when too many keys collide, so e.g. HashMap eventually reverts to the performance of TreeMap in the worst case.
So, in general, what's the thumb rule (or is it entirely constraint dependent) for these kinds of problems? I usually stick to using set and map instead of their unordered variants, but in this case it was topsy turvy.
For this problem, you could just use a
vector<char>orvector<bool>to mark elements which you've already seen.That's what I did: 314567229, search for
can_solve().This technique is generally useful when you have a set or map where the keys are a small range of integers, or something that can easily be mapped to a small range of integers.
You just have to be careful about how you initialize/clear the vector, since it can be larger than the input you are processing.
For example, suppose you are given a problem where you get arrays of integers, and you have to output for each array how many distinct values it contains. It's easy to implement this with a std::set or std::unordered_set. But you can also maintain the set in a vector or bool array.
The solution is strictly O(n) per case, and while that's technically the same as if you'd used a std::unordered_set<>, you'll find that it's much faster in practice because indexing an array has a significantly lower constant overhead than finding an entry in a hash table.
with due respect, problems $$$D$$$ is not a good problem
great contest, A-E were great, the only nitpick is that i wish D was placed at E
I have huge problems with Problem D...
Never saw such an easy F. Literally it was easier than C
D and F could be replaced
I think future problem authors could notice a small problem.
When we think about the MEX of an array $$$a$$$ of length $$$n$$$, it is obvious that we only need to focus on value $$$a_i$$$, which is less than $$$n$$$.
So problems like E have no necessity to make $$$a_i\le 10^9$$$.
Some participants, like me, may ignore the range, using
int c[200005]to save the occurrence of a value. And get RE as a result.But I don't think this is an interesting thing.
Nope,this is called coordinate condensation,and also a technique.Some problem like segmenttree/mo'algorithm also met the same problem,for n only up to 2e5 but the element up to 1e9 this require you using hashing technique
You didn't catch my point. Under the background of MEX, those $$$a_i \gt n$$$ are quite meaningless.
Did you mean discretization?
Could anyone please explain problem D? Spent so much time on it but still couldn't figure it out :( TIA
divide it by four parts and dfs
Автокомментарий: текст был обновлен пользователем Kogut_Ivan (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by Kogut_Ivan (previous revision, new revision, compare).
yehhh, this is a first contest i can clear on time
Got hacked in E
me too
Who thought F should be F among the testers (and D be D). Meet me personally
And who tested E..
Call me too, despite having so many authors and testers this is pathetic
Fucking E, set got TLE :)?
I personally found particularly D, F and G really fun and educational. Thank you :)
i feel F is the easiest of all C,D,E,F
E is exactly the type of codeforces question that makes me want to quit sometimes. I used a (properly randomized) set to keep track of items in the current subarray, and I got AC, with a runtime of 1700ms. I assumed that the test setters had created strong test cases, so I moved on to F, and after getting it I finished 180th in the contest. This morning, I found out that I had been hacked.
Apparently, the intended solution was to use a boolean array instead of set. However, both solutions worked during the contest, and they both have the optimal space/time complexity. Is there any way during the contest to figure out that a set is in fact slightly too slow, or is it just luck of the draw? Kogut_Ivan y'all need to make better testcases...
no in div-3 you can't expect the perfect test cases , it test cases had to be perfect there would have been no point of hacking phase , as your solution(1700 ms) was too close to time limit , you should have optimised your solution during contest
What's the point of having a time limit then? With the weak testcases they had, even a 1000ms solution wouldn't have been guaranteed to pass. If they're going to set the time limit low enough that a very natural solution to the problem (with the right space/time complexity) doesn't pass, they should at least make testcases that exclude that type of solution instead of letting us find out 10 hours later during the hacking phase, with no chance to correct our code.
Accidentally spotted very suspicious participant: https://mirror.codeforces.com/submissions/KS_star/contest/2093 Obfuscated code with names a,b,c,...: 314628685 314630580 314632645, and all solutions submitted within couple minutes
Problem D giving TLE in test case 4...can anyone help me with this recursive approach.
len*lenoverflows.thanks for such interesting problems . i just love this contest
Hello Codeforces Team,
I am writing to sincerely apologize for unintentionally violating the rules during Codeforces Round 1016 (Div. 3), significantly coincides with solutions Samad_2g/314636123, RubayetRafsan/314640595.specifically for problem 2093D.
Both of the accounts Samad_2g and RubayetRafsan belong to me. I submitted the same type solution from both accounts during the contest without realizing that this was a rules violation. It was a mistake from my side due to a lack of understanding, and I had no intention to gain an unfair advantage.
I now fully understand that participating with multiple accounts is strictly prohibited. I assure you that I will never repeat such a mistake again.
I kindly request that you keep my main account "RubayetRafsan" active, and I’m completely okay with "Samad_2g" being blocked or deactivated if necessary.
Please accept my sincere apologies, and thank you for your time and understanding.
Sincerely, RubayetRafsan