Привет, Codeforces!
25 марта 2016 года в 16:00 MSK после продолжительного перерыва состоится очередной десятый учебный раунд Educational Codeforces Round 10 для участников из первого и второго дивизионов. Перерыв, конечно же, связан с большой плотностью соревнований и чемпионатов на Codeforces.
<То же, что и было раньше>
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день, в течение которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.
Не стесняйтесь присылать простые (и даже очень простые) задачи (но обязательно интересные). Почти каждый раунд достаточно быстро выбираются кандидаты для задач C, D, E, F, а вот задача A обычно ставится самой последней, когда уже почти всё готово.
</То же, что и было раньше>
Теперь уже традиционно комплект задач был полностью предложен участниками сообщества. Задачу А уже в третий раз предложил пользователь unprost (ну сами понимаете не стоит ждать короткого условия :-)). Задачу B прислал пользователь Smaug. Задача C — ещё одна задача из комплекта, который прислали Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. Задачи D и E были предложены Алексеем Дергуновым dalex. Задачу F ещё давно прислал Lewin Gan Lewin.
Благодарю их и всех кто присылает задачи или просто наброски!
Задачи D и E были подготовлены Алексеем Дергуновым dalex. Остальные задачи подготовил я (Эдвард Давтян). Хочу отметить генератор тестов по задаче E, который я писал примерно столько же, сколько решение задачи F. Спасибо Маше Беловой Delinur за проверку английских текстов условий. Задачи тестировали пользователи unprost, Smaug, Aleksa Plavsic allllekssssa, Алексей Дергунов dalex и Lewin Gan Lewin. Большое им за это спасибо!
На раунде вам по традиции будут предложено шесть задач. Надеюсь они вам понравятся!
P.S.: Мне очень нравится задача F, надеюсь увидеть Accepted-ы по ней.
Good luck and have fun!
UPD: Соревнование закончено. Разбор задач готов.
The time in this announcement may be wrong
In this announcement
In Contest section 
Oh sorry. Fixed now.
On a completely unrelated note : Will my problems ever get considered, since it's been >3 weeks.
Hey. You send me problems after ER9. It's the first round after that. You can be sure that I'll check your problems and try to take them.
P.S.: Note the problems C, D, E, F was sent to me in January and February.
I see, so the queue is really long.
Finally an educational round! Also When will we be having round #346? It has been a while now
Thanks a lot Edvard for all your efforts . Just make the editorials a little detailed for problems D, E and F .
I'll try to make editorials more detailed, but unfortunately you should wait until tomorrow. The programming camp in MIPT will start tomorrow and I'll go to Moscow right after the round.
This guy is using the chair wrong >.<
Did anyone else find the problem C really hard to understand? You didn't specify that (x, y) is a pair of indices. All the time I was thinking that it's a segment of numbers.
Same here. It took me more than one hour to understand the statement. Unfortunately i didn't have time to code after i understood it. In my opinion D was way easier.
No it's very easy, and much easier than D. It's just harder to understand.
No I wasn't confused, but what in heaven in test case 4!!!
Yes! Also A confused me a bit which made me start with D :)
I don't think that .
I found it clear and I started with it :D
Почему нельзя писать дорешку сразу после раунда, как раньше? "Результаты заморожены, зарегистрируйтесь на дорешивание, бла бла бла..." Раньше можно было сразу взять и отправить код, который написал в последние секунды. Сейчас нужно ждать день, что бы просто дорешать задачи? И, кстати, очень интересно услышать идеи на Ешку. Просидел час, пытаясь пропихнуть что-то не сильно умное — не получилось.
А еще взломать никого, кроме себя, не получается
На фазе взломов могут участвовать только те кто участвовали на раунде?
Was the open hacking phase started?
Yeah, "open hacking phase is running: 23:48:14", we simply can't use it :(
Look here http://codeforces.com/contest/652/hacks
Lol, I can't open anyone's code.
except youself..
I dont understand what going on here.Only Code owner hacking their solution.Lol
Please, use correct words in problem statements!
Intervals instead of segments in C confused me a bit.
I cant submit problems nor register for practice in this contest, is that disabled?
Not able to submit solutions after the contest has ended. Clicking on "Register for practice" is not working.
UPD: Registering for a virtual contest is working.
Please try to make good problem statements. A and C lacked too much clearity. Many people lost their points because of that. :)
There is no points in this round)
Points in the sense, their position in this round. I know this is not a rated round, but performance does matter.
Hacking phase has started, but not able to view others' solutions. Please fix it .
Unable to submit code.
how to solve E? it seems less harder than D(how to solve D by the way)
For D,we can sort the intervals by end points.Then for the ith interval to count how many intervals lie completely within it we just need to count how many starting points for the intervals from the 1st to i-1th interval are greater than the starting point of the ith interval. This can be done using a Fenwick tree.
Find all bridges and biconnected components of our graph. The answer is "YES" if there is a "good" edge inside some biconnected component on the unique path from biconnected component containing start, to biconnected component containing end.
It's also yes if a good edge connects 2 components lying on that unique path.
what is biconnected components of our graph? Is it same as Strongly Connected Components? I think SCCs are only defined for Directed Graphs otherwise the definition won't make any sense!
When is the editorial coming up?
An edge is a "bridge" if removing it disconnects our graph. Two vertices are in the same biconnected component if there is a path between them that doesn't use any bridges.
Oh Okay I get it thanks ! I know about bridges but I hadn't heard about Biconnected components! All I need to figure out now is an algorithm to find out BCC.!
you can modify Tarjan algorithm (which find SCC) to find BCC
As far as I know the most widely used definition of biconnected component is that it is an articulation-point-free subgraph (eg see here). Wikipedia calls the components relevant to this problem 2-edge-connected components.
Are you sure about that? In a non-simple cycle, we have no bridges, but we have articulation point. I think you meant articulation point.
You destroy edges when you cross them, not vertices.
I thought you were speaking in general about biconnected components, not just relevant to the problem :) Even if we destroy edges, a biconnected component will still have no articulation point, and bridges will form a separate block. I have just started learning about biconnectivity, so please excuse my mistakes.
Oh, I see the misunderstanding. Yes, I think I was using the wrong terminology here, but we seem to all be on the same page about the actual algorithm. Apologies.
Hi, could you suggest some good readings about biconnected components? I searched but could not find any.
http://codeforces.com/blog/entry/43986
Or if a bridge itself in this path is a "good" edge.
I Can't Open Any One's Code, (Except Mine).Is This Happening To Me Only? :O
No, It's happening to everyone .
Thanks.Now I Just Saw The Announcement :) ..
I have no idea about the russian version but the english version of nearly all problem statements had a lot of grammatical errors.
I solved B,C,D and couldn't get A because I understood that I have to reach the exact height h2 .
I sent a question and they didn't response to it .
Similar thing happened with me. I wasted like 15-20 minutes on A, then did B, C, D, and later came back to A, asked them for explanation of a sample case, but they simply said "Reread statement", so I tried to think up something and did submit, but got hacked later :/
Hacking is going on, but i can't see others code !!! any explanation ???
It's Not Working. They"ll Fix It Soon..
I desperately want to submit a solution but I am unable to do so.should I have to wait another 23 hours??
please help.
Hacking phase was reconfigured. Now it works as expected. Happy hacking!
Помогите разобраться, почему такое решение по D получает TL 15 ? Отсортируем все отрезки по r и начнем их обрабатывать по очереди в порядке сортировки. Пусть у нас текущий отрезок это — (l[i],r[i]).Тогда понятно,что если есть какие-то отрезки которые лежат внутри этого то они встретились раньше этого.Тогда среди уже обработанных отрезков надо найти все которые начинаются позже нашего, то есть все такие j < i: l[i] < l[j] => отрезок j находится внутри i. Это можно сделать set-ом если по окончании обработки отрезка положить его левый конец в set. А все j можно искать upper_bound — ом. Сложность O(nlog(n)). Вот код : 16932603.
distance за линию работает на не-random-access итераторах.
А понял. Не знал об этом. А как "отремонтировать" решение?
Можно заюзать структуру отсюда
Чуть измененный код: 16939677
Есть что-нибудь, что работает за константу?
Стандартные структуры данных не помогут. Самый простой способ — дерево Фенвика. Ну и плюс надо сжать координаты (т.е. сделать чтобы все координаты были от 0 до 2n-1, а конфигурация отрезков не поменялась)
very strange thing happened with D, 5*200000 sized array failed for segment tree (WA on test 16) while 6*200000 gets AC. I always thought 4 times the size is enough :(
The maximum number of distinct points is 2 * 2e5 not 2e5.
oh yeah my bad!
I try to use my test generator but I get "Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]" (I wrote "cout<<endl" at the end). Any ideas?
I think that you print an unnecessary space at the end of your input array.
Thanks, works!
В задаче F ведь просто представим что муравьи проходят друг через друга и все! :)
Кажется, мне кто-то рассказывал, что она была в ШАДе.
I feel I'm the only Idiot who thought there will be a case where I should print "Impossible" in B ..
what would be the answer of A if input is: 500 555 6 1? If answer is 1, how?
Hello man! :) Well first day it climbs from 500 → 548 (6*8) ... in the night, it slips back by 12 (so to 536) third day, it can climb up to 72 (6*12) which is enough :)
that means answer is 0 as it will reach the apple before 2 pm next day ?
exactly! .> "0" is, if it reaches apple during first 8 hours :) [2pm → 10pm]
but in sample test case it gives wrong on "0".
Sorry, not sure what you meant — so I'll try to comment all samples:
A) 10 → 36 (+8*2) → 24 (-12*1) → 48 (+12*2) (== day 1)
B) 10 → 18 (+8*1) (== day 2)
C) a < b && it can't do it during first day (== -1)
D) 1 → 41 (+5*8) → -7 (-12*4) → 53 (+12*5) (== day 1)
okay. Got it!! Thank you for your reply. I did a silly mistake on understanding the question.
Lol in A I assumed boy returns to look exactly at 2pm on any day.
i assumed the day end at 2pm and got +6
I am sorry what do you mean by +6 ? I solved A by taking the snail 4 hours back in time, and so I didn't have to add extra condition for 1st day
Six unsuccessful submissions as I can see :)
ok got it :) Statements were badly written.
I got +5 because of that ! Poor problem statement :)
Is there any tutorial for this round?
I am sure I have solved a similar problem to D somewhere before.
In hacking with generator, what does the text field for generator parameter do? Is it just taking in some constants which we can easily specify within the code itself?
Problem A was very hard to understand for a poor english readers like me.
problem B:
for test case : 5 1 3 2 2 5
my output was 2 2 5 3 1
whats wrong in this? i think 2 conditions already satisfied in this .. please help me
i dont think you understood the question properly the indexing should start from 1. so here 5 at an odd place is greater than 2 which is at an even place which is violating second condition
Post editorial, please or tell me how to solve problem C!
here is the editorial
still not able to realize the solution of problem C after reading the editorial, lol, can anyone help me
Imagine you have intervals i..n for i = 1..n. Also nearest foe pair for this interval is ([j], [k]), were j and k are positions of numbers of the pair in the permutation — this means all intervals inside i..k-1 interval would be the good ones, and all inside k..n would be the bad ones, and you need the good ones to answer
Yes, the statement was quite messy, and I've also spent some time to understand it
In E, I am struggling with proving why we must consider biconnected components, that is, why can't we use more relaxed constraints. Can anyone help me? I mean, we only need to make sure that there is a path between boy and dealer which doesn't use any edge twice, and the artifact edge is also in the path.
By creating a graph that have biconnected components, we have a unique path between the source and the sink. If there were multiple paths to follow, how would you try them all?
Thanks I got it :)
Поясните пожалуйста условие задачи С. Я так и не смог понять его.
Интервал (x,y) это набор (целых) чисел от x до y?
Что значит, что интервал содержит пару? — Он содержит оба числа из пары?
При чем тут перестановка?
И что значит что интервал не является корректным?
Can anyone explain why does a programmer need a headphone as shown in the pic ?
Hello,
A) Not do disturb neighbor, while listening to loud music
B) Not to by disturbed by neighbor, who is listening to loud music
There is
unexpected verdictfor hack 222111 (not mine). Any updates on it?The second solution to that problem worked wrong on that test. It was fixed and hack is rejudged.
It says "ignored" now instead of success or failure.
The solution of dreamoon_love_AA works correct on it. Anyway we add that test to the testset. The test is:
can anyone tell me in the first case of C, why (3,4) is not counted? I think I had great trouble understanding the problem.
Because foes [3,2] are within this interval
I am not able to understand problem C even after reading editorial. Can any one explain in detail?
Good day to you man!
Not sure, whether you missed statement or solution, so:
Statement says, that there is permutation of N numbers and there are pairs of "pointers" to the array. Now the question is "how many sequences are there, which do not include any pair (meaning both pointers of the pair)?".
My solution:
A) I read all pairs [begin,end] and "sorted" them (I used heap) by their ends (minimal first). Begin and end are mapped to array.
B) Now for each beginning of sequence (==index in array), there are as many sequences as number of possible ends of the sequences. The question is, how co count number of possible ends? Well as you have sorted pairs → you end the sequence at any index, which is closer to beginning sequence, than the end of nearest pair, for which it is true, that it begins not sooner, than the beginning of the sequence.
Hmm slightly confusing, isn't it — I'll try to do it once again, so you can choose better explanation (if any of them will be enough)
a) Map permutation to indexes
b) Map pairs to indexes
c) Make pairs as [begin,end]
d) Sort pairs by end first
e) Iterate through every index of array
Complexity O(Nlog(N))
Can someone give me some problems like this E, please?
Doing some reading on biconnectivity, 2-connectivity, 2-edge-connectivity (quite confusing) for problem E, when I came across this line on wikipedia
Is it true for directed graphs only, or also for undirected graphs as well. I can't find a case where this can be true for undirected graph. Please help :)
This graph contains such an edge:
Image
Ah yes! Thank you :)