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

isaf27 for the great coordination, valuable advice, and patience.

Renatyss, stepanov.aa, _tryhard, Siberian, kirill.kligunov, arbuzick for the help during discussing and preparing problems.

Our testers: AlperenT, ArtNext, EvgeniyPonasenkov, FedShat, Qwerty1232, TeaTime, TheEvilBird, ak2006, generic_placeholder_name, philmol, silvvasil, tox1c_kid for their feedback

pakhomovee for the task, that didn't find its place in the final problemset.

KAN for helping with round preparation

MikeMirzayanov for codeforces and polygon platform

*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$$$

**UPD** — Editorial

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

The

unusual timestrikes back. For once, I can skip my classes with an actually good reason for it.NA memeIn 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.

For Indians too.

Friendly for Chinese students, not so friendly for us working in companies :P

The problems were not friendly at all.

D has made me realise i need a year to do that problem

sed lyf.

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?

In india , it's every day holiday due to online classes

sbke liye nhi laxman

the contest time has been changed to 19:10 for japan

Score distribution?

Yay, waking up at 2 am on the West Coast will be so fun,

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.

unsual time with unsual rating change

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.

Ok thanks

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!

same to you

same to everybody

Delay by 5 minutes

note

5 minutesdelaydelayed by 5 minutes

okeeeey lets go +5 min

Delay 5 minutes ...

authors İlluminati confirmed (visible in dark mode)unfamiliar time, familiar delay. :(

Is it rated?

m1,m2,m3 do not load.

Yes it's rated ...

Shitty speedforces

SpeeeeeedForcesMe wondering what to do after A,B,C

Do D

I wish I could. D question looks terrifying

I would gladly give starters.

The difficulty gap between c and d was huge

Speedforces for sure

The gap between C and D is tremendous

Borforces.(Boring contest)

It means that you can AK abc in atcoder? Wow, how strong you are!

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.

No its not only you. Cont me too in your team

the A's statement was so terrible that I had to guess the solution......

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.

This contest ruined my day

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 a

_{2i-1}= a_{2i}, 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.com/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?

Here's mineBasic Idea for

A:Parallel to X-AxisLowerthan Current Line. [P3 Point's Y Co-ordinate should be Less than Line's Y Co-ordinate].Code [C++] [Div 2 A]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 !

Man the questions were very confusing at first. Nevertheless another fun round!!

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

How to solve D

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.

exactly

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?

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.

yeah.

thanks a lot! i hope you do this every round.

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==0`

No need. ignoring sorting costs me a big drop.

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)

i solved using map

Both B and C can be solved by map:)

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 code

Accepted code

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.

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

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.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?

you can read about why you TLE'd using unordered_map here:

https://codeforces.com/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.com/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!

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 :(

ooh...Now it's really the 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.

The pretests ....

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.

thanks,though i got that

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

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.com/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

Thanks, got it. Giving all unique to one doesn't works. Can you share how you approach this kind of questions basically GREEDY?

Pretty fast systests!

Why are submissions still hidden ?

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.

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.com/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;`

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

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 :-)

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

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.

Did anyone faced this problem too?The image was cropped for 8-10 mins in chrome.I changed to brave it was fine there.

a refresh solved that for me

It didn't help :(

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

147472401 why I got tle on B using unordered_map? please explain anyone

use map it will be fine

It's time to read (https://codeforces.com/blog/entry/62393)

thank you bro

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!

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! Costed me both

B and Ctoday! Will keep in mind for the later contests.Thanks for the answer! Will never do this for a second time haha.

why did my submission of div2/c 147429231 got TLEd? It's overall complexity is O(nlogn).

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

Wrong Code for BCan Anyone tell if my logic for Div2 B is correct or not .. Editorial and other solutions are not visible yet. Sorry for inconvenience.

How to solve div2D/div1B ?

Hint 1How palindromes can be useful in this problem?

AnswerYou can insert

anyeven 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 commentsWow, 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.

i just start codeforces not long time, and i think problems are hard for me :(

how do you miss such an important pretest on C bruh

tourist is one contest away to 4000 for the second time.

.

my solution give tle when i submitted it c++17 but when i submit the same code in c++14 it got accepted

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?

yes

Try this n= 4 and k=2, and ar=[8,16,4,32]. Ans should be 0.

Thanks!!!!

It's easy to prove why sorting is needed.

Let's say you have an array [x, x

^{2}, x^{3}, x^{4}]. Optimally it's easy to see that all pairs will be used but let's say you decided to pair x^{2}and x^{3}together. Now x and x^{4}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]

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? :)

plz open the solution seeing mode of other

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`

.## include <bits/stdc++.h>

using namespace std;

## define ll long long

## 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 ?

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

Why solution of problem E is giving wrong answer on TC 3

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 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<value, count>`

or something else to pass.I see. Thanks a lot!

https://codeforces.com/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)`

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.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.com/contest/1642/submission/147435078

But I tried testing it locally, it took a long time with some custom inputs.

See https://codeforces.com/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 to`if(s.lower_bound(d*x) != s.upper_bound(d*x))`

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.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-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 executed`g++ --std=c++17 -Wall -fstack-protector-all -fsanitize=address -fno-omit-frame-pointer -O2 great_sequence2.cpp -o C2`

Though it seems a bit dangerous to use count with multiset. I am certainly never using it again for finding values.

See https://codeforces.com/blog/entry/57646

You also can solve problem C with multiset: 147440170

`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?

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

If I'm not wrong

`minimise`

is 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) time`

Can 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 < < C)-1-x]$$$ (i.e. cheapest mask that is a submask of the complement of x).

Thanks a lot!

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?

why my Div2C solution doesn't work https://codeforces.com/contest/1642/submission/147490769

InputExpected OutputYour Outputthank you!

Đề như đb <3(trans: nice problem pro, keep it up <3)

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