When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Snezhok's blog

By Snezhok, 6 years ago, translation, In English

Hello everybody!

Congratulations to the platform Codeforces with an Anniversary 450th round!

We are glad to report that Codeforces Round #450 (Div.2) takes place on December 11 19:05 MSK. The round will be rated for Div.2 participants. Traditionally, we invite Div.1 participants to join out of competition. I hope stronger participants also will find interesting problems for themselves:)

The problems are created by me and Nikita slelaron Kostlivcev. We want to show our great appreciation to Nikolay KAN Kalinin for round coordination, mike_live and Arpa for testing the problems and of course Mike MikeMirzayanov Mirzayanov for great platforms Codeforces and Polygon.

You will have 5 problems to solve in 2 hours.

Scoring as usual: 500 — 1000 — 1500 — 2000 — 2500.

Good luck to all and enjoy the problems!

UPD: Contest is finished! I hope you enjoyed the round:)

UPD: Editorial. The problem E will be posted soon.

UPD: The problem E was posted.

Congratulations to the winners!!!

Div 1

  1. KrK

  2. zscc

  3. wwwwodddd

  4. uwi

  5. oversolver

  6. Shayan

  7. dreamoon_love_AA

  8. please_delete_account

  9. alexrcoleman

  10. guille

Div 2

  1. zeronumber

  2. Brightness

  3. UBICA

  4. Lyon_71

  5. mmkh

  6. I_Love_Adriana_Chechik

  7. Ant_Man

  8. yuvalsalant

  9. Natsume_Mio

  10. PuriceLoh420

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Jubilee for codeforces, the first for me)

Good luck :D

»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

5 div2 contests and 1 div1 in 9 days? already best december gift

»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

is it semi-rated ?

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

    Actually that's interesting point. You can generalize it a little bit. I saw previously some comments whether it would be 0,25 rated, 0,1123 rated, etc. I would go even further. For example it could be 2 rated, which means that rating change would be doubled. It could even be -1 rated, which means the better you do, the worse rating gain.

    It could be an x rated round with x being a real number. We could also count the expected value of rating ratio. I think currently it might be something around 0,75-0,8 rated round.

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

      What if we add complex numbers too, so a contest can be z-rated. Therefore we’ll need to add another dimension to the rating graph.

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

      Is there exists a real number such that it is x-rated?

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

      And the fun part begins when participants can choose the value of x before the round. So its like a gamble you take before seeing the problem. Could be a fun little thing to do in codeforces.

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

      The setter must have seen all these values in the comments and hence comes div2 B.

»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

he did not say "the scoring will be announced shortly before the start of the contest." This is a miracle xD

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

Five contest in ten day

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

Typical Div 1 users: "I will just create a new account participate with it. So I can ruin other Div2 users."

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

    Why would we do that? My skills have regressed so much that I can't even clear a div2 round ... (*sobbs in a corner)

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

5 contests in 9 days Indians be like:

![ ](Image and video hosting by TinyPic)

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

    Google translate has left me even more confused

    "Bro if someone will choke me and chill, lots of fun will do the code for fores"

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

      It means that if someone will tell me to chill and have fun then I will do Codeforces Rounds!

»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Been looking at red username for so long I thought Anniversary was a person

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

Deleted

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

Hope you make progress and show yourselves!

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For God's shake resolve servers' issues before the contest!

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

3 rated contests in a week, week of the FINAL EXAMS for God's sake...

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

    Meanwhile in China we have the ICPC East Continent Final in the upcoming weekned, failing final exams here I coooommmmmeeeeee

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

It's to late for Chinese coders. I can only participate the next one. 555

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

Why the frequency of div1 contests so low? We want more div1 contests.

»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

May God bless the servers !

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

    May God bless you too !! Hope so you will not become newbie as you seem again. I would suggest work on the problems rather than just complaining. Also in case of server doesn't work well it will anyway don't affect your performance because you are still not capable of solving even C problem in any contest :D

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

      Trying to get upvotes lol -7 contribution xD

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

        I said the truth. Why are you defending her? Is she is your sister or girlfriend? I wrote the truth because I usually got annoyed when someone who is not at all good in cp and just keeps on complaining about Codeforces which I personally feel is the best competitive programming site in the world.

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

          maybe after writing this she became my girlfriend lol

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

          Servers affect everyone, sometimes people will end up being higher than they would have if there was no server issue, and sometimes they will end up lower. Whether or not you are good does not change the randomness that affects you with server issues. You can be "bad" and still place lower than you should have.

          Moral of the story: Codeforces is a good competitive programming site but you're a douche.

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

            I m sorry if the truth hurts you as well !! Isn't better instead of finding mistakes like pragya_123 stupid girl is doing we should suggest how to improve the Codeforces and make mike and other Codeforces team motivated so that more learning can take place.

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

              [deleted]

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

              Nothing is perfect in this world! Yes, I'm not able to solve C problem. But, it was my general comment for all the coders who suffers sometimes due to slow server! If I'm trying to improve myself, so should codeforces too so that everyone can perform efficiently during contest!

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

                Ohh really you are trying to improve yourself but i m sorry your graph shows the opposite. After 14 months you are a pupil and you say you are improving :( Anyways don't you get you are not made for competitive programming after so many failures you have? Rather you should try modelling or reporting who keeps on complaining.

»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

KAN+Anniversary=Kanniversary

»
6 years ago, # |
Rev. 3   Vote: I like it +30 Vote: I do not like it

Just In case what we all expect happens =)

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hello darkness my old friend..

»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I dedicate my success in today's round to my two senpais: FLEA and babin! Btw I hope babin didn't cheat today!

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

What the... video

»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

There is one thing i have to say: You guys have made the BEST round ever! Your statements are the BEST!

»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

OMG D is so easy!! I wish I didn't waste my time attempting to hack. :(

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

    Okay, maybe not as easy as I thought. we can't just do "distribute k sweets among i students" because we also need to make sure gcd doesn't become some multiple of x.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is test 3 in C?

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

write brute force find sequence google it find sequence on OEIS with formulae == DIV2 D

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

Is the answer to question D-Unusual Sequences simply 2^(floor(y/x)-1)-1??

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

Really cool problemset. Hope more like it are coming!

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

How to do D? Got it down to finding all sequences of numbers that sum to y/x with gcd 1.

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

    Yeah, even I got it that far then I didn't know how to proceed

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

    DIV2 D https://ideone.com/PvYJio This is the link to my DP code. Just got 1 minute late in the contest.The DP code itself is self-explanatory.

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

      I'm not sure I understand lines 105 to 115. How do I show that the number of sequences summing to x with gcd != 1 is the sum of solve(i) for each divisor i of x?

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

        Exactly what Alei said.

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

        For finding number of sequences summing to x with gcd != 1: You can substract sum of solve(i) { Sum of number of sequences summing to x with gcd = n/i where i is a divisor of x } from power(2,x-1) { Total number of sequences summing to x }

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

      Time complexity of your solution?

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

    Inclusion-exclusion:

    1. add the number of ways when the numbers are multiple of g.

    2. remove the ways when the numbers are multiple of g multiplied by a prime

    3. add the ways when the numbers are multiple of g multiplied by two distinct primes

    4. ... and so on

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

What is the idea behind B & C ? :(

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

    B: Java BigDecimal with "a lot" of extra decimal places, then just string.indexOf(c). That pass the system pretests.

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

    For B, you could actually code it like you'd do long division in real life. Store the digits of the quotient in a vector. Whenever an intermediate dividend is attained twice, break the loop, possibly using a set. Then just check if c exists in the vector. If it does, just print the position(1-indexed) and if it doesn't print -1.

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

    For C maintain a map/dictionary/hashset with int, bool with values for if the number is a record before removing any number. Then take max(p[0], p[1) as maxsofar and the other as secondmax. Now iterate through all numbers. If they are bigger than the secondmax then that means you only need to remove the maxsofar element to make that element a record. Store the frequencies of what number must be removed in a map. Then just check the max value of frequency and in case of a clash, the minimum of the two. You'll also need to subtract one of the frequency for a particular element if it was previously a record because in removing that number you'll also reducing a pre-existing record.

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

The problems and the statements were excellent. Although to me E seemed a bit easier than usual.

Good job :)

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

You can find D here https://oeis.org/A000740 Is it okay?

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

Can anyone explain how to solve problem C?

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

    sorry my poor englishh, you can compute current records, if i'th element less than only one element on previous all elements, you can push vector <pair<int, int>> these elements, first is p[i], second is only one element that (p[i] < p[j] && j < i) p[j], if i'th element equal this vector's second element current_ans + number of vector's elements (v[i].second == p[i]) then, if i'th element also record element current_ans — 1, you can finish this problem.

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

    A somewhat different(maybe) approach:

    For each element find number of elements less than it and before it in the permutation. Get all elements such that there is exactly one element before it that violates the condition of this element being a record. Say we store them in c Now for each element find all elements greater than it c. Observe that we can get number of records in O(1) for each element being dropped.

    Note: All of the above computation can be easily done by a merge sort tree

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

thanks for very short conditions))

»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

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

This was the best codeforces contest so far.

»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

In my opinion problem B,C,D,E were from almost same difficulty level. So the order one attempts the problems matters a lot in the standings. This is certainly not good for the contest.

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

    In my opinion problem B,C,D,E were from almost same difficulty level.

    Please tell me it is joke.

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

      When did you reach on problem C , I mean what was the time ?

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

        What do you mean? B was easy problem, but I stuck on it, so I read C and googled solution of B (fortunately, found). C was quite standard problem, it was easy to get idea fast.

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

          What's the point of googling the answers though

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

        you can see standing on this round

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

    if you tell me about it during contest, i would solve D, E.

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

Problem E can be solved with FFT?

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

    yes with fft we can find from what all positions there is a possibility of t being there. the idea is for finding at pos i we need ((s[i+j]-t[j])^2)*(s[i+j]) summation over j from 0 to m-1 to be equal to zero assuming value for character '?' to be zero and rest some positive value. This we can find for all i using convolutions(which can be solved by fft).

    NOTE: We are not using any special knowledge about t here.

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

      E can be solved without FFT, bcs of t="abababa..."

      we need FFT when t is arbitrary string

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

    Yes, the idea was finding the number of wildcard matching in strings, which can easily be solved using FFT. I was trying the same, fell short of time. After this was a simple DP solution.

    For fft, technique try to find the following sum, . The places, it is 0 are the places where the string T can match string S, from position i. Expand the expression, which is simply prefix sums and one convulution using FFT. Using FFT in this problem, we can do it for general strings as DP is independent of it.

    This is actually what is explained in above comments too.

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

    http://codeforces.com/blog/entry/49613?#comment-335977 this can be used to solve it for any pattern (not limited to "ababababa...")

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

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

    Nice background for coding :P

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

In problem D, I forgot that the answer is 1 but no 0 when x=y...sad story:(

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

    is that corner case?, if yes too sad

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

      My friend and I always wrong answer on test 3... And when x=y our answers are same to 0 :(

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

      it is not corner case.

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

system testing too slow :(

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

How many iterations do we need to prove our "-1" answer in B? I did 1e5, it passed final testing, but I saw div. 1 users did more, just for precautions?

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

    I couldn't find any answer greater than 50. You can prove a bound O(B) using the pidgeonhole principle on the number of steps until finding a cycle.

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

Nice problems! Thanks!

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

nice problems, can't wait the editorial. short statements <3 ++respect

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

Update: I'm sorry for such a comment. I understood.

LOL problem setter,poor test case on problem "B"-div-2.

if input is 22 4 5

answer should be 1.

but I have found -1 from many accpeted code.

How how how????????????

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

    And why should the answer be 1 and not -1 can you please explain?

    4/22 is a repeating fraction and 5 never comes in the sequence. Please have a look once before posting

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

    Ummm.. Answer is definitely -1

    4/22 = 0.(18)

    5 cannot be found.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

tests of problem C were weak some incorrect solutions passed system tests. For example simple test 2 2 1

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve C?

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

    You basically keep current maximum and second maximum on the array as you iterate. Removing maximum element will add record if(a[i] > maximum2 && a[i] < maximum). The rest is easy from here.

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

      Could you please clarify a bit more. I had thought something like this during the contest but my doubt is this.

      Suppose we have 1 2 5 4 3 Now when a[i]=4 we have a[i]<maximum and a[i]>maximum2 so removing this should add a record. Well it does make 4 a record but how is the number of records maximized? In 1 2 5 4 3 we have two records 2,5 and in 1 2 4 3 we still have 2 records. So the number isn't really maximised is it? And since the question says that we need print the smallest number which maximises the total (which we cant in this question) shouldn't we print 3 as its the smallest but the number of records are still 2?

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

        In my opinion, I think it should print 3……emmm...what is Judy's answer?

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

        Thats why I said in my comment, you have cnt array which tells change, and you set cnt[i] to -1 if i is initialy record (not index i, but value i of course). So here you would have cnt[5] = -1. Later , cnt[5] gets increased only once, because only 4 will become record, so cnt[5] =0. Since cnt[1] = 0, solution will be 1, not 3 or 5 as you said. So we dont look who makes most new records, we only look for change in records. Thats why answer will not be 5, but 1, since cnt[1] = 0 ( it is 0 because 1 is not initial record, we only set cnt[i] to -1 if it is initial record). Hope this helped.

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

    I implemented a solution which is n log n

    My solution
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

i became purple for the 8th time

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

9 9 5 8 6 3 2 4 1 7

for the given case how the answer be 9?

here if we remove 1 then the permutation will be 9 5 8 6 3 2 4 7 and we get the maximum record which is 3 (2, 4, 7) isn't it?. then shouldn't the answer 1?

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

    No, if we remove 1 the record numbers are (9) and removing 9 they are (5,8)

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

      that's mean the record always starts with the 1st element?

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

        there is no "record" to keep, being a record number is a property defined in the problem statement, read it again

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

For problem C, the pretest 3 is:

5

4 3 5 1 2

Accepted output is: 1

My program gave output: 3

I didn't understand why the output is 1. Probably I have misunderstood the problem.

For this input, I thought that if 3 removed then there would be 2 records: 4 and 5 ( because after removal of 3 the sequence would be- 4 5 1 2, the increasing sequence is 4 5 and then 1 is less than 5,so sequence breaks here)

But if 1 would be removed then there would be only one record: 4 ( because 3 is greater than 4, so the increasing sequence would break here)

Where I had misunderstood? Thanks in advance.

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

    The sequence will be 4 3 5 2 .. 4 (larger than 3) and 5(larger than 3 and 4) are records.

    since 1 < 3 then the answer will be 1

    The problem isn't asking for the longest increasing subsequence, it's asking for the number of indices such that a[i] is larger than a[j] for all 1 <=j < i

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

      How 4 is a record? def says 1<=j<i?

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

        The first number in the sequence is always a record since it's already larger than all the previous numbers(in this case none).

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hi!

In problem D, I found a correct solution that should be TLE.

If I run the code in this accepted submission: http://codeforces.com/contest/900/submission/33138278 , against case "1 999999527", it lasts like 15 seconds.

It really surprised me that it got Accepted.

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

Why the answer is 1 in prob. C,why not 4? 5 4 3 5 1 2

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

    Something is wrong with the input. The numbers are permutation of the first n numbers.

    Also in the question it was mentioned that we need to print the smallest of all the elements which when removing gives us the maximum number of records

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

      The input is

      5
      4 3 5 1 2
      

      The Prob.C says that "a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai." And if I delete number 1 , then it is "4 3 5 2", only a1...a1 is ok But if I delete number 4 , then it is "3 5 1 2",the a1...a2 is ok? If I misunderstand the meaning , please tell me ,thank you

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

        The way i've interpreted the problem, which I'm not entirely sure is correct is something like this.

        When we have 4 3 5 1 2 there is only 1 record 5 as for only this i we have a[j]<a[i] for all 1<=j<i.

        If we remove 4 then we'll have 3 5 1 2 now too the number of records will be one because 5 is the only record. In fact if we remove any number other than 5 then the number of records would be one. As we need to remove the smallest number for which the number of records are maximised (which is one in this case) we remove 1.

        I'm not entirely sure but this is what I think the question means. Although I've got a doubt against this too. Over here. Maybe you can help if you understand my doubt? Cause I myself am not sure if i've correctly understood the question.

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

          Oh, thank you. Let me see your doubt...

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

      Oh, I see ,does it mean that the a1...ak don't have to be consecutive? For example , as "4 3 5 2" I can choose a1,a3 to be a record?

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

What category of question does problem E, fall into? Can someone suggest similar problems.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Wow..That's my first time solved all problems in div2,Thanks for writers!

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

How to solve problem C?