Wind_Eagle's blog

By Wind_Eagle, 5 weeks 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, csani, Monogon, guptapratham42, 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

»
4 weeks ago, # |
  Vote: I like it +91 Vote: I do not like it

As a tester, ask me anything.

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

    What's the solution to the last problem?

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

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

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

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

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

    Hi Monogon, How come you are getting downvotes?

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

    How so orz?

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

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

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

        I think this one comes from Um_nik's blog.

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

          Must be a notorious coincidence.

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

    is this like the ecnerwala blog but in contest blog?

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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?

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

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

    How to become tester???!!!!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +51 Vote: I do not like it
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I guess it was a joke.

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

          Oh wow. Didn't knew it was a joke. I wanted to help him become a tester once. :(

          Spoiler
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          r/woooosh

    • »
      »
      »
      4 weeks 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!

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

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

      • »
        »
        »
        »
        4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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?

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

    How was the testing?

    • »
      »
      »
      4 weeks 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.

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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.

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

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

    • »
      »
      »
      4 weeks 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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Monogon Love the way you ask for upvotes. One upvote for you from my side. LOL

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

    How is Monogon ?

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

      I'm doing ok. What about you?

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

        Just started now need to explore the things !

  • »
    »
    4 weeks 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.

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

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

    • »
      »
      »
      4 weeks 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.

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

    As a tester, how much contribution do you want ?

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

    how to get +195 contribution?

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

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

    Why does Errichto has two youtube channels?

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

      So he can say he has double the subscribers.

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

        Why don't you have a youtube channel?

        • »
          »
          »
          »
          »
          4 weeks 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.

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

            You can do DIV-2/3 if you're comfortable.. It will not put pressure on you as it would be unrated for you.

  • »
    »
    4 weeks 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?

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

    When are you becoming red ?

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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...

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

    how to get contribution??

    • »
      »
      »
      4 weeks 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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    include<bits/stdc++.h>

    using namespace std; typedef long long ll;

    int main(){ int t; cin>>t; while(t--){ ll n, count = 0, limit; cin>>n; ll a[n]; bool flag = true;

        limit = n*(n-1);
        limit = limit/2;
        limit -= 1; 
    
        for(ll i = 0; i < n; ++i){
           cin>>a[i];
        }
    
           for(ll i = 0; i < n - 1 && flag; ++i){
             for (ll j = i + 1; j < n && flag; j++){
              if(a[i] > a[j]){
                  count++;
                  if(count > limit){
                     flag = false;
                     break;
                  }
              }
           }
        } 
    
    
    
        if(count <= limit && flag)
           cout<<"YES"<<endl;
        else 
           cout<<"NO"<<endl; 
    
    }
    return 0;
    

    } Its the 1st sum: why did this kept exceeding pretest 2

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

      This is quadratic, the constraints can go upto 10^5.

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

        Yes. I just figured it out. What's the solution to it?

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

          An array can take atmost n*(n-1)/2 swaps to sort and that worst case is when the array is strictly decreasing.

»
4 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

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

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

    This was a genuine question but whatever...

    • »
      »
      »
      4 weeks 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.

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

        Well, I suppose I should've searched before posting here.

  • »
    »
    4 weeks 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 :)

»
4 weeks ago, # |
  Vote: I like it +57 Vote: I do not like it

I love rounds coordinated by antontrygubO_o.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      4 weeks 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...

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

      No Adhoc/Constructive unfortunately :'(

»
4 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Legend says Monogon will reply to every comment on this blog

  • »
    »
    4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

Is the apocalypse near? Why is Monogon getting downvotes?

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Hope there will be short statements and strong pretests .

»
4 weeks 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

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

Long statements is Boring :(

»
4 weeks 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 ://.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

We hope there will be interesting tasks with strong pretests.

»
4 weeks 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)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I will get rating in this round.

»
4 weeks 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 ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck everyone and hope u positive rating change

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the problem statements clear? They can be long provided they are clear.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'll do you one better: Why is Monogon?

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Is Mono gone?

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Who is monogon?

»
4 weeks 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..!!

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

After seeing the long lists of upcoming contests...

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I think that this round will be amazing

  • »
    »
    4 weeks 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 :(

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

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

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Adhoc shit incoming

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it
»
4 weeks 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. :(

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

i really started to love the comment section lol

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Best Of Luck to everybody for the round

»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

hello,MikeMirzayanov..plz..help me..i forgot to register in this contest..please..enable me to join the contest!.or anyone help me..(its bigger than ocean..)..plz..give me a chance..

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

    Nibel is a forest where Ori lives.

    • »
      »
      »
      4 weeks 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

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

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

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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 :)

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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)..

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

                The contest is over now.

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

.

»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

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

»
4 weeks 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 :(

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice Round! What's the solution for D?

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

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

    • »
      »
      »
      4 weeks 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.

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

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

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

nice round .. thank you how to solve C2 ?

  • »
    »
    4 weeks 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)

  • »
    »
    4 weeks 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).

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

      Can you pls explain the reasoning behind this? Thanks!

      • »
        »
        »
        »
        4 weeks 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).

  • »
    »
    4 weeks 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).

    • »
      »
      »
      4 weeks 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
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

As a participant, I declare that this round was nice

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hint for C2?

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it
»
4 weeks 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...

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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 :(

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

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

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

    How did you use a segment tree to solve that?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a hint for C2?

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

    Wait for editorial, it will appear very soon.

  • »
    »
    4 weeks 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.

»
4 weeks 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.

»
4 weeks 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 ?

  • »
    »
    4 weeks 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.

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

      OMG I'm so stupid

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

      And here I am! Applied bubble sort logic and was counting the number of swaps. I'm so dumb!!!! Received TLE.

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

    well the number of inversions required will be maximum when the array is sorted in decreasing order and all elements are distinct and it will be equal to : n*(n-1)/2. Since we are given 1 operation less then this count so answer will be no only when all elements are distinct and sorted in decreasing order.

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

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

  • »
    »
    4 weeks 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

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

    It was bubble sort, and in worst case number of swaps are (n*(n-1))/2. So we just need to check if it was the worst case of bubble sort i.e strictly decreasing array.

  • »
    »
    4 weeks 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

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

    You write so unreadable code man :(

    • »
      »
      »
      4 weeks 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

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

        The merge sort part in your code is something which looks close to actual code, the rest looks like some cryptic code written to burn someone's eyes. No offense.

  • »
    »
    4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Really Nice problems. tnx :)

»
4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

»
4 weeks 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

  • »
    »
    4 weeks 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)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what wrong in my code? 93694586

»
4 weeks 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

  • »
    »
    4 weeks 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).

    • »
      »
      »
      4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really, Enjoyed the contest! Thanks to all the testers and problem setters who made such a fantastic contest. You guys are legends. Love you all.. :)

»
4 weeks 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.

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

    Why? The stories were short and nice :)

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

      Atleast I agree with Wind_Eagle, they were actually nice and short :)

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

      Usually, you guys say that you don't like stories now you are liking his comment just because he is yellow

  • »
    »
    4 weeks 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.

»
4 weeks 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

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Nice problems.

»
4 weeks 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

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

    In the best case scenario you always choose an odd number of Pokemon so sometimes your code will needlessly subtract the last element I think.

  • »
    »
    4 weeks 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?

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

      yes,I think so..my friend wrote similar code.only difference was I wrote a[n]=a[n-1]-1; and he wrote a[n]=0;

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I solved B 30 seconds after the contest so unlucky...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    not needed

  • »
    »
    4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Realy like it. Waiting for your next contest.

»
4 weeks 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.

  • »
    »
    4 weeks 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

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

      But we still have to use the brute force approach with a nested loop right ? Please help me since I've got 2 TLEs in a row.

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

        store the highest bit in a map or something. Then for each unique value k of highest bit add (k choose 2) to the total.

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

    Definitely no need for sorting as it will disturb the order of calculation of answer in the first place..just calculate the position of highest set bit in all numbers and notice the following :

    AND of 2 number will be greater or equal then XOR iff the position of highest set bit in a[i] and a[j] are the same, else XOR will always be greater.

    Store these positions of highest bits of all numbers in an array and iterate to find all such indices which are equal. Can use a map for it.

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

    I think you can solve it with brute force I am not sure because I optimized it 20 seconds before the contest ended but what you need to use is this to optimize it. https://www.geeksforgeeks.org/sum-product-pairs-array-elements/ I am not 100% sure my approach is correct as I can't submit now but I got TLE and not WA before the optimization.

  • »
    »
    4 weeks 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).

  • »
    »
    4 weeks 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

»
4 weeks 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.

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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..

  • »
    »
    4 weeks 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 :)

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

.

  • »
    »
    4 weeks 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.

»
4 weeks 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

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone explain in problem A why there are 0 exchanges for values 2,1?

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

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

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

      maybe

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why in problem A there are 0 exchanges for values 2,1?

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

    using formula in A max exchnages allowed = (n * (n − 1)) / 2 − 1 for n = 2 , max exchanges allowed = 0

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Did anyone solve E using flows?

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

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

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

is it DIV 2 or DIV 1 ? please reply !!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone prove why this solution for C1 is correct?

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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.

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A: To sort an array of size n, we need n * log n moves. But the sad part is the problem wasn't go though this solution.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, I commented Twice

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It went well. Very cool contest

»
4 weeks 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.com/contest/1420/submission/93711225

»
4 weeks 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: ).

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      Sorry, my bad

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

      can you explain the difference?

      • »
        »
        »
        »
        4 weeks 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].

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Good to see the editorial has the hint part.

»
4 weeks 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 :)

»
4 weeks 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

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldnt even solve A!!

  • »
    »
    4 weeks 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.

»
4 weeks 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.

»
4 weeks 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 :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem similar to C1 was already on internet.

Check this Wind_Eagle .

https://tkramesh.wordpress.com/2009/10/08/maximum-alternating-sum-subsequence/

»
4 weeks 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?

  • »
    »
    4 weeks 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.

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

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

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

»
4 weeks ago, # |