Snezhok's blog

By Snezhok, 9 months 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. Bugman

  6. Shayan_Jahan

  7. dreamoon

  8. yosei-san

  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. PuriceLoh

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

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

Jubilee for codeforces, the first for me)

Good luck :D

»
9 months 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

»
9 months ago, # |
  Vote: I like it +42 Vote: I do not like it

is it semi-rated ?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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.

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

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

          And now there are even more possibilities by adding the "Educational" prefix to the previous ones.

    • »
      »
      »
      9 months 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?

    • »
      »
      »
      9 months 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.

    • »
      »
      »
      9 months 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.

»
9 months 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

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

Five contest in ten day

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

Guys, knowledge that cins/couts are very slow on big inputs/outputs is important on contests, and in this task this was one of the problems

»
9 months 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."

  • »
    »
    9 months 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)

»
9 months 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)

  • »
    »
    9 months 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"

    • »
      »
      »
      9 months 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!

»
9 months 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

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

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

Deleted

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

Hope you make progress and show yourselves!

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

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

»
9 months 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...

  • »
    »
    9 months 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

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

Before the contest : The contest is rated.

During the contest : we are sorry for the long queue.

After the contest : The contest is going to be unrated because of technical issues.

short sad story

»
9 months 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

»
9 months 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.

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

    Because div2 users> div1 users.

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

    it is hard to create hard div1D-div1F problems so just relax

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

    More difficult to think up div1 questions presumably

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

gud luck to all :>

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

May God bless the servers !

  • »
    »
    9 months 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

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

      Trying to get upvotes lol -7 contribution xD

      • »
        »
        »
        »
        9 months 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.

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

          maybe after writing this she became my girlfriend lol

        • »
          »
          »
          »
          »
          9 months 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.

          • »
            »
            »
            »
            »
            »
            9 months 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 pragyarustagi 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.

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

              I think the criticism is necessary for bringing improvement, so be cool!!

            • »
              »
              »
              »
              »
              »
              »
              9 months 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!

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months 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.

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

                  Lets not pass personal comments

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

                  It seems she hired you as an advocate because she doesn't have her own mouth.How much she paid you btw? I pay her more when se comes to my house :D

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

                  Maybe you are not worth replying. So, peace off from my side, too.

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

                  First learn how to write in english peace off My God you are seriously a illterate person. FYI its piss off not peace off.

                  I can't able to control my laughter ROFL.

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

                  1 pupil defending another pupil really fascinating to watch!!

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

                  You are hilarious. Yes, piss off can be used for you, as you suggested. But here's what peace off means : https://www.urbandictionary.com/define.php?term=Peace%20off

                  See, you just proved how literate you are :)

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

                  Seriously, man. Peace out. I've got much important work to do.

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

                  Yes i completely forgot that you have to clean my shit...so sorry carry on. Also clean the bathrooms as well.

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

    First, have a look at your last 6 contest performance just 1 problem solved? Still, will you blame the Codeforces server?

»
9 months ago, # |
  Vote: I like it +20 Vote: I do not like it

KAN+Anniversary=Kanniversary

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

Just In case what we all expect happens =)

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Hello darkness my old friend..

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

Very long queue

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

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

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

What the... video

»
9 months 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!

»
9 months 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. :(

  • »
    »
    9 months 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.

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

What is test 3 in C?

»
9 months 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

»
9 months 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??

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

Really cool problemset. Hope more like it are coming!

»
9 months 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.

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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?

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

        Exactly what Alei said.

      • »
        »
        »
        »
        9 months 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 }

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

      Time complexity of your solution?

  • »
    »
    9 months 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

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

What is the idea behind B & C ? :(

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

»
9 months 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 :)

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

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

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

Can anyone explain how to solve problem C?

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

    How much time did you have when you reached C ?

  • »
    »
    9 months 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.

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

      Is the first element considered as record?

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

        yes

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

        Yes, since there is no "j" such that 1 <= j < 1. Anyways, even if you consider it to not be a record that won't change the answer as removing no element will change its status(whether it is a record or not).

  • »
    »
    9 months 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

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

thanks for very short conditions))

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

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

This was the best codeforces contest so far.

»
9 months 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.

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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 ?

      • »
        »
        »
        »
        9 months 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.

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

          I meant TIME , no problem if you didn't understood .

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

          What's the point of googling the answers though

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

        you can see standing on this round

  • »
    »
    9 months 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.

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

Problem E can be solved with FFT?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

  • »
    »
    9 months 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.

  • »
    »
    9 months 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...")

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

»
9 months 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:(

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

    is that corner case?, if yes too sad

    • »
      »
      »
      9 months 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 :(

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

      it is not corner case.

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

system testing too slow :(

»
9 months 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?

  • »
    »
    9 months 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.

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

Nice problems! Thanks!

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

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

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

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

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

»
9 months 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

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

How to solve C?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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?

      • »
        »
        »
        »
        9 months 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?

      • »
        »
        »
        »
        9 months 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.

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

    I implemented a solution which is n log n

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

i became purple for the 8th time

»
9 months 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?

  • »
    »
    9 months 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)

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

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

      • »
        »
        »
        »
        9 months 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

»
9 months 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.

  • »
    »
    9 months 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

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

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

      • »
        »
        »
        »
        9 months 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).

»
9 months 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.

»
9 months 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

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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

      • »
        »
        »
        »
        9 months 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.

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

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

    • »
      »
      »
      9 months 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?

»
9 months 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.

»
9 months 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!

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

How to solve problem C?