Edvard's blog

Educational Codeforces Round 8
By Edvard, history, 9 years ago, translation, In English

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

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

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

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

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

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

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

    And Codechef Cook off and HackerRank 101 Hack on Sunday!

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

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

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

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

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

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

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

nice

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

Limak returns :)

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

Bear, I think..marat.snowbear

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

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!

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

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

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

Now your task is to help tourist

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

DAMN 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... :@ :@ :@

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

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

Image

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

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

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

    dynamic programming !

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

    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

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

      You don't need to make that distinction (i = 0, 1, 2). First of all, subtract 1 from a, then just count the amount of nonnegative d-magic numbers less than or equal to a and subtract it from the amount of nonnegative d-magic numbers less than or equal to b.

      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

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

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

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

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

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

      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 brilliant

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

Problem A is like:

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

No hacking phase ?

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

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

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

Very interesting!

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

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

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

Again let me thank authors for polar bear problems.

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

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

→ Reply