Brovko's blog

By Brovko, 18 months ago, In English

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:

  1. heno239
  2. Um_nik
  3. maspy
  4. jiangly
  5. ksun48

Div2:

  1. billieeyelash
  2. PokerCareer
  3. simiao1986
  4. i_will_be_less_than_blue
  5. Timonnable
  • Vote: I like it
  • +144
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
  Vote: I like it +97 Vote: I do not like it

What happened to Pinely Codeforces Round 1 ?

»
18 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Lol i got pinged

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +10 Vote: I do not like it

hoping for more than +2 delta

»
18 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Brovko round! Will be pleasant to partake!

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to be a pupil❤
Why even I don't reach pupil and continue to get negative rating!(⊙_⊙)?

»
18 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Why was this changed from a combined round to D2?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this Round be rated or unrated?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the score distribution be announced?

»
18 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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?

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

lucky

»
18 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

upd: failed

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The updated ratings will be available soon.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ignore it. Just solve your problems:)

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Yes man exactly thats the point

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will become specialist after this round

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

My first contest in like 3 weeks.

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

tough

»
18 months ago, # |
  Vote: I like it +32 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Actually B is a double problem.

    B1 is understanding B, then B2 is solving B.

»
18 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Unbalanced Round. -_-

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How unbalanced do you want the contest to be?
Authors: YES!

»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Unbalanced Round :(

»
18 months ago, # |
  Vote: I like it +10 Vote: I do not like it

B and C need to be swapped LOL twice as many C solves as B

»
18 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +11 Vote: I do not like it

190 years for getting dressed :-| !!

»
18 months ago, # |
Rev. 4   Vote: I like it +56 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    congrats!

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Binary search works too

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        18 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        18 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

        1e8 + 1e-12 == 1e8
        True
        
»
18 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cout<<123456789.5<<endl; and you will get 1.23457e+08 in the output I believe this is the reason

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Should the test system consider both as correct? I think the problem statement didn't say "scientific notation is not allowed".

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i had no idea about this:))

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
18 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve D?

  • »
    »
    18 months ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    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

    1. 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).
    2. 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!

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      How?

      • »
        »
        »
        »
        18 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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!).

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +2 Vote: I do not like it

was B binary search?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    no. it requires ternary search!

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Binary search also works here

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      There is a simpler solution: (min(a[i]-t[i])+max(a[i]+t[i]))/2

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please describe your intuition behind it?

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like 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.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ternary search, but what was testcase 3 :((

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      need to increase precision of double printed...

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +39 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

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

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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)

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use ternary search

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please elaborate?

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you so much for this explanation!

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      nice solution. Thanks a lot

»
18 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Video Solution for Problem B,Problem C.

»
18 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Today's round was GeometryForces brought to you by: B

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    "Mom, can we have subtractions in absolute value?"

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

    Subtractions in absolute value at home:

    Geometry

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
18 months ago, # |
  Vote: I like it +43 Vote: I do not like it

Problem D solution was leaked on youtube :(

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

any hint or the solution of B ?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like 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

»
18 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Although B > C, I enjoyed solving problem B.

My idea
»
18 months ago, # |
  Vote: I like it +44 Vote: I do not like it

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

»
18 months ago, # |
Rev. 4   Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

»
18 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Why is the standings frozen?

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
18 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

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.

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh nice, very creative idea!

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if there are many person with same max_dressing time?

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

»
18 months ago, # |
  Vote: I like it -31 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
18 months ago, # |
Rev. 2   Vote: I like it +65 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

»
18 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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!

»
18 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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!

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

»
18 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Why are standings frozen?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

what is "standing frozen"?

»
18 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +13 Vote: I do not like it

-10 social rating for authors

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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)

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Spoiler

    You should put them first in main().

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to find cheaters?

Spoiler
  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    [deleted]

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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:

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    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!

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      should we ping Mike ig?

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do these numbers mean?

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
18 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

On what topic the second question was based on?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
18 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +63 Vote: I do not like it

Problem B

»
18 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]$$$?

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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] ...$$$

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the visualization. I understood it now.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved B right after the contest sadge

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like 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

»
18 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I had experienced it once before. From next time you will be aware of it, take it positively :)

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like 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).

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +2 Vote: I do not like it

WA Submission AC Submission

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B

Binary_search solution
Ternary_search solution

»
18 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!!

»
18 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Failed 6 times during contest...

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      here is an accepted solution with your code:173541867

      • »
        »
        »
        »
        18 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like 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...

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B

The horrible problem B

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to implement B by the Binary Search Method given in the Editorial. I am not able to get why it is not passed if we use long double instead of long int in the calculation of diff in the following code. Can anyone help? Brovko shnirelman

Link

If we replace ld by ll in diff then it passes the TC. Link: https://codeforces.com/contest/1730/submission/185451105

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need more than $$$30$$$ iterations for non-integer binary search.