Привет, Codeforces!
Рады пригласить вас на Codeforces Round 773 (Div. 1) и Codeforces Round 773 (Div. 2), которые пройдут в 23.02.2022 13:10 (Московское время). Обратите внимание на нестандартное время начала! Раунд будет рейтинговым для обоих дивизионов. У вас будет 2 часа на решение 6 задач. Советуем прочитать все задачи.
Задачи основаны на олимпиаде RocketOlymp, и были придуманы и подготовлены __silaedr__, allvik66, alegsandyr, ilyakrasnovv и isaf27.
Большое спасибо
isaf27 за великолепную координацию, ценные советы и терпение
Renatyss, stepanov.aa, mutant, Siberian, kirill.kligunov, arbuzick за помощь при обсуждении и разработке задач
AlperenT, ArtNext, EvgeniyPonasenkov, FedShat, Qwerty1232, TeaTime, TheEvilBird, competitive__programmer, generic_placeholder_name, philmol, silvvasil, tox1c_kid за качественное тестирование и полезные предложения
pakhomovee за задачу, которая не вошла в финальный проблемсет
MikeMirzayanov за отличные системы Codeforces и Polygon
Участникам олимпиады категорически запрещается участвовать в раундах на Codeforces параллельно.
Удачи, высокого рейтинга и удовольствия от решения задач!
UPD — Разбалловка:
div2: $$$500 - 750 - 1250 - 2000 - 2000 - 2500$$$
div1: $$$500 - 1250 - 1250 - 1750 - 2250 - 3000$$$
UPD — Разбор
Notice the unusual time (returns back)
All the best everyone, may the force of positive delta be with you!
Thank you ,Morty
thank you (though it hits me like "positive delta variant of covid" lol
scoring distribution when
scoring distribution when
The unusual time strikes back. For once, I can skip my classes with an actually good reason for it.
In many countries, people usually participate in codeforces round late at night or early in the morning.
Usually I get to participate in 11:35PM (UTC+9)
The good thing is that one participation can count as two days of streak, if I solve at least 1 problem both before and after midnight
yes. always 22:30 in China.
So this unusual time is really friendly to Chinese participants.
because it is afternoon <3.
not that friendly. dinner time.
Friendly for Chinese students, not so friendly for us working in companies :P
The problems were not friendly at all.
I think the IST is blessed in this case.
Dinner time bro :(
Still better than sleeping time :)
Actually it is 13:00 in Russia
As someone in the PST timezone, I cannot wait for this new experience of writing a contest at 2AM in the morning :D
Update:
Using a sample size of the last two contests, I conclude that I perform better at 2-4AM compared to 6:30-8:30AM.
today's codechef round is at the normal time of cf, so we have two rounds today.
Do you participate in all CodeChef's rounds?
Why not?
By the way, this round is amazingly friendly for Japanese. Not only the round starts at 19:05 for Japanese but also Feb.23 is one of our national holiday! Thanks!
in Russia 23rd of Feburary is also national holiday! It's Defender of the Fatherland day
From Japanese?
.
sbke liye nhi laxman
Score distribution?
Yay, waking up at 2 am on the West Coast will be so fun,
Can anyone tell me the what would be the rating of Yesterday's Edu C contest — Inc. Subarray sum ?? I want to practice such type of prblms
I don't have much idea about the rating of that problem but I suppose you may get better results if you ask on the respective contest's announcement/editorial blog.
Rating will be added of the problem in some time
After the last round, I think I have a chance to get into Div. 1. But since the ratings haven't been updated yet, I can't register for Div. 1. Only an hour and a half left, do I just sit tight and wait? What happens if I register for Div. 2 now and then get promoted right before the contest starts?
If you register for Div. 2 and get promoted to Div. 1, your registration will be transferred to Div. 1 automatically. Best of luck for today's contest!
I have the same problem but the reverse of it XD.
I am going to return expert but since the ratings haven't been updated, I am forced to register for Div.1 it's not a bad idea for me but I don't know what will happen if the rating get changed later
Yay, I got my rating change and the passage to Div. 1! Thank you to the Codeforces team! The color didn't get updated though, so I guess I'm gonna be a blue spy in Div. 1. :D
Edit: it got updated while I was writing. :)
Good luck and high rating!
Delay by 5 minutes
note 5 minutes delay
Delay 5 minutes ...
unfamiliar time, familiar delay. :(
Is it rated?
m1,m2,m3 do not load.
Yes it's rated ...
SpeeeeeedForces
Me wondering what to do after A,B,C
Do D
The difficulty gap between c and d was huge
Speedforces for sure
The gap between C and D is tremendous
Is it just me or some of the statements were kind of difficult to interpret?
We could guess how much thousend of partitipants left because of bad statement in A.
why
C<B<A<<<D ??Specialists and pupils after solving A,B,C fast
Me after solving A-B-C in the first 20 minutes and not knowing what to do for the rest of the round ...
That's unfortunate, anyways for future rounds keep in mind that after solving A, B, C you should try problem D.
Figures in A are very huge , hope to be moderate next rounds
Really unbalanced contest, you have my heartfelt downvote.
E should be "cost" more. Its much harded than D (according to standings)
IMO, D has a very nice solution !
Indeed. Just one observation and it's a nice constructive problem.
I wasn't able to solve D, But I think the solution is like in this direction. 1) If any elements occur odd times then the answer is simply -1. 2) We will choose the first segment where ar[end]=ar[start], initially start=0, We can this make segment good(or whatever they say) by doing at most segmentLength-2 operation. these operations may add extra segmentLength-2 elements, but we can handle these elements in the next segment. I think we need to repeat this step till we have no remaining elements.
Correct. The most important realization is that the extra added elements will ALWAYS be possible to pair them in later iterations.
I think it's easy to prove that the extra elements+ rest of the array will not contain any odd element and hence we can make the remaining segment good also.
Wow! I was thinking in the wrong direction probably: I thought of making array such that a2i-1 = a2i, for this we can swap elements until it matches with the same number.
Swapping can be done as follows:
Let's say we have to swap x and y in the sequence, then [x,y] -> [x,y,x,x] -> [x,y,x,y,y,x]. If you observe carefully first 4 numbers sequence is good (tandem repeat), and we are left with [y,x].
Maybe some more thinking/observations need to be done in this method. Has anyone solved D using the same/similar idea?
I did, but the program made an error in the second test https://codeforces.me/contest/1642/submission/147465343
I got this observation but could not handle the implementation part.
You can also "reverse" a segment. For example going from abcd -> abcdabcddcba. The junk part added is a valid subsegment. So just sort the array using this
I passed the problem. The previous error is because I didn't increase the offset under special circumstances. I just added one line to the code in the contest. :-(
Wrong answer Accepted
how to solve A?
The answer would always be 0 if no side is parallel to the x axis. If a side is parallel to x axis , and the third point of the triangle that doesn't lie on that side is BELOW the parallel side , the answer would be the length of that side parallel to x axis.
I did the same. Could you pls share your solution?
Damn only able to solve Problem B...this contest is really unbalanced btw does anyone feels like problem A > problem B
No. For me it was just a basic geo problem . But this time A has less solve idk why
Took me two minutes and a half to see the image of problem A !
Time limits in B and C. It was the last contest for me on Python. I'll go to learn c++.
D was next level adhoc.
.
Can you explain your solution?
.
Ready for downvotes :)
got FSTed on C too ;(... wasnt prepared for this
What is the intended complexity of Div1D? I did N2^Mlog(2e9) and its TLEing :((((
$$$O(n 2^m \log n)$$$ passed in 2950 ms :)
I turned on the setting "show only trusted participants by default" in this round. It seems that for div2 this setting really removes a lot of suspicious participations.
rating update should be with accordance of number of registration and rank. Not in accordance of number of submission and ranks.
If a user registers and doesn't participate then his rating is not affected at all then why should his registration affect the ratings of other people?
Can someone please explain who fall in to this "trusted participants" category?
This happens in div3 rounds, check This post for example.
But I still didn't understand what's the point of removing them from the official standings if their rating is anyway going to change
In order to stop them from affecting your rating, so if hundreds of new un-trusted accounts made by div1 users took part in the contest and solved more problems than you, they won't affect your rating.. they will get rating changes but they won't be part of rating changes calculation for the rest of the participants. (you will get better rating)
that's what i understood. If someone thinks that I'm wrong, correct me please.
I though that Div1 doesn't have cheaters, but it does: sol1 sol2
in DIV2C ,is there any need to sort the array or check whether a[I]%x==0 or not before finding a[I]*x in our map ?
You do need to sort it or use something like a set. But why would you check
a[I]%x==0i got WA for not sorting, because you can get arrays like 4 1, when (1, 4) should pass but without sorting it mistook with this result (4, 16) (1, 4)
Successful SpeedForces round, nothing else to say
exactly
too standard round
poggers sus amogus tokyo ghoul
Why is time limit for D1D so tight? My solution is $$$O(n2^m)$$$ but it runs for 1500ms even after optimizations, but some people's $$$O(n^2/w)$$$ solution runs under 500ms.
Another fun fact: I gave a problem using exactly the same idea as E in a Chinese OJ contest in Feburary 18th. However I lacked time so I didn't pass E :(
I wonder why someone would put 3 pictures with a total of 1.45M in Div2 A?
Can we please have the editorial ilyakrasnovv?
why many programmer pullout of contest without submitting any solution if first and second questions are tough or not easy to understand.
It is not about tough, it is about high probability of getting the problem statement wrong.
A and B weren't too interesting. I don't think A should be in div1 contest, B was not bad though.
C was similar to APIO 2012 Guard but not too much, I liked it. I wasted lots of time trying to find the similar problem tho :(.
D reminds me of USACO 2018 Cowpatibility, but I haven't thought much about it yet, solution is definitely very different.
https://codeforces.me/contest/1641/submission/147415490 Can someone explain why this solution for Div2C/Div1A got a TLE? Is there some quirk with unordered_map I don't know of?
you can read about why you TLE'd using unordered_map here:
https://codeforces.me/blog/entry/62393
Wow. So I have to use a patched unordered_map on contests. Wish I could know that beforehand. A warning like %lld/%I64d would have been nice.
Though I guess it's just a reminder that you should always be careful around hashes. And a small price to pay, since it's the A. :) Thanks a lot for the info!
https://codeforces.me/contest/1641/submission/147500413 got AC with the same code on C++20.
Why are the TLs so tight? I wrote a $$$\mathcal{O}(n \log^2 n)$$$ parallel binary search solution to problem C, and it TLE'd. Had to use Van Embe Boas tree instead (147441626) to pass >_>
i think because solution is O(n log n).
Yes. And the only thing you should use is Segment Tree with $$$O(log{n})$$$ descent instead of binary search.
I used nothing but std::set. Definitely not tight TL for such sol.
Can you explain what is Van Embe Boas Tree? Or some material to learn it?
Stop learning useless DS and algorithms, go and solve some problems, learn how to use binary search. :)
https://www.google.com/search?q=Van+Embe+Boas+Tree
Searching for the answers yourself is another essential skill to master.
See, it even corrects typos for you!
A statement was very confusing
I know how to solve problem D,but it's not easy to finish the code.
In problem B, at first I use vector to insert two integers, then I got TLE on 4. After I replaced vector by an array, I passed. Why can't you just enlarge the Time Limit so that those who use vector instead of array could pass?
The huge pictures in 2A slow down the loading of the page. The coordinates and sizes of the example triangles are not that large and there are extra space that could have been cropped out.
I'm almost certain this is unintended but I have a $$$O(\frac{N^2}{64}+N\sqrt{N})$$$ solution to d1D that passes pretests in under 500ms.
We just sort the arrays by $$$w$$$ then for each element, we just store a bitset of which arrays are incompatible with it.
Of course, storing $$$nm$$$ bitsets is too much memory, so let's only store it for elements which occur more than $$$\sqrt{N}$$$ times. So we need to add another $$$N\sqrt{N}$$$ to complexity to handle elements that occur small number of times, but it's fast.
Meanwhile, my $$$N 2^M \log N$$$ solution required extensive constant optimization in order to pass...
Thanks for your great solution! I learn a lot from it. It is a wonderful idea!
I think Div.1 B shouldn't put at this place. It should be dressed with more confusing skins, added more strange limits, made impossible to code, and placed at Div.1 F. It is a great idea of mass destruction, Div.1 B is a waste of such a great idea.
Maybe this question is very strange. Why $$$n \leq 3 \times 10^5$$$ in question B but $$$n \leq 2 \times 10^5$$$ in question C? Different upper limits make me RE.
How it could be!You just copy the limit before.It's ugly.Reflect your behaviour before blaming the problems.
Why Tle on div2 B
It's time to read this :(
Maybe there is a too big gap between problem div1.B and div1.C. But I think it's very good to make some challenges.
Oh, I made a mistake. I mean that the gap is between div1.A and div1.B.
Idk why I laughed so Hard my brother was sleeping. Damn its too Funny Man
404 — your rating not found
Do you know why did you get TLE for tc 10 on div1 A? I am not able to find what's the problem with your code.
I do the greedy solution from small to big , and create many useless values in the map . It can be $$$O(n\log^2n)$$$ in the worst case.
trash pretest QAQ
I got TLE on both B and C for using unordered map while it got accepted when I replaced it with map :(.
I used custom hash in my unordered map and got accepted. see my submission
bro I had used map even though its giving tle,why?147437440
bcz u are iterating over a map, accesing mp[b] will add a new element in map even if b is not present in the map, so it will become an infinite loop.
Me too ,and I will lost a lot of points......
Wow ， You have strong pretest in Div2 C / Div1 A
I think the main idea of div1-D is similar to this problem(except parallel binary search): https://codeforces.me/problemset/problem/1285/F
I applied the exact same idea and passed, I don't think parallel binary search is needed.
DIdn't solve D cause of one line of code. I want to kill myself lol
FSTed C due to 1 line of code ;(
This round is typically speedforces with weak pretests. (Div 2A is confusing and makes a lot of people quit, that's why so few contestants in div2)
When the difficulty gap between two problems are very large (like C and D in div2), then the ranking of contestant will depend on the speed that solve these easy problems. If you get stuck on one "easy" problem for a long time or make wrong submission, or failed the system test (the pretest of problem div2C is so weak), and you cannot solve hard problem, you will be finished.
Personally I don't like this kind of contest.
I don't either...
Hello guys ! Can someone explain to me why is that a normal set is faster than an unordered_set , the only operation i used on them is inserting elements and getting the size !!
due to hash collisions, the time complexity of unordered_set per operations can be up to O(n), you can read about it here
I request all contest writers here that guys please make some strong pretests.You will get nothing by trolling participants.
ou yeah, another trash round, bad pretests C + no balance
A GOOD FST ROUND
Can someone suggest any test case where this gives WA (pretest aren't visible). Logic: For k = 1, answer is number of distinct power ups. The if minimum frequency element currently is 1 then it answer is same as for k-1.
Test:
1
4
1 1 2 2
Right answer:
2 2 3 4
Your answer:
2 3 3 4
Pretty fast systests!
Why are submissions still hidden ?
Good contest guys but I think you had weak tests for C. My submission https://codeforces.me/contest/1642/submission/147435078 is AC. I used a multiset with count. And I found out that count is actually really slow in multisets. So it shouldn't AC for the following example input. It should TLE.
I solve Div1D with such a randomize:
for every element x we determine f(x) as a random number in 0...19
then for every i=1...n we will compute mask of the f of elements in the a_i
mask[i]=or(1<<f(x),x in a[i])
then we solve problem (find two non-intersected masks with minimal sum of weights) with subset DP
we repeat it 35 times,and take minimal of the answers
link:
https://pastebin.com/z03e8wU1
Thanks! I like this approach. Instead of repeating for 35 times, I repeat it until the execution time of my program passes 2.95 seconds.
How do you calculate that ?
Use chrono library in C++. Here's my submission. 147486866
I remember this problem used the same trick.
Has the system testing system changed?
It looked like it was rejudged several times even when it got TLE.
I watched 300iq and found his div1D rejudged several times even during the system test
https://codeforces.me/contest/1642/submission/147449848 Can someone please explain why my submission exceeded the memory limit on test 10 for div2C/div1A ?
do not clear the map during each testcase, and set up a new map
NOTHING HERE
But i am initialising a new map for each testcase!
So could you plz paste your code here? I can't view your code now
uh
when you process
mp[val]-=mn;whenval=it.ff*x, it will change the elements in mp, which hasn't been traverse currentlyand this may cause the order of the map changed(you know, the elements in the map are sorted from small to big), and that will cause something wrong?
Just my guess, I am not sure
Guess i got it. Should'nt have traversed in the map lol. Thanks for helping out!
Modifying values in a map while iterating over it is ok. Even inserting new keys is ok, insertion doesn't invalidate any iterators.
If val is not in mp,
if (mp[val])will add it to the map with value 0. So if ll could store huge values, the loop would never terminate, and in practice it can take a very long time.thank you for teaching a lot :-)
Just use a multiset and save yourself some trouble.
mp.size() gives 0 after mp.clear(). so what about that?
This is false, clear erases the nodes and deallocates used memory.
It took 2-3 mins for my browser to load it completely.
Turn on your VPN and reload the page.
Also MikeMirzayanov Why submissions are not available?
same
147445279 why I got tle on B using unordered_map? please explain anyone
https://codeforces.me/blog/entry/62393
Hi there. I don't know where to ask general questions about solutions so I post them here. Pls tell me if it's a wrong place.
For both B & C I passed all the pretest cases, and failed with TLEs in the system tests. The original compiler I was using in the competition was C++17. After the competition I submitted the exactly same solutions with another compiler (C++14) and both of them passed all the tests.
In both problems, the main complexity is coming from O(n) operations on unordered_set (unordered_map), where n is 1e5. So normally it should be far from the time complexity bound.
It's my first time to encounter such a situation. It'd be very helpful if someone could tell me some general ideas to cope with this, like which compiler I shall choose by default during the contest. Since the pretests are all passed, it seemed impossible to see the difference during the contest.
Thanks in advance!
If an unordered_map fails with TLE it is most likely that there is some test with special numbers, so that the unordered_map degenerated to O(n) instead of O(logn) behaviour.
This is well known, and the short solution is to just not use unordered_map, else use your own hashing functions.
unordered_map degenerates straight to O(N) per query. I also should say, that tests are incredibly weak. For C, there was no simple 200000 2 all 1s test, and everyone, who used multiset::count, passed on systests(!!), when they shouldn't have.
lower_bound with multiset works tho
Thanks for the answer! Will never do this for a second time haha.
A slight modification for problem div2C/div1A —
If x is not known and we need to print both optimal x and minimum no of elements to add in array ,
What will be the best approach for this, ie with minimum time complexity?
I wasted a whole lot of my time thinking about this problem because I did not notice that x is given :( What a pity for me.
bro wai C no have a[i]*x limit pretest
Can Anyone tell if my logic for Div2 B is correct or not .. Editorial and other solutions are not visible yet. Sorry for inconvenience.
problems rating(1000 , 900 , 800 , 2200)
How to solve div2D/div1B ?
How palindromes can be useful in this problem?
You can insert any even length palindrome! (by inserting first and last element, then the second and penultimate and so on)
I recommend solving 1 2 3 1 3 2 while reading this hint.
Find first position $$$j \gt 0$$$ equals to $$$a_0$$$. If there is no such position, then there is no answer. Otherwise you can insert $$$a[1..j - 1] + reverse(a[1..j - 1])$$$ after $$$j$$$. Now you can see that $$$a[0..j - 1] = a[j..2 \cdot j - 1]$$$!
UPD:
Wow, thanks a lot!
problems rating be like(1000 , 900 , 800 , 2200)
When will the rating of Div.2 be updated?
It had been updated, thx.
I would suggest organizers use compressed images for problem statements. Heavy images increase problem statement download latency.
how do you miss such an important pretest on C bruh
tourist is one contest away to 4000 for the second time.
.
Problem C: Can any one please give me a testcase where not sorting the array gives wrong ans!
1 10 3 15 15 15 45 45 5 5 5 135 135 Try this
value of x??
3
getting same for the above test case using sort and without sort
0?
Try this n= 4 and k=2, and ar=[8,16,4,32]. Ans should be 0.
Thanks!!!!
I think there is something wrong about rating in this contest, or because of the number of participants?
روح نام ننه يا حازم
may be due to less participation because of unusual time!!
Sad …
No editorial yet and submissions not yet public, are we preparing to repeat the contest? :)
During contest when I made submission for problem A, I got wrong answer. But when I submitted the same code after contest (link) with fixed and setprecision(12) before printing double I got it accepted. For the problem A, the answer would always be an integer. So why would it be incorrect when not using precision and fixed?
In some cases it will be formatted like this:
1e15.May I know how to solve Div1C?
q * log(n)^2 solution:
Maintain set of positions P that can be ill. For x = 0 queries you need to erase positions from P from l to r. If pos is not in set P answer is NO, otherwise answer is YES if there is some segment [l, r] with x = 1 with L < l <= pos <= r < R (L is maximal position < pos in P, R is minimal position > pos in P). You can solve this with maintaining set in segment tree vertices.
You can solve this with maintaining set in segment tree vertices.Can you elaborate more?
For segments with $$$x=1$$$ insert $$$r_i$$$ into position $$$l_i$$$ in segment tree path to leaf, when checking query $$$[L + 1, pos]$$$ if there exists segment with $$$pos \leq r_i \leq R - 1$$$. Because set is sorted you can binary search to check it.
You can just maintain a set of non intersecting segment of guaranteed 0, and set of segments with value 1 but without one segment entirly containing anouther, then to check if there is 1 in given position we can check if ther is a segement containing 1 and this point is the only non-zero one
I thought my code can pass problem C with time complexity O(nlogn), however, it exceeds time limits just at test3. Is there anyone who can help check my program? Thanks a lot.
multiset::count(x)works in $$$O(log(n) + cnt(x))$$$, where $$$n$$$ is the multiset size and $$$cnt(x)$$$ is total number of occurrences ofxin the multiset. Therefore, it could be very slow (if there are multiple occurrences ofxand you search it many times). You should usemap<value, count>or something else to pass.https://codeforces.me/contest/1642/submission/147442302
Sorry to ask. But can u tell why my code passes with multiset count. Or are the tests just weak?
It seems astounding. Looks like the compiler optimizes
if (multiset.count(x)toif (multiset.find(x) != multiset.end()).I resubmitted your code with slight changes (
if (s.count(d*x))->int count = s.count(d*x); if (count > 0)) and TLEd.oww understood thnx. got astoundingly saved today.
Same :>>>
Honestly, I had no idea this is a thing in even as low as C++14 on cf. Spent so many points this round resubmitting my code and trying to hack...
Any guesses on why the compiler optimises in this case? In a previous contests I have a submission that TLEs with multiset.count but gets AC with multiset.find() (I think there are many more examples though)
Oh, when I submit the TLE code with the compiler GNU C++20 (64) it gets AC. C++14 did not optimise for me (I dont understand awoo's comment).
Interesting, I passed with 147469288 after todays contest.
Maybe there's no test, but i tested locally and in custom invocation and it worked instantly on a test that should've taken long. See submissions 147512462 and 147512485.
Even my code with multiset and count passes. https://codeforces.me/contest/1642/submission/147435078
But I tried testing it locally, it took a long time with some custom inputs.
See https://codeforces.me/blog/entry/100208?#comment-889480
We did a bit more digging into this.
if(std::distance(s.lower_bound(d*x), s.upper_bound(d*x)))is the underlying operation that is magically optimized 147514900. It seems like it is optimized toif(s.lower_bound(d*x) != s.upper_bound(d*x))Casting to
intmakes it TLE 147515554, but casting tolong longmakes it AC 147515787. So that TLE happens just because casting 64 bit unsigned to 32 bit signed messes with the boolean optimization.How do you control those optimisations? I have tried with multisets and counts locally with custom data and didn't get any optimisation. My code (with multiset
count) took a long time. Way longer than the one with justfind. See https://codeforces.me/blog/entry/100208?#comment-889480Dug a bit more it seems like the part which turns off compiler optimisations is
-fsanitize=address. This is my full build command that was getting executedg++ --std=c++17 -Wall -fstack-protector-all -fsanitize=address -fno-omit-frame-pointer -O2 great_sequence2.cpp -o C2Though it seems a bit dangerous to use count with multiset. I am certainly never using it again for finding values.
See https://codeforces.me/blog/entry/57646
multiset::count(x)works in $$$O(log(n)+cnt(x))$$$??? Wtf??? I also got miraculously saved by compiler optimization, would never expect such counterintuitive inefficiencyHow to solve Div1C?
[Deleted ...]
If I'm not wrong
minimiseis correct in British EnglishIm sorry but what...? Even if minimise is wrong, did it really affect your understanding of the problem that much ?!
I'll admit it's quite careless of me not to realize C could overflow but one still would expect the pretests to have a case for that...
It's interesting for me to read that many people solved Div1D in $$$O(n 2^m \log)$$$ as both me and my friends found a solution with seemingly different complexities.
I choose a number $$$C$$$ (probably sth between 10 and 20 depending on the implementation) and randomly map each number to sth from the interval [0, C). If two sets of size m are disjoint then there is a positive probability that they will be mapped to disjoint sets as well (and if they are not disjoint, then they will be mapped to non-disjoint sets too). That prob is sth like $$$ \ge (\frac{C-m}{C})^m$$$, so if we repeat that, say, $$$8(\frac{C}{C-m})^m$$$ times then we have a good success probability. If all our numbers are from interval [0, C) then we can easily solve our problem in either $$$O(4^C)$$$ or $$$O(3^C)$$$ or $$$O(2^C \cdot C)$$$ time, what gives $$$O(8(\frac{C}{C-m})^m (n + 2^C \cdot C))$$$ solution. $$$C=2m$$$ kinda gives quite similar complexity, but setting C to 20 instead of 10 gives rather a better one.
If all our numbers are from interval [0, C) then we can easily solve our problem in either O(4^C) or O(3^C) or O(2^C⋅C) timeCan you please detail a bit about this ?You think of each set as a bitmask, there are only $$$2^C$$$ of them. For each mask you store the cheapest row that corresponded to it. By bruteforcing all pairs you get $$$O(4^C)$$$. However there are only $$$3^C$$$ pairs of masks that are disjoint and you are only interested in these and you can get such complexity by cleverly iterating through them. For $$$2^C \cdot C$$$ you compute a simple dp of form dp[x] = cheapest mask that is a submask of x in $$$2^C \cdot C$$$ and then if you have a mask $$$x$$$ you check it with $$$dp[(1 \lt \lt C)-1-x]$$$ (i.e. cheapest mask that is a submask of the complement of x).
why my Div2C solution doesn't work https://codeforces.me/contest/1642/submission/147490769
thank you!
My solution for prob A passes 136 test cases on Test 2 and fails the 137th. But I really have no idea why!
https://codeforces.me/contest/1641/submission/147497119
mine too!
Failing testcase: Ticket 594
Thank you my dear!
https://cfstress.com/status/599 ???
Good contest, finally I became Pupil. Thank you so much people!
Was Problem A more difficult than usual problem A of div 2? I was got 1 WA and solved after solving b c.
I'm a bit sad for ilyakrasnovv who gets a -94 negative contribution because of this post ....
Upd : Now -70 -> -66 (Upd 1) -> +80 (Upd 2)
Now I'm not sad !
Yeah, I am not really sure why? Doesn't seem to me like there were any issues with this round?
Apparently some complained about the image for problem A(it took a long time to load ); the difficulty gap between C and D, which lead to a fastforces for those who didn't solve D; and finally the order of difficulty of problems (many thought C<B<A)
Also so many FSTs
No mercy for people without
#define int long longin their templates. tnowak learn your lessonI'm pretty new at codeforces, but doesn't long long take memory pretty much ? Correct me if I'm wrong ...
It does. But I much rather fix MLE over WA.
I wonder Why do only few number of programmers gave this contest and why does this post has huge number dislikes ?any specific reason;-;
Because of problem A some people left. (Reason may be geometry).
I also think same-;
Why don't we have the an editorial yet?
The pretests are awful.It's to easy to FST.
Different verdicts on main tests and pretests do be quite annoying, but you see, passing pretests does not always indicate that your solutions are absolutely correct. One may pay attention to details and boundary conditions and code more precisely, so that your program is strong enough and able to get rid of sticky FSTs.
Problem D and E is super great!
Even though I still can't get an accepted submission on div2 E/ div1 C, I really enjoyed the problem! Thanks setters!
147529502 question C , why is it giving TLE?
l
maine apne dost ko dia apna code usk accept hogya mera nhiii hua
Bhai bhai ;(
147428133 This is my submission from yesterday's educational round, here I have used unordered sets and it gave TLE on test case 6 but if I used a set in place of unordered it gets accepted. But since only insertion is executed how can it give TLE as far as I know, unordered sets have O(1) complexity while set uses O(log N) complexity.
Do not use unordered map in Codeforces haha
codeforces？ speedforces！
i only see politicforces