### Brovko's blog

By Brovko, 2 months ago,

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:

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:

• +144

 » 2 months ago, # |   +97 What happened to Pinely Codeforces Round 1 ?
•  » » 2 months ago, # ^ |   0 what even is pinely?
•  » » » 2 months ago, # ^ |   +1
•  » » » 2 months ago, # ^ |   +74 .
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Let's just admit that this contest's Problem B is even harder than last contest's Problem D1.
•  » » » » 2 months ago, # ^ |   0 B is so hard :(
 » 2 months ago, # | ← Rev. 2 →   +24 Brovko The announcement says it will be 2 hrs, but in contests page it shows 2.30 hrs. What is the right one lolupd.: fixed
•  » » 2 months ago, # ^ |   +13 thanks, fixed
 » 2 months ago, # |   +15 As a participant,I'm hoping for a great round OvO!
 » 2 months ago, # |   +13 isn't this contest's previous name Pinely Codeforces Round 1 ?
 » 2 months ago, # |   +5 Hope to beat my previous best! Everyone wants the same right? Good luck!!
 » 2 months ago, # |   +10 Lol i got pinged
•  » » 2 months ago, # ^ |   +6 What a coincidence... Me too! I would like to request a refund...
•  » » 2 months ago, # ^ |   +5 Also the round is nice, you can participate if you want
 » 2 months ago, # |   +10 hoping for more than +2 delta
 » 2 months ago, # |   +13 Brovko round! Will be pleasant to partake!
 » 2 months ago, # |   0 I want to be a pupil❤ Why even I don't reach pupil and continue to get negative rating!(⊙_⊙)？
•  » » 2 months ago, # ^ |   -17 practise more problems in 1200-1300 range
•  » » » 2 months ago, # ^ |   0 Hope I'll become pupil in this round
•  » » » » 2 months ago, # ^ |   0 me as well
•  » » » » » 2 months ago, # ^ |   0 In which year you are in?
•  » » » » » » 2 months ago, # ^ |   0 2nd
•  » » » » » » » 2 months ago, # ^ |   0 same iam from delhi technological university
•  » » » » » » » » 2 months ago, # ^ |   0 same from Vit vellore
•  » » » » 2 months ago, # ^ |   0 yeah mee too :(
•  » » 2 months ago, # ^ |   0 Solve A and B If this doesn't help, Solve A and B faster If this still doesn't help, something's wrong in the process
•  » » » 2 months ago, # ^ |   0 Noted!
•  » » 2 months ago, # ^ |   0 I also being pupil after 50 contest...
 » 2 months ago, # |   0 Hoping +ve delta!
 » 2 months ago, # |   +34 Why was this changed from a combined round to D2?
•  » » 2 months ago, # ^ |   +17 I don't know what happened to Pinely Round but it was canceled and replaced by common Div2.
•  » » » 2 months ago, # ^ |   0 Oh, okay. Thank you for the fast reply.
 » 2 months ago, # |   0 Is this Round be rated or unrated?
•  » » 2 months ago, # ^ |   +33 It is rated for people with less than $2100$ rating.
 » 2 months ago, # |   0 I am going to give my best in this contest..hoping for a positive delta
 » 2 months ago, # |   0 hopeing to solve C today
 » 2 months ago, # |   0 Hello, World
 » 2 months ago, # |   0 When will the score distribution be announced?
 » 2 months ago, # |   0 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
•  » » 2 months ago, # ^ |   0 Same the contest are not visible but my rating is as earlier
 » 2 months ago, # |   0 What happened to ratings, 3 to 4 rounds ratings are rolled back, is it for me or for everyone?
•  » » 2 months ago, # ^ |   0 no,its for everyone
 » 2 months ago, # | ← Rev. 2 →   +11 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?
 » 2 months ago, # |   +6 lucky
 » 2 months ago, # | ← Rev. 2 →   +3 Cool Scoring distribution. Will try to solve 5/6.upd: failed
•  » » 2 months ago, # ^ |   0 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."
•  » » » 2 months ago, # ^ |   0 The updated ratings will be available soon.
•  » » » 2 months ago, # ^ |   0 Ignore it. Just solve your problems:)
•  » » » » 2 months ago, # ^ |   +6 Yes man exactly thats the point
•  » » » » » 2 months ago, # ^ |   +6 They will remove cheaters, update scoreboard and reapply the new rating changes.
 » 2 months ago, # |   0 Thank you to everyone who participated in creating this contest
 » 2 months ago, # |   0 I hope the problem statements are as concise and short as announcement :)
 » 2 months ago, # |   0 I am a Newbie now. Will become Specialist after the contest. Wait and Watch.
•  » » 2 months ago, # ^ |   0 IIITH...BROOOOOOOO
 » 2 months ago, # |   0 it is said that good luck is hiding in the problems !!!
 » 2 months ago, # |   0 I will become specialist after this round
•  » » 2 months ago, # ^ |   0 same goal :)
•  » » » 2 months ago, # ^ |   0 one of my another account is also pupil xxzxsyl
 » 2 months ago, # |   +5 My first contest in like 3 weeks.
•  » » 2 months ago, # ^ |   0 sad lol
 » 2 months ago, # | ← Rev. 2 →   0 ..
 » 2 months ago, # |   +6 tough
 » 2 months ago, # |   +32 The best B problen I've seen.(Joke)
•  » » 2 months ago, # ^ |   +23 Actually B is a double problem.B1 is understanding B, then B2 is solving B.
 » 2 months ago, # |   +2 Unbalanced Round. -_-
 » 2 months ago, # |   +6 How unbalanced do you want the contest to be? Authors: YES!
 » 2 months ago, # |   +9 Unbalanced Round :(
 » 2 months ago, # |   +10 B and C need to be swapped LOL twice as many C solves as B
 » 2 months ago, # | ← Rev. 2 →   +2 Even I like the idea of B it was too hard to be B
 » 2 months ago, # |   0 Am I the only one who still does not understand Problem B?
 » 2 months ago, # |   +11 190 years for getting dressed :-| !!
 » 2 months ago, # | ← Rev. 4 →   +56 Oh my god! I cannot even imagine that I could officially be top 20 in a div2 contest.
•  » » 2 months ago, # ^ |   +1 congrats!
•  » » 2 months ago, # ^ |   0 How do you see your approximate performance and rating before rating canculations? Is it a browser extension or it could be unlocked in settings?
•  » » » 2 months ago, # ^ |   +3 I am using carrot, a browser extension by Chrome.
•  » » » » 2 months ago, # ^ |   0 Cool, thanks :)
•  » » » 2 months ago, # ^ |   0 It is browser extension called carrot.
•  » » » » 2 months ago, # ^ |   +5 I love carrots
•  » » 2 months ago, # ^ |   +16 "No human is limited". Believe in yourself, maybe one day you can become a LGM!
•  » » 2 months ago, # ^ |   0 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
 » 2 months ago, # |   +6 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
•  » » 2 months ago, # ^ |   0 it requires absolutely no algorithmic skills and even worse, it is easy to pass with an intuitive solution without proof
•  » » 2 months ago, # ^ |   +8 I have no idea how to solve D, though spent a lot of time on itBut for B it was a clear ternary search from the start
•  » » » 2 months ago, # ^ |   0 any guess where my submission went wrong 173488027
•  » » » » 2 months ago, # ^ |   0 Take a look at Ticket 16219 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 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
•  » » » » 2 months ago, # ^ |   0 First sentence is actually lie, I used binary and wrong naming for it
•  » » » 2 months ago, # ^ |   0 Binary search works too
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I don't think ternary search is needed for B Please look at my submission 173464664
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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 :PBut 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)
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Yeah, buffering shouldn't have affected so much for t=1000Also I only intended to change eps as constant factor optimization But apparently it lead to some kind of infinite loop because of precision issuesI didn't think about it during the contest but for big numbers step of 1e-10 does not exist, so while loop becomes infinite 1e8 + 1e-12 == 1e8 True 
 » 2 months ago, # |   +14 The problem B is good example why Codeforces EDU section is helpful
•  » » 2 months ago, # ^ |   0 why
 » 2 months ago, # |   +5 I'm wondering what B's pretest 3 is. Got many WAs on that pretest.
•  » » 2 months ago, # ^ |   0 cout<<123456789.5<
•  » » » 2 months ago, # ^ |   0 Should the test system consider both as correct? I think the problem statement didn't say "scientific notation is not allowed".
•  » » » » 2 months ago, # ^ |   0 scientific notation losses the accuracy by only reserving certain number of digits
•  » » » » » 2 months ago, # ^ |   0 Oh, OK, but such issues aren't related to algorithms / problem solving. I wasn't even aware of this thing before.
•  » » » 2 months ago, # ^ |   +1 It got me too :( Could have solved ABCD otherwise :(
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +14 How to solve D?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +2 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 Swap any letters at position $i$, $s_1[i]$ and $s_2[i]$. (i.e exchange the letters at position $i$ of both the strings. Note that $s_1$ is not the original $s_1$, it is the reversed string). Swap any pairs $(s_1[i] , s_2[i])$ and $(s_1[j] , s_2[j])$, for any index $i$ and $j$. Now its easy to solve!
•  » » » 2 months ago, # ^ |   +4 Swap any pairs (s1[i],s2[i]) and (s1[j],s2[j]), for any index i and jHow?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 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!).
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 in another observation you actually have wrote a cyclic shift of 1 unit left
 » 2 months ago, # |   +2 was B binary search?
•  » » 2 months ago, # ^ |   -9 no. it requires ternary search!
•  » » » 2 months ago, # ^ |   +10 Binary search also works here
•  » » » 2 months ago, # ^ |   +10 There is a simpler solution: (min(a[i]-t[i])+max(a[i]+t[i]))/2
•  » » » » 2 months ago, # ^ |   0 What's the intuition for that? How does subtracting the ready time get you the answer?
•  » » » » 2 months ago, # ^ |   0 Can you please describe your intuition behind it?
•  » » » » » 2 months ago, # ^ |   +3 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.
•  » » » 2 months ago, # ^ |   0 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
•  » » 2 months ago, # ^ |   0 ternary search, but what was testcase 3 :((
•  » » » 2 months ago, # ^ |   +4 need to increase precision of double printed...
•  » » » 2 months ago, # ^ |   0 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
•  » » » » 2 months ago, # ^ |   0 yeah eps=1e-6, the problem was with set precision.
•  » » 2 months ago, # ^ |   0 yep
•  » » 2 months ago, # ^ |   0 someone said it's ternary search , I ll search what ternary search is.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » 2 months ago, # ^ |   0 well however if the mid point
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   0 I didn't use setprecision in double . thats why I got wa — _ -
•  » » 2 months ago, # ^ |   0 I used binary search,but got TLE at point 4.
 » 2 months ago, # |   +39 This is the worst round I've ever participated in.
 » 2 months ago, # |   +3 u regret wasting time on B and not trying C dont u?
 » 2 months ago, # |   +2 In contest : swap(Problem B, Problem C) :(
 » 2 months ago, # |   +6 Wasted about 30 minutes thinking of $B$ and solved $C$ in like 15 minuteswhy didn't you swap $B$ and $C$ :(
 » 2 months ago, # |   +5 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)
 » 2 months ago, # |   +8 Someone give me a hint for B so I can feel stupid.
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # | ← Rev. 2 →   0 Was debugging 1e+08 mistake in task B 30 min :(
 » 2 months ago, # |   0 How do you solve B? I tried a ton of different things but none of them worked :(
•  » » 2 months ago, # ^ |   0 use ternary search
•  » » » 2 months ago, # ^ |   0 Could you please elaborate?
•  » » » 2 months ago, # ^ |   0 i've used greedy
•  » » » 2 months ago, # ^ |   0 You don't need ternary search, there an O(n) solution.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 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
•  » » » 2 months ago, # ^ |   +5 Thank you so much for this explanation!
•  » » » 2 months ago, # ^ |   +13 nice solution. Thanks a lot
 » 2 months ago, # | ← Rev. 2 →   +1 Video Solution for Problem B,Problem C.
 » 2 months ago, # |   0 could one help me to understand problem b, it take all my time
 » 2 months ago, # |   -26 Today's round was GeometryForces brought to you by: B
•  » » 2 months ago, # ^ |   +5 "Mom, can we have subtractions in absolute value?""No, we have subtractions in absolute value at home"Subtractions in absolute value at home:Geometry
•  » » » 2 months ago, # ^ |   -12 ok but I interpreted it as intersection of straight lines (or the graph precisely) on a x-y plane tho
 » 2 months ago, # |   +1 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.
•  » » 2 months ago, # ^ |   -9 It was a bad contest. Problem setter should think about it.
 » 2 months ago, # |   +43 Problem D solution was leaked on youtube :(
•  » » 2 months ago, # ^ |   0 Yes :(Link
•  » » 2 months ago, # ^ |   0 Are you for real? Where?
•  » » 2 months ago, # ^ |   0 Ok that explains why c has thousands of AC while B doesn’t
•  » » » 2 months ago, # ^ |   0 He said problem D !!
•  » » » » 2 months ago, # ^ |   0 Looked at the account. A b d were leaked
•  » » 2 months ago, # ^ |   0 https://www.youtube.com/watch?v=QWYxr-IEwE0so it would seem
•  » » 2 months ago, # ^ |   -21 This round needs to be unrated
 » 2 months ago, # |   +1 any hint or the solution of B ?
•  » » 2 months ago, # ^ |   0 Hint for solution without any search: Find their equivalent starting points
•  » » » 2 months ago, # ^ |   0 I tried to do that and it failed. How did you do it?
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 Use binary search to get the answer. In fact, here's a parabolic and you should find the x of the lowest point. Implementation
•  » » » 2 months ago, # ^ |   0 cout<
 » 2 months ago, # | ← Rev. 2 →   +1 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 how farthest left 'l' and how farthest right 'r' can a person can go with time 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 intersects with all [l , r] pairs. Now the answer will be (ans_l + ans_)/2 i.e mid-point. Code173439901
 » 2 months ago, # |   0 I don't know why don't they clarify problem B earlier?
 » 2 months ago, # |   +44 I think this is too hard for a Div. 2 round
 » 2 months ago, # | ← Rev. 4 →   +7 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.
•  » » 2 months ago, # ^ |   +3 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
 » 2 months ago, # |   0 I wasted too much time on B ;-(I had the solution for E but the contest was basically over at that point :(
 » 2 months ago, # |   0 B was confusing For me . Anyone found it easier ?
 » 2 months ago, # |   +42 Why is the standings frozen?
 » 2 months ago, # | ← Rev. 2 →   0 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
 » 2 months ago, # | ← Rev. 2 →   +12 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.
•  » » 2 months ago, # ^ |   0 Oh nice, very creative idea!
•  » » 2 months ago, # ^ |   0 What if there are many person with same max_dressing time?
•  » » » 2 months ago, # ^ |   +1 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.
•  » » 2 months ago, # ^ |   +3 I think you misunderstand the problem. Applying operation with k = 5 on initial strings results in s1 = daabaa and s2 = aabada.
•  » » » 2 months ago, # ^ |   -8 Okay!:) Thankyou TsReaper
 » 2 months ago, # |   0 any link to study ternary search?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0
 » 2 months ago, # |   0 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
 » 2 months ago, # |   0 Can someone explain their approach for Problem B.Took a lot of time still unable to figure out the approach
 » 2 months ago, # | ← Rev. 2 →   +65 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.
•  » » 2 months ago, # ^ |   +2 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.
 » 2 months ago, # |   +38 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!
 » 2 months ago, # | ← Rev. 2 →   +1 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!
•  » » 2 months ago, # ^ |   +1 It's ok. We all have some bad times, look at my plot for example
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Well (my delta for this round is -47 as well)Guess I'm saving my luck for my school's TST in 2 weeks
 » 2 months ago, # | ← Rev. 3 →   0 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
 » 2 months ago, # |   +8 Why are standings frozen?
 » 2 months ago, # |   0 And here i thought i would solve the first 2 questions this time....
•  » » 2 months ago, # ^ |   0 I even thought of solving three problems... 😂😂😂
•  » » » 2 months ago, # ^ |   0 i thought i will solve 2 but didnt know it will be C and not B
 » 2 months ago, # |   +6 what is "standing frozen"?
 » 2 months ago, # | ← Rev. 2 →   +3 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
 » 2 months ago, # |   0 i get 5 wrong answer in c in test 3 :( :( why????
 » 2 months ago, # |   +8 Was not even aware of the C++ scientific notation / std::set precision things before. Got WAs on B for this single stupid reason.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +12 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
•  » » » 2 months ago, # ^ |   0 Same. My ranking would've been halved if I just put setpercision on my first attempt.
 » 2 months ago, # |   0 Am I the only one who is not able to see other participant's solution after system testing?
•  » » 2 months ago, # ^ |   0 Yes
 » 2 months ago, # |   0 According to my guidebook, the answer to problem A is 42
 » 2 months ago, # |   +13 -10 social rating for authors
•  » » 2 months ago, # ^ |   +7 No neko-tyan and no bowl of rice for the authors
 » 2 months ago, # |   +3 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)
•  » » 2 months ago, # ^ |   +1 Spoiler#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { } return 0; } You should put them first in main().
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 Thank you, I have already understood. It's funny that it works with some compilers/arguments and not with others
 » 2 months ago, # |   0 How to find cheaters? Spoilerselect idiots who solved D in last 10 minutes xD
•  » » 2 months ago, # ^ | ← Rev. 2 →   -16 [deleted]
•  » » » 2 months ago, # ^ |   +1 I'm talking about low rank people who solved D.. sure not all who solved it are cheaters
•  » » 2 months ago, # ^ |   +11 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 abovep.s. link for video if needed:
•  » » 2 months ago, # ^ | ← Rev. 2 →   +27 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!
•  » » » 2 months ago, # ^ |   0 I think cheater skipped all the problem. It's too weak to just skip that problem.
•  » » » » 2 months ago, # ^ |   0 obviously
•  » » » 2 months ago, # ^ |   0 should we ping Mike ig?
•  » » » 2 months ago, # ^ |   0 What do these numbers mean?
•  » » » » 2 months ago, # ^ |   +1 These numbers are submission IDs.
 » 2 months ago, # | ← Rev. 2 →   0 Unbalanced round. Good thing I decided to skip B after like 30 minutes though
 » 2 months ago, # |   +6 How should I know that I need to put cout<
 » 2 months ago, # | ← Rev. 2 →   +4 Will this round be unrated due to solution leaking? It seems hard to prevent someone posting solution on YT during contest though:(
 » 2 months ago, # |   0 On what topic the second question was based on?
•  » » 2 months ago, # ^ |   +8 cout << fixed << setprecision(10)<< ans << '\n';
 » 2 months ago, # |   0 how to solve C?? plzz help
•  » » 2 months ago, # ^ |   0 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
•  » » » 2 months ago, # ^ |   0 thanks for explaining :)
 » 2 months ago, # |   +1 For B: The difference between during contest and after contestcout << fixed << setprecision(10);CRY !! CRY !! CRYhttps://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
 » 2 months ago, # | ← Rev. 2 →   +3 WOW!! Ones who solved C is more than ones who solved B XD
 » 2 months ago, # |   0 I solved problem B easily but couldn't solve C. Don't know whether to feel sad or happy about this.
•  » » 2 months ago, # ^ |   +3 Be proud of yourself. Of course be happy❤❤
 » 2 months ago, # |   +63 Problem B
 » 2 months ago, # | ← Rev. 2 →   +6 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 2 months ago, # ^ |   0 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]$?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +1 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] ...$
•  » » » » 2 months ago, # ^ |   0 Thanks for the visualization. I understood it now.
 » 2 months ago, # |   0 173499940 why I am getting tle though the solution is O(n) for question b
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 Solved B right after the contest sadge
 » 2 months ago, # |   0 Wow, what a problem B!! was not able to solve it :(
 » 2 months ago, # |   +8 Wtfffff double may not catch 0.5 without setprecision for numbers under 10^9 this is really sad my rating would have greatly increased
 » 2 months ago, # |   0 Can we solve Problem C using stack or Queue? If yes then please explain approach.
•  » » 2 months ago, # ^ |   0 yes but it's not necessary, yet here is an answer using a stack. answer#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { string a; cin >> a; int n = a.size(); stack s; string b = ""; for (int i = n - 1; i >= 0; i--) { if (s.size() == 0) s.push(a[i]); else { if (a[i] <= s.top()) s.push(a[i]); else b += min(char(a[i] + 1), '9'); } } string ans = ""; while (s.size()) { ans += s.top(); s.pop(); } ans += b; sort(ans.begin(), ans.end()); cout << ans << "\n"; } return 0; } 
 » 2 months ago, # |   +29 The winner list is nothing similar as the correct one. What happened?
•  » » 2 months ago, # ^ |   +20 Sorry, now it's fixed
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   +3 I had experienced it once before. From next time you will be aware of it, take it positively :)
 » 2 months ago, # |   +1 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.
•  » » 2 months ago, # ^ |   +1 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).
 » 2 months ago, # |   +1 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 iObviously 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
 » 2 months ago, # |   +2 Welcome to life, where you get penalised for stupid little compiler problems ;-;
 » 2 months ago, # |   0 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.
 » 2 months ago, # |   0 In problem B , will the graph between X(meeting point) and the time be a parabola?
»
2 months ago, # |
0

# B

Binary_search solution
Ternary_search solution

 » 2 months ago, # | ← Rev. 2 →   -13 https://codeforces.com/problemset/problem/782/BJust go through this problem, i find this problem very similar to todays Round 823 Problem BPlease look into it, Mike.Thanks in advance
•  » » 2 months ago, # ^ |   +3 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!!
 » 2 months ago, # |   0 just to say becoming Specialist, feels good.
 » 2 months ago, # | ← Rev. 3 →   0 Hello would you please review my code for problem B? 173484519
•  » » 2 months ago, # ^ |   0 Failed 6 times during contest...
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +1 you've just had to add "cout << setprecision(15) << fixed"here is an accepted solution with your code:173541867
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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...
 » 2 months ago, # |   0 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
 » 2 months ago, # |   0 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<
 » 2 months ago, # |   0 There is a BIG gap between C and D! C's rating is 1200 while D's rating is 2200.
 » 2 months ago, # |   0 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.
 » 2 months ago, # |   0 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.
 » 2 months ago, # |   +3 Nice contest， now i think D is harder than C not a little.
»
2 months ago, # |
0

### The horrible problem B

 » 2 months ago, # |   0 There was cheating please check this https://codeforces.com/blog/entry/107295
 » 2 months ago, # |   0 Negative comment! Question B is more difficult than question C? It's unreasonable! I want to complain!