Hello, Codeforces!

We invite you to Codeforces Round #823 (Div. 2) which will be held on Sep/25/2022 17:35 (Moscow time). You will be given **2 hours** to solve **6 problems**.

The problems were invented and prepared by shnirelman, Lankin and me.

We would like to thank:

isaf27 for coordinating the round.

KAN for the help during preparation of the contest.

kevinxiehk, 74TrAkToR, Aleks5d, cadmiumky, satyam_343, gothic_kobra, NikitaSemenov, tibinyte for testing the round.

MikeMirzayanov for Codeforces and Polygon.

Wish you good luck and high rating!

The scoring distribution will be announced closer to the beginning of the round.

**UPD**: Scoring distribution: **500 — 1000 — 1500 — 2250 — 2250 — 3000**.

**UPD2**: Editorial: https://codeforces.com/blog/entry/107293.

**UPD3**: Winners.

Div1:

Div2:

What happened to Pinely Codeforces Round 1 ?

what even is pinely?

Click

Let's just admit that this contest's Problem B is even harder than last contest's Problem D1.

B is so hard :(

Brovko The announcement says it will be 2 hrs, but in contests page it shows 2.30 hrs. What is the right one lol

upd.: fixed

thanks, fixed

As a participant,I'm hoping for a great round OvO!

isn't this contest's previous name Pinely Codeforces Round 1 ?

Hope to beat my previous best! Everyone wants the same right? Good luck!!

Lol i got pinged

What a coincidence... Me too! I would like to request a refund...

Also the round is nice, you can participate if you want

hoping for more than +2 delta

Brovko round! Will be pleasant to partake!

I want to be a pupil❤

Why even I don't reach pupil and continue to get negative rating!(⊙_⊙)？

practise more problems in 1200-1300 range

Hope I'll become pupil in this round

me as well

In which year you are in?

2nd

same iam from delhi technological university

same from Vit vellore

yeah mee too :(

Noted!

I also being pupil after 50 contest...

Hoping +ve delta!

Why was this changed from a combined round to D2?

I don't know what happened to Pinely Round but it was canceled and replaced by common Div2.

Oh, okay. Thank you for the fast reply.

Is this Round be rated or unrated?

It is rated for people with less than $$$2100$$$ rating.

I am going to give my best in this contest..hoping for a positive delta

hopeing to solve C today

Hello, World

When will the score distribution be announced?

hi guys is there any problem with codeforces because i lost all my ratings automatically which i earned during my last 3 contest , magically all last 3 contest turned from rated to unratted the first contest i gave was div 4 and then i gave div 3 and div 2 till yesterday everything was ok but from today afternoon it got happen i lost all my ratings

Same the contest are not visible but my rating is as earlier

What happened to ratings, 3 to 4 rounds ratings are rolled back, is it for me or for everyone?

no,its for everyone

Something strange has happened to me.

Days ago I found I'm unregistered and I couldn't register this round, a black message block appeared at the bottom right corner telling me that my rating should be between 0 and 2099. And I could only find people who are under 2100 in the namelist.

But this kind of black block just appeared in rounds like #814 before.

Yesterday I found I've already registered it. I can find my name in the last page of namelist. It may mean I'm among the first ones who registered.

Is it a bug?

lucky

Cool Scoring distribution. Will try to solve 5/6.

upd: failed

can you please tell me whats is the meaning of rollback what is the meaning of this line " Rating changes for last rounds are temporarily rolled back. They will be returned soon."

The updated ratings will be available soon.

Ignore it. Just solve your problems:)

Yes man exactly thats the point

They will remove cheaters, update scoreboard and reapply the new rating changes.

Thank you to everyone who participated in creating this contest

I hope the problem statements are as concise and short as announcement :)

I am a Newbie now. Will become Specialist after the contest. Wait and Watch.

IIITH...BROOOOOOOO

it is said that good luck is hiding in the problems !!!

I will become specialist after this round

same goal :)

one of my another account is also pupil xxzxsyl

My first contest in like 3 weeks.

sad lol

..

toughThe best B problen I've seen.(Joke)

Actually B is a double problem.

B1 is understanding B, then B2 is solving B.

Unbalanced Round. -_-

How unbalanced do you want the contest to be?

Authors:

YES!Unbalanced Round :(B and C need to be swapped LOL twice as many C solves as B

Even I like the idea of B it was too hard to be B

Am I the only one who still does not understand Problem B?

190 years for getting dressed

`:-|`

!!Oh my god! I cannot even imagine that I could officially be top 20 in a div2 contest.

congrats!

How do you see your approximate performance and rating before rating canculations? Is it a browser extension or it could be unlocked in settings?

I am using carrot, a browser extension by Chrome.

Cool, thanks :)

It is browser extension called carrot.

I love carrots

"No human is limited". Believe in yourself, maybe one day you can become a LGM!

Congrats!

Now that I think of it you may be in top 10 because a lot of top participants are just alt accounts of div1 users :D

B > D and this is not even a joke. If D stood instead of B and people believed that it was easy, then many times more people would solve it

it requires absolutely no algorithmic skills and even worse, it is easy to pass with an intuitive solution without proof

I have no idea how to solve D, though spent a lot of time on it

But for B it was a clear ternary search from the start

any guess where my submission went wrong 173488027

Take a look at Ticket 16219 from

CF Stressfor a counter example.also used ternary search, but have another idea:

smth like go from left to right, remember worst person to the left and to the right, only a new one can become worse than the left worst, because with each movement a constant is added to all The worst on the right can be tracked, for example, by initially calculating the time for each to reach 0 and sorting them by it

First sentence is actually lie, I used binary and wrong naming for it

Binary search works too

I don't think ternary search is needed for B Please look at my submission 173464664

I did use a similar logic, but during contest I did not sort the final results before taking the average of the first and last element of the array.

Only got AC after contest ended.

Huh. Was buffering output really the only difference between your TLE/AC submissions for B? Is that depressing or weird? I can't even tell anymore :P

But otherwise, usual gripes: how hard is it to just ask "when and where can everyone meet at the earliest?" (grumble wtf is even summary in the clarification?)

edit: oh, changed epsilon, duh (also 'summary' meant for 'summation'... uhgh)

Yeah, buffering shouldn't have affected so much for t=1000

Also I only intended to change eps as constant factor optimization But apparently it lead to some kind of infinite loop because of precision issues

I didn't think about it during the contest but for big numbers step of 1e-10 does not exist, so while loop becomes infinite

The problem B is good example why Codeforces EDU section is helpful

why

I'm wondering what B's pretest 3 is. Got many WAs on that pretest.

`cout<<123456789.5<<endl;`

and you will get`1.23457e+08`

in the output I believe this is the reasonShould the test system consider both as correct? I think the problem statement didn't say "scientific notation is not allowed".

scientific notation losses the accuracy by only reserving certain number of digits

Oh, OK, but such issues aren't related to algorithms / problem solving. I wasn't even aware of this thing before.

It got me too :( Could have solved ABCD otherwise :(

i had no idea about this:))

I think you made the same mistake I kept on making for an hour. Basically, (a+b)/c, where c is a double and a, b are ints, returns a double in scientific notation. You need to convert that scientific notation to a decimal.

How to solve D?

The idea is simple first of all, imagine two strings, Reverse of $$$s_1$$$ and orginal $$$s_2$$$. Now everytime you perform an operation, you select a suffix of length $$$k$$$ from both the strings, reverse them and swap them. It simplifies the problem (makes it easier to visualize).

So, first reverse $$$s_1$$$. i.e $$$s_1 <= reverse(s_1)$$$ Now, with a bit of playing around you can prove that you can

Now its easy to solve!

Swap any pairs (s1[i],s2[i]) and (s1[j],s2[j]), for any index i and jHow?

It's sufficient to prove that I can swap any adjacent pairs $$$(s_1[i],s_2[i])$$$ , $$$(s_1[i+1],s_2[i+1])$$$ without affecting the rest of the strings.

Another observation: You can cyclic shift the pairs right by $$$1$$$ unit $$$(s_1[i],s_2[i])$$$ , $$$(s_1[i+1],s_2[i+1])$$$ , $$$(s_1[i+2],s_2[i+2])$$$ ..... $$$(s_1[n],s_2[n])$$$ thus getting $$$(s_1[i+1],s_2[i+1])$$$ , $$$(s_1[i+2],s_2[i+2])$$$ , $$$(s_1[i+3],s_2[i+3])$$$ ..... $$$(s_1[1],s_2[1])$$$

By performing operation $$$k=1$$$ , $$$k=n-i+1$$$, $$$k=n-i$$$ in order. (I will denote it by $$$(1,n-i+1,n-i)$$$ from now on).

Now to swap $$$(s_1[i],s_2[i])$$$ , $$$(s_1[i+1],s_2[i+1])$$$. You should keep shifting the portion $$$[i+1,n]$$$ to the right until $$$(s_1[i+1],s_2[i+1])$$$ reaches the end of the array. More formally, shift right $$$n-i-1$$$ times on the portion $$$[i+1,n]$$$.

Then, perform one right cyclic shift in the portion $$$[i,n]$$$. Voila! You swapped the adjacent pairs! (Rest of the strings remain unchanged!).

in another observation you actually have wrote a cyclic shift of 1 unit left

was B binary search?

no. it requires ternary search!

Binary search also works here

There is a simpler solution:

`(min(a[i]-t[i])+max(a[i]+t[i]))/2`

What's the intuition for that? How does subtracting the ready time get you the answer?

Can you please describe your intuition behind it?

Draw straight lines (rays up) at an angle of 45 (with coordinate axes) with centers at points (x_i, t_i). Then you need to understand that these lines are this place-time where a person from a point (X_i, T_I) can get. Further, it becomes clear how to look for the optimal place of the meeting — the intersection of the "most left" min(a[i]-t[i]) straight and "right" max(a[i]+t[i]) straight line.

I solved it with binary search. Just search for time and for each time and each person look the range of coordinates he can visit. If the intersection of all persons is not empty — this time is good and you can decrease it

ternary search, but what was testcase 3 :((

need to increase precision of double printed...

have you set epsilon as 1e-6 and print upto 6 decimal digits? It was initially failing for me in testcase 3 due to this

yeah eps=1e-6, the problem was with set precision.

yep

someone said it's ternary search , I ll search what ternary search is.

You could binary search, yes.

But you could also just calculate the minimum $$$x - t$$$ and the maximum $$$x + t$$$ and take the midpoint as the answer.

Proof: If the same person has both the minimum $$$x - t$$$ AND the maximum $$$x + t$$$, then this person is taking a crapton of time to get dressed, and everybody else can reach this location by the time this person is done.

Otherwise, suppose person $$$P$$$ has the minimum $$$x - t$$$ and person $$$Q$$$ has the maximum $$$x + t$$$. Since $$$P \neq Q$$$, this means $$$x_P < x_Q$$$ (otherwise, whoever has the higher $$$t$$$ would have claimed the other's rank). The claim is that the ideal midpoint is $$$\frac{x_p - t_p + x_q + t_q}{2}$$$. It's easy to see that $$$P$$$ and $$$Q$$$ will spend the longest time to reach this point, compared to everyone else, since anyone who spends longer time will either have a lower $$$x - t$$$ than $$$P$$$ (if they were moving right) or a higher $$$x + t$$$ than $$$Q$$$ (if they were moving left). Here, $$$P$$$ and $$$Q$$$ take the same amount of time, and it's the optimal time, because changing the position in any direction will cause one of $$$P$$$ or $$$Q$$$ to spend more time to get there.

well however if the mid point<xmin then xmin is the answer. Same for xmax. I missed the point and solved the problem in hard way

There are no further cases to consider if you just choose the midpoint of the minimum $$$x_i - t_i$$$ and the maximum $$$x_i + t_i$$$. 173500218.

If there was some case you missed that caused your submission to fail, I would guess that you used a different (and likely more complicated) approach than this simple min/max and midpoint calculation.

I didn't use setprecision in double . thats why I got wa — _ -

I used binary search,but got TLE at point 4.

This is the worst round I've ever participated in.

u regret wasting time on B and not trying C dont u?

In contest : swap(Problem B, Problem C) :(

Wasted about 30 minutes thinking of $$$B$$$ and solved $$$C$$$ in like 15 minutes

why didn't you swap $$$B$$$ and $$$C$$$ :(

What happened to problem B, whick I have been thinking about 2 hours? (I know that I'm stupid, but I'm not the only one who failed the task)

Someone give me a hint for B so I can feel stupid.

Find the minimum value of $$$x_i - t_i$$$ and the maximum value of $$$x_i + t_i$$$ (they can overlap). The answer is the midpoint of these two values.

You shouldn't feel stupid though, because even though it's actually not that hard to prove this result, I think it's very difficult to actually come up with this idea with enough confidence that it might work, before one can consider trying to prove it.

Was debugging 1e+08 mistake in task B 30 min :(

How do you solve B? I tried a ton of different things but none of them worked :(

use ternary search

Could you please elaborate?

i've used greedy

You don't need ternary search, there an O(n) solution.

An alternative solution to binary/ternary search:

For each person, we create two new locations, the location that is t[i] units to the left of the person and the location that is t[i] units to the right of the person. Now we find the location among these locations that is furthest to the right and then the location among the locations that is furthest to the left and pick the location exactly in the middle between them.

However, I did not prove this solution and it might not work after the system tests, but it just felt right. The main reason for this idea is that in an optimal solution there will be a latest person that comes from the left (and arrives at the same time as if he was t[i] units to the left of where he originally started), and there will be a latest person from the right. If these people do not arrive at the same time it is probably not the optimal location because you can move the location closer to the person that comes later.

A cool thing about this solution though is that it can run in O(n) and not O(nlogn) like most other solutions.

Edit: This solution does in fact work since it passed system tests

Thank you so much for this explanation!

nice solution. Thanks a lot

Video Solution for Problem B,Problem C.

could one help me to understand problem b, it take all my time

Today's round was

GeometryForcesbrought to you by: B"Mom, can we have subtractions in absolute value?"

"No, we have subtractions in absolute value at home"

Subtractions in absolute value at home:

Geometryok but I interpreted it as intersection of straight lines (or the graph precisely) on a x-y plane tho

I think B is more difficult than C even D.Is this order a joke?I spend so much time on B and any solve three problems finally.I feel so sad.

It was a bad contest. Problem setter should think about it.

Problem D solution was leaked on youtube :(

Yes :(

Link

Are you for real? Where?

Ok that explains why c has thousands of AC while B doesn’t

He said problem D !!

Looked at the account. A b d were leaked

https://www.youtube.com/watch?v=QWYxr-IEwE0

so it would seem

This round needs to be unrated

any hint or the solution of B ?

Hint for solution without any search: Find their equivalent starting points

I tried to do that and it failed. How did you do it?

Use binary search to get the answer. In fact, here's a parabolic and you should find the x of the lowest point. Implementation

cout<<fixed<<r<<endl; what is fixed in your code ?

Although B > C, I enjoyed solving problem B.

My ideaBinary search on the maximum time taken by any person. Then once you fix time,

find [l, r]for each person. [l , r] represents howfarthest left 'l'and howfarthest right 'r'can a person can go withtime taken = mid.Once you find [l , r] pairs for everyone, you need to consider a range (lets say[ans_l , ans_r]) such that it

intersectswith all [l , r] pairs. Now the answer will be`(ans_l + ans_)/2`

i.emid-point.Code173439901

I don't know why don't they clarify problem B earlier?

I think this is too hard for a Div. 2 round

I honestly think B is too hard for a Div2B. It was only after room scanning that I learned that taking the midpoint between the minimum $$$x - t$$$ and the maximum $$$x + t$$$ yields the correct answer, but despite this leading to an extremely simple solution, the reasoning to arrive at such a conclusion is extremely difficult to achieve, imo. Most approaches seemed to involve binary searching instead, which I don't think should be a necessity for a Div2B.

I also hate floating point numbers and kept getting wrong answers because I didn't know how to set the precision until I looked it up. I really don't think it's justified for a Div2B to punish those who don't know how to deal with floating point precision. EDIT: Yes, I confirmed that the issue was floating point precision. Although the answer only requires one decimal place, the use of a floating point type (I used long double, in particular) limits the default number of significant figures to be displayed, so you need to set the precision to pass.

Was it really about floating point precision??? I did a solution where I sorted the $$$x[i]$$$, could obtain the minimum time assuming the meeting point is in between each segment($$$x[i]$$$ and $$$x[i+1]$$$) in $$$O(1)$$$, checked the time taken if meeting was at each $$$x[i]$$$, and still got it wrong... I am extremely demoralized, normally I'd walk away from a contest thinking I'd learn something but that was just terrible, the difficult D and E didn't help either

I wasted too much time on B ;-(

I had the solution for E but the contest was basically over at that point :(

B was confusing For me . Anyone found it easier ?

Why is the standings frozen?

for problem B, why does this gives tle https://codeforces.com/contest/1730/submission/173459830 while this passes https://codeforces.com/contest/1730/submission/173475885

My approach for B: Let idx be the index of the person with the maximum dressing time. Now, until this person gets dressed, move all other people "towards" person with index idx(only for the remaining time). Finally, just output (min + max)/2.

Oh nice, very creative idea!

What if there are many person with same max_dressing time?

You can actually pick any of them. Consider a case where you only have 2 of them. Let x1 and x2 be their coordinates (x1 < x2).

All people to the right of x2 move towards x2, and all people to the left of x1 move towards x1. The middle ones can move in any direction, but that doesn't matter because they aren't the extremes.

You can easily generalize this notion by induction for >2 people with same dressing time.

Hey Brovko!!! In the problem D (prefixes and suffixes) , the ans will be "YES" for this input, 6 abadaa adaaba BUT YOUR OUTPUT IS SHOWING "NO".

Initially s1=abadaa, s2=adaaba. Operation with k=5, after the operation s1=bbadaa, s2=adaaaa. Operation with k=2, after the operation s1=dbadaa, s2=abaaaa. Operation with k=4, after the operation s1=abadaa, s2=abadaa.

now both strings became equal. if anyone see my fault, then please correct me ... Thankyou

I think you misunderstand the problem. Applying operation with k = 5 on initial strings results in s1 = daabaa and s2 = aabada.

Okay!:) Thankyou TsReaper

any link to study ternary search?

here

I could solve problem C but wasted tym in B first I thought it was binary search but didnot able to solve then thought of weighted median but that also fail

Can someone explain their approach for Problem B.Took a lot of time still unable to figure out the approach

Solution for A was leaked (https://www.youtube.com/watch?v=gHxV9jwwJyk). Solution for C was leaked (https://www.youtube.com/watch?v=VhZytayYfhk). Solution for D was leaked (https://www.youtube.com/watch?v=QWYxr-IEwE0).

Somebody ban SecondPractice who posted solutions and others who cheated.

Brovko shnirelman Lankin MikeMirzayanov

Yea seems like a lot of people copied C, because C wasn't that easy, these incidents keep ruining the performances of those who participate fairly.

Although (scoring distribution) vs (# of AC) is not good as a result, I guess it's hard to estimate the difficulty of this kind of B, and I like the problems itself. Thanks for the writers' work!

Only solved 1 problem in Hacker Cup. Only solved 1 problem in CF-823. Can't even all kill LeetCode Weekly.

What a wonderful weekends!

It's ok. We all have some bad times, look at my plot for example

Well (my delta for this round is -47 as well)

Guess I'm saving my luck for my school's TST in 2 weeks

problem B, if we consider n function yi = ti + |xi — x0|, then the answer will be the x value of their "intersection point".

to get the intersection, one can refer to editorial code of this problem

Why are standings frozen?

And here i thought i would solve the first 2 questions this time....

I even thought of solving three problems... 😂😂😂

i thought i will solve 2 but didnt know it will be C and not B

what is "standing frozen"?

Not sure why my B is wrong what's important is the maximum xi+ti value to meet the minimum xi-ti value right? And taking care the values don't cross the maximum and minimum xi but i got WA on 3

i get 5 wrong answer in c in test 3 :( :( why????

Was not even aware of the C++ scientific notation / std::set precision things before. Got WAs on B for this single stupid reason.

You got to be kidding me, I just edited my contest solution, adding "set_precision" and got AC, I assumed that just defining all variables with long double will work, I have never felt worse after a CP contest ever

Same. My ranking would've been halved if I just put setpercision on my first attempt.

Am I the only one who is not able to see other participant's solution after system testing?

Yes

According to my guidebook, the answer to problem A is 42

-10 social rating for authors

No neko-tyan and no bowl of rice for the authors

Can anyone explain me, how removing cin.tie and ios_base from my code made it correct(without using scanf/printf and cin/cout at the same time)? Proofs:

173471466 and 173471909 in C(somehow gives empty strings with them )

173456777 and 173466682 in B(mystical ML with them)

SpoilerYou should put them first in main().

Thank you, I have already understood. It's funny that it works with some compilers/arguments and not with others

How to find cheaters?

Spoilerselect idiots who solved D in last 10 minutes xD

[deleted]

I'm talking about low rank people who solved D.. sure not all who solved it are cheaters

actually he's right. just skip (but better ban) those whose solution looks like:

I understand, that a lot of people pings you in comments, or you might already know about this situation, but MikeMirzayanov, geranazavr555, can you, please take this into account, while searching for cheaters? If needed, I can personally provide handles of few people with solutions like the one from above

p.s. link for video if needed:

By the way, I found 150+ cheaters using my submission parser. It looks for weird chars like '10' or '20'.

UPD. Thanks to Codeforces team for removing these cheaters!

I think cheater skipped all the problem. It's too weak to just skip that problem.

obviously

should we ping Mike ig?

What do these numbers mean?

These numbers are submission IDs.

Unbalanced round. Good thing I decided to skip B after like 30 minutes though

How should I know that I need to put cout<<fixed<<setprecision(6) at the end? I wrote fricking segment tree to solve B and this is my only mistake.

Will this round be unrated due to solution leaking? It seems hard to prevent someone posting solution on YT during contest though:(

On what topic the second question was based on?

cout << fixed << setprecision(10)<< ans << '\n';

how to solve C?? plzz help

Each digit needs to see how many bigger digits are to its left.. as they have to be moved and so they will gain 1 value.. Trick is that each digit at max needs to be "upvalued" only once, because after once it is moved we can put it in such a place that it won't need to be deleted again.

So we have to take care that 1 digit doesn't gets "upvalued" twice or more... So check from the lowest digit (whatever is present) and increase all the digits to its left which are bigger that it.

https://codeforces.com/contest/1730/submission/173477171

thanks for explaining :)

For B: The difference between during contest and after contest

cout << fixed << setprecision(10);

CRY !! CRY !! CRY

https://codeforces.com/contest/1730/submission/173497432 (after contest) https://codeforces.com/contest/1730/submission/173477171 (during contest)

My logic was to find the max dressing time and make others go towards the lazy dresser till he/she finishes. Then take the mean of the farthest 2 person's position

WOW!!

Ones who solved C is more than ones who solved B XD

I solved problem B easily but couldn't solve C. Don't know whether to feel sad or happy about this.

Be proud of yourself.

Of course be happy❤❤

Problem B

Solution for D:

Note pairs:$$$(a[0],b[n-1]),(a[1],b[n-2]),...,(a[n-1],b[0]).$$$

In pair $$$(a[i],b[j])$$$,if the final position of $$$a[i]$$$ is determined,then $$$b[j]$$$'s position is also determined.

For example,$$$a[i]$$$'s final position is $$$x$$$ in the $$$2^{rd}$$$ string,we can get $$$b[j]$$$'s position is $$$(n-x-1)$$$ in the $$$1^{st}$$$ string.

Now let's check the answer.

If $$$n$$$ is even,

check if we can match each two pairs $$$(a[i_1],b[i_1])$$$,$$$(a[i_2],b[i_2])$$$ ,such that $$$a[i_1]==b[i_2],b[i_1]==a[i_2]$$$ or $$$a[i_1]==a[i_2],b[i_1]==b[i_2]$$$.

In other words,each number of occurrences of pair $$$(min(a[i],b[i]),max(a[i],b[i]))$$$ must be even.

If n is odd,

Similiar to the method above but a bit different.

If you've shown that such pairs are invariants to the operation it would prove the necessity of this condition. For complete proof of the solution sufficiency also should be proven

Shouldn't it be $$$a[i_1] == b[i_1], a[i_2] == b[i_2]$$$ or $$$a[i_1] == a[i_2], b[i_1] == b[i_2]$$$?

It should be $$$a[i_1]==b[i_2],b[i_1]==a[i_2]$$$ or $$$a[i_1]==a[i_2],b[i_1]==b[i_2]$$$.

Assume $$$a[i_1]$$$ is in the $$$1^{st}$$$ string,the two（equal）strings look like:

$$$... a[i_1] ... a[i_2] ...$$$

$$$... b[i_2] ... b[i_1] ...$$$

or

$$$... a[i_1] ... b[i_2] ...$$$

$$$... a[i_2] ... b[i_1] ...$$$

Thanks for the visualization. I understood it now.

173499940 why I am getting tle though the solution is O(n) for question b

Didn't dive in the specific testcase, but you are doing ans=d under some condition, while looping until d<=ans+1, so this might happen quite a lot and cause TLE.

Solved B right after the contest sadge

Wow, what a problem B!! was not able to solve it :(

Wtfffff double may not catch 0.5 without setprecision for numbers under 10^9 this is really sad my rating would have greatly increased

Can we solve Problem C using stack or Queue? If yes then please explain approach.

yes but it's not necessary, yet here is an answer using a stack.

answerThe winner list is nothing similar as the correct one. What happened?

Sorry, now it's fixed

For problem B, how does one know they need to use

`cout << fixed`

during the contest? Or is it purely from experience? I have never had a situation like this before and I think it would be impossible for me to solve this question.I had experienced it once before. From next time you will be aware of it, take it positively :)

I found my solution to B after visualizing it in a coordinate system.

For each ($$$i$$$-th) person, I plot the piecewise function $$$y=f_i(x)=|x-x_i|+t_i$$$ in a coordinate plane. ($$$f_i(x)$$$ is the total amount of time required for $$$i$$$-th person to get dressed and get to the meeting located at $$$x$$$)

Then, I plot the piecewise function $$$y=f(x)=\max_{i=1}^n{f_i(x)}$$$ in the same coordinate plane. (The curve of this function is made up of segments, which actually compose the upper bound of curves plotted in the previous step)

And then, I can see the answer, which is the x coordinate of the lowest point of the curve $$$y=f(x)$$$.

What remains is an elementary mathematics problem, which is not too hard. (Just find the two segments with highest intercepts, one of which has a slope of 1, the other has a slope of -1. Then compute their intersection point)

So, that's how I solved it.

This solution is intuitive & it reduces to the "classic" solution on the editorial once you note that the two segments with the highest intercepts correspond to the minimum and maximum (x_i — t_i) and (x_i + t_i).

My idea for B:

We know the answer is bounded by the max and min position of people. We only need to worry about the latest person arrived, so at each position we only care about the one with the longest prep time.

Define left[i] as the time it takes for everyone left of i (included i) takes to arrive at i Define right[i] as the time it takes for everyone right of i (included i) takes to arrive at i

Obviously if the meeting point is at i then it'd be max of left[i], right[i] If the meeting point is between i and i + 1, then we can find the difference between left[i] and right[i], take whatever left of that segment divided by 2.

This problem is heavy implementation imo. Very hard for Div2B, at least a 1700-1800 rating

WA Submission AC Submission

Welcome to life, where you get penalised for stupid little compiler problems ;-;

A general question. I am a newbie and I feel I am near to a saturation point.

So what should I do to improve? Should practice question that are having ratings greater than my current rating or should I go for B's or C's. I am confused. Please help.

In problem B , will the graph between X(meeting point) and the time be a parabola?

## B

Binary_search solution

Ternary_search solution

https://codeforces.com/problemset/problem/782/B

Just go through this problem, i find this problem very similar to todays Round 823 Problem B

Please look into it, Mike.

Thanks in advance

Nahh, it's not copied it just has similar way to observe the solution but not completely the same. As supposin' that both of them are the same we can also confirm that B782 has absolutely the same approach as in Edu_binary search step3A.

Having the same algorithm to solve or nearly same observation doesn't mean they are completely similar!!

just to say becoming Specialist, feels good.

Hello would you please review my code for problem B? 173484519

Failed 6 times during contest...

you've just had to add "cout << setprecision(15) << fixed"

here is an accepted solution with your code:173541867

Thank you very much!!! I add you to my friend list ^_^.

I have been stuck so many times because of a lack of my basic skills. I have to improve it. With this line, I might become blue because I finish this code in a very short time, but finally, my score dropped a lot. This issue makes me very frustrated and upset.

By the way, I am still confused: Why does my submission fail to work without the

`setprecision`

line?I understand you, last three contests have really been destroying for me..

And what about setprecision: as far as I know, cout doesn't work well with doubles at all.. Though we can think that double provides really good precision, when we try to output it, we can actually get into trouble because we didn't tell to cin we do really want this precision. So, if I have to work with doubles i just add this line to my code immediately. I'm really sorry if my explanation is not so clear, but i'm really sure that you can find more information in different codeforces blog, if you didn't get it :)

I remember next time that

`cout`

for double is crazily buggy and next time I will avoid it~. My code looks very weird because I "finetune" a lot of "hyperparameters" (eg. 3e-7). I was very desperate yesterday. Anyway, I never think of the`setprecision`

line so I deserve losing the score...Thank this round for reducing my rating by 98 points, I mean I have no mental load any more, I will focus on the knowledge and the problem itself rather than the rating

Hello MikeMirzayanov, my all solutions were skipped for the round Codeforces Round #823 (Div. 2). It's frustrating as I received a message from CF that my answer was matched with a few others which can pretty obviously occur as the code was small. I never used the set precision thing before so I googled it and many others came to know this concept the first time too googled it and maybe a little more coincidence occurred when I saw the solution for the problem D. Barcelonian Distance and the solution is 171563303 at the last there is a different way of output the answer i.e cout<<fixed<<setprecision(9)<<endl; which I used so maybe other did the same and our solution may match up to some extend. It is requested to reconsider my case. You can check my other solutions at higher plag and I believe you won't find anything there.

There is a BIG gap between C and D! C's rating is 1200 while D's rating is 2200.

E and F are both 2700 ranking. clist.by gives E 2945, which is even higher than F's 2896. But E only has 2250 points. This is not balanced. Considering B is also somehow harder than C (1572 vs 1214 by clist.by), The balance of this contest is not good.

I got rk3 in this contest and appear in the winner list, which is best of myself, and become IM first time. And when I solved E, I found I'm the first one in rated list. Really a big breakthrough of myself.

Nice contest， now i think D is harder than C not a little.

## The horrible problem B

There was cheatingplease check thishttps://codeforces.com/blog/entry/107295

Negative comment! Question B is more difficult than question C? It's unreasonable! I want to complain!