Edvard's blog

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

Hello, Codeforces!

Educational Codeforces Round 6 will take place on 21 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.

<Your Ad Could Be Here>

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.

</Your Ad Could Be Here>

Thanks a lot to Aleksa Plavsic allllekssssa who suggested several problems, two of them you will see on the round (the problems D and F). Also thanks to Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. They are together suggested five problems, two of them you will see on the round (the problems B and E).

As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov we invented the problems A and C together. Also thanks to Maria Belova Delinur who will check English statements and Aleksa Plavsic allllekssssa who help me with problem testing and have constantly been in touch.

The first problem is pretty simple, so I'm waiting fast accepteds from you. The last problem is pretty difficult, so respect to all particiants who will solve it. I hope you will enjoy the problems!

Good luck and have fun!

UPD 1: I forgot to thank all other users who already sent me the ideas for the problems. I'll try to give that problems to the next rounds.

UPD 2: The main part of the contest is finished. The phase of hacks is started.

UPD 3: The editorial is ready.

UPD 4: The round is over, the results is final.

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

Comments Comments (52)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

Thanks Edvard for mentioning my friends and me. I'll really tried to give good and interesting tasks for contest. Possible you will see more our tasks in future rounds, that doesn't depend on me :)

Enjoy in contest, as always I am glad to hear comments and suggestions after round.

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

Waiting for tourist with AC on last problem in 10 minutes.

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

    I think no man on the world who can solve last task in 10 minutes :P

    EDIT: Congratulation to tourist, he is incredible! But I am not counting his solution as regular :P

    I can promise that he won't solve the hardest task in 10 minutes on my next round ( normally if he works it :D ).

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

    Actually he was able to solve the last one (problem F) in 7 minute .

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

These contests are sucks.

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

I think it is first Turkmen contest.Good luck to everyone!And thanks to contest all problemsetters.

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

So, D is solvable by binary search right?

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

    Maybe you can if instead of wasting time in writing comments , you make the changes :)

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

      I am tired. Only the fact that I figured how to solve D kept me going. Now I'm watching youtube :) Commenting takes literally 1-2 minutes.

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

Am I the only who have passed pretests in B using 7-dimensional array? :D

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

Unfortunately we gave bad constraints to the problem F. As a result some participants solved the problem in O(n2). In spite of this some participants solved the problem with better complexity. The author solution works in time.

К сожалению в задаче F мы неудачно поставили ограничения и поэтому некоторые участники сдали решение за O(n2). Несмотря на это среди решений есть решения асимптотически более быстрые, но работающие примерно столько же. Авторское решение работает за .

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

    Even author solution runtime does not explain such strange difference between limits on n and m.

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

      Actually the hidden constants for m and n is different.

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

      Sorry, I didn't answer before I had some other obligations.

      I am setter of fourth and sixth task. The number of good submissions (till now) is great and I think this round is really good for education..

      I only suggested tasks, with official solutions, so I didn't decide about final constrains for numbers and time limits. In my version(when I sent task) constrains were :

      n<=10^5 m<=10^4 Ai<=10^12

      And my estimation was that 5 seconds enough, but it is changed. Edvard is better programmer with more experience, so I beleive in his decision (and possible it is better to have more correct submissions — 8 good solutions in two hour aren't a lot of).

      I hope you enjoyed in tasks and spent 2 great hours. See you on some other round, any suggestion and opinion about tasks will be helpful.

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

    Так вот как её за 7 минут сдавать. Обидно :(

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

      Да мы тоже сильно расстроились. Мы рассмотрели такую возможность, но у меня было другое наивное решение и как раз его я смог завалить такими ограничениями.

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

Nice contest overall! Russian statements was very clear, except maybe a bit lack of comments on math, like that (+) operation in F is XOR :) I know that, but I also know a lot of people who wouldn't figure out what operation it is. And they can't google for it I guess — hard to write search engine request.

The only flaw I see is difficulty gap between C and DEF. But it is probably very personal thing.

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

    Problem title can help with this

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

      Haha, nice. Well I haven't read problem title until this moment :D

      Anyway, I'm kinda used to get such comments in statement, because they are often presented in regular contests (even easily googled ones like what is tree, what is subtree, etc).

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

        I actually get to the clarification writing interface just to be sure, but when I selected problem I had to read the title

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

Everyone is trying so hard to hack tourist on problem A. well , my friendly advice to those desperate souls: "let it go, my fellow coders. Sad but truth is tourist can solve easy problems too beside hard ones"

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

I think i could not understand problem C properly. In the test case 5 2 2 3 3 3 will 3-5 be a good segment? if yes, then can a good segment contain more than two pearls of same kind, also two pearls each of two different kind?

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

    Yes, and yes, and yes.

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

      uhh i totally misunderstood the question. Got it accepted easily now. thanks!

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

Will the editorial be post after the end of hacking phase?

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

how to solve D?

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

The second problem is very annoying. Otherwise very good and interesting problemset.

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

    I like how you wrote

    while (x)
            ans += ar[x%10], x /= 10;

    Didn't knew we could do that!

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

Hm, interesting. I've submitted two AC solutions to D. Second one was a bit more optimized. And now first one got hacked. And I got penalty as if I made one WA submission before.

Feels fair, but didn't expected such thing :)

So basically I can submit as many AC as I want, and the first one which won't be hacked will be considered as accepted solution, right? And how about hacked ones? Will I get penalty for every one or how else it works?

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

In problem E , Why am I getting a RTE on test 51 . I am using Segment Tree on Time Stamps 15485066

Moreover what is the stack limit on Code Forces? Might be recursion is causing stack overflow ..

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

    I got that problem too. You might use 2d arrays for the trees (i guess). Try using 1d arrays. I tried then time limited :D

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

During the contest i solved B casting every integer in the range [a, b] into a string (using std::to_string()) and then iterating the string with a range based for, and I got TLE (code here).

Then I removed the std::string conversion and did the same thing extracting every digit from the number, using the same complexity [ O(b — a) ], and got AC in 15 ms (code here).

Now on my pc the first solution, with the 1 1000000 tc, works in 130ms while the second one takes 40ms (I haven't got any kind of supercomputer or quantum computer and I compile with the same flags of Codeforces (C++11)). Now the question is: does codeforces hate std::string? is std::to_string() very very slow?

I got 3 TLEs for this :(

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

I wish to say few more things about tasks and whole contest till now.

First I hope you find something interesting in problemset or at least you don't hate tasks :)

This was my help to codeforces, I do this only because of the passion for programming ( and I don't have girlfriend to spend time on it :D ).

I hope to see your problems on the following educational rounds, Edvard is great guy he finished good part of preparation and certainly he would help to new problemsetters. Also I'm always here for any help and question for anything needed.

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

In problem C:

  • a submission with unordered_map fails with TL: 15496737

  • a submission with map gets AC (only one line of code changed!): 15496747

  • a submission with unordered_map and custom hash function: AC again! 15497036. Bit slower compared to map, anyway.

What exactly is test 42? Looks like someone went through the trouble to generated an extremely bad test case input that causes huge number of collisions in that specific G++ implementation of unordered map. In my opinion, it's a bit against the spirit of the competition ;)

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

    Against the spirit of the competition? Come on, it's just an unrated competition and also it's called an educational round ;) how so?

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

    Hi kfx and sgtlaugh,

    Can you please explain how having huge number of collisions give TLE? Shouldn't it give a Wrong Answer instead?

    And also can you please explain how would one generate such a test case programmatically.

    (My solution also got hacked due to the same reason)

    Thanks a lot! :)

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

Now when the hacking is finished I want to ask something. On the A problem I found a solution with O(n) complexity, e.g. there was iterating from 10^9 to -10^9. I tried to hack it using x1=10^9 and x2=-10^9 and the hacking attempt was unsuccessful. However, on my laptop it run more than 2s and the limit is 0.5s. Is the limit actually higher or am I missing something?

Thanks.

→ Reply