MinakoKojima's blog

Codeforces Round #259
By MinakoKojima, 10 years ago, In English

Greeting!

Codeforces Round #259 (Div. 1 and Div. 2) will take place on August 1st, 19:30 MSK.

Setters are: sevenkplus, xlk and me.

Testers are: vfleaking, GuyUpLion, ztxz16 , CMHJT and Trinitrophenol.

Many thanks to Gerald for his help in giving advise about the problems. And we gratefully acknowledge MikeMirzayanov and his team, who bring us the world best competitive programming platform!

Tonight, you will come to Equestria and help our Friendship Princess — Twilight Sparkle to solve those intractable challenges one after another.

Twilight Sparkle is a main protagonist of the series — My Little Pony: Friendship Is Magic.

She is a female unicorn pony who transforms into an alicorn and becomes a princess in the third season of the series. She has a cutie mark of a 6-pointed magenta star with a white one behind it and 5 more smaller ones at each end of the magneta star.

Of course, I guarantee not knowing the storyline and setting won't hold you back from solving these problems~

UPD

In Div. 1, scores for each problem will be 500-1000-1500-2500-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2000-2500.

UPD

Contest is over! Congratulations to the winners! Here are the top 6 in Div.1 division:

  1. Petr

  2. msg555

  3. cgy4ever

  4. dzy493941464

  5. kcm1700

  6. Jacob

And here are the top 6 in Div.2 division:

  1. laomao

  2. AcySbl

  3. mpp121

  4. nuip

  5. chenzeyu97

  6. Horia

Editorial is here.

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

Comments Comments (232)
| Write comment?
»
10 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Of course, we guarantee knowing those background storyline and setting won't help you to solve any of our problems.

A pedantic note: I think you should instead guarantee that not knowing the setting won't hold you back from solving these problems. The reason is knowing this particular background might bring to your life some friendship which -- as we all know -- is magic. And noone should doubt that magic can help them solve tough problems.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +12 Vote: I do not like it

    Exactly! Thank you for remind me this! ~

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

    I don't know whether it is also that popular in other countries, but in Poland it is very common to name function returning least significant bit a "MAGIC".

    int MAGIC(int n) {
  return n - (n & (n - 1));
}

    So, are you suggesting that this function will help? Maybe some Fenwick trees :P?

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

      Why not n&-n?

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

        I hate this n&-n thing xd. That is very strongly depending on system of representing it in a computer. Everyone who knows what is a binary system can agree with my version but to get your version work we need some kind of weird arrangement how to represent negative numbers and fact that it's working is rather a funny coincidence. n&-n is easier to remember, but n — (n & (n — 1)); is easier to come up with on your own and much more reasonable in my opinion.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          (never mind, I messed up)

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

          Your argument is true but almost all softwares&&hardwares use the same way to represent negative. So using n&-n is OK i think. And more important n&-n works faster and because it's a very basic operation, say in Fenwick trees this trick proved to be helpful.

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

      In China, It's called the lowbit.

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

      One my friend names functions MAGIC, MAGICMAGIC, variables — temp, temptemp :)

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

        Deducing from that style of coding — is his rating greater than 1500? I wouldn't expect that :P.

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

          How about this style of coding? ;)

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

            I just wonder why he doesn't use a swap() function... Even <algorithm> gives one easy-to-use template

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

    In many cases, the background is related with incredible and strange story. Thus, I always drop into puzzled condition.

    → Reply
»
10 years ago, # |
  Vote: I like it +88 Vote: I do not like it

I hope it will help me :3

→ Reply
»
10 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Wait, just one pwny? You guys haven't figured out how to stack pwnies like how you stack cows yet?

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

    Maybe they want to create more contests like that :P.

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

      they have already stacked up 4 contests. this is the fourth consecutive Div-1 round organized by a Chinese coder. :)
      let us see how long they can keep it going!

      → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I won't solve these tasks if Rarity doesn't appear.

→ Reply
»
10 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Python will help me.

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

    it looks like a horse — -?lol

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    Python haven't helped me. Maybe, these problems are better to solve with FiM++. Or with better brains.

    → Reply
»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

why not 21:00 start?

→ Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Oh yes!! There seems to be MLP FiM problem set!

I'm looking forward to compete this round as Equestrian (see my profile).

I'm waiting for The Wonderbolt characters' problem...

→ Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Most recent Div.1 CF Round authors are from China. Chinese people seem to have many ideas to write problems :)

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

    That's because we can finally have a long long holiday AND MORE IMPORTANT some people think setting a CF round is a lot of fun XD

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

I believe this round will be very wonderful. I can't wait to join the round. MinakoKojima, you are my idol..（^ω^）

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

orzzz! Have got ready to become green again...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be so great if start time of this Chinese-author round were to changed earlier to usual Chinese round time 21:00.

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Firstly — next Chinese contest, secondly — brony contest. Gotta get outta from here xD. I won't be surprised if I see 5x3000 pts :D.

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

    It might be with dynamic scoring :D

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

    And then, Div 2 gets 3x3000pts problems, which will frighten off the news to Codeforces. ~

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

      OK, show them some mercy. Problem A may be 2500 pts (Div1) only.

      → Reply
»
10 years ago, # |
  Vote: I like it +65 Vote: I do not like it

My daughter loves Twilight Sparkle. Every night I have to watch My Little Pony with her. I hope to get a good result in this round. I would like to show to my little daughter that my name has the same color of her Twilight Sparkle.

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

    My best wish to you. Also give my regards to your lovely daughter~

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

Good luck & AC for fun!

→ Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Going to participate in the Div. 1 contest for the first time! Want to have a good experience! May the Almighty help me and all thanks goes to him!

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

    Good luck!

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

      Thanks and hope will see you in Div 1 in the next contest after today. Though I might be in Div 2 that time. :)

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

        thx 4 ur wish, let's fight 4 the goal of div 1 together! good luck again! ：）

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

        WOWOWOWOWOWOWOWOW Its unbelievable that i m purple now!~ thx 4 ur hope ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :)

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

          Feeling happy to see that! Congratulations! I should be in Div 2 from next contest, but I could not even get a chance to submit a solution! Had no idea to make a solution.

          However, best of luck for the next contests! :)

          → Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It seem to appear problems as "the one that don't know ******(an algorithm name) will FST!"

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

    Don't worry.

    The one, who don't know ***, won't pass the pretest.

    → Reply
»
10 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I think Chinese problem setters are supposed to adjust the start time to fit Chinese participants even if only in one round.

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It's typical Chinese Round! God bless us.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why can't I register for Codeforces Round #259 (Div. 1)?

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

    Your contest rating must be above 1700 in order to register for Div. 1 contests.

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

    Div 2 (especially Chinese Round Div 2) is more suitable for you.

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Chinese round again... but why not 17:00 MSK T_T

Btw I hope I can improve my rank to CM after this contest :D

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

    (Maybe they need to have supper, but problem setter don't need to sleep early.)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that setter xlk and tester GuyUpLion are the same person.

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

    Maybe I'm wrong, but their names are Ke Bi and they are from Shijiazhuang.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      They are definitely different people. Just one of them didn't tell us his true name.

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

        Hmm, I guess one of them is Ke's girl friend.

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

          Thank you for not guessing one is Ke's boy friend.

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

    If you use your true name, I can also register the same account as you.

    Why don't you think that is a common name? (Actually, it's a rare last name in China.)

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

Thanks MinakoKojima , xlk & sevenkplus for arranging the round. We hope more DIV1 rounds from you :)

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

    It's a typical Chinese round.

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

      What is the characteristics of a "typical Chinese round" ??

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

        Hard problems (usually due to hard math) and weaker pretests than usual.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Hard math is better than very long code,do you think so?I also think that passing the Chinese pretests is skimble-skamble

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

            When you can solve a problem, less code is a plus. When it's Chinese level hard, most people can't solve it, so it doesn't really matter how much code it needs :D

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

      This time our pretests seem to be strong.

      → Reply
»
10 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Thank you for spoilers about 3rd season in announce =/

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

MLP

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if there was not any xiaodao in the world, it would be "Codeforces Round #59" you are maker of half of my contest life:P

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope me can finish 2 problems in this round!

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

    As a bad resault,I only finish one problem

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i just registered for this contest, and guess what i saw!
i think these three accounts are all the same person, and if found out they should be banned!
EDIT: it appears that the "real account" of this person has commented on OP about 10 minutes ago.

→ Reply
»
10 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Извеняюсь за вопрос а эта строчка егодня вам придется посетить Equestria и помочь очень дружелюбной принцессе, Twilight Sparkle, решить несколько задачек. такая и должна быть?

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

    А что не так? Сегодня вы посетите Equestria и поможете решить несколько задачек очень дружелюбной принцессе по имени Twilight Sparkle

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't take medicine today，so I feel that my name is green QAQ I hope I can solve one problem designed by Chinese

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I think that it's the first codeforces round which tested by gray coder))

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

tourist is the last registrant, thereby marking his name for all to see in the next 3ish minutes.

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

I am going to sleep. Remaining problems is very hard.

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Awesome contest!! Thanks MinakoKojima , sevenkplus and xlk :D

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

how to solve Div-1 B?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    DP[i][mask] for each i = 1 .. n calculate min answer from 1 to i by using mask of prime numbers.

    if we choose for b[i] not prime number we can call b[i] = p[x1] * p[x2].... so it's mask of primes.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Oh what a nice solution. I was thinking of a completely different Solution 7320838 during contest.

      Too bad that i couldn't find my bug in contest :(

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

    dp[i][mask] is the answer for the first i numbers if the numbers we used divide only the prime numbers from mask.

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

    Here is a short explanation.

    You have to notice that it is a Bitmask DP problem. There are 16 primes less than 58. So keep a mask of 2^16, representing the primes used before. Then start a dp with states dp(pos,mask). In each position, you can place from 1-60. You can however only place a number if and only if it contains primes that have not been used before. Otherwise you can get gcd > 1.

    Just take the minimum configuration. Later print your path.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it -14 Vote: I do not like it

      But you can't choose 100 pairwise primes less than 58. Don't downvote if I'm wrong. We are all here to learn.

      Edit: NVM, forgot about 1s.

      → Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Found few people in my room who used this for solution of Div1 A : pow ( m, n ). Instant hack with test case ( 100000, 100000 ) :p That really boosted my ranking :D

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

    i tried to hack two participants who used pow function to find xy, but it returned Unsuccessful hacking attempt. :(
    any idea why?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it +17 Vote: I do not like it

      JuanMata You can not hack your friends :P

      You were just simply looking at power function. I was using power function differently. My code has expressions of the form pow(x/y, n). It would have failed if I would have done pow(x, n) / pow(y, n).

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

      We generally don't use pow cause of precision error. But since we are working with double here and the judge is going to ignore 10^-4 error anyways, I guess precision no longer becomes a issue anymore.

      I managed to hack cause they were trying to find pow(10^5,10^5), which is a large number and will given INF or NAN.

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

      It depends on how one uses it. I used pow as well. Except I had pow(x, y) only, where 0 <= x <= 1, which is why I don't get overflow, unlike if I was to use pow(m, n).

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

        yes, i got it.
        but what i mean is, doesn't pow(x,y) take to run?

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

          I think it is doable in O(log y) time.

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

            i know we can implement finding in .
            but i was referring to the pow function provided by <cmath>.

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

          pow(x,y) uses an expansion

          ...so a coprocessor (in short, a part of processor that conducts some funny operations, including computations on floating point numbers) needs to do exp (ex), ln () and mul (x·y) operations. Each of them can be done in a matter of dozens of CPU clock ticks.

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

            In VC++ pow(x,y) with integer y refers to binary exponentiation

            template<class _Ty> inline
        _Ty _Pow_int(_Ty _X, int _Y) throw()
        {unsigned int _N;
        if (_Y >= 0)
                _N = (unsigned int)_Y;
        else
                _N = (unsigned int)(-_Y);
        for (_Ty _Z = _Ty(1); ; _X *= _X)
                {if ((_N & 1) != 0)
                        _Z *= _X;
                if ((_N >>= 1) == 0)
                        return (_Y < 0 ? _Ty(1) / _Z : _Z); }}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              This code — an terrible nightmare for the hacker... 0_0

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

      why do you expect pow function for fail ?

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

        when we take (10^5)^(10^5) in denominator i thought it will work in python. so tried to write in python, but got only runtime errors (i had not used python before)

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

          Yeah... python can handle pretty large numbers, but it's still slow working with them. That's why you get TLE's if you do the unsimplified formula.

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

    How to solve Div 1-A?

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

      The probability that no value is bigger that x is equal to . It means that probability that max value is equal to x is equal to (probability of not getting >x) — (probability of not getting >x-1). Then you can compute the expected value.

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

        I got the formula...But I could not translate it into code..as the constraints were too high.

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

          Programming languages usually have a routine to compute the powers of floating-point numbers very fast.

          E.g. in C++ you can compute as follows:

          result = pow((double)x/m, n);

          You can assume it works in constant time.

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

          C++ has a useful function: pow(base,exponent), which is fast enough.

          → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it +21 Vote: I do not like it

        We can simplify the formula as:

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

          could you explain this simplification?

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

            There is a chance that maximum will be  ≤ k. Consider sequence 1, 2, ..., m: probability for each k to be the max is minus probability that every less value would be the maximum, so . Then multiply by value to get the expected value and you should get something along these lines.

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

              I just realized telescoping series in this sum. Anyway, thanks

              → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 7   Vote: I like it +8 Vote: I do not like it

            Sorry, duplicated and deleted. See below.

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

            It can be derived like this:

            also:

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

    are you serious? http://codeforces.net/contest/453/submission/7310927

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

      Well, this guys did this:

      p = (i) / (double)m;
p = pow(p, n)

      Since, p <= 1, pow ( p, n ) will not overflow. pow ( m, n ) however will overflow.

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

        Ac-93 probably meant that you included a (quite long) segment tree implementation in an easy math task :D

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

          firstly, the code is submitted by Ac-93 himself.
          secondly, he is not invoking those functions anywhere in main. i don't see anything wrong with having segment tree implementation as part of one's template.

          → Reply
»
10 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Thank you for the contest and for the great tasks!

If I would give feedback on the tasks, I would say that I disliked that the graph is not guaranteed to be connected in Div1 C/Div2 E. This, in my opinion, was a restriction with a single purpose in mind — let's invent some edge cases, which is the purpose I heavily dislike. If the graph is connected, there are no edge cases at all (and it is always possible to construct a path). Now, because this is not guaranteed, I had to add a bunch of "edge case" code — find out which vertex to start DFS from (rather than starting from any with single component), check if there is only 1 connected component etc. With a single component I felt that the task actually had short and clean solution in code. Was it really necessary to do this?

Furthermore, because the authors didn't include any test with answer -1 in pretests, I had wasted an hour worth of points before someone hacked me and I found the lack of outputing -1 in my code. Sure, this is completely my fault. But one of the point of pretests is to check the format of the output (like if there are mutiple possible string outputs — have them all in pretests), and in this case -1 was never tested. Is it fair to penalize people who accidently mistyped this constant?

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

    Sorry for that, acknowledged.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Furthermore, because the authors didn't include any test with answer -1 in pretests,

    Wait, what?

    I don't mind the possible disconnectedness, especially because the "if there's no answer" in the statement worked as a good hint, but the pretests definitely should've taken care of that. I also didn't really try hacking C because I thought the only special case was included in the pretests... I wonder how many people were in a similar situation.

    Well, as I said above: weaker pretests than usual. Although in a different way than I meant :D

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Yeah, I didn't paid too much attention to the hint "if there's no answer", because I see authors putting this in even if there is always solution, to hide that fact, because it might make the task easier.

      But to highlight my point about disconnectedness, here is the difference between my original code and the accepted version. Sure, it certainly doesn't make the task bad — I liked it very much, but this code was in my opinion unnecessary and brought nothing to the solution of the task except edge cases. Before the whole code was: read the graph, run DFS, output the answer. Now we have extra steps: find the vertex to start from, check that there is no 1 in array after DFS.

      And yeah, there were different approaches to this problem, in which having unconnected graph only brought 1 line modification.

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

        My modifications were much simpler, it's mostly just rewriting "0" to "i" in a big chunk of code.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV1 A and DIV1B?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 12   Vote: I like it 0 Vote: I do not like it

    Div1A -> Calculate seperately the number of times:

    1 would be maximum , 2 max ........ m would be maximum

    Number of times 1 max = 1

    Number of times 2 maximum = 2n — 1

    Number of times i maximum = in — ((i - 1)n)

    So Expected value =

    Mix m^n with the numerator and you can get the answer

    I made the mistake of not mixing m^n with the numerator

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

      I think you missed an "i" in the expected value expression.

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

        Thanks for correcting me .

        Please can anyone tell me how do I post mathematical symbols here ?

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

          \sum_{i=1}^m i * \frac{i^n — (i-1)^n}{m^n}

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

            Thanks

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

            This was my mistake! I also did summation from 1 to n. Output for given cases did not match. I did not think of debug. I thought approach was wrong. Then I saw the solutions...

            Saw the same error again (here).

            So, change the summation from 1 to m

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

              No that's not why I coded it wrong . I took summation from 1 to m but did not merge the denominator: m^n with the numerator . Thus I thought that it would overflow and did not do anything about the problem .

              → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

a

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

Task C is good, but I think it would be better to set that the input graph is connected. (The other part is not very interesting).

Task D is also good, but I think the TL is a bit tie. I managed to pass the pretest by code optimization.

Task E seems to be the harder version (force to do it online) of this task: http://hihocoder.com/contest/challenge1/problem/2

I think it is not a good idea to use it here since it has already used in previous contests. For example, since I know I can't even code solution for the eaiser task, I just skip this task and focus on D, it gives me some advantages.

Overall it is a good contest, thank you all writers and testers!

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

    C is by me. It would be a bit unnatural to constrain the graph to be connected. Also, Egor gets WA because of this. :D

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

      And this is why I disliked the absence of this restriction in the first place in the comment above. The whole idea in the solution is run on a single connected component, then you added unnatural expansion (unnatural to the solution rather than unnatural to the statement, and I probably don't even agree that this constraint in the statement is unnatural) to allow graphs to be not connected, so that there are now some edge cases/extra work to do. And as you wrote Egor failed because of this.

      Seems to me that you're pretty happy with that. I believe authors should be happy when people fail their task with a wrong solution, rather than solving it correctly and failing on the edge case. But maybe that's just me.

      Don't get me wrong, I still liked the task and the contest. As cgy4ever I just feel it could have been even better with that restriction.

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

        Sometimes we need to left something to hack, and sometimes we cover the tricky part by constraints or give such case in examples.

        For me, I only left it to hack if the task is very easy or a bit classic. If I'm the writer of this task, I will cover that trick cases, because this task itself is challenging, if someone get the solution but fail by that stupid trick then it is huge lost (Getting the solution is a challenging thing, so he should get points by this).

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

      actually, Egor's solution 7313057 failed on a much easier case than where answer was -1. :D (but you are right about graph not being connected)

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

        It's all about connectedness, so it doesn't matter.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +29 Vote: I do not like it

      Every problem setters should maximize following fraction:

      Interesting
-----------
Frustrating

      To make problems better.

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

      Well, of course I should be more attentive to details, no doubt about this. But I always thought that it is just a good taste for problemsetter to include sample with answer "Impossible" or such if there is such case. I know that at the very least TopCoder requires a thing

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    I know it is bad, that's why I put it in the middle night~ Princess Luna, can you hear me?

    → Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Slowest system testing I've ever seen....only 4 submission are being judged at the same time!

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

    I am amazed that you have done 62 contests but haven't seen slower system testing. The system testing is slow because there are too many test cases for problem A. We apologize for this.

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

      I suppose it's some technical problem...because in every contest I see almost 10 submissions that are being judged simultaneously

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

      there cant be more that 50 cases!

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Oh LOL, DIV2C/DIV1A was damn simple, and I messed it up %)

→ Reply
»
10 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Good problems — 9/10

Having disconnected graph in C was not something to complain about

-1 because two very hard problems for a single match is too much

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

    I was right because I gave up and slept early.

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

    Honestly, I would disagree with the statement "very hard problems", at least with E. It was pretty complicated, I must say, but if you carefully broke down the problem into smaller ones, it became quite straightforward (i.e. no superclever observations and tricks were needed), although implementationally demanding. Of course, it is only my opinion :) And I didn't manage to find a (obvious) bug before the end of the contest, but still it was not "very hard".

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I could find a way to find the expected number for div1 A but I couldn't implement it because I don't know how to avoid overflow my idea like this:

let prob[i] be the probability that the max number is i (for all i from 1 to M) then I compute the expected number.

let dp[i] be number of sequences with length N and every element between 1 and i and max number is i.

dp[i] = i^N-(sum(dp[j]) for every 1<=j<i)

then prob[i]=dp[i]/(M^N)

then expected number is sum(dp[i]*i) for every 1<=i<=M

But I couldn't implement it because I don't know how to avoid overflow of dp[i] and (M^N). is there anyway to implement this idea or I should search for another idea that is easy to implement?

Here is a code for my idea it works correctly for small tests.

This is not the first time that I encounter a probability problem that I could find a solution to solve it but I couldn't implement it.

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

    My first solution was hacked because of the overflow problem, but it's fairly easy to derive the solution that doesn't overflow if you had already come up with the one that does :)

    7318172

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

my submission for problem E (Div 2) is giving WA on pretest 4.But when after the contest i tried the test case it's giving correct answer on my system as well as ideone.
This is the ideone link :- http://ideone.com/EWR4KA
my codeforces submission :- http://codeforces.net/contest/454/submission/7320400
can somebody tell me the reason behind it ??

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

    Can't see any differencies, there's the same (incorrect) answer at ideone, isn't there?

    18 3 2 1 2 4 5 7 5 10 5 4 8 4 9 4 3 6 3

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

    there is no edge from 4 to 3

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Quite unfortunate that my Div1-B solution passed all pretests :'(

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

i saw a few AC submissions in my room for Div-1 A, which printed .
can anyone please provide a proof for this?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    the answer is .

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

      Am I too dumb or is it really not that obvious how the left hand side can be rewritten as the right hand side?

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    JuanMata i don't think the limit of summation will be till m, it will be till m-1 and also instead of first term m+1 shouldn't m be there?

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

    Have a look at this comment. http://codeforces.net/blog/entry/13247#comment-180671. If you simplify it, it will result in your formula.

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

    The sum telescopes to

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

      excellent explanation, thanks very much :)

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Are you sure it is m + 1 in your formula?. There is only one way of getting the maximal element (in n consecutive trials) equal to one, then there are 2n - 1 ways of getting the maximal element equal two, 3n - 2n ways of getting the maximal element equal to 3, and so on. The total number of possibilities is, of course, mn. Then the expectation is calculated in the following way:

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

      In formula by JuanMata the summation is till m. Notice that the last term is (m/m =1) so it will cancel the previous 1 . This will leave the formula given by ericxu0.

      PS: There is a small typo in you formula , the summation should be till m-1 not n.

      → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Div1-B, Nice problem!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div.2 problem B: http://codeforces.net/contest/454/problem/B My Submission: http://codeforces.net/contest/454/submission/7316030 It fails on pretest 6. If I'm right, here is an equivalent test: 5 4 1 2 3 5 How this array can be sorted using the given move? If my test is not equivalent, please update me with a correct one that I can trace. Thanks.

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

    I dont think that it is equivalent. Here is a test case which your code fails. 3 1 2 1.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2-C ?

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

    Look at exmath89's post for the expression to evaluate. To evaluate this expression, for everything in the summation, calculate it with exponentiation by squaring. Then, sum these up and subtract from m to get the answer.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I try to hack 7313853 during contest with test case :

100000
100000 1 2 3 4 .... 99999

It checks all the states , with == operation for deque (99999 times for a 100000 size deque) ... My hacking of TLE was unsuccessful...

Now it has been TLE on case 41 , With a equal N , but using repetitive number 1...

Isn't it Weird ? I mean are we hacking Deep until STL Codes ? :D

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

    The == operator only has to look until it finds a single mismatch -- so for 99999 of those equality comparisons, it exited after looking at just the first element of both deques. The system test case was TLE because it had to look through all of those 1s before finding a mismatch :)

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

      Yes but i was not thinking of The STL implement, i thought its Linear so it should fail.

      I mean my testcase should do some hacks to make STL deque Linear in case of hacking this submission. It was a bit unusual for me.

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

    STL is evil in some way... Believe me, after IPSC 2014 there will be "HashSetKiller" programs, like already exist JavaQuickSortKiller!

    p.s. one problem in this year's IPSC is to hack C++ and Java hashset program to let them get TLE in not very large test case, and there even exists a input that could hack both programs! (See HARD version of that problem)

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

      That's Cool!!

      I will check more in the STL implements.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ratings are updated!

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I was 45 minutes late, but still +71 rating.Thanks for great problems.

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Forgive me if I'm a bit retarded in that subject, but were 50 points always deducted for submissions that fail on a sample test, but not on a 1st test? I thought that rule of not deducting 50 points for submission failing 1st sample test applies to all samples.

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

    It applies only for the first sample, I can't get the point of this though.

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

      I can't get the point of this though

      it is mainly to check that output format exactly matches with what the checker expects. this is especially useful in problems like this one.

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

      This way you are not penalized in case of your submission failing due to wrong output format, or if you simply chose wrong file to upload/ wrong problem to submit against.

      It can be said that you pay for your own carelessness, but anyway prevention of that sort of mistakes is pretty sweet. I guess you've just never submitted wrong file on a contest ;)

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

        Well I believe that it won't hurt if all the samples are included :D

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

          Completely agree with you. In this contest, I got two WA on pretest 2 in div1C, which was one of the samples, directly costing me 100 points.

          Though I didn't pass the system test anyway :(

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

            The point is that you should test the samples. The reason why first sample isn't penalized is I believe to avoid penalties for technical stuff (like how to deal correctly with packages in Java, for example) rather than avoid penalizing for WA1.

            → Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Someone please tell how to solve div1C?

→ Reply
»
10 years ago, # |
  Vote: I like it -37 Vote: I do not like it

May I ask you to do your next contest in "Adventure Time" setting? It's very nice too :).

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

    may i ask you not to post such large photos in comments? they are not so nice. :(

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

      I didn't knew that CF posts pictures in their full size. My first picture-upload :(

      → Reply
»
10 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Following this success, I will make my next round with Pokemons!

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Round Stats

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the awesome problemset. Unfortunately I missed this round :-(.

→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

OFF TOPIC THOUGH: I just came to remember this author MinakoKojima for some special reason. some days ago I was trying to learn link cut tree and found her blog:- http://www.shuizilong.com/house/archives/spoj-9577-dynamic-tree-connectivity/

Thank you MinakoKojima for your contribution to the community.

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

+122 rating. I love ponies, also this is surely great contest!

→ Reply
»
10 years ago, # |
  Vote: I like it -39 Vote: I do not like it

The new Editorial is available here.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give me solution for this round? Thank u.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Div-2 A solution using regexp (language: Perl): longer, shorter.

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Wrong picture guys. When Twilight is solving problems she looks different:

→ Reply