Errichto's blog

Good Bye 2015
By Errichto, 9 years ago, In English

Hi everybody.

The last round of the 2015 will take place on the 30-th of December (starting time). The contest will last 3 hours.

It won't be a usual round. Both divisions will compete together. You will get 8 problems to solve in 3 hours. Points will decrease slower than usually — otherwise you would get eps for solving a problem at the end. Scoring will be announced just before a contest. So will the speed of the points/minute loss.

My goal was to provide you a diverse problemset with interesting problems for all contestants. During a contest you should consider reading not only the next problem but the few next ones.

You will get this round thanks to work of many people. I am a problem setter. GlebsHP helps me with everything (a lot). AlexFetisov, johnasselta and Zlobober are testers (thanks guys!). Delinur translates everything into Russian. Last but not least, MikeMirzayanov provides two awesome platforms — CF and Polygon. And there are so many people involved in Codeforces. Thank you all.

Let me give you more motivation to compete. The New Year is coming for Limak and he needs your help! Limak is a little polar bear by the way. You will help him, won't you?

I wish you great fun and no frustrating bugs. Looking forward to seeing you!

SCORING

Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hours rounds. Points for problems are 500-750-1250-1750-2500-2500-3000-3500. Enjoy the last contest in this year!

EDITORIAL

Instead of refreshing standings you can read an editorial. I will keep polishing it.

WINNERS

I'm amazed by the number of high-rated participants today. Fight was really tough and winners truly deserve respect.

  1. tourist
  2. Petr
  3. Egor
  4. rng_58
  5. black_horse2014
  6. step5
  7. I_love_Tanya_Romanova
  8. bmerry
  9. W4yneb0t
  10. V--o_o--V

It was the last Codeforces round in the 2015. Thanks for participating. And kudos for Mike for creating CF.

I wish you all an awesome year. Let the 2016 be (even) better than the passing year. Cheers.

Announcement of Good Bye 2015
  • Vote: I like it
  • +1387
  • Vote: I do not like it

Comments Comments (231)
| Write comment?
»
9 years ago, # |
  Vote: I like it +73 Vote: I do not like it

Great way to end this year

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

    and how greater it would've been if there were Christmas themed Codeforces t-shirts for top participants..

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

    I wish I can get good rating this round!(For example,purple => orange?)

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

    int main(){cout<<"Good Bye 2015 \n Hello 2016";}

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

I hoped at least the last contest of this year will take place in usual time. And, your generosity of extra 5 minutes are also nonsense when you moved the contest 1 hour back.

By the way, let's guess how many would register this time, I think it will cross 7999.

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

    Let's hope the website won't show "Codeforces is temporary unavailable" two minutes before the contest starts, then make a 15-minute delay.

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

I highly appreciate your contests. They have interesting problems, clear statements, good editorials and what not. Keep up the good work. I am really excited for this one :D

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

Do we have Happy New Year instead of Accepted during this contest? :D

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

    We should have "Good Buy 2015 :(" instead of Wrong Answer or Failing submissions.

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

      Good bye 2015 on test 9

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

        That would be awesome...!!! :)

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

      good buy??

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

        "buy" sounds logical, because wrong answers may cost you.

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

Hope for more interesting algorithmic problems and less maths! :D

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

what's the meaning of TBA ?

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

During a contest you should consider reading not only the next problem but the few next ones.:D

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it

Last contest forever.Bye,bye.

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

Goodbye 2015，and hello,2016

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

Will the contest be rated?

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

    why not?

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

      I suppose, because the timing and the amount of problems are not standard. I suggest that the formula for rating calculation was adjusted right for the 2 hour contests with 5 problems in it.

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

        Wow, a valid argument to ask "rated?". It's not something you see every day.

        Yes, it will be rated.

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

2015
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 99%

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

During the GoodBye2014, I have written a wish that I could become an IGM(rating >= 2600) in 2015. However, now, I have to modify this wish from IGM to GM(rating >= 2400), owing to the rating revolution.

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

is it a rated contest?

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

    yes , and points will decrease slower than usual .it's a good chance to increase your rating,try not to miss it .

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

      How does the rate of decrease of points affect one's chances of getting a better rating? Correct me if I'm wrong, but isn't it all about their position in the leaderboard? All participants should have the same advantage and thus the leaderboard should not show any appreciable changes solely because of this.

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

        Yep, you're absolutely right. The "Good Bye" contests just slightly reduce your expected place in the standings, and that stacks with the expected place reduction because it is a two-div contest, which means that you will need to be at a much lower place than expected just to NOT DECREASE your rating. Hence, the "Good Bye" contests being easier than the other ones.

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

deleted

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +225 Vote: I do not like it

I guess there must be a question on tree(Christmas tree)

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

    Source (the guy is great at comics, give him all the love and attention he deserves!)

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

      Actually, some are funny, but I find most rather cringeworthy "le nerd humur xDDD".

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

Thank you Errichto.

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

Hope it will be a happy ending of this year for every participants :)

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

Is it rated??

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

Hello 2016 World!

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

Is anyone still considering how to make it to take part in the contest?I'm a Chinese high school student of a boarding school and it's midnight when the round is running...

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

    It's kinda tough problem.. I live in Korea and I also have to participate at midnight. At least I am a univeristy student so I have my class afternoon, but it would be really hard for high school students like you. Some unusually-timed contests and virtual participations would be the best answer for now...

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

I hope to celebrate the new year by becoming a specialist :)

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

Wish everyone will have a happy Good Bye 2015,
I have to prepare for my term examination, sigh...

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

Will this round beat record of registrations?

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it -34 Vote: I do not like it
Who will be The best of 2016 ???
tourist or jqdai0815
→ Reply
»
9 years ago, # |
  Vote: I like it +28 Vote: I do not like it

You should delay the contest at the very last minute to maximize number of registrants :)

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

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

The last contest in my birthday, great !!

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

Good bye 2015, sometimes it could be very difficult if you remember all the year, and you would want change something in the past, but it makes sense. 2015 was a great year , especially thanks to codeforces, Thanks for all your contests and make our life fun and special.

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

as far as I remember, Errichto is good author, his contest are full of creativity and they have beautiful statements.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -52 Vote: I do not like it

please postpone the round Real Madrid is playing tomorrow at 7 pm

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

    You want to play football.but we want to play codeforces Good bye Round. So football or codeforces you decided. it is a lame excuse.

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

      I want both. I want to code in front of television. :) :)

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

Another successful year for Codeforces ^_^ <3 Good luck for the next year :D Also thank you Errichto for preparing the last round of the year 2015 :) Hopefully it will be a fantastic round :D

Best wishes to all :)

PS: I changed my handle. It's shorter than before :v ;) Does anybody change their handle yet?

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

    How do we change our handle?

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

      Go to your profile there you will find Settings tab. Click on Settings then you will find "Handle" tab under it. Click on "Handle" tab to change your handle.

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

        Thanks for informing!

        This is my first new year celebrated with codeforces and I didn't know this before.D

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

I wish there was a "Hello 2016" contest

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

Will the coming contest be rated?

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

Really appreciate the effort homo_sapiens is doing here.

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

Why are they always afraid of revealing the scoring distribution before the start of the contest?

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

    It's not because of they are afraid. It just because they don't want to ruin the thrill of the contest. It's only my opinion though.

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

The tags for this post have spoilers for everyone. ;)

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

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

    I am not so selfish. I just want red colour!

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -53 Vote: I do not like it

ليش

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

if rng_58 join in , that would be the ultimate clash of 2015 .

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

Время нового рекорда по количеству зарегистрировавшись пользователей на соревнование! Йо-хо-хо!

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

I hope it will not be "Good Bye div1" round.

→ Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it +17 Vote: I do not like it

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
ONE MORE TIME HAPPY NEW YEAR !!!!!!!!!!!!!!!!

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

The best way to welcome new year with updated rating

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

Good luck Everyone!!!

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

7377 registrants :O . Gotta be some kind of record .

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

Oh f**k this. Once in a year I have the time to compete, I register for the contest, I get the message that I have successfully registered, and now during the contest... what's this? "You should be registered for the contest to be able to submit"? What, if anything, did I do wrong???

Happy new year everyone, enjoy the contest. The problems seem nice.

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

    Thinking back about it, I may have been unlucky to trigger a bug. The issue is that my cookie has apparently expired, so the entire sequence of events (as I remember it) was:

    1. I clicked the link to register.
    2. I got redirected to the login page.
    3. I logged in successfully (still logged in now, posting this).
    4. I was shown the registration rules and a selected option button "register as a single contestant" underneath.
    5. I clicked that I wanted to register.
    6. I was moved back to the contest page and in the bottom right of the window there was a message box that I registered successfully.

    Everything seemed in order, but maybe the sequence of actions triggered some bug somewhere :(

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

      Is there any official way to file a bug report? I went through Help but didn't find any.

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

        I'll check it, thanks.

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

          Thanks :)

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

          Same happened to me. I was lucky to suspect the "register" label and click again on it.

          I've been opening the website regularly. I found it strange for the cookie to expire.

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

I have already solved problem A and B, but in standings it appears as if I have solved only A! Do you know why this can be so?

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

    Even more: on the my submissions page there appears only my submissions for problem B and not for problem A!

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

      Sorry, I do not know the reason right now. I'll investigate it after the round. You can be sure that your submission has been actually submitted if you see it in the "My submissions" tab.

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

        So should I resubmit Problem A(I'll lose Points, because my first submit was at 00:09, now it's over 1:30 since the beginning)

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

          No, please, do not resubmit any solutions. I found the reason and I'll get them back after the contest.

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

It is very interesting who will win this round because 5 Legendary Grandmasters are competiting.

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

I guess, question about jqdai0815 vs tourist is closed now=).

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

How to solve D ? :/

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

    contest is not finished yet!!!

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

    Surprisingly, I find D more solvable than B. Too many corner cases in B with my approach :/

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

      I was trying 30+ mins to implement O(1) solution for B. Was too complex.

      After that, changed algo to "iterate for all acceptable years from first_>=_a to last_<=b" and got AC in <10 min.

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

        I also have tried to solve B via "formula", but it was impossible for me. Then, when I was thought about iteration by all acceptable years (my solution was exactly the same as in editorial), I decided that it will be TL in this case, and I have given up...

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

          I see. Well you should try to evaluate complexity for such algorithms, its very important skill.

          Btw, when I can't evaluate complexity but its easy to code — I code it and just run locally on some huge test to see how it works.

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

            Yes, I have not enough experience for now. Hope to get it more soon

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

tourist solved all _/_

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

    No, he passed the pretests on the 8 problems but he only solved 7 of them at the end.

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

How are people solving B? It seems too twisted to handle all cases.

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

    There are no cases if you do it right :) Just generate all such numbers (up to 2^60 > 10^18) and check how many of them are in the given interval. There are very few such numbers -- you only have to consider all possibilities for the number of binary digits (1..60) and the position of the zero.

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

    I just made a list of all possible such numbers(there are not too many), sorted them, then just searh a and b in the sorted array.

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

      That's actually inefficient for this problem. If there are K such numbers, your code takes , while iterate+compare takes O(K) time.

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

Talk about coding up two 2-D Fenwick Trees for the first time ever, that too during a contest and passing pretests... I can't stress enough on how AWESOME problem C was for me.

There probably is another method for solving it, looking at the number of submissions. Either everyone coded up 2-D BITs or there is a simpler solution

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

    Do you really need to use fenwick tree for C? prefix array is probably enough

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

    Instead of 2D-BIT, you can just do dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(1/0 depending upon value is # or not).

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

    Given that there are no updates in the table, you can use 2-D preffix sum! First accumulate horizontally and then vertically.

    You can answer queries with the same Fenwick Tree method (the inclusion-exclusion thing)

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

    As there is no updates on the grid, only a cumulative matrix is needed.

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

    You don't have update operation so you don't need to use 2D Trees. Just use prefix sums similarly to 1D version.

    Suppose A[x][y] = sum of cells in the rectangle from [1;1] to [x;y]. Then the sum for the rectangle [x1;y1] to [x2;y2] is A[x2][y2] - A[x1 - 1][y2] - A[x2][y1 - 1] + A[x1 - 1][y1 - 1]. And there you go, A[][] can be computed linearly too.

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

      I wrote this, and while trying to hack others, I found that there is actually no need to write 2D-prefix sum... 1D-prefix sum is enough for this problem.

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

D is a good problem. How to solve this problem?

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

    I used two dynamic programmings:

    1). q[i][j]. Let us divide our array in the following way:

    Then we'll compare two last segments (let us call them s1 and s2, from left to right) as numbers: q[i, j] = INFINITY, if s1 > s2, otherwise we'll have maximum common prefix of s1 and s2. Note that during dp q[i, j] may be more than prefix size.

    How to calculate it: First, we can use bruteforce for i = n — 1. Then, use the following scheme:

    if (s[i - j + 1] > s[i - j - j + 1]) q[i][j] = 0;
if (s[i - j + 1] < s[i - j - j + 1]) q[i][j] = INF;
if (s[i - j + 1] == s[i - j - j + 1]) q[i][j] = min(INF, q[i + 1][j] + 1);

    (strings are zero-indexed)

    2). g[i][j]. It means numbers of ways to divide prefix with length i + 1 into numbers, and the last number has length j.

    Precalc: g[0][1] = 1, g[i][i + 1] = 1.

    How to calculate it for each g[i][j]?

    Quite easy. First, let us see that if s[i — j + 1] = '0', then the answer is 0.

    Let us try to form a new group. The end of the previous group was in element with index i-j. How long can be the previous group. It always can be less than j. And when the previous group size can be equal to j? Just in one case: if number in our new group will be more than in an old group. We can check it using q[i, j]: if q[i, j] < j, then we can say that the previous group size was equal to j.

    The answer will be sum of all the g[n — 1, i] (1 <= i <= n).

    Got the solution in O(N^3). Using prefix-sums it can be easily optimized to O(N^2)

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

Either I got dumber with the holidays, or the contest was way too hard for a holiday contest.

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

Why did my solution on E TL11? It's clearly O(Nlog(N)).

ideone: http://ideone.com/jqoGSg

I tried optimising it as much as I could.

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

Very interesting, but so hard :)

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

It cost me too much time to solve B. T.T

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

    As mentioned, if you simply generate all such numbers you can solve it very easily as there are very few numbers. I didn't do that but used a similar method that doesn't have many cases to cover.

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

I could not submit the correct solution for problem E because the site crashed in the last minute. That much with my rating... :(

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

After the end of contest, just 2 sec before, i got this popup: However when i view Hacks tab or my submissions they show nothing like "Hacked"? How to check. Also for C. Would a n**2 + n*q solution pass? Edit: All solution passed. Now if i recall, It might have been due to some submission that i previously opened in the rooms.

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

Damn leap year...

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

how many div 1 participants were there ??

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

Amazing round. Such beautiful problems... I want to solve them all :)

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

God Damn you Errichto :D contest was bad

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

Any elegant solution for F? I spent too much time coding mine and couldn't debug it in the end.

P.S.

Nevermind, the editorial is up and elegant enough

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

    It is just so lovely when you don't have to look at the color of the nickname to translate the question inside of your head to understand that it is meant for div1B and not for div2B :)

    Now, having no confusion at all I must admit that I have no answer to that question. :)

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

    [DELETED]

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

GG & WP & EZ

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

Beautiful problems.However I only solved 3... Anyway, happy new year and hope you all have high rating 2016!

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

I hate problems connected with dates and time. (Just got 2 wrong submissions because of leap year(( )

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

    I thought that 2016 begins with Monday and lost a lot of time.

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +17 Vote: I do not like it

"Instead of refreshing standings you can read an editorial." Of course no. This is the most interesting thing.

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

strict time limit for D :/

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

    Good thing I spent some time optimizing my solution to (nlogn)^2.

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

      mine was O(N^2) which failed :/

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

        Really? That unfortunate. But from previous experience, I think 2.5 secs is more than enough for N^2.

        → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it -8 Vote: I do not like it

    Yes! also my n^2 failed! my submission : 15126528 and also test cases for Problem C were weak. i saw solutions which were checking all possible places for every query and got accepted! which shouldnt cause there are 100000 queries and for every of them whole of matrix may be checked.

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

      Your solution is O(n3), though.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 5   Vote: I like it -11 Vote: I do not like it

        can you explain how is it O(N3) ? i think its O(N2) . Edit , i thought you were talking about my solution.

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

          I think that your solution is also O(N^3).

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

          Functions solve2 and solve calling each other has something to do with your complexity being O(N3). It depends more on what logic you are using.

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

            no thats O(N2) only , i ran it manually on my pc and it took about 3 — 4 seconds for N = 5000 and string = "99999....".

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

              Time limit — 2,5 seconds...

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

              Your code is behaving very strangely and I have no idea why. Here, take a look http://paste.ubuntu.com/14292557/. Just uncomment line 24 to see how it behaves. It's definitely not O(N^2) but I don't see any reason why it shouldn't be theoretically.

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

tourist became winner this year

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

My new year resolution is, I am not going to chicken out of doing contests. I will do each and every one of them. Simple.

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

Did everyone just google how many monday,tuesdays,... are there in 2016? I think the site corresponding to top results stopped working for few seconds.

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

May I know when will the rating changes be shown?

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

NBHEXT says I'm gonna be rank 1 after this contest:

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

Omg, so fucked up with A.

I was using C#'s DateTime class, starting with 01/01/2016 and adding one day on each cycle iteration while under year of 2016. You now, using the class where all the shit is implemented (like 29th of february and so on).

But! DateTime.DayOfWeek using USA notation, where Sunday is 0. And I thought it is Monday who is 0. So, WA. Damn.

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

    Looking at this it would take 30 seconds to come up with an implementable solution This problem probably served its purpose :P

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

Lie down. Try not to cry. Cry a lot.

I knew there was a good chance of my solution getting TLE. But I didn't have enough time to fix the problem during contest. Still, getting TLE at 149th case hurts.

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

When will the rating be updated after the contest?

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

My new year resolution is to become a yellow coder by 2016.

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

I. will. always. use. inline.
I. will. always. use. inline.
I. will. always. use. inline.
I. will. always. use. inline.
I. will. always. use. inline.
I. will. always. use. inline.
I. will. always. use. inline.

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

Not bad.

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

why my submissions fail??? Errichto

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

Problems were NICE and so a little hard Maybe... +1000 Likes on this blog. It is interesting. Tnks.

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

I failed to solve problem E T^T Isn't it greedy?

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

Ratings are now SHOWN

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

oh god !!! :((((((

look at my rating :((

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

There are many "oranges", who failed on A. There are many "blues", who solved D or E. There are some "cyans", who screwed a lot of "oranges".
Am I the only one, who reckons splitting into divisions as a very bad idea?

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

    It is quite good, because on usual 2h contest first two tasks of Div2 are way too easy for Div1 participants. And most of Div2 participants can't solve more than first two tasks.

    So if you merge it for contest of 7 tasks Div1 participants would be forced to code these two easiest tasks to get their points. If you just drop Div2 than a lot of ppl won't be able to solve anything.

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

    What do you suggest instead? 7/2 contests intead of 5/2 we have now? Or something like 7/2.5? Or you want to make a problemset consisting of 5 problems only and covering everything from grey to nutella at the same time?

    In case it wasn't just a random luck — these blues and cyans are going to reach div1 soon anyway; and if it wasn't just a random fail — these oranges will take their place in div2 sooner or later.

    Most div2 users have nothing to do with div1 D-E, most div1 users shouldn't face troubles with div2 A-B. And if it isn't true for some contestant — he is going to change his division soon.

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

Finally become red again :)

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

Legendary_grandmaster ++; -->>Egor

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

"Let the 2016 be (even) better..." — 2016 always is even. How it could be better?

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

Is there any Welcome 2016! Contest ???

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

I see someone learnt his lesson and put ~200 tests at E,great contest and nice problems,thanks Errichto.

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

Ouch, back to purple the same year I turned red!

Btw I updated the Elo-R ratings to reflect the end of 2015: https://raw.githubusercontent.com/EbTech/EloR/master/CFratings2015.txt (again, not totally precise because I don't know which events were unrated).

It's open source (root: https://github.com/EbTech/EloR) so if anyone plays with it and has questions, observations or suggestions, I'd be interested to hear them.

Have a wonderful 2016!

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

    It looks like you started contest 1hr 20min in? Is that right, seems very brave ...

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

      Nah I started with D, had a bug and eventually gave up to return to ABC. Then made another mistake on E.

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

Not play very well...as I haven't known much algorithm...but luckily I am just a freshman

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

Excelent Contest!!

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

https://www.google.com/search?q=%D8%AA%D8%B5%D8%A7%D9%88%DB%8C%D8%B1+%D8%B9%DB%8C%D8%AF+%D9%85%DB%8C%D9%84%D8%A7%D8%AF%DB%8C+2016&biw=1400&bih=708&tbm=isch&tbo=u&source=univ&sa=X&ved=0ahUKEwjNzODjzYXKAhXIvBQKHSV7AL0QsAQIGw#imgrc=rUI2jZP3FNgd4M%3A

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

Happy new Year !!!! Good luck Everyone.....

→ Reply