By PikMike, history, 7 months ago, translation, In English,

Hello Codeforces!

On Mar/22/2019 18:05 (Moscow time) Educational Codeforces Round 62 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all participants!

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

Hello Codeforces!

We want to remind you about the two fully funded scholarships we currently have available:

Master’s in Data Science Scholarship & Master’s in Robotics Scholarship

Both scholarship opportunities include: - Full coverage of the Programme’s tuition fee (€23,000 value) - 3 hours of study a day at Harbour.Space University - 4 hours of internship a day with one of our industrial partners - €12,000 euros a year (living allowance)

If you’re interested in applying for the Robotics Scholarship, apply here.

If you want to apply for the Data Science Scholarship, fill out the form below and we will contact you about the next steps.

GO TO FORM

If you need more information about either, please contact us at hello@harbour.space

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 QDEZ604 7 250
2 dotorya 7 254
3 300iq 7 586
4 dreamoon_love_AA 6 165
5 Hazyknight 6 169

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Haunted_Cpp 8
2 7qk 4
3 Jobaidul 3
4 Abu_Musa_99 3
5 aihay 2
37 successful hacks and 149 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Sonechko 0:01
B usertab34 0:04
C KhaleD_ 0:04
D edisonhello 0:02
E Roundgod 0:23
F QDEZ604 0:38
G 300iq 0:44

UPD: Editorial is out

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

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

It's raining contests

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

    Good to have a rain after a drought

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

    I believe "aloo" flourishes in rain so good for you boi...

    P.S. For advanced species : aloo = potato xD

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

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

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

Expecting this round to be full of awesome questions with strong pretests!!!

»
7 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Thank you, Harbour.Space University for the Educational Rounds. Best of luck everyone :)

Happy Coding

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

    I think Codeforces community doesn't like wishes and greets...

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

      I think so :|

      There are some idiots also, who put down vote in every comment after a bad contest.

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

A contest by Vovuh after such a long time.

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

ROBOTICS a.k.a. the biggest lie and way to tell yourself “i’m good i’m good” and live your whole life in a lie. listen kids, no one cares about your utter trash and useless robots because you’re not the next einstein and the world has enough smart vacuums, smart fridges, smart washing machines etc. (which are better in every way than your “creations” could ever cease to be.)
it’s literally “santa’s real” for big kids / grown adults.

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

May the force be with us! Happy Coding :)

»
7 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Is it rated?

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

    its rated for you

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

    Educational Codeforces Round 62 [Rated for Div. 2], Isn't just the title enough to answer your question ?

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

.

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

there is no "*" mark before the handles of those who are not in DIV2! So is there a change in displaying people who are participating out of contest or only I am seeing this???

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

    There is no out of contest for Educational Rounds. They are for everyone. Just, it is rated for the division 2 participants.

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Im running back home for this contest. Wish I would make it home before start...

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Contest has started.

My mind:donkey mode has been activated

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I want to add some scores.^_^

»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Hope for no 502 bad gateway like there was 3 minutes ago

»
7 months ago, # |
  Vote: I like it -27 Vote: I do not like it

de ce coaie

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

Whoever decided the problem difficulties is a troll.

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

I think the order of Problem C and Problem D should change.

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

Problem statements for problems A and B could be written better. Took me a lot more time than I care to admit to understand the problems.

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

    What is the test case 2 for Problem B?

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

      Probably <<>> Ans = 2

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

      I don't know what test 2 is, but the string is good if and only if it starts with a '>' or ends with a '<'. From here on, it should be clear how to solve it.

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

        How's the answer for <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> [2nd test case, 5th one] 50? I could choose the last < repeatedly until all characters before it are deleted, then choose the first > repeatedly until all characters after it are deleted. If you do that, the answer is 1. The problem statement doesn't place a restriction on the number of times you can choose a character, it only specifies that it must exist in the string. If repeated choices are not allowed, then how does >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> evaluate to 0?

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

          You're allowed to remove characters only before you start performing operations on the string, so you can't reduce it first and then remove.

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

            Ahh! Now it makes sense!! Thanks a lot!

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

    True. The statement for A ruined the contest for me.

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

      After 4 minutes I went to read and solve B, then I came back to A. I don't know why, but reading the problem later helped me understand it.

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

      Yes even I felt doomed

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

      Lmao, felt the same D:

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

Again really nice C it's always fun solving problems that needs thinking

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

What is solution for E?? What is test 5?

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

How do we solve E?

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

    Note that there are no odd palindrome substrings of length > 1 if and only if there are no palindrome substrings of length 3. Then, note that a substring is a palindrome of length 3 if and only if the first character equals the last character in the substring. Thus, you can decompose the array into odd and even index arrays, and the problem becomes how many ways to fill in the array such that no two consecutive elements are equal. Then, we notice that we can further decompose each array into arrays of the form "# -1 -1 -1 .... -1 -1 -1 #", where # is either nothing or a positive element. From here, figuring out the number of constructions is an old HackerRank problem, with a solution on GeeksForGeeks.

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

      Yeah, you are right. That problem in Hackerrank was mine. :)

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

      Can u please provide some example or proof for your statement "_Note that there are no odd palindrome substrings of length > 1 if and only if there are no palindrome substrings of length 3_".

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

        Assume there is an odd palindrome of length >1. Then the middle 3 characters are a palindrome of length 3.

        Assume there is a palindrome of length 3. Then obviously there is an odd palindrome.

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

      My approach was all the elements at odd indexes must be unique and same for even indexes, what's wrong with this approach?

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

        Well, it's not that they must all be unique, it's that they must not have consecutive elements that are equal.

        For example, the array [1, 2, 2, 1, 1] is good, even though your approach would say it is not.

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

    Note that "no palindrome of odd length=no palindrome of length three", then solve for odd/even indices of the array separately.

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

    My idea is not so neat as the others, but I think it works: first I check with rolling hash is the existing array is good or bad. If existing array is good, then you can place any number in place of ? if two ? are at least two characters apart. For the ? which are less than 2 characters apart, we do some case handling. Next we need to check if something like this exists

    1???1, or 21??12

    So, we then handle such cases, and it's O(n). Think of dividing the array into subarrays delimited by ? on each side of it. Then each subarray contributes to the computation for ? on either side of it.

    And finally, we have ???? itself, which is not that hard.

    Overall, it's not that hard but for me and for my idea, I can't code this fast enough.

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

    You can see my dp solution here 51717191

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

      What are your states?

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

        I make a dp array with dp[i][k] is the ans for a sub-array with i numbers -1 with and k = 1 if two number at two head are equal and k = 0 if they're not.

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

How to solve Problem B and C.

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

    You have to find first '>' from left and '<' from end. From this points you can get delete rest of them.

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

      Why? Can you please explain the question and how did you get this. Because I think I am missing something in the question.

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

        From '>' you can delete everything left to it and from '<' — right ones.So, you have delete characters until '>' is first or '<' is last

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

      don't like to criticise individuals, but whoever wrote the statement for problem B is not deserving one. It says " for each operation you have to choose some character that still remains in the string", according to this, one may think that we can chose same character any number of times and then result will either be 1 or 0. But I don't know what he/she intended to write. Disappointed from this round! Also problem A was poorly written too. Took me 25 minutes to understand what the author wants.

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

        That's what I thought in Problem B. Got WA on testcase 2. Can't understand how the problem statement can mean anything else other than the logic which gives 1 and 0 as answer.

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

        You CAN choose the same character any number of times, but the answer is NOT always 1 or 0 :)

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

          Give a counter case

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

            <<>>>>>>>>>>>

            Answer here is 2: delete the fist 2 characters, then keep selecting the first character however many times you need :)

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

              Gotcha must read problem statements more carefully

              Also I submitted C after the contest using priority queue and sorting is there some other approach also. 51723054

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

              For <<>> if i choose 2nd character('<') then the string will become <>> as choosing < will delete its preceding character. Now i can choose the first occurence of '>' which will delete the last character. The string becomes <>. Now delete any one of the characters will make it a good string. So there's only one deletion. How the ans is 2 and not 1? Please correct me if I am wrong

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

              [copied from above, since this thread seems to have more activity] How's the answer for <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> [2nd test case, 5th one] 50? I could choose the last < repeatedly until all characters before it are deleted, then choose the first > repeatedly until all characters after it are deleted. If you do that, the answer is 1. The problem statement doesn't place a restriction on the number of times you can choose a character, it only specifies that it must exist in the string. If repeated choices are not allowed, then how does >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> evaluate to 0?

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

                From nishank.suresh You're allowed to remove characters only before you start performing operations on the string, so you can't reduce it first and then remove.

                It's even in boldface lol. Can't believe I missed that.

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

                  LOL XD I also missed it. Thanks bro

»
7 months ago, # |
  Vote: I like it +64 Vote: I do not like it

It seems dotorya was hacked and 0ahmad0makki0 copied dotorya submissons.

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

What is the TC #16 of Problem E?

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

The problem C is interesting ! can't wait the Editorial... any hint ?

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

    If you are told the minimum beauty value of your elements, could you easily find out what the optimal elements to pick would be?

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

      Yes ! sort the Length and pick at most $$$M$$$ songs such that the beauty of the selected songs greater than or equal to the minimum beauty i told. right ?

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

        Yes exactly, you would just pick the greatest $$$k$$$ lengths such that the beauty is greater than or equal to the minimum beauty.

        If you sort the songs according to beauty, then you can preprocess these $$$k$$$ lengths as juckter said below using a heap, and then iterate over all the possible minimum beauties and take the maximum answer.

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

          could you please explain this part of your code for problem E ...

          if(v[0] == back) {
                   dp[0][0] = 0;
                   dp[0][1] = 1;
                    } 
           else               {
                   dp[0][0] = 1;
                   dp[0][1] = 0;
                 }
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Sure. dp[i][0] is the number of constructions for the first i elements such that the i’th element is not the same as v.back, and dp[i][1] is the number such that it IS equal to v.back.

            That is the base case, so if the first element is equal to the last, dp[0][0] will be 0 and dp[0][1] will be 1, and vice versa if they are not equal.

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

      You can dynamically keep the sum of the k largest elements in the range you care about with a heap

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

    Store beauty and length in a vector of pairs. Sort by beauty in decreasing order. Now travel from index 0 to n-1. If index < k , then take sum of all lengths till index and multiply it by current beauty and keep max of the answer. Store the lengths in a min-heap or a priority queue with min on top. If index>=k then check where current length is greater than min length in heap or not. If it is greater than min length in heap, delete min from heap and add current length to heap and accordingly change the sum of k top lengths. Then take the required product and keep the max.

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

    sort according to beauty in descending order . Then use priority queue to keep track for k-1 largest length songs .

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

    Sort songs in decreasing beauty, and check for each of them what elements to pick such that length of k or less songs are biggest (and those elements have beauty greater or equal than picked song)

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

A is so poorly written I spent literally 20 minutes on figuring out what they want from me.. So I it was too late to compete.. Imho almost every educational has some type of really badly written tasks and that you can't understand anything (mostly D)..

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

    I actually thought D was probably one of the most nicely written problems in the set. Their definition of triangulation was a bit different than what I'm used to, but triangulation of a polygon is a very widely used thing that you should know.

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

      I said mostly D. I was pointing out on previous contests.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • A : 1hr
    • B: 1hr and 5 min. I need major Improvement. ;)
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    In my opinion, none of the problem statements were badly written, they presented exactly what they wanted to. The matter of fact is that if somebody finds it difficult to understand the task, he marks it as badly written. Believe me, not only is solving a task a skill that comes from practice but understanding a task quickly also comes from practice and experience. So don't blame the statements. Sometimes statements are just complex and not "badly written". Just because you are taking time to analyse them and sort everything out in your head, doesn't mean they are badly written.

»
7 months ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

Statement of B was confusing, will give more attention to statements in future contests.

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

    Exactly what I was doing the answer would be zero if (s[0]=='>'||s[n-1]=='<') otherwise 1

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

      Now that I saw solutions of other people, Let me explain. for this case :

      string : <<>> According to us, answer should be 1 but actually lets say when you delete second character, string becomes <>> then you have to delete first character too. Similary if you delete first charater, string becomes <>>, again you have to delete the first character, so answer must be 2 but according to us, it's 1.

      It's my mad during the contest. However I strongly feel that problem statement could have been much much better with proper test cases. I think the intent of statement was to confuse people to write wrong code. Contest should be unrated considering A & B.

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

    You can choose same character any number of times. But that doesn't imply the answer will either be 1 or 0.

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

      Yes, my bad. Sadly I get this after the contest. Will make more test cases in future. Thank you.

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

    don't trust how you understood the problem always read the Note that explain samples ... I did this mistake several times but now I will always read samples note

»
7 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Somehow I found A much harder than D.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    Maybe it's right.

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

    I found all problems harder than D, yeah. D < A < B ~ C

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

    Find solution for D: 1 minute

    Think why solution for D is so easy: 9 minutes

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

      Exactly.

      Well I used argument exchange, so I'll add 2 more steps.

      Find solution : 1 minute
      Prove solution : 1 minute
      Doubt your logic and problem reading skills: 7 minutes
      Code and submit : 2 minutes

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

In problem C I thought that I need to pick adjacent songs only... I was implementing logic similar to KMP and completely wasted 30 minutes lol

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

    weird how the examples show that's clearly not the case?

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

      That shows I was not careful enough

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

        well at least you got accepted, unlike me

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

          Don't compare yourself to other guys, you are just you. Have fun on studying algorithms

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

          Well Bro It is mid night now in East Asia, You are from Georgia Tech so by default I think you are in Atlanta USA, solving problems in mid night sometimes will be pain in ass cause your brain is not functioning well

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

            actually on Betelgeuse, there is no time here

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

    made the same mistake :(

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

F was very nice.

Is the solution:

My idea ??
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    The easiest way to maintain all components is to create a separate vertex for each x-coordinate and y-coordinate, and treat each point as an edge that connects its x-coordinate with its y-coordinate. Then the answer for each component is the product of the number of x-coordinates and the number of y-coordinates in that component.

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

      How do you erase?

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

        I think this is for incremental version. For dynamic version you have use the idea of dynamic connectivity combined with this.

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

        Just like teja349 has written, I get rid of erase operations by applying divide-and-conquer on time axis (just like in classic Dynamic Connectivity Offline problem).

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

Just for the sake of curiosity, can problem E be solved if we also ban palindromes of even length?

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

May I ask why I can see some guys hack them selves by some default inputs? How can this be helpful for them to hack themselves?

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

If I look for something good in this competition, perhaps that will be that the test case wasn't weak.

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

Problem E?!!!

I think I understood it incorrectly, can someone please explain it here, It has poor statements.

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

    I think it's the way to fill all -1 in the array so that there isnt any value of i such that a[i] = a[i+2]

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

    We have to calculate the total number of ways to assign values (in range[1, k]) to the -1's in the array, such that no palindrome of odd length is present in the resulting array.

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

    Ok thanks

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

Can't deduce the Problem B logic Correctly!! Doesn't the problem statement means that every string we have, after some number of operations will either become "<>" or "><"? So the number of removal will either be 1(in case "<>") or 0(for this case"><").

This was the logic I applied. But it seems like I'm missing something. I built this logic because there is no limit to number of operations that i can apply on any given string. So why is this logic wrong? LINK TO MY SUBMISSION Please help!!

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

    We have to remove first, then apply operations

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

    If the original string is like "<<>>", then although remove the most out "<" (or ">"), there is another inner "<>". so the correct answer is 2, not 1.

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

      I get this now. After complete period of 2 hours. Thanks Buddy!! Poorly Written Question played with my ratings :(

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

        What do you mean "Poorly written question"?! It literally says Before applying the operations in BOLD in the problem text. It couldn't be more clear than that.

        It triggers me to no end when people don't read the statement carefully and then they say it's unclear. It's not unclear, you just didn't read it properly.

        (╯ರ ~ ರ)╯︵ ┻━┻

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

          it wasn't unclear. i analyzed it poorly. gonna read statements more carefully. ಥ╭╮ಥ

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

    you need to check bold statement in the problem.

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

      Exactly, it helped me to sort out my confusion. Thanks to the author :)

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

I know we all solved D by some trial and error, guessing, etc... then how can we prove the solution? Any proof?

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

    The edge i..(i+1) is a side of the triangle, in any triangulation. I.e: it would always be an edge. So the best way to connect it to 1 as the third node, and therefore create the minimum possible value.

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

      This assumes separate edges are in separate triangles which need not be the case.

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

    The key idea is that vertices $$$i$$$ and $$$i+1$$$ will always share a triangle.

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

    You are going to have to use all edges in the outer polygon in a triangulation, and for each edge you have to choose one additional label, and using 1 works. So the answer is simply

    $$$ \sum_{i=2}^{n-1} i (i+1) $$$
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      I don't think this proof is correct. This assumes all edges are part of separate triangles. But if there is a triangle with vertices $$$i$$$, $$$i+1$$$ and $$$i+2$$$, then two consecutive edges are accounted for in the same triangle.

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

        That's true, some of the outer edges can be used together. The triangulation I'm saying is optimal is $$$(1,2,3), (1,3,4), (1,4,5), ..., (1,n-1,n)$$$. While intuitive that this is optimal, what I wrote was not a correct argument.

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

    Actually not all solved it by trial and error. I proved it during contest time :)

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

    My guesses was, each edge will hide one vertex, so I will hide the biggest one firstly, then the second biggest one, and so on, so they will appear at most two times.

    But still the above comments are the proof, IMO.

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

    Actually I tried all possible states xD 51705295

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

    it seems i have proved this solution. Suppose there isn't any diagonal from 1 in optimal triangulation. Then we can move this triangulation in clockwise and decrease the cost. So there is some diagonal from 1 to i. Let's consider triangulation of "1 to i" polygon. If there isn't any diagonal from 1 we can do how described above and so on. So, to minimaze the triangulation cost it needs that all diagonals starts in 1.

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

    This comes in somewhat late, but I haven't seen a full proof in the comments yet.

    Let the value of a segment be the product of its endpoint. Then clearly the value of a triange is greater than or equal to the value of any of its sides. Moreover, unless one of the vertices is $$$1$$$, the value of the triangle is greater than or equal to the sum of any two sides. This is because $$$abc - ab - ac$$$ factors as $$$a((b - 1)(c - 1) - 1)$$$ which is non-negative unless $$$b$$$ or $$$c$$$ is $$$1$$$.

    Now note that every side of the polygon belongs to a triangle in the triangulation. If this triangle contains no other side then its value is at least the value of that side. If it does contain another side then the value of the triangle is greater than or equal to the sum of these two sides, unless one of the vertices is $$$1$$$. By adding up it follows that the sum of the values of all the triangles is at least the sum of the values of the sides, except for the two sides that include vertex $$$1$$$ (because they may be included in a triangle that has another side of the polygon).

    Triangulation $$$(1, 2, 3), (1, 3, 4), (1, 4, 5), \dots, (1, n - 1, n)$$$ gives exactly that sum of values, so that's our answer. Also note that the exact labels on the vertices don't matter, all that is needed is that exactly one label is equal to $$$1$$$.

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

banning mkisic_ from point buff

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

I couldn't find a reason why problems D had so many AC's. None the less I found that this was a direct answer to the problem. Actually, Problem D was easier than the problem here, but just a bit of modification to the code would do the logic.

Maybe this is the way, Problem D was supposed to be solved, using that DP approach with O(n^3).

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

    That's not really true. We just greatly underestimated contestants. Personally, I thought that majority will stuck in some sort of dp, so after some discussion we decided to leave a place to a straightforward solution. In the end community surprised me in the good way.

    PS: linear is not a limit: OEIS/interpolation gives us closed formula and $$$O(1)$$$ solution.

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

      Codeforces Community is Strong. It was a nice contest by the way. Thanks

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

      It’s unfortunate because I would’ve been stuck in a DP type solution if I wasn’t thrown off by the fact that many people were solving it within s few minutes, so I realized it must be some type of greedy solution. If it was a contest with a frozen scoreboard I think a lot fewer people would have solved it.

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

    Actually you can solve problem D in O(1) time complexity.

    Let S = 2 * 3 + 3 * 4 + ... + (n-1) * n

    3S = 2 * 3 * (4-1) + 3 * 4 * (5-2) + ... + (n-1) * n * (n+1-(n-2))

    3S = 2 * 3 * 4-1 * 2 * 3 + 3 * 4 * 5-2 * 3 * 4 + ... + (n-1) * n * (n + 1)-(n-2) * (n-1) * n

    3S = (n-1) * n * (n + 1)-6

    S = ((n-1) * n * (n + 1)-6) / 3

    P/s: I don't know how to use Latex :( So the signs and numbers may be ugly

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

      I agree, It was trivial. I proved this after the contest was over. Always triangulating from vertex 1, works.

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

Can someone explain how to solve C and the reason behind it?

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

    Okay, the main intuition behind the answer can be said that, if the beauty is fixed, then you can easily find the answer, by taking the sum of all the largest k songs (sorted by length). Using this intuition, we iterate over through all the different beauties present in the array and dynamically maintain the sum of largest k elements, using a priority queue, and updating the sum while traversing. Here is the link to my code — https://codeforces.com/contest/1140/submission/51714832

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

Hello, Div.2, my old friend

I've come to solve your tasks again...

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

Can we solve C using DP by iterating on k?

If we can't use DP , can you explain why not?

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

    Probably not since you would have (3*10^5)^2 states

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

can anyone explain why the output of <>><<< is '0' ? i don't know how to solve this question whats the logic. maybe i misunderstood the problem please explain anyone

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

    For this problem you can always choose the last item to operate on:

    After 1 operation: <>><< After 2 operations: <>>< After 3 operations: <>< After 4 operations: << After 5 operations: < Done.

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

    The rightmost < will delete all the values to its left. Hence No need to remove anything and answer is 0

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

      then when will be the answer non zero in which case? so according to you we will always get 0 or 1. but more the 1 values are also there in the output . please explain!!

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

        The answer will be zero if string_var[0] == '>' or string_var[n-1] == '<' else answer will be

        min( after_how_much_chars_from_start_appears('>'), after_how_many_chars_from_end_appears('<'))

        Like for <<<<>>> Answer will be 3, Read the problem statement again and READ what is in BOLD

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

check this 0ahmad0makki0 is fake account of dotorya. Same solution and also same template.

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

    this is also pointed out above, but for some strange reason all the comments are heavily downvotes.

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

    It's not my account, and I think that my account was hacked. (Password leak or something) Now I changed my password, and hope it won't happen again.

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

    I can't believe people are upvoting this. Why would dotorya make a fake account and then compete with both of them in the same contest submitting same solutions? I don't think a legendary grandmaster would be that stupid. It must be a hacker's account, should be banned soon.

»
7 months ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve G?

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

I thought the answer could be only "1" or "0",and it took me a while to understand the meaning of Before applying the operations in problem B. ;P

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

Any hint for G?

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

    Let's divide all edges into two types: edges of the first type connect vertices having different remainders modulo $$$2$$$, and edges of the second type connect vertices having same remainders.

    First of all, let's solve an easier version of the problem: we have to minimize the number of edges of the second type in our path, and minimizing the length of the path has lower priority. Then we can build one tree where each vertex is a union of vertices $$$2x + 1$$$ and $$$2x + 2$$$ in the original graph, and use something like binary lifting or centroid decomposition on this tree. For example, if applying binary lifting, we may maintain an array $$$up[N][LOGN][2][2]$$$, where $$$up[v][k][f1][f2]$$$ is the length of the shortest path that starts in vertex $$$2v + f1$$$ of the original graph, goes $$$2^k$$$ steps up the tree, and ends in the vertex having remainder $$$f2$$$ modulo $$$2$$$ in the original graph.

    Okay, but we can't use this approach in the problem from the contest, because sometimes it is better to traverse some additional edges of the second type, so we may choose cheaper edges of the first type. To handle this, let's preprocess all edges of the second type in such a way that cost of each such edge will be equal to the shortest path between its endpoints. This can be done with a Dijkstra-like algorithm.

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

      Thanks for the solution!

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

      How can we made this part "To handle this, let's preprocess all edges of the second type in such a way that cost of each such edge will be equal to the shortest path between its endpoints. This can be done with a Dijkstra-like algorithm." ?

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

        Let's create a graph with $$$n + 1$$$ vertices. $$$i$$$-th vertex will represent an edge between vertices $$$2i - 1$$$ and $$$2i$$$, and in the end, we want the distance from vertex $$$0$$$ to vertex $$$i$$$ be equal to the length of the shortest path between $$$2i - 1$$$ and $$$2i$$$.

        How can we find the shortest path between $$$2i - 1$$$ and $$$2i$$$? We either pick the edge between them, or go to some other neighbor of $$$2i - 1$$$ (let it be $$$2j - 1$$$), take the shortest path between $$$2j - 1$$$ and $$$2j$$$, and take the edge from $$$2j$$$ to $$$2i$$$.

        So, we need to create the following edges in our graph: $$$n$$$ edges going from $$$0$$$ to $$$i$$$ and having weight equal to $$$w_{2i - 1, 2i}$$$ in the original graph, and for every pair of odd neighbors $$$2i - 1$$$ and $$$2j - 1$$$ an edge going from $$$i$$$ to $$$j$$$ and having weight $$$w_{2i - 1, 2j - 1} + w_{2i, 2j}$$$.

        All that's left is to run Dijkstra from vertex $$$0$$$ in this graph, and that's how we get preprocessed weights.

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

if The CF-Predictor broken ? ( Chrome Browser)

=> Use this Website

=> About the Issue

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Second problem ruined the whole contest for me. The problem statement must be properly written.

»
7 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Please update ratings :3

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

What's the approach for F?

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

    I have the following observation but I didn't solved it.

    Consider vertex $$$(x, y)$$$ as an edge connecting $$$a_x$$$ and $$$b_y$$$. Then the answer is the sum of (number of $$$a_i$$$ $$$\times$$$ number of $$$b_j$$$) in each connected component. If we can maintain the connectivity supporting deletion efficiently, the original problem can be solved.

    Edit: I upsolved it by doing divide-and-conquer on time axis. Distribute the lifetime of each vertex to $$$\text{O}(\log n)$$$ time intervals. Then traverse the segment-tree-like structure with disjoint set union operations and restore operations.

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

      Can you give more explanations? It's hard for me to understand your code))

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 6   Vote: I like it +20 Vote: I do not like it

        Firstly, suppose a vertex exists during $$$[2, 9]$$$. Then you can split the interval similarly to range query in segment tree, i.e. $$$[2, 9] \rightarrow [2, 3] + [4, 7] + [8, 9]$$$ (it may vary due to different implenmentations of segment tree/divide-and-conquer).

        Call the following function recursively.

        f(left, right):
          Add vertices with interval [left, right] and record every changes
          if left = right
            Output the current answer
          else
            mid := (left + right) / 2
            f(left, mid)
            f(mid + 1, right)
          Undo the stored changes
        

        It is easy to see that:

        1. each answer is printed in correct order

        2. all vertices have the correct state (existing or not) when each answer is printed

        3. there are almost $$$\text{O}(n \log n)$$$ operations of adding vertices

        4. consequently, there are almost $$$\text{O}(n \log n)$$$ undo operations

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

          It's amazing. I have understood the algorithm and the code!))

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

please update the ratings.

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

Can someone explain their approach in solving C, I dont know why I got hold of a very wrong track in solving it, and finally it became a mess.

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

    Let $$$x = [(\text{beauty}_{k_{1}}, \text{length}_{k_{1}}), (\text{beauty}_{k_{2}}, \text{length}_{k_{2}}), ...]$$$ This array is sorted by beauty.

    Then if you pick $$$(\text{beauty}_{k_{i}}, \text{length}_{k_{i}})$$$ as minimum beautiful song, then you must pick up to $$$k-1$$$ songs from $$$[x_{i+1}, x_{i+2}, ..., x_{n}]$$$. You can use std::multiset or something to pick $$$k-1$$$ most longest songs.

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

    When selecting a song, the total length and minimum beauty matters. So let's sort the songs by decreasing beauty, and process them like that. To make sure we have maximum length, we keep a multiset of the k-1 longest songs processed so far. Let's process song i. We do ans = max(ans, max_total_length*beauty[i]. If the multiset has size less than k-1, add this song's length to it and increase max_total_length. Otherwise, if this song's length is greater than the shortest length in the multiset, remove that length, subtract it from max_total_length, and add the current like previously.

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

      I have a doubt , why don't we take k longest processed so far and do the all think you explained?

»
7 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Please update the rating.

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

Please update the rating.

»
7 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Please update the rating!

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

PLEASE UPDATE THE RATINGS !!!

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

Have refeshed my page hundreds of times.

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

Why not charge in the rating?

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

It is really disappointing that some 2100+ rated players make fake accounts before the contest in order to participate officially. For example take a look at this account: bigbigbigbigcat111 This account was made just before the contest and ranked 30. I think this account was made by bigbigbigcat111 who is unable to participate officially because his rating is above 2100. Making fake accounts and stealing rating from other participants is unacceptable. Please remove him from the list of official participants. Upd: I noticed that he has account: bigbigcat111 and bigcat111 as well. All accounts are from China and they have similar rating.

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

Please do not refresh the ratings... I'm sad enough...

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

...Why hasn't it been rated yet?I've been waiting for a long time.Just be a little faster,OK?Thanks!

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

    Probably there's alot of cheaters in this round that's why the system hasn't started testing.

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

When will the editorial come out?

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

    Probably after the System Testing gets completed I guess

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

What about the System Testing, when it's going to start?

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

Why is system testing is so late?

»
7 months ago, # |
  Vote: I like it -6 Vote: I do not like it

System Testing ended.

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

problem c was very nice,thanks for the problem author!!!

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

When the editorial will be published?

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

Hello!Can anybody expalin why my sol for problem C fails?Seems like it must work.Thanks! https://codeforces.com/contest/1140/submission/51763978

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    • If you use tmp.erase(x), it will remove all the elements with value "x" from the multiset.

    • You have to remove this "if", because of the following case:

    			if (ans[ans.size() - 1] < ans[ans.size() - 2]) {
    					tmp.erase(l[i].second);
    					tmp.insert(a);
    					mus += a;
    					mus -= l[i].second;
    				}
    

    Case:

    4 2
    7000 5
    1 5
    8000 2
    70000 1
    

    https://codeforces.com/contest/1140/submission/51766475

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

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

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

How can we solve D? I think I should solve prefix sum... T^T I will do not go to sleep when I solve D before!!