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

Автор Errichto, 9 лет назад, По-английски

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.

Анонс Good Bye 2015
  • Проголосовать: нравится
  • +1387
  • Проголосовать: не нравится

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

Great way to end this year

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

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.

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

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

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

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

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

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

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

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

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

what's the meaning of TBA ?

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

Жду не дождусь. По прошлому Good Bye помню насколько приятно было его писать. Надеюсь на этом контесте будет такая же праздничная атмосфера, как и в прошлом году :)

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

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

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

Last contest forever.Bye,bye.

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

Goodbye 2015,and hello,2016

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

Will the contest be rated?

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

    why not?

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

      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.

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

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

        Yes, it will be rated.

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

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

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

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.

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

is it a rated contest?

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

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

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

      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.

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

        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.

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

deleted

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

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

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

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

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

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

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

Thank you Errichto.

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

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

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

Is it rated??

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

Hello 2016 World!

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

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

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

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

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

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

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

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

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

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

Will this round beat record of registrations?

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится -34 Проголосовать: не нравится
Who will be The best of 2016 ???
tourist or jqdai0815
»
9 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

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

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

The last contest in my birthday, great !!

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

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.

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

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

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

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

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

    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.

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

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?

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

    How do we change our handle?

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

      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.

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

        Thanks for informing!

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

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

I wish there was a "Hello 2016" contest

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

Will the coming contest be rated?

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

Really appreciate the effort homo_sapiens is doing here.

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

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

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

    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.

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

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

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

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

ليش

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

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

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

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

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

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

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

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

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

The best way to welcome new year with updated rating

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

Желаю всем подняться в рейтинге перед новым годом! Пусть в 2016 году красных станет намного больше!!!

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

Good luck Everyone!!!

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

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

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

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.

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

    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 :(

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

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

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

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?

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

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

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

      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.

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

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

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

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

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

How to solve D ? :/

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

    contest is not finished yet!!!

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

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

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

      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.

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

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

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

          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.

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

tourist solved all _/_

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

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

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

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

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

    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.

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

    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.

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

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

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

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

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

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

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

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

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

    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)

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

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

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

    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.

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

      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.

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

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

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

    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)

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

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

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

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.

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

Very interesting, but so hard :)

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

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

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

    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.

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

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

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

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.

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

Damn leap year...

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

how many div 1 participants were there ??

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

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

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

God Damn you Errichto :D contest was bad

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

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

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

    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. :)

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

    [DELETED]

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

GG & WP & EZ

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

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

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

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

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

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

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

strict time limit for D :/

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

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

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

    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.

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

      Your solution is O(n3), though.

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

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

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

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

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

          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.

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

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

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

tourist became winner this year

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

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.

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

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.

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

May I know when will the rating changes be shown?

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

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

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

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.

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

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

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

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.

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

When will the rating be updated after the contest?

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

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

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

Прочитал D, понял что там динамика, но какая именно — не догадался.

Вместо этого переключился на F (решение придумалось быстро), понял, что она простая (по-крайней мере для F), но отдебажить не успел :(

Наверное стоило всё-таки дожать D, судя по количеству сдавших людей.

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

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.

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

Not bad.

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

why my submissions fail??? Errichto

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

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

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

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

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

Ratings are now SHOWN

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

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

look at my rating :((

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

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?

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

    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.

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

    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.

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

Finally become red again :)

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

Legendary_grandmaster ++; -->>Egor

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

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

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

Is there any Welcome 2016! Contest ???

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

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

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

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!

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

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

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

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

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

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

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

Перенести одну строку и добавить одно условие = Полное решение по E. Эх...

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

Excelent Contest!!

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

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