Блог пользователя Snezhok

Автор Snezhok, 7 лет назад, По-русски

Всем привет!

Поздравляю площадку Codeforces с Юбилейным 450-ым раундом!

Мы рады сообщить, что 11 декабря в 19:05 MSK состоится рейтинговый Codeforces Round #450 для участников из второго дивизиона. Традиционно, приглашаем принять участие в раунде участников первого дивизиона вне конкурса. Надеюсь более сильные участники также найдут для себя интересные задачи:)

Задачи подготовили я и Никита slelaron Костливцев. Хочется выразить благодарность координатору раунда Николаю KAN Калинину за помощь в подготовке контеста, mike_live, Arpa и Livace за тестирование задач и, конечно, Михаилу MikeMirzayanov Мирзаянову за отличные платформы Codeforces и Polygon.

На раунде, как обычно, будет пять задач и два часа на их решение.

Разбалловка стандартная: 500 — 1000 — 1500 — 2000 — 2500.

Желаю всем получить удовольствие от контеста, высокого рейтинга и удачи!

UPD: Соревнование завершилось! Надеюсь раунд вам понравился:)

UPD: Разбор. Задача Е будет скоро добавлена.

UPD: Задача Е добавлена.

Поздравляем победителей!!!

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

  • Проголосовать: нравится
  • +269
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Jubilee for codeforces, the first for me)

Good luck :D

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

is it semi-rated ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +72 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Five contest in ten day

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +91 Проголосовать: не нравится

5 contests in 9 days Indians be like:

![ ](Image and video hosting by TinyPic)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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"

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Wish all the participants high rating! )

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Deleted

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope you make progress and show yourselves!

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Кто дизлайкнет — тот Панин.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

5 Contests in Week And I have Exams :(

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

5 Contests in Week , And I Have Exams :(

»
7 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

May God bless the servers !

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -42 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Trying to get upvotes lol -7 contribution xD

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится -32 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          maybe after writing this she became my girlfriend lol

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится -28 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              [deleted]

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              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!

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится -13 Проголосовать: не нравится

                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.

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

KAN+Anniversary=Kanniversary

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +30 Проголосовать: не нравится

Just In case what we all expect happens =)

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Hello darkness my old friend..

»
7 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

What the... video

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is test 3 in C?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hint for D?

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Really cool problemset. Hope more like it are coming!

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Exactly what Alei said.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 }

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Time complexity of your solution?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the idea behind B & C ? :(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

Good job :)

»
7 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Can anyone explain how to solve problem C?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

thanks for very short conditions))

»
7 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

This was the best codeforces contest so far.

»
7 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится

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

    Please tell me it is joke.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        you can see standing on this round

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E can be solved with FFT?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

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

      we need FFT when t is arbitrary string

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

system testing too slow :(

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice problems! Thanks!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

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????????????

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve C?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I implemented a solution which is n log n

    My solution
»
7 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

i became purple for the 8th time

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Hi!

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

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

It really surprised me that it got Accepted.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem C?

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Уже в который раз я не получаю AC из-за своих "выдуманных" ограничений...  Стоило сменить на чуть больше — AC