Educational Codeforces Round 88 [Rated for Div. 2]
By awoo, history, 5 years ago, translation, In English

Hello Codeforces!

On May/28/2020 17:35 (Moscow time) Educational Codeforces Round 88 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hey Codeforces!

As you may remember, we have a free webinar series starring our all-star faculty members who share valuable content and insiders’ knowledge that you don’t get to learn about in traditional classrooms.

Join us tomorrow, Thursday, May 28 at 12h (BCN) / 17h (BKK) to watch Sergey Gordeychik, CIO of the Inception Institute of Artificial Intelligence, share his expertise and insights in his “Digital Lockdown: AI against COVID-19” session. Sergey will discuss how AI is being used both positively and negatively during the COVID-19 global pandemic. Tune in for some practical examples of how companies are using AI to innovate and disrupt during a time of crisis, exploring topics like Medical Imaging for CT analysis, diagnosis and mass surveillance.

By participating in this webinar you will get a certificate of participation, a special digital gift from Sergey, and stand a chance to win a FREE 3-week module at Harbour.Space University depending on the availability and prerequisites of the course.

See you tomorrow, and good luck on your round!

Reserve your spot now!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 244mhq 6 174
2 bmerry 6 219
3 dlalswp25 6 233
4 hepth 6 238
5 Volkov_Ivan 6 251

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Hideki_Ryuga_L 37
2 KonaeAkira 19:-1
3 ujjwalsingh30 18:-1
4 veteran_ 14
5 hashlib 13
318 successful hacks and 469 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A andryusha_na_knopke 0:01
B thech0sen1 0:03
C IAKWF 0:11
D Kerim.K 0:06
E HeHere 0:06
F user202729_ 0:44

UPD: Editorial is out

  • Vote: I like it
  • +355
  • Vote: I do not like it

Comments Comments (467)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

First comment! Thank you Codeforces and Harbour.Space University for these rounds in this tough time!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +122 Vote: I do not like it

    Don't know the reason of such hatred shown by the community here. I just thanked the organizing panel for their efforts, that's it, as a good gesture. No wonder why the community hated it so much. Maybe because I am a specialist and not a red, not really sure about it.

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

      Don't worry about downvotes too much.

      Your positivity will reach the people no matter what.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      This is one big problem with cf. On one side, there is Mike who is bringing out new div4 contests for not so high rated participants and on other side are these guys who boast a lot about their ratings.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +74 Vote: I do not like it

      If everyone showed thanked the organizer in the comments, then we'd just have a thread of 19,000 people saying thank you. No one wants that, if you want to thank them give them an upvote.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Almost everyone is sad about this lock down (including me), and if these contests give hope to people or put a smile on their face or excite them, there's no harm in saying a "thank you" as a good gesture. And I think that it's nearly impossible for such a large number of people to post it in an announcement. It's just a few, which doesn't flood these announcements. In my case, I just got excited seeing the announcement and that there isn't any comment yet, so I thought why not write a good thing for the organizers, there's nothing bad in it. It gives hope (or just puts a smile) to some, if not all.

        I don't want to hurt anyone with my comments, and if I did, I am sorry about it.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hey, don't worry both of the groups supporting/disagreeing with your comment are right in their point of view. The first group that supported you was for your pleasant thanksgiving and the other group that disagreed on you was because they want that more important messages/helpful messages are to be shown so that it would give way to more important messages in a bunch of good messages. That thanksgiving gesture was very pleasant hope it will spread positivity in this environment.

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I guess you've been downvoted for your 'First comment'. That's totally useless.

      → Reply
»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Where's the unusual time ??

→ Reply
»
5 years ago, # |
  Vote: I like it -141 Vote: I do not like it

Googleforces

Let's goooo!

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope this educational round will be much better than previous one^_^

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -66 Vote: I do not like it

Looking forward to more geometry problems! Especially, ones with subtasks <3

→ Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Lets hope we get to see problems involving both math and graph theory. It was long back when we had problems involving math as well as graph theory.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for having back to back contests! Giving something to cheer for.

→ Reply
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Looking for a data structures problem ..

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I rarely see a Div2C or Div2D a graph theory problem I think in a while i have seen two only one livonia and kingdom and one from ehab and bla bla .... I am looking for good Problems rather than standard ones with unusual time limit and memory limit.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +51 Vote: I do not like it

I hope to see Tree , Data structure , Math Problem But i don't want to see geometry .... i am very weak of that

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    everything is fair until it's not one click away on google. specially when it's prob A/B/C/D. because that makes contest unfair for 80% rated participants.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +44 Vote: I do not like it

      How did you calculate the percentage of the unfairness? Why not 0.4% or 5% or 15% or 146%? Please, provide some proof or stop speculating.

      Anyway, if you deserve your rating you'll gain it in no time. Otherwise, if you need to google A/B/C/D in ER you probably don't have the rating you can be proud of.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Btw how did you generate such numbers .4%,5%,15%,146%. Any formulas for that or random. He is saying correct those who wasted time in solving that suffered. Googlers got Ac instantly. At least it should be not present on google

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it
  • Educational codeforces round exists *
    No one :
    Literally no one :
    People who get negative delta after the contest :
    Educational codeforces rounds should be unrated.
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +37 Vote: I do not like it

    I enjoy every contest even if I get negative delta. I don't know why people complain a lot with the rating! Everyone should enjoy contest even if you get negative or possitive delta! I think that's the authors purpose and what really matters!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Yes, even if there would be no rating system i would have given same or more number of contests. Its the number of questions i do make me feel good than positive or negative delta .

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why score distribution is not given in any educational round announcements?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Because all problem has equal score in educational rounds.

    → Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

RUSH RUSH！！

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -86 Vote: I do not like it

[deleted]

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +58 Vote: I do not like it

    More than 3 years and you're still a newbie. It's your fault, not due to the statement

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I never wrote that I have lower ratings due to the problem statements. I just gave an opinion what I felt and that's it.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        I think the best solution is just practice because reading is also an important skill

        → Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Who else is trying to solve their first div2 c problem

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -47 Vote: I do not like it
  • Problem C : This Problem Can be Solved Mathematically using inequalities.
Idea
Solution

Link to my solution : 81821029

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Woohooo Vovuh is back!

→ Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Hope there are no geometry problems!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -24 Vote: I do not like it

sry, I LOVE MATH!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I love math...! :) Happy coding...

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess should have enjoyed solving C question then?

      It was just an inequality question.

      → Reply
»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

why has no one yet asked whether the round is rated or not!!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It is already written in bold, rated for participants with rating lower than 2100

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    I feel like it's my first contest even if it's my 85th contest. Can you please tell me if the contest is rated or not.
    XD

    → Reply
»
5 years ago, # |
  Vote: I like it -133 Vote: I do not like it

I give up Codeforces and leave this site because of problem C. I am 100% sure that my code is correct but I got 7 WA. I give up. Bye.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    If you got WA then maybe, just maybe, it is not 100% correct..

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    You could instead try E which is easier than C

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I passed pretests on second attempt. Its a pen and paper problem. Looked like binary search first, but its O(1) solution with some messy algebra, theory of increasing/decreasing functions, case work, simplifying fractions.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I figured out that expected precision = 1e-15, I got it accepted when i incurred that change

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I tried to read your code and saw this: 81775456. No pity you leave, since you would be banned for intentional code disguise anyway.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    what with your weird way of writing code. it's like cancer, you write code using define.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I've never laughed so much looking at code (except maybe ArnoldC). Now I have.

    → Reply
»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

1937 : There will be flying cars in 2020

Meanwhile in 2020 : brainless pupils and Newbies exist.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Please change your profile picture, it irritates me every time I see it.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    For fuck's sake, change the dp otherwise don't comment!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Codeforces should introduce report feature.

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Speedforces!

→ Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Last time I was lucky to notice the pattern in C task which resulted in formula answer, this time C revenged! :D

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Tutorial for today's C

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A great contest with beautiful problems and short statements for which Educational rounds are generally known.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can C be solved with the help of binary search ? If yes, how ??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    For even number of cups, the resulting temperature is always the same.

    For odd number of cups, the resulting temperature decreases as we add new cups, but never becomes less than or equal to $$$\frac{h + c}{2}$$$. So if $$$t > \frac{h + c}{2}$$$, we can use binary search to find the first moment it becomes less than $$$t$$$, and check this moment and the moment $$$2$$$ cups before.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      Okay so i was doing everything right but failed to realize that i need to use binary search only for t>(h+c)/2. Changed that and accepted. Thanks !

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I suppose I have a constant time solution.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are not alone.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          of course man..Its basic math and error analysis

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        just saw your solution, can you explain why exactly: 

        lli i = (h-c)/(2*eff);
double boo = (h-c)/(2.0*eff);
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          boo is the value so that the error is absolutely 0.. i is the floor of boo

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please correct me if I'm wrong, but consider $$$h=10$$$ and $$$c=1000000$$$

      Wouldn't the average temperature for odd cups be strictly increasing in this case?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In the statement, it says: "1≤c<h≤10^6". The temperature of the hot cup must be higher/larger than the temperature of the cold cup.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Considering the case 999977 17 499998, where hot temperature is 999977 and cold temperature is 17, target being 499998. Using 499979 pours, and, while using 499981 pours, we get the same difference with the target.

      So shouldn't the answer be 499979. While in the solution, the answer is 499981. Can anyone let me know what I am missing here?

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    If we consider the case where we have $$$X + 1$$$ hot and $$$X$$$ cold, the temperature is a decreasing function, so binary search could work here. However you can also directly calculate the value of $$$X$$$ for which the intersection occurs and then check $$$\lfloor X \rfloor$$$ and $$$\lceil X \rceil $$$ for whichever gives a closer temperature.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I did the same way by directly calculating the intersection value.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can $$$ \lfloor X \rfloor $$$ and $$$ \lceil X \rceil $$$ and then temperatures at these points be calculated with good precision ?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You do not need to calculate them as double, you can calculate as integers directly: either [t / (h + c + 1 — 2 * t)] or 1 + [t / (h + c + 1 — 2 * t)] where / is integer division. even if X is an integer, it would not hurt to calculate temperature difference at X + 1

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, did the same when I finally got an AC

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How did you get this formula? As far as I know, it should be [(h-t)/(h+c-2t)]

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I used double division followed by floor and passed fine. However you can calculate it exactly using integer division.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How did you derive the formula?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            First wlog let $$$c = 0$$$. Let $$$x$$$ be the number of cold cups. Then for the odd case we want $$$h(x+1)/(2x+1) = t$$$. This intersection point only exists if $$$t/h >1/2$$$. Otherwise we take an even number of hot and cold cups. Now just check if the floor or ceil of $$$x$$$ gives a closer answer.

            → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did the same. I think I am having precision issues. Help please. https://mirror.codeforces.com/contest/1359/submission/81752804

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same but still got WA in the third case can somebody tell why? My submission for C- 81790933

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        same problem subcase 66 (getting 2 instead of 1).

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You have most probably missed out on cases where the the difference between h and t is the smallest possible difference and therefore 1 should be the output.
        Tc:
        1
        7 1 6
        Your code fails for this and other similar test cases the answer should be 1 and not 3.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
        1
10 4 9

        here expected 1 found 3.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Seems I forgot to exclude equal case here 1 and 3 both have difference 1 but minimum was to be considered. Thanks

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes. Notice that the more cups you take (assuming it's an odd number), the closer you will be to the average of hot and cold temperatures. Use this fact to binary-search for the smallest number of cups such that the temperature is not more than the target. To deal with any precision issues, check 2-3 numbers above and below what you found and select the best one.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes. I solved it with Binary Search.

    However, my first few submissions for C got WA because of Double precision issues! If this hadn't happened, I would have reached master. :(

    Check out my submission here: 81789311

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the testcase #4 of problem C ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I just changed double to long double and it worked.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Testcase #4 of problem C is some testcase which causes Double precision issues to cause WA>

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      Yes, Fu**ing precision error in python got me that answer wrong and that question sucked soul out of me.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Yes, it sucked the soul out of my rating :(

        I would have finished around rank 100 if I had solved C immediately without any errors...but instead I got 347 :(

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Can relate. I wasn't able to overcome the precision error until after the time was over. :(

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, same problem. Discovered after the contest that the easiest way round this is to use the Python Fraction class (fractions.Fraction), see https://mirror.codeforces.com/contest/1359/submission/81820143. I wasn't aware of this class before, so I actually learnt something from this "Educational" round!

        Not sure what one would do in other languages.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    I was getting TLE on this test, so I think there is some stress-tests, for example:

    30000

    999999 2 500001

    999997 2 500000

    ... and more

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

    for each element in array .. assume the current element as maximum for segment under consideration.

    then find max_left_sum[i] and max_right_sum[i] (crucial part).

    ans will be max(all(max_left_sum[i] + max_right_sum[i]))

    can be done in O(N). once try for yourself, anything more i explained will be a spoiler.

    Spoiler

    this is another question which can be solved using similar technique — Largest Rectangle from Hackerrank

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      I overkilled D using 3 Segment Trees, that ultimately did exactly what you said...

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you using Kandanes algorithm both side ? Can you please tell your solution since what you left is the hardest part . Your can put it as a spoiler .

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have updated the comment with spoiler section(with explanation and code) and a bonus similar problem.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is the complexicity of for loop is n*m where m is no of different value that array element can take m=60 in this case..

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Note that there is no need to check the negative values, since if the biggest value of the subarray is negative, it is better to use a single element subarray which results in sum of 0.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yupp, that largest rectangle problem uses stack to get the next and previous greatest elements. I find stacks tricky hence used segment tree + binary search to find the next, prev greatest element

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      for a decreasing array, the complexity is O(n^2) in the first loop itself. This code will get TLE. right?? Or, please explain why the complexity should be O(n).

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        there is the condition for input -30<=ai<=30.

        this is useful to maintain O(N) if the diversity increases this algorithm reached O(N^2) as you said.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Can we use stacks to solve this problem??

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can also use DP with dp[i][j] := "maximum sum of subarray a[?:i] with max value j" which has pretty trivial transitions, and then maximize dp[i][j]-j, looks like this: 81795283

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    My idea:

    Forget about starting at any time for a moment. Let all cars start moving at $$$t = 0$$$. For any $$$t$$$, Consider the line segments of each car whose endpoints are starting position of that car and position of that car at time $$$t$$$. Find the least $$$t$$$ for which there is an intersection of any two line segments. Then the answer is $$$t$$$, because if line segments corresponding to cars $$$A$$$ and $$$B$$$ intersect, then I can start one of them late and make them crash exactly at $$$t$$$. So binary search on $$$t$$$ and use line sweep to check if there is any intersection.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved C using ternary search . can some one please proof how the shape will be similar to parabola (I just assumed) .

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You can use just Binary Search in the odd number of movements.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you plz tell me how? . I am able to find out that we need to search only in odd position but didnt find the how to solve it as brute gives tle and you said binary search . But I didnt get it how??

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        1. take one cup of the hot water and pour it into an infinitely deep barrel;
        2. take one cup of the cold water and pour it into an infinitely deep barrel;
        3. take one cup of the hot water and pour it into an infinitely deep barrel;
        4. take one cup of the cold water and pour it into an infinitely deep barrel;
        5. and so on...

        Here for every cup of cold water you have already poured a cup of hot water already. So whenever the even number of cups poured, the temperature will be constant which is the avg(h, c).

        After you pour the 1st cup of hot water. The temperature will be h. After you pour the 2nd cup of hot water. The temperature will be slightly low since you have poured one cup of cold water before.

        Therefore, the temperature will be decreasing monotonically towards the avg(h, c) when ever you pour a cup of hot water. So you can use this property to binary search the appropriate value.

        Link to my submission : 81771518 . Hope you find this useful

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No the shape would not be parabolic.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Assume you put x hot cups and x — 1 cold cups. Then middle temperature is (xh + (x-1)c) / (2x-1) If you put x + 1 hot cups and x cold cups then middle temperature is ((x+1)h + xc) / (2x + 1).

    Subtract second from first and you get (h-c)/(4x^2 — 1) which is always positive. So temperature is strictly descending function from number of hot cups.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    I can be proved that $$$ \frac {x} {2 * x - 1} $$$ (x = 1, 2, ...) is decreasiong.

    Proof:

    $$$ 2x^2 + x > 2x^2 + x - 1 $$$

    $$$ x *(2x + 1) > (2x - 1) * (x + 1) $$$

    $$$ \frac{x}{2x-1} > \frac{x + 1}{2(x + 1)-1} $$$

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1

    2

    3

    stock svg images

    I just plotted the graph, and you can see it is a decreasing function for odd number of cups.

    and you can see it is constant for even number of cups.

    → Reply
»
5 years ago, # |
  Vote: I like it +47 Vote: I do not like it

The ordering of problems was very bad E was even easy from C

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think it was easy to guess but not easy to prove .

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      A somewhat loose proof for the solution to E is that if you consider a list of numbers [2,2x,2y,2z,...] such that every term divides the smallest number (for example, 2), no matter how you re-arrange the numbers, eventually, you will have to take it modulo the minimum number in the array, which will cause the result to become 0. Then, it is zero all the way to the end.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +17 Vote: I do not like it

        How to prove that if there is more than one number not the multiple of $$$k$$$ then the final modulo is different?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +30 Vote: I do not like it

          Suppose that there is a number $$$a_i$$$ that is not divisible by $$$a_1$$$.

          Let $$$x$$$ be equal to $$$a_i$$$, and let's take two following orders: $$$[a_1, a_2, a_3, \dots, a_k]$$$ and $$$[a_i, a_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_k]$$$. Then in the first case, $$$x \bmod a_1$$$ is non-zero (but less than all $$$a_i$$$, so it is the resulting value), and in the second case, $$$x \bmod a_i = 0$$$.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If the property isn't true, then there is some number (call it m), which isn't a multiple of k.

          Now, feed in X=k to the machine. If the permutation of A is [k,m,kx,ky,kz,...] then our answer is clearly 0.

          However, if our permutation of A is [m,k,kx,ky,kz,...] then clearly since m is not divisible by k (by definition), then the value will be (k%m), and the value after the second step will also be non-zero. The value of the result won't change after the second step, because kx,ky,kz > k. Therefore, the final result in this state is non-zero.

          So our array that included m was therefore unstable.

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 9   Vote: I like it 0 Vote: I do not like it

        We can prove using mathematical induction. As BledDest showed that only those sequences may work which contain multiples of smallest number .

        Notation : $$$x$$$ mod $$$(a_1,a_2,a_3)$$$ = $$$((x$$$ mod $$$a_1)$$$ mod $$$a_2)$$$ mod $$$a_3$$$

        Base case : $$$size=2$$$ , consider $$$[a_i,v.a_i]$$$ where $$$v>1$$$ . Take any number $$$x$$$. Then $$$x = p.(v.a_i) + r$$$ , where $$$r<v.a_i$$$. Then $$$(x$$$ mod $$$v.a_i)$$$ mod $$$a_i$$$ = $$$r$$$ mod $$$a_i$$$ ,$$$(x$$$ mod $$$a_i )$$$ mod $$$(v.a_i)$$$ = $$$(r$$$ mod $$$a_i)$$$ mod $$$(v.a_i)$$$ = r mod $$$a_i$$$ .

        Assumption : Suppose above is true for size $$$k$$$ i.e $$$[a_1,a_2 ... a_k]$$$. Note that all all elements are multiple of $$$a_1$$$.

        Let us prove for size $$$k+1$$$ i.e $$$[a_1,a_2 ... a_{k+1}]$$$. consider $$$x$$$ mod $$$(a_i,...a_{k+1} ..a_j)$$$ (type 1) and $$$i$$$ not equal to $$$k+1$$$.It will make no difference since $$$a_{k+1}$$$ is not at first position.consider $$$x$$$ mod $$$(a_{k+1} ....a_j)$$$ (type 2) i.e $$$a_{k+1}$$$ is at first position. Then by assumption it will be same for all permutation where $$$a_{k+1}$$$ is at first position. Now we only need to prove that answer for any particular permutation of type 1 and type 2 are same. Let us choose $$$x$$$ mod $$$(a_{k+1},a_1,a_2,a_3.....a_k)$$$ and $$$x$$$ mod $$$(a_1,a_{k+1},a_2,a_3....a_k)$$$. Since $$$x$$$ mod $$$(a_{k+1},a_1)$$$ = $$$x$$$ mod $$$(a_1,a_{k+1})$$$ (from base case proof) hence both are equal . Thus answer is same for all permutation of length $$$k+1$$$.

        I will be thankful if some one points out mistake in above proof.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      suppose the gcd you'll take is g, then x=g*q+r, where r is x%g. now if you take x%(n*g) then x%(n*g)=g*(q%n)+r which is some g*q'+r. after repeated divisions when you finally do %g the answer will be q.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    couldn't agree more

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    The round was very similar to AtCoder Beginner Contest, except for F (which I don't dare to even read lol)

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Why D gets WA on testcase 7.
my submission : 81782286

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    use kadane from left and then again right taking sum-max...i was stuck there as well

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Whaaat??? What the hell?? I just did the left and got struck. But, well. Why we need to do again from the right??

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        pointless...its wrong..my submission is hacked

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        Because the largest number taken at each step (subtracted from the sum) maybe different when taking from the right.

        Example:

        11
3 0 1 -2 5 -5 -1 0 3 2 2

        When taken only from left, the answer is 3 but when taken from right, the answer is 4 (3 2 2).

        However, even this solution doesn't work for cases like,

        8
4 -10 13 -13 2 2 -11 6
        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Couldn't solve it, but i changed my code for this testcase

    n = 6

    [9, 1, -9, 2, 2, 2]

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I didn't come up with a counterexample like this >_<

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Screw up +120 like that. No!!!

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        it is ok, if you use kadanes from left and right still you will end up in this case :P
        7
        30 -20 5 1 3 -20 30
        ans would be 4 but by using two kadanes we get 0 :(

        → Reply
»
5 years ago, # |
  Vote: I like it -43 Vote: I do not like it

C was really interesting...

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solotion of C!!! Please!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used two ternary-search (one for hot == cold + 1 and one for hot == cold) and compared two final results from each ternary search, but I think there are easier solutions

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You don't need to do any search for case hot == cold since the answer for that case must be (h + c) / 2

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      .

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    For all the odd pouring, the temperature at ith pour would be ((i+1)*h/2+(i-1)*c/2) and this has to be equal to t. Now on finding i, the answer would be 2*i-1.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    C can be solved in O(1) time.

    This is my submission: 81757911

    If h == t, clearly the answer is 1. If h + c >= 2 * t, the answer is 2 as the most you can lower the average to the target is via the first cold cup.

    Now we consider the case where the average of h and c is less than t.

    We make an observation that now there will be one more hot cup than cold cup, so let the number of cold cups poured in be k. Inclusive of the latest hot cup, the average temperature would now be ((h+c)k + h) / (2k + 1). We would like to find the value of k such that the fraction is closest to t.

    We first solve the equation where ((h+c)k + h) / (2k + 1) == t. We can then obtain h-t = k(2t-h-c) and k = (h-t)/(2t-h-c). We can see that either floor(k) or ceil(k) will give us the closest value to the target, hence we check the difference between ((h+c)k + h) / (2k + 1) and t for floor(k) and ceil(k), thus solving the problem.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, I am unable to understand why when h+c>=2t, answer will be 2. Can you please explain?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        When the average is greater than t, the smallest average is obtained by pouring 1 hot and 1 cold cup. The average is the same if there is an equal number of hot and cold cups, and it will increase when there is one more hot cup. Thus, 2 is the minimum number of cups for the average to be closest to t.

        → Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

One of the best contests ever. Got to know for the first time(or maybe noticed for the first time) about the modulus property that had to be applied in problem E. Thanks again !!

→ Reply
»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Task C took soul out of me but never showed Accepted

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please tell me what is wrong with this solouton for C 81802932 I know I've been silly there but please help me

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even if $$$\frac{h+c}{2}\neq t$$$, $$$2$$$ may still be an answer. Since $$$\frac{h+c}{2}$$$ may be closer to $$$t$$$ than the answer you use binary search to get.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      that was the case I missed I forget comparing the answer of bs with the answer that I got (h+c)/2 i.e 2

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can D be solved with the DP?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I solved with DP.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Idk about dp, but i'd like to say it can be solved in nlogn independent of ai's values. Sort a list of indices based where indices with higher ai values come first, and hold a segment tree of the prefix sum values. Now just iterate through your list of indices and add them as boundaries for querying in a set as you go, and for each index find the largest prefix sum greater than and index and the least prefix sum less than an index such that the range is within all the boundaries in your set, then update ret with subtracting those prefix sums minus the current indices value.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      It can be solved in O(n) as well independent of ai's value. You can maintain a stack to do so, https://mirror.codeforces.com/contest/1359/submission/81806616 .

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, very cool!

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        can you please explain your solution ?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +21 Vote: I do not like it

          Basically for each index 'i' of array (1-based indexing), I found out what is the rightmost j for which a[j] > a[i] and j < i. Now Assuming this element has to be removed, I maintained a mxl array to maintain max. subarray sum that is ending at [i — 1] for a given 'i'. Note this includes a[i — 1], (no matter if its positive/negative). Now as per the implementation using stack, for left ('L') part, for a given 'i', s.top has 'i — 1' index, so I keep on removing indices from stack for which a[s.top()] <= a[i], but also kept on maintaining the max sum ending at 'i — 1', which includes a[i — 1]. If you observe mxl[s.top()] does not necessary means max sum goes up to indices 2nd topmost element of stack. So to find the mxl[i], you have to make the continuous sum starting from 'i — 1' to the current s.top(), and update the mlx[i] if valid.

          Similar goes for right part.

          And then for each element just assume you are removing it from its range, find what is the max left and right sum within the range.

          Also if you are still having difficulty in understanding this, I would suggest first try solving easy part of this question — Imbalanced Array. The editorial of it have a similar idea.

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I solved it in O(n) . I first used Kadane algorithm and then i consider all subsegment which do not contain negative number .submission Edit : now hacked .

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah, dp[i][j] = max value you can get with a segment ending at i, with maximum equal to j. The transitions are pretty straightforward (just need to offset negative values).

    Submission: here

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the transitions? I don't quite get it

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Initially, you can start a new segment at some index, but it will be the maximum, so dp[i][a[i]] = 0 to start. But also, you could have extended some segment ending at i-1, so there are 2 cases to consider.

        1. j, the old maximum was smaller than a[i]. Then you get dp[i-1][j] + j, because a[i] becomes the new max (you already "paid" for j in dp[i-1][j], so add it back in to compensate).

        2. j is greater than a[i]. The maximum doesn't change, so you get dp[i-1][j] + a[i]

        I hope that helps.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    $$$dp[index][maxval]$$$ is the maximum sum ending at $$$index$$$ containing $$$maxval$$$ as the max value. Answer is $$$max (dp[index][maxval]-maxval)$$$

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

isn't C binary search why alot of people wa on 2 testcase

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Nope, it comes down to a simple tiny equation.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For me personally, it was using binary search even if t<(b+c)/2. As soon as i rectified that, I got it accepted.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

DELETED

→ Reply
»
5 years ago, # |
  Vote: I like it +53 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In q C, my code gave wrong answer in C++17(64) but got accepted in C++14. Happened with anyone?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I guess you were working with double data type.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Is there any problem with double in c++17(64)? Thanks

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know what is actually wrong but i faced problem while comparing two double few times. So i try to compare it keeping it integer.

        Say i need to compare x/a and y/b. I compare x*b and y*a (Multiply both a*b). In this case there is no chance of precession loss.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is wrong with double data type in c++17?

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too! this was really frustrating as i kept on changing my code and still getting the same wrong answer

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same is happening with me too. But I figured this out after reading your comment. Thanks for mentioning. Pupils, here I come.

    → Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I feel if E was before C it would have more solves

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone why my submission to problem D, received runtime error on test 2? It was working fine on my local machine.

Thanks

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F is already in emaxx. https://cp-algorithms.com/geometry/intersecting_segments.html

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    Good thing that awoo found some tests to break that code if it is copypasted without any changes

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      I got AC, copying and pasting that code, just changing EPS and using long double

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    its ok since even mifafao was not able to solve it

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In Problem C, I was worried about using floating point numbers, and then thinking about a solution using only integers ...

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I used my own fraction class for the same, and it didn't even have a greater than operator, damn it sucked :(

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You could have done it by holding best current value by numerator and denominator, then just comparing fractions.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not brute forcing to find a pattern do be like that sometimes. E would have been significantly easier if it was placed as problem C.

→ Reply
»
5 years ago, # |
  Vote: I like it -29 Vote: I do not like it

hi guys why this solution don't work in pb b THANKS . #include<bits/stdc++.h> using namespace std; typedef long long ll;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {

   int n,m,x,y;
   cin>>n>>m>>x>>y;
   char mat[n][m];
   cin.ignore();
   int ans = 0;
   for(int index=0;index<n;index++)
   {
       int curr = 0;

    for(int j=0;j<m;j++)
   {
       char c;
       cin>>c;

       if(c=='.')
        curr++;
       else{
         ans +=min((y*curr/2+curr%2*x),x*curr);
         curr=0;
       }


   }
   ans +=min((y*curr/2+curr%2*x),x*curr);
   }

   cout<<ans<<endl;
    }

    return 0;
}
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your solution will place a 1x2 block for this case:

    .*.*

    The problem states that you can not break the 1x2 block, so this block can be used only when 2 dots are together, like this:

    *..*
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think that's true. In your example, the innermost "else" triggers on each *, at which point curr has value 1, so x is added to the total and curr is reset to 0.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        thanks guys for ur replyes acually , my solution work . i jut forget "(" in y*curr/2 cuz (curr/2)*y!=y*curr/2 . that why i get wrong answer.

        → Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

My AC solution of problem F is wrong. Can anyone hack me? Please (>__<).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    still, I can't! i m so noob ༼ ಥ_ಥ ༽

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you think about the case when the two cars are aline?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution can fail on normal case. You can see other Account solution is quite different with mine.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

AC problem F, just after the contest... WHY I DIDN'T REMEMBER TO USE 1e-10 INSTEAD OF 0.0 !!!

→ Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

For D, i took : max of (maximum subarray sum ending at index i — max element in that subarray) for all indices i, why doesn't this work?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you missed the last exercise because you didn't round an almost zero value to zero before comparing it with zero. So sad :(

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can C be solved using ternary search?

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone explain the following case for problem D?

11
3 0 1 -2 5 -5 -1 0 3 2 2

The answer is 4 but I'm getting 3 after trying it out by hand and with my code.

Edit: Figured it out. In case anyone's wondering, the max_num at each step when taken from left maybe different from the max_num when taken from the right.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me why https://mirror.codeforces.com/contest/1359/submission/81809462 gives TLE

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone tell hack for C? TIA

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Video Editorial :- Problem C

I will add editorial for problem D using segment trees soon.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hi! So I was going through the hacks and saw something odd...

https://mirror.codeforces.com/contest/1359/submission/81798994

So this guy made a smurf, submitted his own code, and intentionally added code which would fail on certain input. And you can even see that the author's name is still the same! There aren't any points for hacks in this contest, but shouldn't there be some action against this user?

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve D without using dp ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    We can use sparse table and concept of NEXT GREATER ELEMENT.\

    CHECKOUT :

    81811299

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    For each element ai find the range at which it is maximum, let the range be [l,r]. The sum it would contribute if Bob chose to remove ai is maxsuffixsum(l,i-1) + maxprefixsum(i+1,r). The first part can be calculated using stack and the second part with segment tree. My submission

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    See my solution, quite easy to code: 81741311

    You can even replace the segment tree with sparse table and set with stack to get an O(N) solution.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem C, I think there is always a way to achieve the average temperature equal to c. Let's say, x number of hot cups were poured and y number of cold cups were poured if we solve the equation assuming, the average temperature will eventually be equal to c, we have hx + cy = tx + ty from here, you get x:y = (t-c):(h-t) taking x and y in this ratio should give the answer, so final answer should x+y For example, in the second sample test case given, x = 15, y = 11, the average temperature will come to 30. So, the judgment is wrong for this question. Please advise on my understanding and correct me if i am wrong.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The problem requires that x-y is either 0 or 1.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to take hot and cold cup alternatingly. So either x=y or x=y+1 You are missing this condition.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone hack my C? 81742048

I believe it is wrong :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I made some random tests for your code, and after 3000 tests, all answers were the same as my code. I think your code is correct! (Or we both made the same mistake)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    long double is not hackable I think.

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here's a proof for $$$E$$$.

Take any index $$$i \neq 1$$$. The condition applied to $$$x = a_1a_2\dots a_k + a_i$$$ in the order $$$a_1,a_2,\dots ,a_k$$$ gives $$$a_i \pmod{a_1}$$$ on each step since this is at most $$$a_1-1$$$ and all modules are greater than that.

Now evaluating in order $$$a_i,a_1,a_2,\dots a_{i-1}, a_{i+1}, \dots a_k$$$ evidently gives $$$0$$$ as $$$a_i | a_1\dots a_k + a_i$$$. Therefore $$$a_i \pmod{a_1}$$$ must be zero, which means $$$a_1|a_i$$$ for all indices $$$i$$$.

Proving that the smallest element dividing all others is enough is not hard. Say $$$r_1 = x \pmod{a_{p_1}}$$$, $$$r_2 = r_1 \pmod{a_{p_2}}, \dots$$$.

Notice that for any $$$r_i$$$ by definition we have $$$r_i = r_{i-1} \pmod{a_{p_i}}$$$ thus $$$a_{p_i}|r_i-r_{i-1}$$$ where we define $$$r_0 = x$$$. Since $$$a_1|a_{p_i}$$$ we must have $$$a_1|r_i-r_{i-1}$$$ for all $$$i$$$. Thus $$$a_1|(r_1-r_0)+(r_2-r_1)+\dots + (r_{k}-r_{k-1}) = r_k-r_0 = r_k-x$$$.

We also know that the result is a non negative integer at most $$$a_1$$$ because once $$$\pmod{a_1}$$$ is applied the result becomes constant as all other modules are bigger. Thus $$$r_k$$$ is always $$$x \pmod{a_1}$$$ no matter what order we do the operations in.

Therefore the problem reduces to finding for each smallest element $$$a$$$, the number of ways in which we can choose $$$a_2 < a_3 < \dots < a_k$$$ integers divisible by it in the range $$$(a,n]$$$.

This is just $$$\displaystyle \sum_{a=1}^{n} \dbinom{\left\lfloor \frac{n-a}{a} \right\rfloor}{k-1}$$$.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Today's ques C went like a Game changer for many .

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the approach for D except seg tree! can we solve it using kadane

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apply Kadane 2 times, one from the first element and second from the last.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know if some variation of kadane can work here . But I can provide you a, without seg solution .

    1. for each element i, we first find smallest j<=i, such that maximum in range [j,i] = ith element. and similarly, we find largest k>=i such that maximum in range [i,k] = ith element. (These both can be achieved with binary search, using any RMQ data structure, sparse table is easiest to write)

    2. Now we need to find, left and right index in range [j,i] and [i,k] such that we get maximum sum. Again binary search and range min/max queries over prefix sum .

    Take the maximum among all indices.

    Solution.

    → Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

In Problem C, Test Case# 4 999977 17 499998

Judgement is: wrong answer 14th numbers differ — expected: '499981', found: '499979'

But 499979 gives perfact 499998 result and it is < 499981 so why it is not correct answer?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    yes you are right

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Same problem here...

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    awoo Please explain this . I have the same problem.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    The result when you pour 499979 cups is not 499998, but 499998.00000200008400352814818222. ‬

    For 499981 the result is 499997.99999799992399711189025183, which is closer to 499998.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But needing the doubles to be so accurate can be problematic. I think the problem for us is the fact we used Java, and perhaps Java calculates the doubles less accurately/differently than c++. This is a problematic property of this problem, even though I think it was somewhat interesting.``

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        1) Java has BigDecimal library

        2) It is possible to do all calculations and comparisons in integer values

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hmm yeah you are right it can be done in integers. Thanks.

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the clarification, I guess mentioning some kind of cutoff precision in problem statement would have been helpful. Most people who use java will use double by default and will fail this.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, and the calculated differences, for me at least, are the same for both numbers: 2.0000734366476536E-6 Maybe it's a problem cuz we use Java? Maybe is c++ more accurate or something.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Some solution in c++ also faced this problem. But it can be solved not using double.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    For 499979, the answer is

    $$$|499998.00000200008400352814818222‬ - 499998| = 0.00000200008400352814818222‬$$$

    and for 499981, the answer is

    $$$|499997.99999799992399711189025183‬ - 499998| = 0.00000200007600288810974817‬$$$

    So, 499981 is the answer.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I got 2.0000734366476536E-6 for both... Why do you think that is the case? I calculated it like this (x is the number of cups — 1 and divided by 2):

      private double averageAfterTries(int x, int h, int c) {

      double result = x;


    result *= (h + c);


    result += h;


    result /= (2 * x + 1);



    return result;


}
      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I struggled with that Test case. When I compared 499979's value and that of 499981 using type double, these values are treated as same because of error. By compareing by fraction like this submit, the result became accepted. https://mirror.codeforces.com/contest/1359/submission/81813380

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My submitted code outputs correct answer in CF but wrong answer in my machine for this test case. I tried to hack some solutions using this TC but failed :v

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it possible to solve problem d in O(n), not using a segment tree?

https://mirror.codeforces.com/contest/1359/submission/81786125

I merged same consecutive sign elements.

Let's say chunk1 = +, chunk2 = -, chunk3 = + ~~

I judged which one is better between (chunk1 + chunk2 + chunk3) or (chunk1) or (chunk3) I couldn't find why this logic is wrong..

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it possible to solve problem D with Kadane Algorithm + Segment Tree to get max query ?? I tried but I'm getting WA.

E: Just tried doing it going once from forward and other backwards but now TLE.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

who can tell me about the case 999977 17 499998 why 499981 is better than 499979?

499979 => 499998.0000020001 499983 => 499997.9999979999

is that cause by accuracy?

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I think educational rounds are going more towards math and heavy implementation nowadays!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B If I can rotate the 2 x 1 tile?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    At first I didn't see that 1x2 tile can't be rotated, so I did this : Run a dfs along adjacent cells and for each connected component, calculate it's cost using the same approach as before.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You would have to check if there exists a perfect bipartite matching for each connected component.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And how is checking a bipartite will calculate the lowest cost?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If 2x <= y, then it's always cheaper to buy two $$$1 \times 1$$$ tiles anyway.

        Otherwise, we would want to maximize the number of $$$1 \times 2$$$ tiles used. You can color each square white or black in an alternating pattern (like a typical chessboard). Since each domino covers one white and one black square, placing the maximum number of $$$1 \times 2$$$ tiles is equivalent to finding a maximum matching.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So you don't want to me solve B also (C, D, E are enough hard I guess) LOL.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone check my submission of Problem D 81799081 I used kadane's algorithm from left and right. It was AC but now it's hacked.

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can anyone please suggest me which compiler is to use?? I am really suffering from this.

81814748 compiler: GNU C++17 (64) — WA

81814723 compiler:GNU C++14 — ACC

I can't get myself out of this.

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there anybody who solved problem C using python? I did a parametric search, but I got WA. I think it's because of the python precision issue...

499979 => 499998.0000020001 499981 => 499997.9999979999

Or should I solve the problem C with a different approach?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use Fraction module , i got the exact same error , solved it with Fraction module after contest

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Solving C with double precision is very sketchy. I had a bunch of issues in Java. I'm not sure if there is a way to force python to keep stuff as integers, but it is possible to solve C using only integer arithmetic.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I faced the same issues in Java cause I was trying to solve using integer Arithmetic. Sadly wasn't able to solve.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Here I solved with python: https://mirror.codeforces.com/contest/1359/submission/81753405

    There are no precisions issues if you don't use floats

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Here's why I think E was probably easier than even C.

So for E literally the only observation you need to make is that all array elements need to be divisible by atleast 1 number in the array or all elements need to be a multiple of a single number in the array for the array to be stable.

So if n(i) is total possible elements divisible by i then ans = ncr(n(1)-1,k-1) + ncr(n(2)-1,k-1) + and so on. Notice that I'm subtracting 1 because I'm fixing the smallest number in n(i) i.e i and finding the combinations of the rest.

So the code just boils down to:

ll ans=0;
for(int i=1;i<=n;i++){
    ll q=n/i;
    ans=(ans+ncr(q-1,k-1))%p;
}
cout<<ans;
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, but how can you be so sure that other arrays will give you different modulo? Apart from checking with bruteforce?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just imagine 2 numbers a and b where a>b and b is not a multiple of a. Now take a number x=a+1, then x%a and x%b will be different always. Now you can add a couple more numbers along with a and b to make it into a longer array, but the mod(array with a before b) will always be different from mod(array with b before a)

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Problem E is easy if you know the tricks, but not easy if you do not.

    Some tricks that we need to know are: - (hardest) Computing nChooseK in mod P space (MOD — 2 trick) - (hard) Recognizing that when you fix the first element of the array, and the appropriate calculation for that is choose(n-1, k-1) - (easy) Using DP to compute factorials quickly

    The problem is definitely suitable for an education round. But, depending on your strengths (whether it's in number theory or implementation), you might think problem E is easy or hard.

    Personally, I found C quite easy — I did a bunch of algebra on paper and then coded it up pretty easily with minimal floating point calculations (despite missing some edge cases)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think ncr%p is an extremely standard problem. Even if you just know about it, the code can be easily taken from the internet, but yea making the observation may take some time based on one's experience.

      I compared it with C because the implementation of C can be a bit tricky, although the equation can be derived easily. If one uses double they have to be extremely careful.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I could upsolve D using 2 segment trees to find min of prefixes and suffixes between given indices. However, I am constantly getting feels of an O(n) solution. Has anybody done this in O(n)? Is it simple enough and could you give a hint?

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

For problem D: We can use the fact that the range of numbers is very small. So, for each number from -30 to +30, we can assume it(let's call it x) as the largest sum and find the maximum sum subarray. For this we can apply modified Kadane's by ignoring the elements > x.

Saw this approach in Ashishgup's code: 81746030

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm unable to hack other people's solutions. I get an "Illegal contest ID" error when I click the hack button. Does anyone know of a work around?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    1. Go to Standings
    2. Click on the solution
    3. Click on #
    4. Click on hack
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are unrated in this contest. You are red bro.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah, it turns out the problem was that I was trying to use the uphacking interface instead of the in contest one. I don't know why they are different, but oh well.

      → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

OMG!! solving C using equation was much simpler :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Why from the past 4 to 5 contests div. 2 and educational rounds are based on mathematical problems, in place of them algorithmic problems should be asked which test the actual capability of contestant.

PS- Mathematical Questions results in large negative delta :)

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

In pF, is it intended to let $$$O(n^2)$$$ pass?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was not, but unfortunately we cannot cut it off because of 64-bit compilers. They are not present in Polygon, so we could not test quadratic solutions there — and I don't think that it's possible to cut $$$O(n \log^2 n)$$$ from $$$O(n^2)$$$ on 64-bit compiler under reasonable constraints since $$$O(n \log^2 n)$$$ solution gets almost no performance improvement while switching from C++17 to C++17 64-bit, but $$$O(n^2)$$$ solution becomes more than twice faster.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -9 Vote: I do not like it

      This actually begs a question as to whether we really need the 64-bit compiler.

      As of now, cons outweigh pros: sure, you can use __int128 and avoid some inconveniences thanks to it, but mostly it is used to squeeze sh*t into the time limit (I've used it only for that purpose, to be honest).

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Actually, this $$$O(N^2)$$$ solution with execution time 2620 ms was not compiled with the 64-bit compiler (it does not get much faster using the 64-bit compiler).

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Now that's odd. Our naive solution is something like 5x slower than that (and it's not even the usage of pragmas that makes this code fast).

        Unfortunately, it seems that it's hard to reasonably cut $$$O(n \log^2 n)$$$ from $$$O(n^2)$$$ in this problem since the maximum TL in Polygon is $$$15000$$$ ms (thus we couldn't increase $$$n$$$ up to $$$10^5$$$).

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My contest submission also passes if I submit with a 32-bit compiler. I don't have any proof, but the 64-bit compiler might be faster because it's GCC 9.2 (versus 7.3) rather than because it's 64-bit.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What was the intended solution? The one I've thought of is to binary search the answer, then test for any line segment intersections inside that, for $$$O(n \log n \log(\frac{maxxy}{precision}))$$$.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody tell me how to solve problem C using binary search and if not then why? Thanks in advance.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, can anyone explain what I'm getting wrong in my solution? Submission I used binary search, m is the the of cups of hot water. Edit: Figured out the problem, was missing a few conditions that could occur. AC submission

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Question C sucked life out of me but I could not solve it. Can anyone please tell me my error....81801589. Thanks in Advance....

→ Reply
»
5 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Educational Rounds are meant to fuck java participants! Last time around with that fenwick tree problem and now with Problem C!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's true. I don't know why they do this.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All the cpp guys are downvoting I guess! Keep doing Im liking it:)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I think that you could solve it in java without any problems link.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But not by using double like the cpp guys could :/ I had no clue why my code was failing and it failed just bcoz of double precision error!

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You should not use doubles, there are only 3 cases to check you could just compare fractions one by one.

          You can check that many people in c++ also got WA because of double precision.

          There is not need to blame the contest.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I submitted exact same code in cpp and got accepted, maybe they had wrong logic or something ! And sorry for blaming these guys as they are putting an effort for sure during these hard times!

            → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

I was specifically careful not to use doubles (or long doubles) in C, to avoid precision issues. After the contest finished, I find out some participants did use doubles and got AC. I tried to find a case where precision breaks their solution, so I figured out some big values that made the following true: $$$\left\lvert t_b-t \right\rvert = \left\lvert t_{b+1}-t \right\rvert$$$. But these imprecise solutions didn't break with that case. I got kind of upset, since I could've saved time submitting with doubles and gotten less penalty. Does anyone know if there's a logic behind float operations leading to imprecisions? Is there some kind of upper bound for which imprecisions just don't happen? How do I know when it's safe to use floats?

→ Reply
»
5 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Today's Education : 'Don't Believe double.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

My solution for D:

We iterate over each value v in range [0, 30] and we fix this value to be the maximum value in the segment we will take. We iterate through the array from end to beginning and when we encounter an element with a value greater than our current fixed value v, we set our current best segment value starting from the current idx to 0 (we reset it). Otherwise we take this element and we add it to the best segment we can take starting from the element to the right of this element. Whenever our current segment value is smaller than 0 we set it to 0 again (we will clear the segment). Now for each iteration we set the max possible segment value to current segment value — v. This is easy to code and is just O(31 * N) = O(N).

https://mirror.codeforces.com/contest/1359/submission/81819736

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Nice solution.The only mistake i made in contest that i didnot iterate from -30 to 30 at first.The remaining part is a simple two pointer problem.

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In Problem C,

WA in contest time using C++17(64): https://mirror.codeforces.com/contest/1359/submission/81772254

AC After contest Using C++14 Exact same code :( : https://mirror.codeforces.com/contest/1359/submission/81811049

But i Can't understand Why???

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I made the same mistake. I won't use this fucking compiler anymore

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    I've run your code on ideone and here are some interesting results.
    This is your exact same code: Code. Here, your code is giving the wrong output.
    Now, look at this code. I've just replaced double with long double in your code and your code is giving correct output for the same case.

    Analyzing these, I think the whole thing is about different precision handlings of different compilers.

    It's only my assumption. ;)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    wait whaaaa?why is this happening!!!!

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem C reminded me of JEE calorimetry problems from Heat and Thermodynamics

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hello

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    that submission got accepted bro!!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I hardcoded test 16.

      I did it since when I've tested tests above 16 I always got good answer

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

PROBLEM C

For test case

999977 17 499998

Why is minimum number of cups 499981 and not 499979? Calculated temperature for both are equally distant from t.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, Can you please recheck your calculation. I am getting closer value at 499981

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the difference in values that you're getting? I'm getting a difference of 2.0000734366476536E-6 with both the values.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah bro, Sorry. It is what you are saying. I don't know why the answer is that. I My code gave 499979 and was giving wrong answer in the contest.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes u r right for both of the values we got 2.0000734366476536e-06 this difference and also in question clearly mentioned "If there are multiple answers with the minimum absolute difference, then print the smallest of them." So answer must be 499979

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I guess all the solutions of problem C must be re-checked regarding this issue.

          → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No issues in Test cases bro :

    if answer 499981 , difference is 0.00000200007599460150231607258319855

    if answer 499979 , difference is 0.00000200008400952356169000267982483

    U can clearly see that 499981 is more optimal :)

    If u have any other test case let me know :)

    → Reply
»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

even div 3 E's were better than this E

→ Reply
»
5 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Pardon me if I am wrong but problem C was unfair to most of the participants who tried to solve it through Integer Arithmetic.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I don't know why the community here behaves like this. The same issue when posted above by a red coder got upvotes and here all are downvoting my comment. It is demoralizing. It makes someone think twice before posting his views. Instead of downvoting if people could have replied to this thread that would have helped me to learn something. After all, we all are here to help each other. I tried to solve this problem using integer arithmetic but because of very high precision, I wasn't able to solve it. The same code in C++ 14 passed all the test cases. So, it frustrates when you spend your whole time in a problem and later you discover something like this. I would love it if someone corrects me in reply to this thread.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Did you mean double arithmetic? I'm not seeing any integer-based solutions in your submissions.

      There are many other problems that also have issues with double precision, and I think it was just by chance that C++ 14 worked in this problem. You just have to deal with what you're given sometimes. I wrote a working (but ugly) Java solution during the contest by implementing a fraction class, but I'm sure using BigDecimal would work here if you wanted to have more precision than double.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I mean double arithmetic. Yeah, Thanks for providing such a detailed explanation.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you expect someone to realise during the contest that they're getting WA due to bad precision even with double and that they need to use BigDouble?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          You sort of build up an intuition about when doubles are ok and when they're not. My general rule of thumb is that if you need to get some binary/integer answer from a comparison, you shouldn't use doubles, especially if two values can be within $$$10^{-4}$$$ of each other.

          This problem had binary comparisons with precision of $$$5 * 10^{-7}$$$, which is well below $$$10^{-4}$$$.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What about when I use C++17(64), it gives me WA, while the same code is AC on C++14. I could never guess this in a contest.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I really think it's just coincidence that C++14 works and C++17(64) doesn't (some weird compiler differences). You can't rely on that to always be the case.

              Maybe try long double for higher precision?

              → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +27 Vote: I do not like it

D was a good problem, great way to apply so many different techniques.

My first one was (the one I came up with in the contest): go through the prefix, maintain on $$$ [1, r] $$$ suffix maximums for that prefix and prefix sums. Also maintain in the segment tree $$$ \mathrm{PrefixSum}[i] + \mathrm{PrefSufMax}[i] $$$. Then the answer assuming that the end of segment is in $$$ r $$$ is $$$ \mathrm{PrefixSum}[r] $$$ minus minimum query in the segment tree. Now how to update the maximums and segment tree: just do it naively. $$$ C \leq 30 $$$ and it will work fast enough: this could be proved rigorously if you consider potential function $$$ \Phi(S) := rC - \sum_{[1,r]} \mathrm{PrefSufMax}[i] $$$. But this is seriously overcomplicated stuff (although it appears to be slightly fun). Submission: 81806418 in $$$ \mathcal{O}(n C \log n) $$$.

This one is much more interesting imho. Run kadanes (that must take at least one element), subtract 30, relax the answer, set $$$ a_i = 30 $$$ to $$$ a_i := -\infty $$$. Now kadanes again, $$$ a_i = 29 \rightarrow a_i := -\infty $$$, subtract 29, relax the answer and so on. Submission: 81825489 in $$$ \mathcal{O}(n C) $$$.

I saw people coming up with completely different techniques, quite interested to see what is going to be in the editorial.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you mean by "relax the answer" ? Give it a massage xD ? sorry if its a bad joke but legit confused.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Suppose $$$ ans' $$$ is cost function on a feasible solution and $$$ ans $$$ is the global answer you're going to print. What I meant by relaxing was updating $$$ ans = \max(ans, ans') $$$. I thought it was a technical term, but apparently it's not lol

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't get why the second aproach works, could you please explain it?

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

solution for C using binary search + struct for comparing fractions 81827499

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I know E was mathematical but still, inmho contest would have been better if E and D swapped positions. Many people use m2.codeforces during the contest, hence don't see standings sometimes.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    And again, E had less submission than D. So, even the normal users wouldn't get the intuition that E was easier than D.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I try to solve problem C, but my code keeps failing at TC 3 (on a seemingly corner case). Can you help me spot the bug?

Here is the code: https://mirror.codeforces.com/contest/1359/submission/81828965

Thanks!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2C, I'm not sure about this Test case #2:

759542 609405 620256

The correct answer is 2, which implies:

64217.5 = abs(t - (h+c)/2)

But if you use just 1, you get:

10851 = min(abs(h-t), abs(c-t))

which is smaller. Shouldn't the correct answer be 1?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well, I guess if you use just 1 then difference should be abs(h-t) and not min(abs(h-t),abs(c-t) and in this case, abs(h-t) is 139286 which is definitely greater than 64217.5

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why do we have time for hacking when pretests are so strong?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Problem D had a DP solution as well:

If we assume arr[i] is the maximum element in the answer subarray, then we just need to find the maximum subarray starting from (i — 1) going towards left and not having any element greater than arr[i] and similarly for right.

Define solve_left(index, max_allowed) as a function which gives the maximum sum starting from (i — 1) and going towards left and not having any number greater than max_allowed, now it simply terminates if arr[index] > max_allowed otherwise we can try including it and going one step left.

Similary we can do for right, so answer will be maximum of solve_left(i — 1, arr[i]) + solve_right(i + 1, arr[i]) for all such i. This ofcourse works only because arr[i] can't be very large.

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

...where $$$x$$$ is the number of jokers in the winner's hand, and $$$y$$$ is the maximum number of jokers among all other players. If there are two or more players with maximum number of jokers...

Was anybody else thrown off by perceiving the last sentence as referring to "the maximum number of jokers among all other players"? :(

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Could someone please mention what is the hack for problem D. So many solutions are failing

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C can be solved without binary search. There are 3 possible cases

Case 1: h=t

Case 2: number of hot water cups=n and number of cold water cups=n

Case 3: number of hot water cups=n+1 and number of cold water cups=n

we can solve each case separately and select the appropriate answer.

(in case 3, we need to consider both ceil and floor value for answer)

My Submission: https://mirror.codeforces.com/contest/1359/submission/81845040

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how to get the optimal answer from a formula? Because I still don't understand. Thanks in advance.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      Let the number of hot cups be p and cold cups be q

      So our value closest to given_temp(t) would be in the form ((h.p)+(c.q))/(p+q)

      For case 1, the minimum count of cups to be poured is obviously 1

      For case 2 p=q=n, our equation would just be ((h.n)+(c.n))/(2.n) [for this case the minimum count of cups to be poured will always be 2]

      For case 3 p=n+1 and q=n, put the values in the equation and equate it to given_temp(t) and solve for n. Then consider both floor and ceil value of n.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks. I understand now. Now i feel like my binary search solution is a bit stupid.

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Most simple solution for D is trying out all maximum values: Solution

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u explain ur solution?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am checking for each number i from 1 to 30, such that this number i is the maximum allowed candidate in any contiguous sub-sequence by running a loop over N (like we do in Kadane's algorithm). Now if we carefully analyse this and dry run over a test case, then we can observe that all the possible contiguous sub-sequences will be taken into account and we get our maximum answer.. :)

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me please!

https://mirror.codeforces.com/contest/1359/submission/81801071

why my code is tle?Truly thanks!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly same here brother...... I am also getting TLE on test case 4.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Trying every result is too slow if the test case is:

    30000

    1000000 1 500001

    [Same test case for 29999 more times]

    Your code has a time complexity of O(result/2-1)

    Which maximum could be: O(30000*(99999/2-1) <-maximum result) = O(1499955000), which is TLE.

    Try binary searching the result.

    TLE on test case 4 (Trying all values of n): 81758945

    Accepted using binary search: 81782856

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

2 hours since hacking phase got over

Why isn't the system test starting?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    System testing finished more than an hour ago. Rating changes are yet to come.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ohh, I didn't see it, must be a very fast testing

      → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it
  • Problem C : This Problem Can be Solved Mathematically using inequalities.
Idea
Solution

Link to my solution : 81821029

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain step 3 in more detail. Namely, how does the inequality simplify?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you simply have to solve for n :-

      t >= (n*h+(n-1)*c)/(2*n-1) ==> (2*n-1)t >= (nh+nc-c) ==> (2nt-nh-nc) >= (c-t) ==> n(2*t-h-c) >= (t-c) ==> n >= (t-c)/(2*t-h-c)

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is it taking longer than usual in rating updation :/ ???

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Weak pretests for D...solutions which used segtree(without kadane) were very much prone to it!!

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

So many different solutions for D work. even my naive O(nlog^2(n)) solution.

https://mirror.codeforces.com/contest/1359/submission/81855994

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is someone's luck more broken than my increased rating?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Mine. Rating doesn't matter buddy.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You have been blue in the past bro. It gives a massive confidence boost for sure. Hard luck though hope next time we reach blue.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    See rating curve of Likhon5

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

CF-Predictor shows -2 in my rating but got +2. Became master with minimum required.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    It is exactly deviated by 4 . I don't know why but it happened with me too in last round .

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C: Could someone please tell why this is failing?

https://mirror.codeforces.com/contest/1359/submission/81861059

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Wait for the editorials is too long!!

→ Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

Can we get a diversity of problems? Problems where we need to use data structures like Trees, Graphs, Union Find, Tries? Now half of the problems are math.

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

when will the editorial be out????

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My code gives correct answer for Problem C test case 2 in Sublime Text and online compilers but incorrect output by codeforces compiler. Please Help.

Code

Test case-(5th subtask of test case 2)

1

763097 140997 594537

Expected Output- 3

My output in cf-2

My output in other compilers-3

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me about penalty system? i solved two question without incorrect solution and one of my friend also solved two question with -6 penalty but still got same rank as mine ? how ? and also we both submitted the questions on same time.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD : Fixed

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +2 Vote: I do not like it

    for first case do some pen and paper work, write down all combination (like : 1,2,3 and 1,2,4 and so on). Than you can see that from all the value of array(a1,a2,...ak) the minimum one should be the divisor of all other value, if any array satisfy this than this is a stable array. So, now you can put (i = 1 to n) every value in the first position of the array and you can choose rest k-1 position from the number of divisors of that i in (n-i). you can do this by ncr, here n is the number of divisor of chosen i in (n-i) and r is k-1.
    Now, why it works. you can observe that when in array a1,a2..ak (the array is sorted) at least 1 value is not divisible by a1 than you can choose that value (for example that value is ak), now if your observe that when the permutation is look like this one : ak, ak-1, ... a1, than the total modulo will be 0 and if you take this permutation : a1,a2,..ak, than total modulo will be different cause ak is not divisble by a1 and that is why (ak%a1) will not be 0 and also will be less than all other value in that array and it will remain same till the end.
    I upsolved this problem, it turned out that E was much easier than C and D. I wish i could try to solve E instead C and D in the contest time. Anyway, i tried to share my approach.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What I could think of was... If you consider a case where there is a number A and you make your array in such a way that the first element is A and then all the other elements are multiples of, you can be sure of following the constraint. If you consider any permutation of this array the answer to the modulus after all the elements will be X%A. You can try out some cases using pen and paper and you will see that is only what happens. So now you want to make an array like this. For this, you can just fix the first element A. Now let us say there are M multiples of A which are <=N. So, now you can choose K-1 from these M multiples doing C(M , K-1) % MOD. Find the summation for all the values of A. And this will be your answer. You can find the number of multiples of each value of A in O(NlogN) and you can compute C(M , K-1) for all of them by pre-computing the factorials and using Fermat's Little Theorem. Overall Time complexity will be O(NLogN)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wrong answer ll ans = m/(k-1) + (m%(k-1) >0) ? 1:0 ; right answer ll ans = m/(k-1) ; ans += (m%(k-1) >0) ? 1:0 ; why???

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    + has higher precedence than ?, so your first version means

    ans = (m/(k-1) + (m%(k-1) >0)) ? 1:0
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you can do this one : int ans = m/(k-1) + ((m%(k-1) > 0) ? 1 : 0);

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When do we get the editorial for the contest?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain the solution for problem F? Long time no editorial:(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Well, there's the intended solution and the brute force solution.

    The intended solution: we'll binary search for the answer. So we need to know whether it's possible for two cars to collide in the first T seconds. For a specific car, the possible points it could be after T seconds form a line segment (from the initial point to the point it would reach after driving for T seconds — it can be anywhere along this segment depending on when it starts). If any two of those segments intersect, it can be arranged for the respective cars to collide, otherwise not. There is a standard (although somewhat complicated) $$$O(n \log n)$$$ line sweep algorithm to decide whether a set of line segments contains any intersections.

    The brute force solution is just to check each pair of cars to find the intersection time. As long as you implement it reasonably efficiently (e.g. make sure you do O(n) rather than O(n²) sqrts) and are careful about rounding errors, it'll pass. You need to consider a few cases: - The cars move in non-parallel directions: solve a system of linear equations, and check that both cars reach the intersection after a positive time. - The cars move in parallel directions, along different lines. - The cars move in parallel directions along the same line, either towards either other, away from each other, or one of each.

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem D :- Easy Dp approach :D 81882431 check it

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This solution is too simple to try to understand what x, fl, mx, -mx, abs(mx) mean ;)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial not published yet? by the way, great contest! Cheers

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think authors are busy with today's Kotlin Heroes: Episode 4 as both rounds are prepared by same authors. So editorial is not published yet.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello,

I would like you to help me with this problem https://mirror.codeforces.com/contest/1359/problem/C

The expected answer for : h = 999977, c = 17, and t = 499998 is 499981

Shouldn't it be 499979 instead ?

I've checked using this snippet (python 3):

h = 999977
c = 17
t = 499998

def f(a):
   x = a // 2
   return (x * (h + c) + h)/(2 * x + 1)

print(abs(t - f(499981)) - abs(t - f(499979)))
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your text to link here...

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I'm too working on this problem now.

    I'm also getting 499979 as the answer

    in order to debug printed the range of answer close to the target and their absolute difference.

    for the test case

    1 999977 17 499998

    Debug is printed in the format (how many times we pour water, average temperature, difference of average with the target temperature)

    499977 499998.0000060003 0.0000060002785176038740000
    499979 499998.0000020001 0.0000020000734366476536000 499981 499997.9999979999 -0.0000020000734366476536000 499983 499997.9999939998 -0.0000060002203099429610000 499985 499997.9999899997 -0.0000100003089755773540000

    by this precision 499979 and 499981 trials are closest to t=499998 with same differnce as the problem asks for minimum amount of times with which we can pour water that achieves closest distance 499979 should be the answer.

    Still wanted to know whether there are any precision errors here ? Can anyone help we with this case ? or debug the correct precision ?

    EDIT : Got it from other comments regarding the precision difference :(

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

tutorials are still not published :(

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Alternative solution for problem D using dp https://ideone.com/wPZS3p

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply