Wind_Eagle's blog

Codeforces Round #672 (Div. 2)
By Wind_Eagle, 4 years ago, translation, In English

Hello, Codeforces!

I am very glad to invite you to the Codeforces Round #672 (Div. 2), which will take place in Sep/24/2020 17:35 (Moscow time). This round will be rated for the participants with rating lower than 2100.

All tasks were made by me, but gepardo helped me a lot with the last two tasks, probably these tasks wouldn't have appeared if he didn't help me.

My thanks to:

  • antontrygubO_o for coordinating this round. With this great coordination only good tasks remained in the contest.

  • gepardo made a lot, there wouldn't have been this contest if he didn't help me. He not only helped me with making last two tasks, but also helped me to understand how to make tasks for Codeforces rounds. Thanks!

  • EIK this is the person who teached me competitive programming — my Informatics teacher. Thanks!

  • programmer228, Hacktafly, K1ppy inspired me to make this round, listened for the every task idea, provided feedback and testing. Thanks!

  • Osama_Alkhodairy, vamaddur, thenymphsofdelphi, Devil, Ari, SleepyShashwat, TechNite, Monogon, Tech.Maniac, Kavit_Kheni for testing the round and the tasks. Thanks!

  • MikeMirzayanov for Codeforces and Polygon platforms. Thanks!

  • You for participating in this round. Thanks!

You will have 2 hours for solving 5 tasks, one of which will be divided into easy and hard verions. I hope you will enjoy the round, I tried to make short statements and strong pretests interesting tasks.

Score distribution: 500 — 1000 — (1000 + 1250) — 2000 — 3000

UPD: The editorial is available. English version will be ready after the system testing is over.

UPD2: The english version of the editorial is ready.

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

Comments Comments (286)
| Write comment?
»
4 years ago, # |
  Vote: I like it +91 Vote: I do not like it

As a tester, ask me anything.

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

    What's the solution to the last problem?

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

      I would tell you if I knew how to solve it :sob:

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

        Now this seems entirely believable, it wasn't easy at all

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

    Hi Monogon, How come you are getting downvotes?

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

      I don't know, I thought my formula for getting upvotes was foolproof. To become top contributor, maybe I'll just make another contest instead.

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

    How so orz?

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

      I just memorized some stuff that's enough to solve puzzles.

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

        I think this one comes from Um_nik's blog.

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

          Must be a notorious coincidence.

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

    is this like the ecnerwala blog but in contest blog?

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

      Not at all. In ecnerwala's blog, you get to ask someone who's actually good.

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

        so do you mean you are not good? if so why should we ask you when we can ask ecnerwala?

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

          I cannot say for sure whether you should ask me or ecnerwala, as it depends not only on the question you ask, but also on what you seek to gain from asking. If you ask ecnerwala, he may give a thoughtful reply. But such a reply might also come very late or never seeing that his AMA was posted some time ago. On the other hand, my replies are likely to be stupid, repeated jokes, but you will get them immediately.

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

            Whenever I see Monogon in the list of testers, I immediately visit the comments section for his quick wit. The comments section, in general, is great fun. Or maybe it's the lockdown that's rendered me so aimless.

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

    How to become tester???!!!!

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

      Click

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

      It's very simple. Just pick a random user from the "top rated" or "top contributors" box to the right, and send them a direct message asking to be a tester. They are all making contests right now, so they'll immediately let you see the upcoming problems and pay you to test them. Hope this helps!

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

        they pay you to test or you pay them to test?

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

          It depends on how well you do. Testing is no different than a game of blackjack.

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

          You guys are getting paid?

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

            why you are asking me? ive never been tester

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

        I'm pretty sure Errichto isn't making any rated contest for cf right now.

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

        don't they judge me ??? I want to know what qualification need to be a tester?

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

    How was the testing?

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

      Testing was good. I found that one problem had appeared before and so it was replaced. But then because it was replaced, I dropped in the standings, and other testers assumed I was even dumber than I really was.

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

    As a tester. You cannot participate in this round. Is this guaranteed by technical means or is it consciously? Do you know all the problems? Or only the parts?

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

      Yes, I know all the problems, and I'm not allowed to participate in the contest. I don't think there's anything in the system preventing testers from actually registering for the contest and submitting solutions, but obviously it would get caught by Mike Mirzayanov's omnipresence.

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

    MR. Monogon , Why 5 problem in most of the recent contests ?

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

      This is a better question to ask coordinators. It could be a false pattern in random data.

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

    How is Monogon ?

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

      I'm doing ok. What about you?

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

        Just started now need to explore the things !

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

    What is the probability of solution getting accepted after passing of pretests in total.

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

      Hope it is not like previous contest. I know your pain brother.. :(

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

      Given the large number of users, there have to be very few pretests on early problems to prevent a long queue. This is pretty limiting, even if each test has many test cases. So, it's very hard to write good pretests. Despite this, I think on average we're in a much better place than a few years ago.

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

    As a tester, how much contribution do you want ?

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

    how to get +195 contribution?

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

      Just set 2 contests solo, 1 contest on a team, write a tutorial, and hijack the comment section of all rounds you test as your personal upvote farm.

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

        Your genius, it generates gravity. Really loved(and upvoted) every comment. errichto should have participated too.

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

    Why does Errichto has two youtube channels?

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

      So he can say he has double the subscribers.

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

        Why don't you have a youtube channel?

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

          I've considered it. But I'm afraid doing screencasts will put pressure on me, and will negatively impact my performance. Especially if I provide commentary. Other content such as video tutorials is actually very time-consuming, and I don't think I could explain things better than existing resources for most topics. I admire those who do make videos and try to grow the competitive programming community because I understand it's a lot of work. Personally, I find problemsetting a better way for me to give to the community.

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

    Why does problem C have more point in total than problem D?

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

    When are you becoming red ?

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

    Where is/are Mifafavov, is there some bigger conspiracy we are not aware of?

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

      If it's a conspiracy then I'm not a part of it. Although I suppose I'd say that even if I was in the conspiracy...

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

    how to get contribution??

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it
      1. Host contest.
      2. Post announcement and editorial.
      3. Test a round and hijack its comment section.

      It's a known fact.

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

off-topic, how to be a tester for some round?

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

    This was a genuine question but whatever...

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

      Genuine question asked on almost every other contest announcement blog. Again and again.

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

    Usually you can connect with the coordinators or the author and they can allow you to test and discuss , mostly its yellows and reds because of their greater experience and knowledge they can find issues / judge difficulty better. Hope that helps :)

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

I love rounds coordinated by antontrygubO_o.

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

    Ad-hoc and Constructive algorithm missiles incoming!!

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

      First of all, I'm not talking about the nature of the problems. Sometimes I like ad-hoc and constructive problems, and sometimes I don't.
      What I like and he delivers — short statement, strong pretests, normal readable English, coherent sentences (unlike the last round), understandable and unambiguous statements.
      I enjoy reading the clear statements in his rounds, and I never feel ripped off after the contest. I think that's a good enough reason to like his rounds...

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

Legend says Monogon will reply to every comment on this blog

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

    Well it would be kind of rude not to answer questions in my own AMA, wouldn't it?

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

Is the apocalypse near? Why is Monogon getting downvotes?

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

Hope there will be short statements and strong pretests .

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

After a series of thanks by WIND_EAGLE,thanks from the contestants who will witness a positive rating change

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

Interesting that most of testers for the Div2 round are orange or higher.

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

Long statements is Boring :(

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

Whenever I see the short statements and strong presets statement, I instantaneously imagine that I will be losing rating in this contest but then again most of the contest I take part in become unrated ://.

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

We hope there will be interesting tasks with strong pretests.

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

Monogon has earned a total of 652 upvotes in this blog alone where the blog post is sitting at 414. (Also, you might think how free am I to do count such dumb shit. Guess what, you are right)

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

Interesting to see the total score of problem C greater than that of problem D ! I wonder how many times has this happened before ?

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

Best of luck everyone and hope u positive rating change

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

Will Monogon Comment Here Or Has Mono Gone??!!

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

Is Mono gone?

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

Who is monogon?

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

it's really amazing how he tried to appreciate every one..!!

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

After seeing the long lists of upcoming contests...

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

I think that this round will be amazing

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

    But I won't take part in it :(

    It's toooooooooo late for me :(

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

      Ohh, it's really sad.I hope that virtual solve help you

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

Adhoc shit incoming

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

I hope that queue of testing solutions is not long on this round

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

I am not sure why this happened last time but the pretests were way too short as compared to other recent cf rounds. Quite a few failed system tests. Hope it is not the case this time around. :(

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

i really started to love the comment section lol

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

Best Of Luck to everybody for the round

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

I still don't know who, or what Nibel is.

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

    Nibel is a forest where Ori lives.

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

      Is the plot based on Ori and the Will of the Wisps? I had played Ori 1 and didn't recognize things in the statement

      nice problems btw

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

        No, the statement is based on Ori and the Blind Forest.

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

          Sorry I'm just dumb. I never played the game in English and never remembered the names of those things.

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

            Well, I understand you, I've never played this game in English too :)

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

              hey,can you please give me a chance to register..i forgot..and solved problem A 1 hour ago(maybe much)..

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

                The contest is over now.

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

.

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

As a participant, I declare that this round was great.

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

when you spend an hour debugging code because u forgot to set mod inverse factorial of 0 to 1 :(

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

    The contest is still ongoing.

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

    when you spend an hour first trying to fit python solution into the constraints and getting +4 rejected and then giving up and rewriting it in c++

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

    Dude, what is wrong with you ? why are you posting such things during contest ? MikeMirzayanov

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

Nice Round! What's the solution for D?

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

    Just sorting ends of the intervals and then a bit of combinatorics

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

      Come on, answer the question or ignore it. But do not act like a dick.

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

        Come on. I did answer it. Without giving details, but nevertheless.

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

          That "answer" did not help at all. You just did tell that is was easy for you.

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

            I'm pretty sure that knowing that you need to put ends of the intervals in the array and then use combinatorics is quite a huge hint

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

nice round .. thank you how to solve C2 ?

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

    reconsider (check for peak or bottom) only adjacent elements of swapped ones. (and the swapped elements too of course)

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

    Answer is sum of max(a[i] — a[i + 1], 0) (a[0] = 0). Change in answer can be calculated in O(1).

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

      Can you pls explain the reasoning behind this? Thanks!

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

        If we take two numbers, first number should be larger than second. So if there is some decreasing sequence $$$a_1, a_2, a_3, ..., a_k$$$, value of $$$a_1$$$ — $$$a_k$$$ is same as $$$(a_1 - a_2) + (a_3 - a_4) + (a_i - a_{i+1})$$$. So we will always add two numbers(add zero to end of array a answer doesn't change).

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

    Seems like I massively overkilled but my solution would work for any changes, not just swaps:

    Keep a segment tree where each node store the maximum value of a sequence with the following properties: (starting with pos, ending with neg), (starting with pos, ending with pos), (starting with neg, ending with pos), (starting with neg, ending with neg)

    The merge is trivial to do in O(1).

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

      Using the observation that as long as numbers are distinct, the contribution of $$$i$$$th term to the final answer depends only on $$$a_{i - 1}, a_i, a_{i + 1}$$$, you can arbitrarily update any index trivially in $$$O(1)$$$.

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

As a participant, I declare that this round was nice

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

Hint for C2?

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

    If a[i] is greater than a[i-1] and a[i+1], add a[i] to the answer. If a[i] is less than a[i-1] and a[i+1], subtract a[i] from the answer. And let a[0]=a[n+1]=0. Change the contribution of up to 6 positions per exchange. Complexity: O(n).

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

Solution of D: https://www.geeksforgeeks.org/number-of-ways-to-choose-k-intersecting-line-segments-on-x-axis/

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

Time limit on C2 was too tight. I wrote up a Segment Tree and got TLE on pretest 6...

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

    No, I also wrote a segment tree, got AC in 1.2s, it's 16*N only.

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

      Actually it's 8*N since you can reduce the size of the tree to 2*N with a well known trick. Still, my seg tree implementation must be bad, because I still got TLE. Very sad :(

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

    The same, wrote a solution with sets O(QlogN) and got TLE.

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

    How did you use a segment tree to solve that?

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

Can someone give a hint for C2?

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

    Wait for editorial, it will appear very soon.

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

    Keep track of maximas and minimas in an array, and see how answer can easily be computed only from the sums and indices of maximas and minimas.

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

Problem D: https://www.geeksforgeeks.org/number-of-ways-to-choose-k-intersecting-line-segments-on-x-axis/

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

Most common mistake made in those 3500 failed submissions of problem D in this round %9982444353.

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

I solved A using mergesort lol how did u count inversions so easily ? isn't it counting inversions ?

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

    Total number of swap needed for sorting a strictly decreasing array are $$$n * (n - 1) / 2$$$. That means if the array is not strictly decreasing answer is YES, else NO.

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

    When listening to your college teacher actually pays off lol..

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

    { a1 > a2 > a3 > a4 > ... > an } is the only case that you need to make exactly n*(n-1)/2 operations

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

    You don't need inversions, you have to check if atleast one pair i < j with a[i] <= a[j], you can just store minimum

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

    You write so unreadable code man :(

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

      if you mean mergesort code I didn't write it just copied it from some site I don't even how it's working

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

    By the way you can also solve it (count inversions) using a segment tree

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

My favorite room is the one with 3 * 10^5 lamps

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

Can anyone please tell how to calculate binomial coefficient C(n,r)%Prime when n<=10^9 ? (or n<=10^18 maybe)!

(Please don't give Links of blogs. I went through many of them during the contest. Please provide a link to the Code)

Also, can anyone please tell why my solution for Problem D gave TLE on Test-11 (Gave me PTSD)? Thanks.

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

I solved C2 with a segment tree to maintain the product of matrices.

It feels so dumb to write such a monster to solve a d2C.

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

    Can you please explain the basic idea? I can't think of a way to merge nodes, support updates, and queries.

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

      Sorry for the late reply.

      First we redefine the multiplication of matricies. Here $$$C_{i,j} = \max { A_{i,k} + B_{k,j} }$$$.

      Consider the dp solution of C1: $$$f_{i,0} = \max ( f_{i-1,0}, f_{i-1,1} + a_i) , f_{i,1} = \max ( f_{i-1,1}, f_{i-1,0} - a_i)$$$. It can be represented as a matrix multiplication. We have

      $$$ \quad \begin{bmatrix} f_{i-1,0} & f_{i-1,1} \end{bmatrix} \quad

      \times

      \quad \begin{bmatrix} 0 & a_i \\ -a_i & 0 \end{bmatrix} \quad

      =

      \quad \begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix} \quad

      $$$

      You can use a segment tree to maintain the product of the matricies. Check my submission for better understanding

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

for problem D, Time Complexity of my Python 3 solution is O(NlogN) but still getting TLE.

can anybody help. link of My solution

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

    You don't seem to use any recursion in your code, it should work with pypy (without all the setrecursionlimit, threading etc code)

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

      I don't think there is any need for recursion. here is my solution in pypy which was also getting TLE.

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

How to solve E?

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

    If we fix number of zeros between adjacent ones (let's denote it as $$$g_i$$$), then answer is sum of $$$g_i$$$ * (sum $$$g_j$$$ where $$$j$$$ < $$$i$$$). So now this can be easily calculated with dp[i][last][moves], each transition is O(N), overall complexity is O(N^5), but there is a lot of unreachable states so it should pass.

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

what the hell is that quotations in starting of each question??

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

Can someone tell me what wrong in my code? 93694586

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

The problems were great but for heavens sake you didn't have to set such tight constraints for D

Really annoying when solution with the correct asymptotic does not fit into constraints just because it is written in the wrong language and/or lacks some microoptimisations

I understand that there are plenty c++ lovers here, but still, don't do it. It is div2 after all

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

    I implemented counting the overlapping intervals. That needs to sort an array of size N*2 which should be possible in all languages. The other loop is then O(n).

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

      That's the same thing I did

      Except that just sorting 3*10^5 tuples in pypy can take nearly a second. Much faster in cpython though.

      Note that even your c++ solution with all io-tricks takes half a second.

      10^5 would be enough to cut off ineffective c++ solutions

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

problems were nice but is it too hard for problem setters to understand that we don't want any lame story along with the problems.

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

    Why? The stories were short and nice :)

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

    adding the stories is something that gives happiness to the problem setters. If one doesn't know the game the story doesn't feel awesome(maybe lame) but just bear with it for the setters.

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

Hi, I tried to use segment tree to maintain maximum and minimum for alternating sequence with odd and even length for C1 and C2, it passes the sample test but failed on pretest 2? Could someone have a look and help me figure out what is wrong? Tks a lot!

My Submission

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

    I used a similar recursive implementation and got TLE on pretest 5. I'll try this blog when I get time. BTW I used your CP templates to make mine, thanks for putting it on Github!

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

about long long. Is it okay to use long long everytime, because I forget sometimes when to use it, and today, I wasted my time thinking my logic to B is wrong.

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

Problem D How to get (Cmn mod M) when m is big

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

can someone explain me whats wrong with my code? 93695276 Its giving WA in pretest 6

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

    are you sure your code is ignoring even index (in reference to the subsequence) value if that is situated at last index?

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

why do you need to sort the array in problem B?

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

    not needed

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

    You don't need to sort the array. To see if x & y >= x ^ y, just look at the most significant bit of each number. Only if these two numbers have the same most significant bit, then we have x & y >= x ^ y (because in the xor operation, this most significant bit is destroyed, while in the and operation it is preserved).

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

Realy like it. Waiting for your next contest.

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

What are your guys' approaches to solve B ? I'm really curious since the only one I can think of is using brute force.

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

    Hint:-
    $$$a[i]$$$ $$$and$$$ $$$a[j]$$$ $$$>=$$$ $$$a[i]$$$ $$$xor$$$ $$$a[j]$$$ if highest bit set in a[i] and a[j] are same

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

    Consider two numbers a and b. If both of them have highest bit on the same position, then a&b > a^b. Otherwise a&b < a^b. The rest should be easy (if not, i can explain).

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

    I took a time to think this (especially to use long long instead of int). see the numbers as its binary form. now AND of 2 numbers will be one always less than or equal to the minimum of the two. XOR of 2 numbers can be more or less than any of the two. sol- count all the numbers whose highest precedence bit is set and those bit are in the respective positions of the array. do this for all the positions from 0 to 33, and add the number of ways you can choose 2 numbers at ith(higest precedence) postion as set. (pos[i]C2) my sol

    Note that the answer depends only on higest precedence bit

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

Can someone please tell me what was the solution to A. I'm new and this was my 2nd contest. I applied bubble sort logic and counted the number of swaps but got TLE on pretest 2.

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

    I used merge sort just coz I had a prepared file for finding inversions ... it works but there must be so much easier ways as well

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

      The total number of swaps needed for sorting a strictly decreasing array is n∗(n−1)/2. That means if the array is not strictly decreasing answer is YES, else NO.

      -- by some guy whose name was in blue..

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

    Actually the intuition of inversion count actually makes sense, but the worst case of such is when the array is in strictly decreasing manner. This case takes the no of swaps = (n * (n — 1)) / 2 and hence if the array is in any other manner it will take less than this much swaps which is the intended limit given to us. So if the array is strictly decreasing we need more than the given limit of swaps and answer is no else yes. Hope this helps and wwelcome to cf community :)

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

.

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

    5 6

    the expected answer to this is 0 but ur solution gives 1. it s one of many special cases where "If the number of bits of 2 integers are same, it's a valid pair" isn't correct.

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

I solved my first official dp problem ever but struggled with A and B... so basically my rating just raised from newbie to happy newbie xDxDxD

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

C was nice observation based : ans = sum(max(0,a[i] — a[i+1])), where a[N+1] = 0

D was standard problem if you know the range overlap relation, ie,

max(L1,L2,L3.....LK) <= min(R1,R2,R3,R4....Rk) So fix Li, as max of all L's for a set of choices of K intervals, then if M intervals overlap with such an Li, then add to the answer:

ncr(M,k) — ncr(M-D,k) , where D is the number of intervals with left boundry = Li

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

I am just wondering if the C2 is more difficult than D.

I completed D very fast but still has less idea for C2.

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

    When I came to the task C, I thought that it will be good task D. But I had current task D which could not be a task C. So I decided to make C1 and C2.

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

      Alright,I am thinking about a solution based on dp and never think that:

      $$$ans=\sum\limits_{i=1}^{n}max(0,a[i]-a[i-1])$$$

      This conclusion is not difficult to prove but I'm always think abount dp dp dp dp dp.

      I am still have a lot to improve

      QAQ

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

        Can you prove why the above solution works? I too spent a lot of time coming up with dp solution but failed and submitted the wrong greedy.

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

          If your dp[i][0/1] means that the previous number to the i-th number is subtracted(0) or added(1),You will have a simple equation:

          $$$dp[i][0] = max(dp[i-1][0],dp[i-1][1]-a[i])$$$
          $$$dp[i][1] = max(dp[i-1][1],dp[i-1][0]-a[i])$$$

          Notice that dp will be add only if $a[i] > a[i-1]$. Also dp will add a[i] — a[i — 1]

          so this is why that solution works.

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

      Should've put C1 -> D -> C2 if possible LOL

      maybe

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

Did anyone solve E using flows?

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

    Please, let me know your solution with flows, I am very interested!

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

      Actually I misinterpreted the question and allowed all 1 positions to move by a single step in one chance. So for each chance I made a layer of nodes corresponding to the gaps between 1s, and connected the final layer with the sink, with edges with cost (i-1) for each flow so that they add upto (gap*(gap-1)/2). Applying MinCostMaxFlow will give the answer. Without the restriction of a single move in a chance we can easily add edges between the layers but I am unable to figure out how to impose this restriction.

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

I like this kind of contest with strong pretests. For problem D, enumerate the ending points of all values, and then count the number of new values $$$a$$$ each time, and the number of values that are still ending before $$$b$$$. The added contribution of the answer is: COMB(a + b, k) — COMB(b, k).

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

Can anyone prove why this solution for C1 is correct?

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

    He took local maximas for addition in the sum and local minimas for the subtrating values. This would always greedily prove best for u

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

      You too have solved like this. I'm not getting why this will give an optimal answer.

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

        Check the editorial, the solution for C2 uses exactly this idea.

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

It went well. Very cool contest

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

Can anyone tell me where I did wrong with the solution for D? https://codeforces.net/contest/1420/submission/93711225

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

can anybody tell me why it is important to use long long in problem B ? (as I wasted 3 submissions before getting it correct D: ).

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

    If all numbers are same and n = 1e5 then the answer (n * (n — 1)) / 2 will overflow int.

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

I want to say that problem C1 is not new. Check this

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

    In this problem you need to choose a segment, not a subsequence.

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

      Sorry, my bad

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

      can you explain the difference?

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

        Segment is something like [2,3,4,5,6], all elements are neighboring, subsequence is something like [2,3,5,7,10].

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

Good to see the editorial has the hint part.

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

Can we solve C2 with some dp and breaking array into $$$sqrt(n)$$$ part ??

and then find this values for each part with dp:

  1. maximum sum if we start with a negative and end with a positive

  2. maximum sum if we start with a positive and end with a positive

  3. maximum sum if we start with a negative and end with a negative

  4. maximum sum if we start with a positive and end with a negative

and then we need another dp to calculate the final answer witch can be done in $$$O(sqrt(n))$$$

each time we just need to recalculate dp values for 2 part(the ones witch the L and R are inside them)

i tried the above solution and i know that the time complexity is really bad( $$$O((n + q) sqrt(n))$$$ and got TLE on test 5 with long long and WA on test 5 with int because of overflow)

i just want to know if my solution gives the correct answer or not(i don't care about the time, just want to know if the algorithm is correct or not) ??

EDIT: i submitted my code witch got TLE on pretest 5 with GNU C++17 (64) and got AC :( the time complexity isn't so bad :)

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

The best thing about this contest was the stories were short!! Hope this stays for a longer run

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

Thanks a lot for preparing for this contests.Although problems are a little easy.

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

Couldnt even solve A!!

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

    I can understand it, task A was a little bit difficult for task A.

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

Greedy solution for problem C1:

Iterate from left to right.

Find decreasing segments. (a[i] > a[i+1] > a[i+2] > ... > a[j])

Take first and last number of the segments. (a[i] — a[j])

Sum up every segments.

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

i know that A can be done in less than 5 line of code easily but the harder solution can be done in n log n with just a search in google

the same thing with c1, just a google search

other problems were nice, but its not good to see problems witch their solution is "just google things" in a CF contest :)

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

If there were 36 pretests in problem D and my solution 93708784 passed all the pretests, how can I get TLE on test 17 during system testing?

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

    If your solution tightly fits into the time limit, it might happen that it worked a little longer on system tests and got TLE.

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

      Such strict time limit that O(nlogn) solution did not fit.

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

        The intended solution is also $$$O(n\log n)$$$ and fits into time limits twice on Java. But those sets and maps significantly show down your solution, while you may use only sorting.

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

          Just added another map for storing calculated inverse mod values and it worked 93729552.

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

why did u add quotes in problem statements???? dumbest contest ever......

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

    I like these quotes :)

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

      so u just put them in a contest???? where is the logic broooo...

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

        Well, the logic is that quotes can be just skipped if you don't want to read them.

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

          how do we know they are useless without reading them??? you have to realize these are not your personal notes, we had a clock on our head, and do u really think this is some sort of smart or funny move? because I clearly can't see the point of putting them in the contest!!

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

editorial by tourist.

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

Overkill.png

When you overkill problem A with Merge Sort and Counting Inversions!

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

Wind_Eagle MikeMirzayanov I got TLE on test 9 in system testing and after that I submitted same code and I got accepted verdict.

I request you to look into this situation and do the needful.

Please review my code

TLE Solution- https://codeforces.net/contest/1420/submission/93705280

Accepted Solution — https://codeforces.net/contest/1420/submission/93728093

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

    I guess it is the reason for the higher load of the evaluation machine during system testing? Because your program running time is already close to the time limit. I don't know if it can be rejudged, the author must have this permission. It depends on whether he is willing to help you.

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

    Timer on Codeforces is not so precise, it has some inaccuracy.

    Well, it happens sometimes. I don't know is this enough reason to rejudge solutions in contests. I cannot take a decision in this situation.

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

      So, Who can take this decision? Because this is not my fault. Problem Setter can make question with Time 3s instead of 2s for avoiding such situations. Or another option is to reduce N which can be 10^5 or 2*10^5

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

        Well, if i'd made the TL 3 seconds, somebody who had TL might pass the task with 2998 ms after the system tests. He would say that I should make 4 seconds e.t.c.

        Who can take this decision? Only MikeMirzayanov I think :)

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

          If I were the only one then I won't say anything. but many people got accepted verdict with this close margin. you can see that here with accepted filter on C2 question https://codeforces.net/contest/1420/status/page/55?order=BY_CONSUMED_TIME_ASC

          and more and more people are getting TLE on this problem.

          e.g. https://codeforces.net/contest/1420/submission/93659360 Can you explain me how TLE for this solution?

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

            Yes, I can explain. Participant made an obvious mistake: he forgot to write ios_base::sync_with_stdio(false); cin.tie(0);

            You cannot read and write in one time without this commands; otherwise you will have TL.

            He could read all the data and write the answers only after this, maybe it wouldn't get TL then.

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

            If someone implemented the code efficiently enough to fit in the time limit, he/she should not be able to get WA on both pretests/system tests. However, for inefficient codes, the author cannot complain whether the judging system judged AC or TLE. Sure, it is unfair that if both of people with same codes got constrasting results(in this case: AC and TLE), but it is not the thing that author can complain, because the time can vary with status of server, which is uncontrollable. Moreover, you had chance to know that your code's processing time on your submission logs, which would be very close to the time limit. You first should have looked over the code what makes the processing time so long.

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

    I don't understand what people expect posting such examples every contest
    I'm especially surprised to see it from a candidate master.
    Obviously execution time of the program slightly changes on different runs. That's completely normal
    Program that has a borderline performance obviously may pass and may not pass by a mere chance
    It would be one thing if one of your solutions passed with 1s and the other TLEd with 2s
    But 1996ms. Are you fckg serious?

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

check out this solution of c2 93676743

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

Problem D : can anyone explain why my code got wrong answer for test case 44, although i have done the same thing mentioned in editorial.

submission : 93742154 Thanks for Help

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

In general what is the reason for the rating changes to be rolled back? Also when do they get fixed?

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

When is the rating returned? Why did it take so long to remove the cheaters? In the past, it did not take more than one hour!

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

I just received a message from System: Your solution 93688303 for the problem 1420C2 - Pokémon Army (hard version) significantly coincides with solutions 93698667. I have no idea how this match happened. I have coded this myself and haven't shared it with anyone / anywhere online. Our solutions indeed match a lot, but it's mostly because variables we used (a, l, r) was defined in problem statement itself. The best evidence I can put for my defence is consistency in my coding style compared with other problems. For example I use lf instead of endl. Pinging admin MikeMirzayanov, coordinator antontrygubO_o and setter Wind_Eagle to please look into this matter.

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

    There is one explanation for this case, which is that this person has another account and this other account is in your same room and closed the problem C2, then take your code and send it from this account!

    But do not worry, only he will be disqualified from the contest.

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

      Oh, I didn't think about that possibility. Thanks. But again, to close C2, he had to solve C2. If he solved C2, why would he send my code from another account? Also if he indeed copied from my code, I don't think he would code so similarly.

      I am worried not for possible disqualification of me (I can gain / lose rating later), but because I am sensitive about accusation of cheating.

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

        No one will accuse you of cheating because he is the one who sent your code after you, I think MikeMirzayanov should see this, Let's see how that person got your code!?

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

this was a smooth round. problems were good yet rating changes are taking like forever. any idea why?

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

The rating has been reset!

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

what is DDOS attack ?

→ Reply