Привет, Codeforces!
30 апреля в 17:35 по Москве начнётся Educational Codeforces Round 43.
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной готовили Михаил awoo Пикляев, Роман Roms Глазов и Адилбек adedalic Далабаев.
Также мы хотим поблагодарить Ивана BledDest Андросова и Максима Neon Мещерякова за помощь в подготовке раунда.
Удачи в раунде! Успешных решений!
UPD: Раунд будет содержать 6 задач вместо 7.
UPD2: Опбликован разбор
Поздравляем победителей:
| 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 |
Поздравляем лучших взломщиков:
| 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 успешных взломов и 656 неудачных взломов!
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| 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 |
100000!!!
http://codeforces.com/contests/100000
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.
Because, after 967 comes 100000!!! joke ;)
Technically, I don't understand the joke.
Maybe it has to do with codeforces 1000th(binary) anniversary? Although there are more zeroes than that :)
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.
But last rounds ID was 967 :)
Why contest http://codeforces.com/contest/967 is not showing rates? How long do I need to wait ?
Be patient.
You can always use CF Predictor.
http://codeforces.com/blog/entry/50411
Thx for sharing. I've found a gate toward a new world :D
Codeforces contests come at once
So many contests recently, thank you codeforces!
!!!
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 :)
Why CF have this tendention to increase number of tasks in 2 hour contests?
Educational rounds have been usually consist of 6-7 problems, pal.
Happiness is having codeforces round in 3 consecutive days. :D
Thanks a lot to the Codeforces team and the authors. :D
Hi! Why isn't the round appearing in the contests page? (as well as in the "Pay attention" tab)
EDIT: Fixed!
Seems it's back now!
Is it rated ( ͡° ͜ʖ ͡°)
anyone knows that if you say "is it rated?" you won't get positive vote no longer.
Mark, You should add a button called
Report 'is it rated' comment. Please. We need itYou are just jealous that my contrib is higher than yours.
good for you.
Wish u lots of Heck(Hack)!!
Ha Ha Ha These hacks are useless for rating!!
Unless if you got hacked. Then it will suffer your rating
But it is fun to hack other's solutions. :D
Yea Also showing talent to the defender. :D :D
Solve the problem and leave the hacking to halyavin
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!!
But it's the most normal time...
5 min delay
5 min delay! :3
Contest delays.
What the crap is with this 5 min delay ?!?!?! And yes, when the initial timer ran out CodeForces did freeze for me
How to solve D?
west book : 1.3.65 :)
What's that supposed to mean?
here is the solution , this is a problem from West book , problem 1.3.65
This problem was also proposed in EGMO 2017.
See https://artofproblemsolving.com/community/c6h1425420p8029369
Thanks!!
yw :)
Hey can you please tell me how to get this book/app?
here you are ...
Alright. Thank you :)
What is the exact name of the Book?
Priest OTK main, but cant solved E problem :)
Any idea of test 5 about E?
My solution was failed on 5. Possible test case :
2 2 1
10 15
6 1
Answer should be 41
В задаче F используется алгоритм потока с ограничениями?
Any idea for test 10 in E?
Please tell me what is the wrong in my code.
2 1 2
7 3
6 1
Answer is 20 right? This isn't the test case.
My submission gives: 20
Which I think is the correct answer for the above test
try this:
2 1 2
12 4
11 1
Is solution to problem F flow with lowerbound? (and minDegree ≤ sqrt(n))
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.
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)
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.
Any idea for test 30 of problem E? I have wrong answer on test 30 T_T
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
Yes, it is.
Do we have to apply the assignment operation on some element more than once in any situation?
No, it doesn't make sense since first spell affects only hp.
How to solve C? Binary search?
I solved it with sweep line algorithm and some optimisations.
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.
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).
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.
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
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 ?
I think that you compute prefixes before you sort elements.
Oh, You are right. Thx. It's funny that it passed 7 tests.
Try to hack my B
Try Yourself first because it is possible to hack your own solution by yourself.
How to solve D?
How to solve E ?
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
2 1 2 5 3 6 6
I think that it's not always optimal to choose the one with the biggest difference.
Choosing maximum difference regardless of sum of other values is not optimal
Oh nice! I got it, thanks!
Hi to everyone! Could you tell me some tests with marginal situations of E problem?
Check this test. My solution failed on this :( http://codeforces.com/blog/entry/59163?#comment-427552.
The one in reply section
35?
Yes
3 1 2
10 7
10 6
9 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
Does somebody know why this submission for E isn't working on test 10?
try this test: 2 1 2 4 1 6 6 answer — 16
Nice! Got it! Thanks for your testcase.
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))
When will our ratings take affect?
After Codeforces Round #478 (Div. 2).
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?
How do you know that? Is it believable?
when will system testing begin
Can somebody tell me will our rating change before round #478? (^:
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.
I hope yes:)
i hope yes too눈_눈
Yes
It is system testing now. Why the result has been published?
Why http://codeforces.com/contest/976/submission/37757342 got runtime error?
I think, it is because your comp function.
What is wrong with it?
Replace this
a.second.second < b.second.second
With this
a.second.second <= b.second.second
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?
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.
Got it! Thank you.
http://codeforces.com/contest/976/submission/37770261
in my solution also samething happened..can you explain it why??
I couldnt get exactly why it is creating problem.
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.
so we shouldn't show such one way behaviour in compare function
but even then cmpr(a, b) = cmpr(b, a) = false..wouldnt this be problem
Nope. This is what I understood from PikMike's comment and this link.
For all a, comp(a,a)==false
Где разбор?
Спасибо авторам за задачи :) Особенно приятно было читать условие задачи E, вспомнилась механика одной очень хорошей игры :D
hacked my own friend's solutions hahahaha
EDIT-One of them down voted me :P
xD
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
When does it rating change? )sorry to my poor English
I'm new to cf, can anybody explain me the hacking system.ty in advance.
http://codeforces.com/blog/entry/6249
что случилось? почему рейтинг не обновляют?
Мне вот интересно, что будет с теми, кто наберет 1900+ и перескочит в Div1, но уже зарегистрирован на раунд 478 (Div2 only). Может решают эту проблему?
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?
I think it depends on the moment you press "Register". If before rating change, you will be counted as a Div2 participant nonetheless.
Nice, about time with the rating changes :)
why same code give wa on cf??
https://ideone.com/Ul11qu
http://codeforces.com/contest/976/submission/37800674
Firstly, never use implicit cast but use
static_castinstead. Secondly, you castlong longtodoublewhich leads to undefined behavior. E.g. the same code gives the correct answer on C++17 compiler. Try to cast it tolong doubleinstead.Why casting long long to double causes undefined behavior ?
To be more precise, it causes implementation defined behavior (depends on the platform and/or compiler version). Nevertheless,
doubleusually has only 53 bits of mantissa, which is not enough to store everylong longinteger, 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 tolong doubleand vice versa.Отличные задачи!