By vovuh, history, 3 years ago, translation,

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 saw.ai 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
D dotorya 0:26
E djq_cpp 0:21

• +176

 » 3 years ago, # | ← Rev. 3 →   +44
•  » » 3 years ago, # ^ | ← Rev. 2 →   -9 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.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   -28 Because, after 967 comes 100000!!! joke ;)
•  » » » » 3 years ago, # ^ |   +1 Technically, I don't understand the joke.
•  » » » 3 years ago, # ^ |   +8 Maybe it has to do with codeforces 1000th(binary) anniversary? Although there are more zeroes than that :)
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 According to your theory, this contest will be filled with the number 32 everywhere I guess :DUPD: Round ID changed to 976 now. So perhaps it was a test or something.
•  » » » 3 years ago, # ^ |   +5 But last rounds ID was 967 :)
 » 3 years ago, # |   0 Why contest http://codeforces.com/contest/967 is not showing rates? How long do I need to wait ?
•  » » 3 years ago, # ^ |   +11 Be patient.
•  » » 3 years ago, # ^ |   +17 You can always use CF Predictor.http://codeforces.com/blog/entry/50411
•  » » » 3 years ago, # ^ |   0 Thx for sharing. I've found a gate toward a new world :D
 » 3 years ago, # | ← Rev. 2 →   +1 Codeforces contests come at once
 » 3 years ago, # |   +18 So many contests recently, thank you codeforces!
 » 3 years ago, # |   +7 !!!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 :)
 » 3 years ago, # |   0 Why CF have this tendention to increase number of tasks in 2 hour contests?
•  » » 3 years ago, # ^ |   +2 Educational rounds have been usually consist of 6-7 problems, pal.
 » 3 years ago, # |   +6 Happiness is having codeforces round in 3 consecutive days. :DThanks a lot to the Codeforces team and the authors. :D
 » 3 years ago, # | ← Rev. 3 →   +11 Hi! Why isn't the round appearing in the contests page? (as well as in the "Pay attention" tab)EDIT: Fixed!
•  » » 3 years ago, # ^ |   +2 Seems it's back now!
 » 3 years ago, # |   -100 Is it rated ( ͡° ͜ʖ ͡°)
•  » » 3 years ago, # ^ |   -14 anyone knows that if you say "is it rated?" you won't get positive vote no longer.
•  » » 3 years ago, # ^ |   +20 Mark, You should add a button called Report 'is it rated' comment. Please. We need it
•  » » » 3 years ago, # ^ |   -16 You are just jealous that my contrib is higher than yours.
•  » » » » 3 years ago, # ^ |   0 good for you.
 » 3 years ago, # |   0 Wish u lots of Heck(Hack)!!
•  » » 3 years ago, # ^ |   +13 Ha Ha Ha These hacks are useless for rating!!
•  » » » 3 years ago, # ^ |   +9 Unless if you got hacked. Then it will suffer your rating
•  » » » » 3 years ago, # ^ |   -9 Unless u r div2 (ofc)
•  » » » 3 years ago, # ^ |   +6 But it is fun to hack other's solutions. :D
•  » » » » 3 years ago, # ^ |   +4 Yea Also showing talent to the defender. :D :D
•  » » 3 years ago, # ^ |   +70 Solve the problem and leave the hacking to halyavin
 » 3 years ago, # |   +27 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!!
•  » » 3 years ago, # ^ |   +27 But it's the most normal time...
 » 3 years ago, # |   +15 5 min delay
 » 3 years ago, # |   0 5 min delay! :3
 » 3 years ago, # | ← Rev. 2 →   +5 Contest delays.
 » 3 years ago, # |   +4 What the crap is with this 5 min delay ?!?!?! And yes, when the initial timer ran out CodeForces did freeze for me
 » 3 years ago, # |   +26 How to solve D?
•  » » 3 years ago, # ^ |   +20 west book : 1.3.65 :)
•  » » » 3 years ago, # ^ |   +1 What's that supposed to mean?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +28
•  » » » » » 3 years ago, # ^ |   +4 This problem was also proposed in EGMO 2017.
•  » » » 3 years ago, # ^ |   +5 Thanks!!
•  » » » » 3 years ago, # ^ |   0 yw :)
•  » » » » » 3 years ago, # ^ |   0 Hey can you please tell me how to get this book/app?
•  » » » » » » 3 years ago, # ^ |   +6
•  » » » » » » » 3 years ago, # ^ |   0 Alright. Thank you :)
•  » » » » » 3 years ago, # ^ |   0 why same code give wa on cf??https://ideone.com/Ul11quhttp://codeforces.com/contest/976/submission/37800674
•  » » » 16 months ago, # ^ |   0 What is the exact name of the Book?
 » 3 years ago, # |   +4 Any idea of test 5 about E?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 My solution was failed on 5. Possible test case :2 2 110 156 1Answer should be 41
 » 3 years ago, # | ← Rev. 3 →   +39 Any idea for test 10 in E?Please tell me what is the wrong in my code.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 2 1 27 36 1
•  » » » 3 years ago, # ^ |   0 Answer is 20 right? This isn't the test case.
•  » » » 3 years ago, # ^ |   0 My submission gives: 20Which I think is the correct answer for the above test
•  » » » » 3 years ago, # ^ |   +16 try this:2 1 212 411 1
 » 3 years ago, # | ← Rev. 2 →   +3 Is solution to problem F flow with lowerbound? (and minDegree ≤ sqrt(n))
•  » » 3 years ago, # ^ |   +5 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 Any idea for test 30 of problem E? I have wrong answer on test 30 T_T
 » 3 years ago, # |   +25 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
•  » » 3 years ago, # ^ |   +17 Yes, it is.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 Do we have to apply the assignment operation on some element more than once in any situation?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 No, it doesn't make sense since first spell affects only hp.
 » 3 years ago, # |   +1 How to solve C? Binary search?
•  » » 3 years ago, # ^ |   +1 I solved it with sweep line algorithm and some optimisations.
•  » » 3 years ago, # ^ |   +3 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 conditionsMine passed the prelim cases, lets see how it goes.
•  » » 3 years ago, # ^ |   0 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).
•  » » 3 years ago, # ^ |   +8 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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
 » 3 years ago, # | ← Rev. 2 →   +10 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 ?
•  » » 3 years ago, # ^ |   +6 I think that you compute prefixes before you sort elements.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +16 Oh, You are right. Thx. It's funny that it passed 7 tests.
 » 3 years ago, # |   0 Try to hack my B
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 Try Yourself first because it is possible to hack your own solution by yourself.
 » 3 years ago, # |   +4 How to solve D?
 » 3 years ago, # |   +3 How to solve E ?
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 2 1 2 5 3 6 6I think that it's not always optimal to choose the one with the biggest difference.
•  » » 3 years ago, # ^ |   0 Choosing maximum difference regardless of sum of other values is not optimal
•  » » 3 years ago, # ^ |   0 Oh nice! I got it, thanks!
 » 3 years ago, # |   +6 Hi to everyone! Could you tell me some tests with marginal situations of E problem?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Check this test. My solution failed on this :( http://codeforces.com/blog/entry/59163?#comment-427552.The one in reply section
•  » » » 3 years ago, # ^ |   0 35?
•  » » » » 3 years ago, # ^ |   0 Yes
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 3 1 210 710 69 5 (ans = 36) I had an issue because I was finding the best creature to use the As on as the creature such that power after A — (max of hp and atk) was maximal. However, in that case, 10 7 and 10 6 are treated the same but they really shouldn't be
 » 3 years ago, # |   0 Does somebody know why this submission for E isn't working on test 10?
•  » » 3 years ago, # ^ |   +18 try this test: 2 1 2 4 1 6 6 answer — 16
•  » » » 3 years ago, # ^ |   0 Nice! Got it! Thanks for your testcase.
 » 3 years ago, # | ← Rev. 2 →   0 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))
 » 3 years ago, # |   +13 When will our ratings take affect?
•  » » 3 years ago, # ^ |   -12 After Codeforces Round #478 (Div. 2).
•  » » » 3 years ago, # ^ |   +16 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?
•  » » » 3 years ago, # ^ |   +4 How do you know that? Is it believable?
 » 3 years ago, # |   +15 when will system testing begin
 » 3 years ago, # |   +18 Can somebody tell me will our rating change before round #478? (^:
•  » » 3 years ago, # ^ |   +2 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.
•  » » 3 years ago, # ^ |   +3 I hope yes:)
•  » » » 3 years ago, # ^ |   0 i hope yes too눈_눈
•  » » 3 years ago, # ^ |   0 Yes
 » 3 years ago, # |   +28 It is system testing now. Why the result has been published?
 » 3 years ago, # |   0 Why http://codeforces.com/contest/976/submission/37757342 got runtime error?
•  » » 3 years ago, # ^ |   0 I think, it is because your comp function.
•  » » » 3 years ago, # ^ |   0 What is wrong with it?
•  » » » » 3 years ago, # ^ |   0 Replace thisa.second.second < b.second.secondWith thisa.second.second <= b.second.second
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » » 3 years ago, # ^ |   +7 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.
•  » » » » » » » 3 years ago, # ^ |   0 Got it! Thank you.
•  » » » » » » » » 3 years ago, # ^ |   0 http://codeforces.com/contest/976/submission/37770261in my solution also samething happened..can you explain it why??I couldnt get exactly why it is creating problem.
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 See this.... This will clarify your doubt.If node a is 2 4 and node b is also 2 4, then your cmpr(a, b) = cmpr(b, a) = true, which is undefined behavior.
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 so we shouldn't show such one way behaviour in compare function
•  » » » » » » » » » 3 years ago, # ^ |   0 but even then cmpr(a, b) = cmpr(b, a) = false..wouldnt this be problem
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Nope. This is what I understood from PikMike's comment and this link. For all a, comp(a,a)==false
 » 3 years ago, # | ← Rev. 3 →   +16 hacked my own friend's solutions hahahahaEDIT-One of them down voted me :P
•  » » 3 years ago, # ^ |   0 xD
 » 3 years ago, # |   +11 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
 » 3 years ago, # |   +1 When does it rating change? )sorry to my poor English
 » 3 years ago, # |   0 I'm new to cf, can anybody explain me the hacking system.ty in advance.
•  » » 3 years ago, # ^ |   +3
 » 3 years ago, # |   +12 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?
•  » » 3 years ago, # ^ |   0 I think it depends on the moment you press "Register". If before rating change, you will be counted as a Div2 participant nonetheless.
 » 3 years ago, # | ← Rev. 2 →   0 Nice, about time with the rating changes :)
 » 3 years ago, # | ← Rev. 2 →   0 why same code give wa on cf??https://ideone.com/Ul11quhttp://codeforces.com/contest/976/submission/37800674
•  » » 3 years ago, # ^ |   +3 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.
•  » » » 3 years ago, # ^ |   0 Thanks a lot, @mtropets. You saved my life :D
•  » » » 3 years ago, # ^ |   0 Why casting long long to double causes undefined behavior ?
•  » » » » 3 years ago, # ^ |   0 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.