### Errichto's blog

By Errichto, 6 years ago,

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.

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

• +1387

 » 6 years ago, # |   +73 Great way to end this year
•  » » 6 years ago, # ^ |   +111 and how greater it would've been if there were Christmas themed Codeforces t-shirts for top participants..
•  » » 6 years ago, # ^ |   +7 I wish I can get good rating this round!(For example,purple => orange?)
•  » » 6 years ago, # ^ | ← Rev. 2 →   -11 int main(){cout<<"Good Bye 2015 \n Hello 2016";}
 » 6 years ago, # |   -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.
•  » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   -9 = let's hope there will not be high number of participants?
 » 6 years ago, # |   +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
•  » » 6 years ago, # ^ |   +183 Thanks for these words
•  » » » 6 years ago, # ^ |   +157 I'm amazed by your productivity, I have a feeling that you are most active setter right now :)
•  » » » 6 years ago, # ^ |   +16 Errichto as expected :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +22 Good bye 2015 is running and...
•  » » 6 years ago, # ^ |   +14 His problems are interesting. But some of his editorials could use a little more work. :)
 » 6 years ago, # |   +46 Do we have Happy New Year instead of Accepted during this contest? :D
•  » » 6 years ago, # ^ |   +15 We should have "Good Buy 2015 :(" instead of Wrong Answer or Failing submissions.
•  » » » 6 years ago, # ^ |   +172 Good bye 2015 on test 9
•  » » » » 6 years ago, # ^ |   0 That would be awesome...!!! :)
•  » » » 6 years ago, # ^ |   +11 good buy??
•  » » » » 6 years ago, # ^ |   +1 "buy" sounds logical, because wrong answers may cost you.
 » 6 years ago, # |   -108 Hope for more interesting algorithmic problems and less maths! :D
•  » » 6 years ago, # ^ |   -18 Hope for more interesting maths and less algorithmic problems! :D
 » 6 years ago, # |   -29 what's the meaning of TBA ?
•  » » 6 years ago, # ^ |   +7 To Be Announced
•  » » 6 years ago, # ^ |   -8 2BAnnounced
 » 6 years ago, # |   0 During a contest you should consider reading not only the next problem but the few next ones.:D
 » 6 years ago, # | ← Rev. 2 →   -35 Last contest forever.Bye,bye.
 » 6 years ago, # |   +2 Goodbye 2015，and hello,2016
 » 6 years ago, # |   0 Will the contest be rated?
•  » » 6 years ago, # ^ |   0 why not?
•  » » » 6 years ago, # ^ | ← 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.
•  » » » » 6 years ago, # ^ |   +109 Wow, a valid argument to ask "rated?". It's not something you see every day.Yes, it will be rated.
 » 6 years ago, # |   +41 2015||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 99%
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ |   0 Failed to become Grand Master in 2015......
•  » » » 6 years ago, # ^ |   0 Rating changes aren't out yet :)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 You don't need that !! The rating formula is public and so is this awesome tool
 » 6 years ago, # |   -22 is it a rated contest?
•  » » 6 years ago, # ^ |   +17 yes , and points will decrease slower than usual .it's a good chance to increase your rating,try not to miss it .
•  » » » 6 years ago, # ^ |   +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.
•  » » » » 6 years ago, # ^ |   +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.
 » 6 years ago, # | ← Rev. 2 →   -30 deleted
 » 6 years ago, # | ← Rev. 3 →   +225 I guess there must be a question on tree(Christmas tree)
•  » » 6 years ago, # ^ |   +10 Source (the guy is great at comics, give him all the love and attention he deserves!)
•  » » » 6 years ago, # ^ |   -26 Actually, some are funny, but I find most rather cringeworthy "le nerd humur xDDD".
 » 6 years ago, # |   0 Thank you Errichto.
 » 6 years ago, # |   0 Hope it will be a happy ending of this year for every participants :)
 » 6 years ago, # |   -24 Is it rated??
•  » » 6 years ago, # ^ |   +6
•  » » 6 years ago, # ^ |   +1 yes..
 » 6 years ago, # |   -20 Contest's problems may be easy..
 » 6 years ago, # |   0 Hello 2016 World!
 » 6 years ago, # |   -6 I hope it wlil be best round in this year))
 » 6 years ago, # |   +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...
•  » » 6 years ago, # ^ |   +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...
 » 6 years ago, # |   0 I hope to celebrate the new year by becoming a specialist :)
 » 6 years ago, # |   0 Wish everyone will have a happy Good Bye 2015, I have to prepare for my term examination, sigh...
 » 6 years ago, # |   +31 Will this round beat record of registrations?
»
6 years ago, # |
Rev. 4   -34
###### Who will be The best of 2016 ???tourist or Retired_MiFaFaOvO
•  » » 6 years ago, # ^ |   +27
•  » » » 6 years ago, # ^ |   0 Oh...It seems that now it became Retired_MiFaFaOvO
•  » » 6 years ago, # ^ |   +30 Why this constant comparison of Tourist and TooSimple?Tourist is the only one.
•  » » » 6 years ago, # ^ |   +12 I think TooSimple is quite excellent now.And in the Codeforces Round #336 (Div. 1), matthew99 became the rank 1 who is a Chinese high school student!
•  » » » » 6 years ago, # ^ |   -11 Was matthew99 born in 1999? If so, that's crazy.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   -15 Of course he was born in 1999
•  » » » » » » 6 years ago, # ^ |   -12 Not everybody chooses to append their year of birth to their handle.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +15 3 years ago YuukaKazami achieved 2600+ rating, 1.5 year before going to IOIRetired_MiFaFaOvO achieved 2600+ early 2015, before going to IOI, he also got his 1st win in early 2014.Every year China has lots of great high school competitive programmer. Nothing is crazy here.
•  » » » » » » 6 years ago, # ^ |   -10 And then there's tourist of course.
•  » » » » 6 years ago, # ^ |   -18 So, who seems excellent to you now? tourist is still more Experienced than Retired_MiFaFaOvO. So, he is definitely better. But, he doesn't need to prove it all the time. Sometimes, he seems to be tired of winning. And then, if you want to challenge thinking him as weak, he will come to you as a Giant.#Stop_this_constant_comparison... 
•  » » » 6 years ago, # ^ |   +49 No it should be TooSimple
•  » » » » 6 years ago, # ^ |   +24 May be you
 » 6 years ago, # |   +28 You should delay the contest at the very last minute to maximize number of registrants :)
 » 6 years ago, # |   +211
•  » » 6 years ago, # ^ | ← Rev. 3 →   -11 I think this is picture same www.quora.com/Who-are-some-good-looking-competitive-programmers but this on picture sentence change.
•  » » » 6 years ago, # ^ |   +6 So?
•  » » 6 years ago, # ^ |   -9 5 persons of Legends register this contest... It will be very interesting ... tourist VS Petr VS Toosimple VS rng_58 VS ... WOW!!!
•  » » 6 years ago, # ^ |   0 Gennady Kortowich (tourist) captures his breath after contest good by 2015 !
 » 6 years ago, # |   +21 The last contest in my birthday, great !!
 » 6 years ago, # |   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.
 » 6 years ago, # |   +22 as far as I remember, Errichto is good author, his contest are full of creativity and they have beautiful statements.
 » 6 years ago, # | ← Rev. 2 →   -52 please postpone the round Real Madrid is playing tomorrow at 7 pm
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   +3 I want both. I want to code in front of television. :) :)
 » 6 years ago, # |   +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 :DBest wishes to all :)PS: I changed my handle. It's shorter than before :v ;) Does anybody change their handle yet?
•  » » 6 years ago, # ^ |   0 How do we change our handle?
•  » » » 6 years ago, # ^ |   +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.
•  » » » » 6 years ago, # ^ |   0 Thanks for informing!This is my first new year celebrated with codeforces and I didn't know this before.D
 » 6 years ago, # |   -23 Running on pretest 20 Running on pretest 16 Accepted (20) 15 ms :D
 » 6 years ago, # | ← Rev. 2 →   +17 I wish there was a "Hello 2016" contest
 » 6 years ago, # |   -7 Will the coming contest be rated?
•  » » 6 years ago, # ^ |   0 Yes.
 » 6 years ago, # |   0 In 2016 the authors' fees is...Yeah, so nice to be the last div2 author in 2015.
 » 6 years ago, # |   +6 Really appreciate the effort homo_sapiens is doing here.
 » 6 years ago, # |   -16 I guess there must be a question on tree(Christmas tree)
 » 6 years ago, # |   +1 Why are they always afraid of revealing the scoring distribution before the start of the contest?
•  » » 6 years ago, # ^ |   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.
 » 6 years ago, # |   -13 Good bye 2015
 » 6 years ago, # |   -10 The tags for this post have spoilers for everyone. ;)
 » 6 years ago, # |   +4
•  » » 6 years ago, # ^ |   +9 I am not so selfish. I just want red colour!
 » 6 years ago, # | ← Rev. 2 →   -53 ليش
 » 6 years ago, # |   +28 if rng_58 join in , that would be the ultimate clash of 2015 .
•  » » 6 years ago, # ^ |   +362 Yes, joined.
•  » » » 6 years ago, # ^ |   0 Thanks and we want to see a great match.
•  » » 6 years ago, # ^ |   +1 what about subscriber , Will he join?!!
•  » » » 6 years ago, # ^ |   0 And vepifanov :)
 » 6 years ago, # |   +1 Время нового рекорда по количеству зарегистрировавшись пользователей на соревнование! Йо-хо-хо!
 » 6 years ago, # |   +44 I hope it will not be "Good Bye div1" round.
 » 6 years ago, # | ← Rev. 5 →   +17 ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ONE MORE TIME HAPPY NEW YEAR !!!!!!!!!!!!!!!!
 » 6 years ago, # |   +7 The best way to welcome new year with updated rating
 » 6 years ago, # |   +16 Good luck Everyone!!!
 » 6 years ago, # |   0 7377 registrants :O . Gotta be some kind of record .
•  » » 6 years ago, # ^ |   +18 crash guaranteed
•  » » 6 years ago, # ^ |   0 make that 7543
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ | ← 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: I clicked the link to register. I got redirected to the login page. I logged in successfully (still logged in now, posting this). I was shown the registration rules and a selected option button "register as a single contestant" underneath. I clicked that I wanted to register. 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 :(
•  » » » 6 years ago, # ^ |   +8 Is there any official way to file a bug report? I went through Help but didn't find any.
•  » » » » 6 years ago, # ^ |   +13 I'll check it, thanks.
•  » » » » » 6 years ago, # ^ |   0 Thanks :)
•  » » » » » 6 years ago, # ^ |   +6 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.
 » 6 years ago, # |   +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?
•  » » 6 years ago, # ^ |   +5 Even more: on the my submissions page there appears only my submissions for problem B and not for problem A!
•  » » » 6 years ago, # ^ |   +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.
•  » » » » 6 years ago, # ^ |   +5 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)
•  » » » » » 6 years ago, # ^ |   +5 No, please, do not resubmit any solutions. I found the reason and I'll get them back after the contest.
•  » » » » » » 6 years ago, # ^ |   +5 Thank you!
 » 6 years ago, # | ← Rev. 2 →   0 It is very interesting who will win this round because 5 Legendary Grandmasters are competiting.
 » 6 years ago, # | ← Rev. 2 →   +18 I guess, question about Retired_MiFaFaOvO vs tourist is closed now=).
 » 6 years ago, # |   0 How to solve D ? :/
•  » » 6 years ago, # ^ |   +1 contest is not finished yet!!!
•  » » 6 years ago, # ^ |   0 Surprisingly, I find D more solvable than B. Too many corner cases in B with my approach :/
•  » » » 6 years ago, # ^ |   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.
•  » » » » 6 years ago, # ^ |   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...
•  » » » » » 6 years ago, # ^ |   -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.
•  » » » » » » 6 years ago, # ^ |   0 Yes, I have not enough experience for now. Hope to get it more soon
 » 6 years ago, # | ← Rev. 2 →   0 tourist solved all _/_
•  » » 6 years ago, # ^ |   0 No, he passed the pretests on the 8 problems but he only solved 7 of them at the end.
 » 6 years ago, # |   -8 How are people solving B? It seems too twisted to handle all cases.
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   0 Oh no!!! Prefix sums got me again :(
•  » » 6 years ago, # ^ |   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.
•  » » » 6 years ago, # ^ |   +15 That's actually inefficient for this problem. If there are K such numbers, your code takes , while iterate+compare takes O(K) time.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 /
 » 6 years ago, # |   +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
•  » » 6 years ago, # ^ |   +8 Do you really need to use fenwick tree for C? prefix array is probably enough
•  » » 6 years ago, # ^ | ← 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).
•  » » 6 years ago, # ^ |   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)
•  » » 6 years ago, # ^ |   0 As there is no updates on the grid, only a cumulative matrix is needed.
•  » » 6 years ago, # ^ |   +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.
•  » » » 6 years ago, # ^ |   +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.
•  » » » » 6 years ago, # ^ |   0 Could you explain it, please? :)
 » 6 years ago, # |   +8 D is a good problem. How to solve this problem?
•  » » 6 years ago, # ^ | ← 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)
•  » » » 6 years ago, # ^ |   0 Wow, thanks.
•  » » » 6 years ago, # ^ |   0 I think there is another way to get q[i][j].We can use Saffix Array to get the longest commom prefix of s1 and s2.
•  » » » » 6 years ago, # ^ |   0 I did it. 15122800
 » 6 years ago, # |   0 Either I got dumber with the holidays, or the contest was way too hard for a holiday contest.
 » 6 years ago, # |   +6 Why did my solution on E TL11? It's clearly O(Nlog(N)).ideone: http://ideone.com/jqoGSgI tried optimising it as much as I could.
 » 6 years ago, # |   +3 Very interesting, but so hard :)
 » 6 years ago, # |   0 It cost me too much time to solve B. T.T
•  » » 6 years ago, # ^ |   -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.
 » 6 years ago, # |   +3 I could not submit the correct solution for problem E because the site crashed in the last minute. That much with my rating... :(
•  » » 6 years ago, # ^ |   +5
 » 6 years ago, # | ← 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.
 » 6 years ago, # |   0 Damn leap year...
•  » » 6 years ago, # ^ |   0 I see what you did there ...
 » 6 years ago, # |   +1 how many div 1 participants were there ??
 » 6 years ago, # |   +3 Amazing round. Such beautiful problems... I want to solve them all :)
 » 6 years ago, # |   -63 God Damn you Errichto :D contest was bad
•  » » 6 years ago, # ^ |   +14 Nopes.
 » 6 years ago, # | ← 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
•  » » 6 years ago, # ^ |   +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. :)
•  » » 6 years ago, # ^ | ← Rev. 6 →   0 [DELETED]
 » 6 years ago, # |   0 GG & WP & EZ
 » 6 years ago, # |   0 Beautiful problems.However I only solved 3... Anyway, happy new year and hope you all have high rating 2016!
 » 6 years ago, # |   +19 I hate problems connected with dates and time. (Just got 2 wrong submissions because of leap year(( )
•  » » 6 years ago, # ^ |   +3 I thought that 2016 begins with Monday and lost a lot of time.
 » 6 years ago, # | ← Rev. 4 →   +17 "Instead of refreshing standings you can read an editorial." Of course no. This is the most interesting thing.
 » 6 years ago, # |   -6 strict time limit for D :/
•  » » 6 years ago, # ^ |   0 Good thing I spent some time optimizing my solution to (nlogn)^2.
•  » » » 6 years ago, # ^ |   0 mine was O(N^2) which failed :/
•  » » » » 6 years ago, # ^ |   0 Really? That unfortunate. But from previous experience, I think 2.5 secs is more than enough for N^2.
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ |   +29 Your solution is O(n3), though.
•  » » » » 6 years ago, # ^ | ← 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.
•  » » » » » 6 years ago, # ^ |   +3 I think that your solution is also O(N^3).
•  » » » » » 6 years ago, # ^ |   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.
•  » » » » » » 6 years ago, # ^ |   -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....".
•  » » » » » » » 6 years ago, # ^ |   +12 Time limit — 2,5 seconds...
•  » » » » » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 tourist became winner this year
•  » » 6 years ago, # ^ |   0 Big deal
•  » » 6 years ago, # ^ |   +8 Is it unusual?!
•  » » 6 years ago, # ^ |   0 It may be a surprise for you bit it has become a habit got Tourist.
 » 6 years ago, # |   +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.
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ |   0 LOL. How difficult do you think it was calculating it on your own?
•  » » » 6 years ago, # ^ |   +1 Yes but I trust google more :P
•  » » 6 years ago, # ^ |   +38 So funny :-) Imagine the confusion of the website's owner...
 » 6 years ago, # |   +3 May I know when will the rating changes be shown?
 » 6 years ago, # |   +54 NBHEXT says I'm gonna be rank 1 after this contest:
•  » » 6 years ago, # ^ |   +3 It say's I'll be red, I wish it would be true
•  » » » 6 years ago, # ^ |   0 How much change does it show for rank 1841 ? **just curious :P **
•  » » » » 6 years ago, # ^ |   0 It shows +44. Congratulations!
•  » » » » » 6 years ago, # ^ |   0 Actually got +70 :D
•  » » » » » » 6 years ago, # ^ |   0 I told Rubanenko that I am almost sure it shows wrong rating changes but he said it's only for Legendary Masters. Seems like I was right :)
 » 6 years ago, # |   +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.
•  » » 6 years ago, # ^ |   +8 Looking at this it would take 30 seconds to come up with an implementable solution This problem probably served its purpose :P
 » 6 years ago, # |   +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.
 » 6 years ago, # |   +16 When will the rating be updated after the contest?
 » 6 years ago, # |   0 My new year resolution is to become a yellow coder by 2016.
•  » » 6 years ago, # ^ |   +9 By 2016 This mans you have 1 day for that. ALL the best!
 » 6 years ago, # |   -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.
 » 6 years ago, # | ← Rev. 2 →   +10 Not bad.
 » 6 years ago, # |   -67 why my submissions fail??? Errichto
•  » » 6 years ago, # ^ |   +19 Firstly, Errichto has nothing to do with it.Secondly, it's because you copied code from another submission.
•  » » » 6 years ago, # ^ |   -48 I solve all problems myself
•  » » » » 6 years ago, # ^ |   +89 Submissions:
•  » » » 6 years ago, # ^ |   0 But how does one do it? :/
 » 6 years ago, # |   0 Problems were NICE and so a little hard Maybe... +1000 Likes on this blog. It is interesting. Tnks.
 » 6 years ago, # |   0 I failed to solve problem E T^T Isn't it greedy?
 » 6 years ago, # |   0 Ratings are now SHOWN
 » 6 years ago, # |   +2 oh god !!! :((((((look at my rating :((
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 It seems 2016 was pretty eager to see you become purple :)
 » 6 years ago, # |   -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?
•  » » 6 years ago, # ^ |   +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.
•  » » 6 years ago, # ^ |   +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.
 » 6 years ago, # |   +46 Finally become red again :)
•  » » 6 years ago, # ^ |   +30 Same here :)) Awesome feeling
 » 6 years ago, # |   +17 Legendary_grandmaster ++; -->>Egor
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 Legendary_grandmaster --; -->>Um_nik
•  » » » 6 years ago, # ^ |   +18 Conservation of legendary grandmasters???
•  » » » » 6 years ago, # ^ |   +13 Conservation of nutella
 » 6 years ago, # |   +11 "Let the 2016 be (even) better..." — 2016 always is even. How it could be better?
 » 6 years ago, # |   +15 Is there any Welcome 2016! Contest ???
 » 6 years ago, # | ← Rev. 2 →   +46 I see someone learnt his lesson and put ~200 tests at E,great contest and nice problems,thanks Errichto.
•  » » 6 years ago, # ^ |   +33 I try not to make the same mistake twice.
 » 6 years ago, # | ← 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!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 It looks like you started contest 1hr 20min in? Is that right, seems very brave ...
•  » » » 6 years ago, # ^ |   +3 Nah I started with D, had a bug and eventually gave up to return to ABC. Then made another mistake on E.
 » 6 years ago, # |   0 Why didn't my record, I had A C
 » 6 years ago, # |   0 Not play very well...as I haven't known much algorithm...but luckily I am just a freshman
 » 6 years ago, # | ← Rev. 2 →   0 I have No Idea What could be The Best Gift for New Year after watching My Rating Increased 133 . I wish to be Red within Next Year . Keep Me In your Prayers . I would Like to be a RED like tourist .
 » 6 years ago, # |   0 The submissions in the problemset section have been reset,i guess,after the contest. When will they be back up ?Link for Problems with reset submissions Some of my Accepted problems also show a red mark ?
 » 6 years ago, # |   -23 Excelent Contest!!
 » 6 years ago, # |   -10
•  » » 6 years ago, # ^ |   -18 No, thank you. We don't need your bombs...
 » 6 years ago, # |   0 Happy new Year !!!! Good luck Everyone.....
 » 6 years ago, # |   0 Happy new year to all and kudos to codeforces
 » 6 years ago, # |   -13 I share my personal thing with all of you. I feel happy because in this year I will go to Bus tours from new york. Its my aim I will go there with m friends and I will go son in 2016.