Educational Codeforces Round 43 [Rated for Div. 2]
By vovuh, history, 6 years ago, translation, In English

Hello Codeforces!

On April 30, 17:35 MSK Educational Codeforces Round 43 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were prepared by Mikhail awoo Piklyaev, Roman Roms Glazov, Adilbek adedalic Dalabaev and me.

We'd like to thank Ivan BledDest Androsov and Maksim Neon Mescheryakov for the help in preparing the round.

Good luck to all participants!

UPD: The round will contain 6 problems instead of 7.

UPD2: Editorial

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dotorya 6 150
2 I_love_Tanya_Romanova 6 276
3 uwi 6 324
4 nuip 6 327
5 dreamoon_love_AA 6 328

Congratulations to the best hackers:

Rank Competitor Hack Count
1 hryniuk 66:-4
2 Aemon 65:-13
3 bitcoin 56:-2
4 uwi 57:-12
5 im0qianqian 40:-1

777 successful hacks and 656 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A 300iq 0:00
B I_love_Tanya_Romanova 0:05
C readers3 0:06
D dotorya 0:26
E djq_cpp 0:21
F kraskevich 0:24

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

Comments Comments (125)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +44 Vote: I do not like it

100000!!!

http://codeforces.com/contests/100000

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

    I'm curious, but why is this round's ID so special? I meant, latest IDs are just 966 and 967.

    UPD: Round ID changed to 976 now. So perhaps it was a test or something.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it -28 Vote: I do not like it

      Because, after 967 comes 100000!!! joke ;)

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

        Technically, I don't understand the joke.

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

      Maybe it has to do with codeforces 1000th(binary) anniversary? Although there are more zeroes than that :)

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

        According to your theory, this contest will be filled with the number 32 everywhere I guess :D

        UPD: Round ID changed to 976 now. So perhaps it was a test or something.

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

      But last rounds ID was 967 :)

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

Why contest http://codeforces.com/contest/967 is not showing rates? How long do I need to wait ?

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

Codeforces contests come at once

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

So many contests recently, thank you codeforces!

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

!!!

This round begins 23 hrs 30 mins earlier than CF#478. 2 hours contest plus 24 hours hacking end 30 mins after the end of CF #478 :)

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

Why CF have this tendention to increase number of tasks in 2 hour contests?

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

    Educational rounds have been usually consist of 6-7 problems, pal.

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

Happiness is having codeforces round in 3 consecutive days. :D

Thanks a lot to the Codeforces team and the authors. :D

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

Hi! Why isn't the round appearing in the contests page? (as well as in the "Pay attention" tab)
EDIT: Fixed!

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

Is it rated ( ͡° ͜ʖ ͡°)

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

    anyone knows that if you say "is it rated?" you won't get positive vote no longer.

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

    Mark, You should add a button called Report 'is it rated' comment. Please. We need it

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

Wish u lots of Heck(Hack)!!

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

This would be my first CF contest (mainly because this is one of the few contests which starts at a suitable time for me)! I'm just so excited!!

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

5 min delay

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

5 min delay! :3

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

Contest delays.

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

What the crap is with this 5 min delay ?!?!?! And yes, when the initial timer ran out CodeForces did freeze for me

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

How to solve D?

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

Any idea of test 5 about E?

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

    My solution was failed on 5. Possible test case :

    2 2 1

    10 15

    6 1

    Answer should be 41

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

Any idea for test 10 in E?

Please tell me what is the wrong in my code.

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

Is solution to problem F flow with lowerbound? (and minDegree ≤ sqrt(n))

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

    Well, I think this might pass with some really fast flow algorithm.

    Intended solution is to build the following network: for chosen k, connect the source to every vertex of the first part with edge with capacity d(x) - k (where d(x) is the degree of vertex), then transform every edge of the original graph into a directed edge with capacity 1, and then connect each vertex from the second part to the sink with capacity d(x) - k. Then edges saturated by the maxflow are not present in the answer (and all other edges are in the answer).

    To solve it fastly, we might just iterate on k from its greatest value to 0 and each time augment the flow we found on previous iteration. Since maxflow in the network is at most m, and we will do not more than m searches that don't augment the flow, this solution is quadratic.

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

      But we can just use the same approach (iterating k and use flow from previous step) in flow with lowerbound solution, can't we? (I'm not sure about this)

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

      There's also other solution. Iterate on k from 0 to greatest value and gradually increment the capacity of edges from source/to sink by 1 (so it becomes k in each step). The answer is the saturated edges + any other edges that you choose to make degree[u] < k higher up until k. In other words, the edges from max flow cover 2 vertices and the rest covers just 1 and the answer is k * (n1 + n2) — maxflow.

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

Any idea for test 30 of problem E? I have wrong answer on test 30 T_T

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

Is this approach for E correct?

If you are going to double the health, then all such operations must be done for the same element

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

    Yes, it is.

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

      Do we have to apply the assignment operation on some element more than once in any situation?

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

        No, it doesn't make sense since first spell affects only hp.

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

How to solve C? Binary search?

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

    I solved it with sweep line algorithm and some optimisations.

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

    Sort the segments if starting of any 2 elements is same, they overlap if end of i >= end of i+1, they overlap Check using the given conditions

    Mine passed the prelim cases, lets see how it goes.

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

    You may sort the pairs of {L,R} in non-decreasing L's, if two elements have the same L value, the element with bigger R get the smaller index. By sorting, you can check the R values only (because you are sure that the L value of the current element is bigger than or equal all previous elements) and if you found an R value that is smaller than the previous R value, then you've found the answer (which is the element we are currently at and the one directly before it).

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

    Sort all segments by their left border and keep track of the segment with the greatest right border on prefix. Now when you are considering segment i, all the previous ones have less left border and you only have to check whether the right border on the corresponding prefix is no less that yours.

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

    You can store the pairs as(L,-1*R) and then sort it. Then keep track of the max value of R encountered while traversing the array If maxR >= curR then print both the indices

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

Why can't we in E use the first spell only for one creature? When we are using the first spell it has sense only when hp will be bigger then dmg and if we use the first spell for two creatures then one of the creatures had bigger dmg do we could use first spells from the one with smaller dmg.

If this approach is correct can someone tell me what is wrong with this submit: http://codeforces.com/contest/976/submission/37772123 ?

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

    I think that you compute prefixes before you sort elements.

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

      Oh, You are right. Thx. It's funny that it passed 7 tests.

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

Try to hack my B

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

    Try Yourself first because it is possible to hack your own solution by yourself.

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

How to solve D?

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

How to solve E ?

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

I seem to have gotten the right idea for E but my solution did not pass. I am not able to find the mistake I have made. Can someone please help?

http://codeforces.com/contest/976/submission/37772350

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

    2 1 2 5 3 6 6

    I think that it's not always optimal to choose the one with the biggest difference.

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

    Choosing maximum difference regardless of sum of other values is not optimal

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

    Oh nice! I got it, thanks!

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

Hi to everyone! Could you tell me some tests with marginal situations of E problem?

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

Does somebody know why this submission for E isn't working on test 10?

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

    try this test: 2 1 2 4 1 6 6 answer — 16

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

      Nice! Got it! Thanks for your testcase.

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

why is it that in problem F, calling a maxFlow algorithm for every degree <= minDeg is within time constrains, shouldn't it be O(minDeg*V^2*E) — if we use Dinic for example.

UPD: I think this maybe because the graph can be very sparse, if you have for example all 2000 vertexes on both sides then m = 2000 implies that minDeg <= 1, so only one call to maxFlow will be needed. On the other hand, I think in the worst case minDeg will be O(sqrt(m))

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

When will our ratings take affect?

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

    After Codeforces Round #478 (Div. 2).

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

      So what if somebody were to become Div1 after any of the individual rating changes from the 2 rounds?

      The second one is discarded or how exactly?

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

      How do you know that? Is it believable?

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

when will system testing begin

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

Can somebody tell me will our rating change before round #478? (^:

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

    Most probably yes. They have finished the system testing just now and it is hardly a matter of time that rating changes will start reflecting. Since round 478 is still around 5 hours away so most probably you will be able to participate in div.1 if you have made it to div.1 after system testings.

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

    I hope yes:)

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

    Yes

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

It is system testing now. Why the result has been published?

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

Why http://codeforces.com/contest/976/submission/37757342 got runtime error?

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

    I think, it is because your comp function.

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

      What is wrong with it?

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

        Replace this

        a.second.second < b.second.second

        With this

        a.second.second <= b.second.second

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

          Why this caused runtime error?

          I didn't understood what is the mistake in a.second.second < b.second.second. I don't know what is wrong in my solution which I should not repeat again.

          HELP!!! Anybody?

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

            You replace "less" function with your comp. The requirement for it is such that there can't be both a < b and b < a, it's undefined behavior. And you return true in case of equality.

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

hacked my own friend's solutions hahahaha

EDIT-One of them down voted me :P

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

Educational rounds are really adventurous. Take one full day for hacking. In case ur code survives system testing your anxiety until rating update is there.

by A Div2 Coder

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

When does it rating change? )sorry to my poor English

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

I'm new to cf, can anybody explain me the hacking system.ty in advance.

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

I have a question. I will be candidate master in this round.but rating doesn't change now.if I take part in next round, i am a div1 participant or a div2 participant?

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

    I think it depends on the moment you press "Register". If before rating change, you will be counted as a Div2 participant nonetheless.

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

Nice, about time with the rating changes :)

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

why same code give wa on cf??

https://ideone.com/Ul11qu

http://codeforces.com/contest/976/submission/37800674

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

    Firstly, never use implicit cast but use static_cast instead. Secondly, you cast long long to double which leads to undefined behavior. E.g. the same code gives the correct answer on C++17 compiler. Try to cast it to long double instead.

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

      Why casting long long to double causes undefined behavior ?

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

        To be more precise, it causes implementation defined behavior (depends on the platform and/or compiler version). Nevertheless, double usually has only 53 bits of mantissa, which is not enough to store every long long integer, and you definitely should see a compiler warning if you haven't disabled any. Why implementation defined? Because each compiler acts in a different way. So depending on the compiler version, optimization level and other factors you can get different results, e.g. possible auto-conversion to long double and vice versa.

        → Reply