### ilyakrasnovv's blog

By ilyakrasnovv, 6 months ago, translation,

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round #773 (Div. 1) and Codeforces Round #773 (Div. 2), which will be held on Feb/23/2022 13:10 (Moscow time). Notice the unusual time! The round will be rated for both divisions. Each division will have 6 problems, and you will have 2 hours to solve them. We recommend you read all the problems!

Tasks are based on RocketOlymp, and were written and prepared by __silaedr__, Allvik06, alegsandyr, ilyakrasnovv, and isaf27.

We are very thankful to

Olympiad's participants cannot participate in codeforces rounds simultaneously.

Good luck and have fun!

UPD — Scoring distribution:

div2: $500 - 750 - 1250 - 2000 - 2000 - 2500$

div1: $500 - 1250 - 1250 - 1750 - 2250 - 3000$

UPDEditorial

• +53

 » 6 months ago, # | ← Rev. 3 →   +41 Notice the unusual time (returns back)All the best everyone, may the force of positive delta be with you!
•  » » 6 months ago, # ^ |   +1 Thank you ,Morty
•  » » 6 months ago, # ^ |   +1 thank you (though it hits me like "positive delta variant of covid" lol
 » 6 months ago, # |   0 scoring distribution when
 » 6 months ago, # |   +24 The unusual time strikes back. For once, I can skip my classes with an actually good reason for it.
 » 6 months ago, # |   +96 NA meme
•  » » 6 months ago, # ^ |   +14 In many countries, people usually participate in codeforces round late at night or early in the morning.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +49 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
•  » » » 6 months ago, # ^ |   +49 yes. always 22:30 in China.
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   +23 So this unusual time is really friendly to Chinese participants.because it is afternoon <3.
•  » » » » » 6 months ago, # ^ |   +32 not that friendly. dinner time.
•  » » » » » 6 months ago, # ^ |   -9 For Indians too.
•  » » » » » 6 months ago, # ^ |   +2 Friendly for Chinese students, not so friendly for us working in companies :P
•  » » » » » 6 months ago, # ^ |   +29 The problems were not friendly at all.
•  » » » » » » 6 months ago, # ^ |   0 D has made me realise i need a year to do that problem
•  » » » » 6 months ago, # ^ |   -10 sed lyf.
•  » » » 6 months ago, # ^ |   +10 I think the IST is blessed in this case.
•  » » » » 6 months ago, # ^ |   0 Dinner time bro :(
•  » » » » » 6 months ago, # ^ |   +11 Still better than sleeping time :)
•  » » 6 months ago, # ^ |   0 Actually it is 13:00 in Russia
 » 6 months ago, # |   +34 As someone in the PST timezone, I cannot wait for this new experience of writing a contest at 2AM in the morning :D
•  » » 6 months ago, # ^ |   +3 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.
 » 6 months ago, # |   +6 today's codechef round is at the normal time of cf, so we have two rounds today.
•  » » 6 months ago, # ^ |   0 Do you participate in all CodeChef's rounds?
•  » » » 6 months ago, # ^ |   +20 Why not?
 » 6 months ago, # |   +62 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!
•  » » 6 months ago, # ^ |   -29 in Russia 23rd of Feburary is also national holiday! It's Defender of the Fatherland day
•  » » » 6 months ago, # ^ |   +21 From Japanese?
•  » » » 6 months ago, # ^ |   -27 In india , it's every day holiday due to online classes
•  » » » » 6 months ago, # ^ |   +7 sbke liye nhi laxman
•  » » 6 months ago, # ^ |   -13 the contest time has been changed to 19:10 for japan
 » 6 months ago, # |   +5 Score distribution?
 » 6 months ago, # |   +4 Yay, waking up at 2 am on the West Coast will be so fun,
•  » » 6 months ago, # ^ |   -19 I think everyone except school kids have this habit of remaining awake till 2 AM in every part of the world ,there might be some exceptions but very little.
 » 6 months ago, # |   0 unsual time with unsual rating change
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 Ok thanks
•  » » 6 months ago, # ^ |   0 Rating will be added of the problem in some time
 » 6 months ago, # |   +58 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?
•  » » 6 months ago, # ^ |   +9 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!
•  » » 6 months ago, # ^ |   +17 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
•  » » 6 months ago, # ^ | ← Rev. 2 →   +19 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. :DEdit: it got updated while I was writing. :)
 » 6 months ago, # |   0 Good luck and high rating!
•  » » 6 months ago, # ^ |   0 same to you
•  » » » 6 months ago, # ^ |   0 same to everybody
 » 6 months ago, # |   +5 Delay by 5 minutes
 » 6 months ago, # |   +7 note 5 minutes delay
 » 6 months ago, # |   -8 delayed by 5 minutes
 » 6 months ago, # |   0 okeeeey lets go +5 min
 » 6 months ago, # |   0 Delay 5 minutes ...
 » 6 months ago, # | ← Rev. 2 →   0 authors İlluminati confirmed (visible in dark mode)
 » 6 months ago, # |   +14 unfamiliar time, familiar delay. :(
 » 6 months ago, # |   +1 Is it rated? m1,m2,m3 do not load.
•  » » 6 months ago, # ^ |   0 Yes it's rated ...
 » 6 months ago, # |   -39 Shitty speedforces
 » 6 months ago, # | ← Rev. 2 →   -44 SpeeeeeedForces
 » 6 months ago, # |   -14 Me wondering what to do after A,B,C
•  » » 6 months ago, # ^ |   +67 Do D
•  » » » 6 months ago, # ^ |   -28 I wish I could. D question looks terrifying
 » 6 months ago, # |   -10 I would gladly give starters.
 » 6 months ago, # |   +18 The difficulty gap between c and d was huge
 » 6 months ago, # | ← Rev. 3 →   -10 Speedforces for sureThe gap between C and D is tremendous
 » 6 months ago, # |   -26 Borforces.(Boring contest)
 » 6 months ago, # |   +39
•  » » 6 months ago, # ^ |   0 It means that you can AK abc in atcoder? Wow, how strong you are!
 » 6 months ago, # | ← Rev. 2 →   +59 Is it just me or some of the statements were kind of difficult to interpret?
•  » » 6 months ago, # ^ |   +14 We could guess how much thousend of partitipants left because of bad statement in A.
•  » » 6 months ago, # ^ |   0 No its not only you. Cont me too in your team
•  » » » 6 months ago, # ^ |   0 the A's statement was so terrible that I had to guess the solution......
 » 6 months ago, # |   +18 why C
 » 6 months ago, # |   +16 Specialists and pupils after solving A,B,C fast
 » 6 months ago, # |   -17 Me after solving A-B-C in the first 20 minutes and not knowing what to do for the rest of the round ...
•  » » 6 months ago, # ^ |   +151 That's unfortunate, anyways for future rounds keep in mind that after solving A, B, C you should try problem D.
 » 6 months ago, # |   -11 This contest ruined my day
 » 6 months ago, # |   +9 Figures in A are very huge , hope to be moderate next rounds
 » 6 months ago, # |   0 Really unbalanced contest, you have my heartfelt downvote.
 » 6 months ago, # |   +3 E should be "cost" more. Its much harded than D (according to standings)
 » 6 months ago, # |   +9 IMO, D has a very nice solution !
•  » » 6 months ago, # ^ |   +1 Indeed. Just one observation and it's a nice constructive problem.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +18 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.
•  » » » 6 months ago, # ^ |   0 Correct. The most important realization is that the extra added elements will ALWAYS be possible to pair them in later iterations.
•  » » » » 6 months ago, # ^ |   +1 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.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 6 months ago, # ^ |   0 I did, but the program made an error in the second test https://codeforces.com/contest/1642/submission/147465343
•  » » » 6 months ago, # ^ |   -7 I got this observation but could not handle the implementation part.
•  » » » 6 months ago, # ^ |   +7 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
•  » » » 6 months ago, # ^ |   +1 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. :-(
 » 6 months ago, # |   0 how to solve A?
•  » » 6 months ago, # ^ |   +5 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.
•  » » » 6 months ago, # ^ |   0 I did the same. Could you pls share your solution?
•  » » » » 6 months ago, # ^ |   +8 pair p[3]; for (int i = 0; i < 3; i++) { cin >> p[i].first >> p[i].second; } if (p[0].second == p[1].second && p[0].second != 0 && p[2].second < p[0].second) { cout << abs(p[1].first - p[0].first); } else if (p[1].second == p[2].second && p[1].second != 0 && p[0].second < p[1].second) { cout << abs(p[1].first - p[2].first); } else if (p[0].second == p[2].second && p[0].second != 0 && p[1].second < p[0].second) { cout << abs(p[0].first - p[2].first); } else { cout << 0; } cout << line; 
•  » » » » 6 months ago, # ^ |   0 Here's mineint solve(array, 3>& a) { sort(a.begin(), a.end(), [](const pair& lhs, const pair& rhs) { ret lhs.second < rhs.second; }); if (a[0].second < a[1].second && a[1].second == a[2].second) { ret abs(a[1].first - a[2].first); } ret 0; } 
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Basic Idea for A : Line [between P1 & P2] Parallel to X-Axis Third Point Should be Lower than Current Line. [P3 Point's Y Co-ordinate should be Less than Line's Y Co-ordinate]. Code [C++] [Div 2 A]void solve() { double ans = 0; double x[3], y[3]; FOR(i, 0, 2) cin >> x[i] >> y[i]; FOR(i, 0, 2) { if (y[i] == y[(i + 1) % 3] && y[i] != 0) { if (y[(i + 2) % 3] < y[i]) ans += abs(x[i] - x[(i + 1) % 3]); } } cout << fixed << setprecision(12) << ans << endl; return; } 
 » 6 months ago, # |   0 Damn only able to solve Problem B...this contest is really unbalanced btw does anyone feels like problem A > problem B
•  » » 6 months ago, # ^ |   +2 No. For me it was just a basic geo problem . But this time A has less solve idk why
 » 6 months ago, # |   +10 Took me two minutes and a half to see the image of problem A !
 » 6 months ago, # |   0 Man the questions were very confusing at first. Nevertheless another fun round!!
 » 6 months ago, # | ← Rev. 2 →   0 Time limits in B and C. It was the last contest for me on Python. I'll go to learn c++.
 » 6 months ago, # |   -14 D was next level adhoc.
 » 6 months ago, # | ← Rev. 4 →   +2 .
•  » » 6 months ago, # ^ |   +3 Can you explain your solution?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -12 .
•  » » 6 months ago, # ^ |   +5 Ready for downvotes :)
•  » » » 6 months ago, # ^ |   0 got FSTed on C too ;(... wasnt prepared for this
•  » » 6 months ago, # ^ |   -6 How to solve D
 » 6 months ago, # |   +18 What is the intended complexity of Div1D? I did N2^Mlog(2e9) and its TLEing :((((
•  » » 6 months ago, # ^ |   0 $O(n 2^m \log n)$ passed in 2950 ms :)
 » 6 months ago, # |   +90 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   -25 rating update should be with accordance of number of registration and rank. Not in accordance of number of submission and ranks.
•  » » » 6 months ago, # ^ |   0 exactly
•  » » » 6 months ago, # ^ |   +3 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?
•  » » » » 6 months ago, # ^ |   0 If what OP suggests is implemented, then the rating of the users who register and do not participate would also be affected, like it's done on atcoder.
•  » » » 6 weeks ago, # ^ |   0 yeah.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 thanks a lot! i hope you do this every round.
•  » » 6 months ago, # ^ |   +11 Can someone please explain who fall in to this "trusted participants" category?
•  » » » 6 months ago, # ^ |   0 This happens in div3 rounds, check This post for example.
•  » » » » 6 months ago, # ^ |   0 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
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 6 months ago, # |   +22 I though that Div1 doesn't have cheaters, but it does: sol1 sol2
 » 6 months ago, # | ← Rev. 2 →   0 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 ?
•  » » 6 months ago, # ^ |   0 You do need to sort it or use something like a set. But why would you check a[I]%x==0
•  » » » 6 months ago, # ^ |   0 No need. ignoring sorting costs me a big drop.
•  » » 6 months ago, # ^ |   0 i 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)
•  » » 6 months ago, # ^ |   0 i solved using map
•  » » » 6 months ago, # ^ |   0 Both B and C can be solved by map:)
•  » » 6 months ago, # ^ |   0 I didn't sort the array, just stored it in a map. And removed y*x for each y in the map. Unfortunately my code TLED, just because I used mp[y*x]=0 instead of just removing y*x from the map(mp.erase(y*x)).Tled codeAccepted code
 » 6 months ago, # |   +5 Successful SpeedForces round, nothing else to say
•  » » 6 months ago, # ^ |   -10 exactly
 » 6 months ago, # |   0 too standard round
 » 6 months ago, # |   +26 poggers sus amogus tokyo ghoul
 » 6 months ago, # | ← Rev. 3 →   +26 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 :(
 » 6 months ago, # |   +21 I wonder why someone would put 3 pictures with a total of 1.45M in Div2 A?
 » 6 months ago, # |   +5 Can we please have the editorial ilyakrasnovv?
 » 6 months ago, # | ← Rev. 2 →   0 why many programmer pullout of contest without submitting any solution if first and second questions are tough or not easy to understand.
•  » » 6 months ago, # ^ |   0 I think for many programmers and for me also 1st questions is a special problem it should be kept easy. Not to complicate its statement like this
•  » » 6 months ago, # ^ |   +4 It is not about tough, it is about high probability of getting the problem statement wrong.
 » 6 months ago, # | ← Rev. 3 →   +15 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.
 » 6 months ago, # |   0 https://codeforces.com/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?
•  » » 6 months ago, # ^ |   +11 you can read about why you TLE'd using unordered_map here:https://codeforces.com/blog/entry/62393
•  » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   +3 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!
•  » » » 6 months ago, # ^ |   0 https://codeforces.com/contest/1641/submission/147500413 got AC with the same code on C++20.
 » 6 months ago, # |   +8 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 >_>
•  » » 6 months ago, # ^ |   +30 i think because solution is O(n log n).
•  » » » 6 months ago, # ^ |   +14 Yes. And the only thing you should use is Segment Tree with $O(log{n})$ descent instead of binary search.
•  » » » » 6 months ago, # ^ |   +13 I used nothing but std::set. Definitely not tight TL for such sol.
•  » » 6 months ago, # ^ |   0 Can you explain what is Van Embe Boas Tree? Or some material to learn it?
•  » » » 6 months ago, # ^ |   +29 Stop learning useless DS and algorithms, go and solve some problems, learn how to use binary search. :)
•  » » » 6 months ago, # ^ |   +25 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!
 » 6 months ago, # |   +10 I know how to solve problem D,but it's not easy to finish the code.
 » 6 months ago, # | ← Rev. 2 →   +37 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?
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   +104 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.
•  » » 6 months ago, # ^ |   +47 Meanwhile, my $N 2^M \log N$ solution required extensive constant optimization in order to pass...
•  » » 6 months ago, # ^ |   -8 Thanks for your great solution! I learn a lot from it. It is a wonderful idea!
 » 6 months ago, # |   +50 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.
 » 6 months ago, # |   -44 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.
•  » » 5 weeks ago, # ^ |   0 How it could be!You just copy the limit before.It's ugly.Reflect your behaviour before blaming the problems.
 » 6 months ago, # |   0 Why Tle on div2 B
•  » » 6 months ago, # ^ |   +1 It's time to read this :(
•  » » » 6 months ago, # ^ |   0 ooh...Now it's really the time to read this
 » 6 months ago, # |   +14 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.
•  » » 6 months ago, # ^ |   +4 Oh, I made a mistake. I mean that the gap is between div1.A and div1.B.
 » 6 months ago, # |   +1089 The pretests ....
•  » » 6 months ago, # ^ | ← Rev. 2 →   +123
•  » » » 6 months ago, # ^ |   +28 Idk why I laughed so Hard my brother was sleeping. Damn its too Funny Man
•  » » 6 months ago, # ^ |   +8 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.
•  » » » 6 months ago, # ^ |   +10 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.
 » 6 months ago, # |   +30 trash pretest QAQ
 » 6 months ago, # |   0 I got TLE on both B and C for using unordered map while it got accepted when I replaced it with map :(.
•  » » 6 months ago, # ^ |   0 I used custom hash in my unordered map and got accepted. see my submission
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 bro I had used map even though its giving tle,why?147437440
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 thanks,though i got that
•  » » 6 months ago, # ^ |   0 Exactly....what's the reason?? I thought using normal map takes up more complexity so I used unordered map and FST in both B and C
•  » » 6 months ago, # ^ |   0 Me too ,and I will lost a lot of points......
 » 6 months ago, # |   +17 Wow ， You have strong pretest in Div2 C / Div1 A
 » 6 months ago, # |   +4 I think the main idea of div1-D is similar to this problem(except parallel binary search): https://codeforces.com/problemset/problem/1285/F
•  » » 6 months ago, # ^ |   0 I applied the exact same idea and passed, I don't think parallel binary search is needed.
 » 6 months ago, # |   -8 DIdn't solve D cause of one line of code. I want to kill myself lol
•  » » 6 months ago, # ^ |   +9 FSTed C due to 1 line of code ;(
 » 6 months ago, # | ← Rev. 8 →   +33 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.
•  » » 6 months ago, # ^ |   0 I don't either...
 » 6 months ago, # |   0 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 !!
•  » » 6 months ago, # ^ |   0 due to hash collisions, the time complexity of unordered_set per operations can be up to O(n), you can read about it here
 » 6 months ago, # | ← Rev. 2 →   +9 I request all contest writers here that guys please make some strong pretests.You will get nothing by trolling participants.
 » 6 months ago, # |   +2 ou yeah, another trash round, bad pretests C + no balance
 » 6 months ago, # |   +73 A GOOD FST ROUND
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 Test:141 1 2 2Right answer:2 2 3 4Your answer:2 3 3 4
•  » » » 6 months ago, # ^ |   0 Thanks, got it. Giving all unique to one doesn't works. Can you share how you approach this kind of questions basically GREEDY?
 » 6 months ago, # |   +11 Pretty fast systests!
 » 6 months ago, # |   +84 Why are submissions still hidden ?
 » 6 months ago, # | ← Rev. 3 →   0 Good contest guys but I think you had weak tests for C. My submission https://codeforces.com/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. 1 200000 1 (100000 times) 2 (100000 times) 
 » 6 months ago, # | ← Rev. 3 →   +69 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<
•  » » 6 months ago, # ^ |   +10 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.
•  » » » 6 months ago, # ^ |   0 How do you calculate that ?
•  » » » » 6 months ago, # ^ |   0 Use chrono library in C++. Here's my submission. 147486866
•  » » 6 months ago, # ^ |   0 I remember this problem used the same trick.
 » 6 months ago, # |   +19 Has the system testing system changed?It looked like it was rejudged several times even when it got TLE.
•  » » 6 months ago, # ^ |   +27 I watched 300iq and found his div1D rejudged several times even during the system test
 » 6 months ago, # |   0 https://codeforces.com/contest/1642/submission/147449848 Can someone please explain why my submission exceeded the memory limit on test 10 for div2C/div1A ?
•  » » 6 months ago, # ^ |   +1 do not clear the map during each testcase, and set up a new map
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -14 NOTHING HERE
•  » » » » 6 months ago, # ^ |   0 But i am initialising a new map for each testcase!
•  » » » » » 6 months ago, # ^ |   0 So could you plz paste your code here? I can't view your code now
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 void solve(){ ll n,x; cin>>n>>x; vl a(n); take(a); sort(all(a)); map mp; fr(i,n){ mp[a[i]]++; } ll ans=0; for(auto it : mp){ ll val = it.ff*x; if(mp[val]){ ll mn = min(mp[val],it.ss); mp[val]-=mn; ll num = val/x; mp[num]-=mn; } } trav(e,mp){ ans+=e.ss; } cout<
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 uhwhen you process mp[val]-=mn; when val=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
•  » » » » » » » » 6 months ago, # ^ |   +8 Guess i got it. Should'nt have traversed in the map lol. Thanks for helping out!
•  » » » » » » » » 6 months ago, # ^ |   +8 Modifying values in a map while iterating over it is ok. Even inserting new keys is ok, insertion doesn't invalidate any iterators.
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » » » » » 6 months ago, # ^ |   +8 thank you for teaching a lot :-)
•  » » » » » » » » 6 months ago, # ^ |   0 that's why i got tle in my code......hope i knew that earlier :-<...thanks for explaining....i think map.find() will give the correct answer
•  » » » » » » » 6 months ago, # ^ |   0 Just use a multiset and save yourself some trouble.
•  » » » » 6 months ago, # ^ |   +9 mp.size() gives 0 after mp.clear(). so what about that?
•  » » » » 6 months ago, # ^ |   +25 This is false, clear erases the nodes and deallocates used memory.
 » 6 months ago, # |   0 Did anyone faced this problem too?The image was cropped for 8-10 mins in chrome.I changed to brave it was fine there.
•  » » 6 months ago, # ^ |   0 a refresh solved that for me
•  » » » 6 months ago, # ^ |   0 It didn't help :(
•  » » 6 months ago, # ^ |   +2 It took 2-3 mins for my browser to load it completely.
•  » » 6 months ago, # ^ |   +2 Turn on your VPN and reload the page.Also MikeMirzayanov Why submissions are not available?
•  » » 6 months ago, # ^ |   0 same
 » 6 months ago, # |   0 147472401 why I got tle on B using unordered_map? please explain anyone
•  » » 6 months ago, # ^ |   0 use map it will be fine
•  » » 6 months ago, # ^ |   0 It's time to read (https://codeforces.com/blog/entry/62393)
•  » » » 6 months ago, # ^ |   0 thank you bro
 » 6 months ago, # |   +5 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. SpoilerIn 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!
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 lower_bound with multiset works tho
•  » » » 6 months ago, # ^ |   0 Thanks! Costed me both B and C today! Will keep in mind for the later contests.
•  » » » 6 months ago, # ^ |   0 Thanks for the answer! Will never do this for a second time haha.
 » 6 months ago, # |   0 why did my submission of div2/c 147429231 got TLEd? It's overall complexity is O(nlogn).
 » 6 months ago, # | ← Rev. 2 →   0 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?
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +6 bro wai C no have a[i]*x limit pretest
 » 6 months ago, # |   +1 Wrong Code for B long long n; cin>>n; mapmp; for(long long i=0;i>c; mp[c]++; } long long ans = mp.size(); vectorcnt; for(auto it:mp){ cnt.push_back(it.second); } sort(cnt.begin(),cnt.end()); for(long long i=0;i0)ans++; cout<
 » 6 months ago, # |   0 How to solve div2D/div1B ?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +21 Hint 1How palindromes can be useful in this problem? AnswerYou can insert any even length palindrome! (by inserting first and last element, then the second and penultimate and so on) Hint 2I recommend solving 1 2 3 1 3 2 while reading this hint.Find first position $j > 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: Implementation with comments#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while(t--) { int n; cin >> n; vector a(n); for(auto &v: a) cin >> v; vector> op; // Operations vector ans; // Division into blocks in the final answer int del = 0; // Number of deleted elements bool bad = false; while(!a.empty()) { int j = 1; // First position > 0 equals to a[0] while(j < (int)a.size() && a[j] != a[0]) j++; if(j == (int)a.size()) { bad = true; break; } // Tricky: // I don't insert the first part of the palindrome (2 3) // 1 2 3 1 3 2 // 1 2 3 1 -> 1 2 3 1 3 2 for(int i = 1; i < j; i++) a.insert(a.begin() + i + j, a[j - i]); // 1 2 3 1 // 1 2 3 1 2 3 3 2 // H H for(int i = 1; i < j; i++) op.push_back({i + j + del, a[i]}); // 1 2 3 1 3 2 // H H H H for(int i = 0; i <= j; i++) a.erase(a.begin()); del += j * 2; ans.push_back(j * 2); } if(bad) { cout << "-1\n"; continue; } cout << op.size() << "\n"; for(auto [x, y]: op) cout << x << " " << y << "\n"; cout << ans.size() << "\n"; for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << " \n"[i == (int)ans.size() - 1]; // Cool implementation trick } } 
•  » » » 6 months ago, # ^ |   0 Wow, thanks a lot!
 » 6 months ago, # |   +14 problems rating be like(1000 , 900 , 800 , 2200)
 » 6 months ago, # | ← Rev. 2 →   -8 When will the rating of Div.2 be updated?
•  » » 6 months ago, # ^ |   -8 It had been updated, thx.
 » 6 months ago, # |   +5 I would suggest organizers use compressed images for problem statements. Heavy images increase problem statement download latency.
 » 6 months ago, # |   0 i just start codeforces not long time, and i think problems are hard for me :(
 » 6 months ago, # |   0 how do you miss such an important pretest on C bruh
 » 6 months ago, # |   +55 tourist is one contest away to 4000 for the second time.
 » 6 months ago, # | ← Rev. 5 →   -38 .
 » 6 months ago, # |   0 my solution give tle when i submitted it c++17 but when i submit the same code in c++14 it got accepted
 » 6 months ago, # |   0 Problem C: Can any one please give me a testcase where not sorting the array gives wrong ans!
•  » » 6 months ago, # ^ |   0 1 10 3 15 15 15 45 45 5 5 5 135 135 Try this
•  » » » 6 months ago, # ^ |   -10 value of x??
•  » » » » 6 months ago, # ^ |   0 3
•  » » » » » 6 months ago, # ^ |   0 getting same for the above test case using sort and without sort
•  » » » » » » 6 months ago, # ^ |   0 0?
•  » » » » » » » 6 months ago, # ^ |   0 yes
•  » » 6 months ago, # ^ |   0 Try this n= 4 and k=2, and ar=[8,16,4,32]. Ans should be 0.
•  » » » 6 months ago, # ^ |   +1 Thanks!!!!
•  » » 6 months ago, # ^ | ← Rev. 5 →   0 It's easy to prove why sorting is needed.Let's say you have an array [x, x2, x3, x4]. Optimally it's easy to see that all pairs will be used but let's say you decided to pair x2 and x3 together. Now x and x4 can't be paired together so you lost one pair.You can create such test cases easily. One such example is [4, 2, 1, 8, 2, 16]
 » 6 months ago, # | ← Rev. 2 →   -39 I think there is something wrong about rating in this contest, or because of the number of participants?
•  » » 6 months ago, # ^ |   -16 روح نام ننه يا حازم
•  » » 6 months ago, # ^ |   0 may be due to less participation because of unusual time!!
•  » » » 6 months ago, # ^ |   0 Sad …
 » 6 months ago, # |   +9 No editorial yet and submissions not yet public, are we preparing to repeat the contest? :)
 » 6 months ago, # |   0 plz open the solution seeing mode of other
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ |   +8 In some cases it will be formatted like this: 1e15.
»
6 months ago, # |
-68

# include <bits/stdc++.h>

using namespace std;

# define ld long double

const ll MOD = 1e9 + 7; const ll INF = 1e9; const ld EPS = 1e-9;

void solve() { int n; cin >> n; int x; unordered_set mp; for (int i = 0; i < n; i++) { cin >> x; mp.insert(x); } int sz = mp.size(); for (int k = 1; k < sz; k++) cout << sz << " "; for (int k = sz; k <= n; k++) cout << k << " "; cout << "\n"; }

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; cin >> tc; for (int t = 1; t <= tc; t++) { // cout << "Case #" << t << ": "; solve(); } }

Can someone tell why this is giving TLE for problem B ?

 » 6 months ago, # | ← Rev. 2 →   +16 May I know how to solve Div1C?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » 6 months ago, # ^ |   0 You can solve this with maintaining set in segment tree vertices. Can you elaborate more?
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   +8 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.
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   -10 Why solution of problem E is giving wrong answer on TC 3
 » 6 months ago, # |   +8 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 seq, del; seq.clear(), del.clear(); for (int i = 0; i < n; i++) { long long a; scanf("%lld", &a); seq.insert(a); } for (multiset::iterator i = seq.begin(); i != seq.end(); i++) if (vis(*i)) { if (vis(*i * x)) { del.insert(*i); del.insert(*i * x); } } printf("%d\n", seq.size() - del.size()); 
•  » » 6 months ago, # ^ |   +8 multiset::count(x) works in $O(log(n) + cnt(x))$, where $n$ is the multiset size and $cnt(x)$ is total number of occurrences of x in the multiset. Therefore, it could be very slow (if there are multiple occurrences of x and you search it many times). You should use map or something else to pass.
•  » » » 6 months ago, # ^ |   0 I see. Thanks a lot!
•  » » » 6 months ago, # ^ |   0 https://codeforces.com/contest/1642/submission/147442302Sorry to ask. But can u tell why my code passes with multiset count. Or are the tests just weak?
•  » » » » 6 months ago, # ^ |   +42 It seems astounding. Looks like the compiler optimizes if (multiset.count(x) to if (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.
•  » » » » » 6 months ago, # ^ |   0 oww understood thnx. got astoundingly saved today.
•  » » » » » » 6 months ago, # ^ |   -8 Same :>>>
•  » » » » » 6 months ago, # ^ |   0 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...
•  » » » » » 6 months ago, # ^ |   +15 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)
•  » » » » » » 6 months ago, # ^ |   0 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).
•  » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » » 6 months ago, # ^ |   0 Even my code with multiset and count passes. https://codeforces.com/contest/1642/submission/147435078But I tried testing it locally, it took a long time with some custom inputs.
•  » » » » » 6 months ago, # ^ |   +36 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 to if(s.lower_bound(d*x) != s.upper_bound(d*x)) I resubmitted your code with slight changes (if (s.count(d*x)) -> int count = s.count(d*x); if (count > 0)) and TLEd. Casting to int makes it TLE 147515554, but casting to long long makes it AC 147515787. So that TLE happens just because casting 64 bit unsigned to 32 bit signed messes with the boolean optimization.
•  » » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 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 just find. See https://codeforces.com/blog/entry/100208?#comment-889480
•  » » » » » » » 6 months ago, # ^ | ← Rev. 5 →   0 Dug 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 executed g++ --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.
•  » » » 6 months ago, # ^ |   0 You also can solve problem C with multiset: 147440170
•  » » » 6 months ago, # ^ |   +17 multiset::count(x) works in $O(log(n)+cnt(x))$??? Wtf??? I also got miraculously saved by compiler optimization, would never expect such counterintuitive inefficiency
 » 6 months ago, # |   +14 How to solve Div1C?
 » 6 months ago, # | ← Rev. 4 →   -155 I think it will be the worst contest this year.The statement is not clear and difficult to understand.This is just a simple example of bad review ! minimise !?His use of the English language is very bad bad
•  » » 6 months ago, # ^ |   +50 If I'm not wrong minimise is correct in British English
•  » » 6 months ago, # ^ |   +18 Im sorry but what...? Even if minimise is wrong, did it really affect your understanding of the problem that much ?!
 » 6 months ago, # |   0 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...
 » 6 months ago, # |   +79 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.
•  » » 6 months ago, # ^ |   0 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) time  Can you please detail a bit about this ?
•  » » » 6 months ago, # ^ |   +18 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 < < C)-1-x]$ (i.e. cheapest mask that is a submask of the complement of x).
•  » » » » 6 months ago, # ^ |   0 Thanks a lot!
 » 6 months ago, # |   0 In Codeforces Round #773 (Div. 2), problem 'B. Power Walking', my submission got TLE while submitting in G++17. But it got accepted in G++14. Why?
 » 6 months ago, # | ← Rev. 2 →   0 why my Div2C solution doesn't work https://codeforces.com/contest/1642/submission/147490769
•  » » 6 months ago, # ^ |   +3 Input1 5 2 7 4 8 1 2  Expected Output1  Your Output3 `
•  » » » 6 months ago, # ^ |   0 thank you!
 » 6 months ago, # |   -14 Đề như đb <3(trans: nice problem pro, keep it up <3)
 » 6 months ago, # |   0 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.com/contest/1641/submission/147497119