Hello, Codeforces!

Educational Codeforces Round 8 will take place on 19 February 2016 at 18:00 MSK for the first and the second divisions. You can read about educational rounds here and here. I hope that the high density of contests on Codeforces will not startle you and you will participate in ER8.

<The phrase about simple problems is added in the end>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks.

</The phrase about simple problems is added in the end>

This time (for the first time) the problemset was totally suggested by Codeforces users. The problem А suggested by user unprost. The problem B was taken form the problems sent by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. The problem D suggested by Kareem Mohamed Kareem_Mohamed (but I made it more difficult to make it more interesting for you :-)). The problem E sent Ali Ahmadi Kuzey. The problems C and F are suggested by Kamil Debowski Errichto.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

This time the problems wasn't prepared only by me (Edvard Davtyan). Thanks a lot to Kamil Debowski Errichto who not only suggested the problems C and F, but also prepared them. Thanks to Maria Belova Delinur for checking the English statements. Also thanks a lot to Ali Ahmadi Kuzey who helped me with testing of some problems.

A few words about the problems: A) Easy problem with the long statement; B) I hope you will not write hard solution; C) It's interesting; D) It's a little technical, but contains very useful technique; E) I like this problem; F) Very cool problem if you will not solve during the contest I recommend to solve it in practice.

Good luck and have fun!

UPD1: The first phase of the contest finished. Hacks started. The editorial is ready.

By the reason that all the problems of Errichto are about a bears, below you can see the illustration for the problem C (it seems Limak is the leftmost):

Very intresting :) B problem creatad by three users :)

3 contests on 3 consecutive days (and then USACO right after them) :D

And Codechef Cook off and HackerRank 101 Hack on Sunday!

And today will be , Usaco Feb Third contest, and Hackerearth!!!

I liked it when i registered at two Educational rounds at the same time :)

Hi It was a nice statement :) I hope problems like the statement be nice and short :) Ty man

nice

Limak returns :)

This is my first time to play Codeforces.

is it a new thing that registration closes at end of contest, i remember earlier it used to end 5 minutes prior to contest start, to avoid players just coming in midway and solving problems, Now is it true, that it is open invitation to join anytime you want, so div1 guys can join even 1 hour later and score more than hardworking div2. :P

Only for Gym Contests and Educational Rounds because they are unrated for everyone.

wow , it's really nice then

Bear, I think..marat.snowbear

Please extend the contest by at least 15 minutes. I couldn't access codeforces because of server problems. edit:I am serious.I could open all other sites!

Edvard , I think that you love Problem E because of its game(Zbazi).

I dunno that game.

it's more like a band than a game :D

Now your task is to help touristDAMN IT! My Geany crashed two times erasing completely my E both times and I just finished it for the third time, it's done, 5 seconds after it ended :/

UPD: Even worse, it now gets accepted... :@ :@ :@

changed cin from 16209365 to scanf in 16211539 and got accepted.

Image

Use cin or scanf, never use both.

Update: Tried to use all cin/cout but still got WA. Now I get confused...cin xor scanf? :D

i think we shouldnt use both cin and scanf when using sync_with_stdio link link

Why? It works for me.

Accepted

any ideas for D? How to make it efficiently despite the fact N is so big?

dynamic programming !

Dude... you're brilliant

I am using dynamic programming dp[i][index][remainder], i = 0,1,2, when i == 0 it means all previous digits[0..i -1] are the same with lowerbound string and when i == 2, all previous digits are the same with upperbound string, when i == 1, we can choose any number from 0 to 9. as for the remainder, the idea is very similar with problem B. So we should discuss cases when index is even or odd, I feel my solution is kind of troublesome and there are many corner cases, but at least it works right now :) You can refer to my code http://www.codeforces.com/contest/628/submission/16211896

You don't need to make that distinction (

i= 0, 1, 2). First of all, subtract 1 froma, then just count the amount of nonnegatived-magic numbers less than or equal toaand subtract it from the amount of nonnegatived-magic numbers less than or equal tob.Additionally, while you do need to keep track of the case where all digits are equal to the upperbound, there's no need to make an entire vector for it since there is always either 1 or 0 ways to do it (the latter happens when the upperbound is not

d-magic).Implementation: 16208100

Yea, I can avoid a lot of corner cases without i = 0,1,2 thank you :P

Incidentally, the idea for B is actually much simpler (due to M being 4). The blog says "I hope you will not write hard solution",

Thank you guys! With your help and the editorial I managed to code the solution :))

The most tricky part was how to deal with the modulo result because of course if the numbers length was of 2000, then you would need to add something like 10^2000 to the modulo value when you are testing different values for these numbers. The trick is awesome, to maintain all the modulo calculations in the 0-M range you don't need to power 10^1000, because although you start processing the i=0 that is the more significant digits you act like the other part of the number does not exist and every time you add one more digit, you just multiply by 10 the current modulo, add the new digit and make it modulo M. I am not sure why this modulo property applies, but it is

brilliantProblem A is like:

No hacking phase ?

Hacking phase is ON. You can view anybody's solution and proceed forward into hacking! :)

Thanks! Didn't know that

Thanks , Really amazing contest ,looking forward to the solutions. Good job

Very interesting!

in 2nd problem , changing from %lld to %I64d gave an ac.! why is that so ?

Are you sure about it? It looks weird.

Again let me thank authors for polar bear problems.

halyavin is using Energizer batteries, instead of Simple ones :)