Всем привет!
Вот и пришло время очередного, уже 80-го по счёту раунда на Codeforces.
Контест готовили: Alex_KPR, winger, RAD, Connector, it4.kp. Надеюсь, что всё пройдёт гладко, и всем понравятся задачи про пробуждение Ктулху, ограбление корована, унылость штанов шахтёра и, конечно же, про очаровашку Хексадесимал.
Кстати, Connector сегодня отмечает свой день варенья — давайте дружно его поздравим с праздником! =)
Всем удачи и приятного времяпрепровождения!
_____________________________________
Спасибо всем за участие! =)
Подведём итоги раунда. В первую десятку в первом дивизионе вошли:
Место | Кто |
1 | SergeiRogulenko |
2 | hos.lyric |
3 | Romka |
4 | neal |
5 | sdya |
6 | KADR |
7 | ftiasch |
8 | niyaznigmatul |
9 | dolphinigle |
10 | AleX |
Стоит отметить, что с задачей E справилось всего двое: победитель раунда SergeiRogulenko, и MBabin, занявший 76-е место.
Первые три места во втором дивизионе заняли:
Поздравляем победителей и желаем всем удачи в следующем раунде!
Официальный разбор будет опубликован позднее. Стоит отметить, что AlexanderBolshakov уже опубликовал свой разбор на страницах Codeforces.
Спасибо Delinur за перевод условий на английский язык!
_____________________________________
Опубликован разбор.
Мне кажется не совсем правильным, что если авторов контеста много, то в основном прирост к вкладу получает только тот, кто опубликовал в блоге приглашение на этот раунд.
Поэтому предлагаю каждому из авторов написать что нить в этом треде, чтобы те, кто уважают труд авторов могли бы хотя бы плюсуя его пост выразить благодарность в более наглядном способе.
Сарказм? Если по делу, то вот почему в лидерах по вкладу it4.kp не видно?
А он участвовал наверно не в одном десятке соревнований. Не справедливо.
Codeforces Beta Round #9
Codeforces Beta Round #58
Codeforces Beta Round #69
В этот раз было уделено много внимания именно условиям. На мой взгляд они весьма понятные =)
PS Спасибо всем за поздравления =)
Макар, жизнь измеряется не количеством сделанных вдохов и выдохов, а количеством тех моментов, когда от счастья захватывает дух. Пусть у тебя будет этих моментов, как n в цикле:
while (2>1){
n+=1;
}
можно выкрутиться
int n=0;
while(true){
++n;
if(false) break;
}
out.print(":)");
Так и жизнь - полоса белая - полоса чёрная... :D
..Happy Birthday .~
Item 6.
If some people break the few rules we have here for communication, that's not a valid reason to break them too.
I think it is impolite at all to write in Russian anything while here is kept _international_ contest. Especially in the topic about this contest.
All foreigners would spent their time trying to check with google-translator whether all these Russian guys are discussing contest problems or chatting about something else...
Хорошие задачи. Приятно видеть, что и условия "укоротились" ;-)
Что за весьма короткое по записи решение задачи C для div 2. Я в своём такого "навоял", аж стыдно.
Граф Ктулховидный, если он связный и в нем ровно 1 цикл (т.е. количество ребер равно количеству вершин). Разумеется, речь идет о тех графах, которые разрешены условием (без петель и прочей ереси).
Следовательно, все решение - в одном обходе графа.
Вот допустим есть такой граф:
5 6
1 2
2 3
1 3
2 4
4 5
3 5.
В нем много разных циклов есть.
Если мы удалим некоторые из них (например 1-2-3-1), то граф всё равно не будет ктулховским, т.к. циклов то не будет, но будет путь 2-4-5-3, что вроде не хорошо.
Поэтому можно по-подробнее про нахождение цикла?
Такой граф отсеивается уже тем условием, что в нем ребер больше, чем вершин.
Предположим, у нас есть дерево. В нем ребер на 1 меньше, чем вершин. Добавление ребра между любой парой уже существующих вершин создаст в графе 1 цикл. Теперь можем сказать, что перед нам - Ктулху. Каждая вершина цикла будет корнем дерева (возможно, из одной вершини), и все они соединены этим циклом.
А если добавить еще хоть одно ребро, то появятся лишние циклы.
Ну а связность проверяем, чтоб отбросить случай, когда есть несколько компонент, в каждой из которых "что-то лишнее" - за счет удаленных мостов между компонентами.
|
6
|
4--\
| |
1 |
| |
5--/
|
2
Это Ктулху из 1-го примера, или я ошибаюсь? Как сосчитать 3 (или более) корневых дерева растущих на цикле?
Получилось... ну не то чтобы сильно мало, но и не сказать, что сильно много.
UPD: А, пардон, для div2...
Завещаю будущим поколениям учиться планировать время контеста и не повторять моих ошибок.Его решение и до этого часа выглядело не хуже)
А планировать контест - целое искусство. Сам хотел бы научиться этому.
It was such an interesting contest. The guy called Cthulhu was funny :) Good job! Thanks to the organizers. Keep up the good work :)
I think there are too many things that could be improved in Codeforces. Some Div 2 coders are really good and rating system is really strange.
One thing that I would like to see very much is the problem statistics. For example, after each problem they could post the percentage or number of with verdicts "failed pretest" , "hacked", "failed system tests", and "accepted", not only the number of accepted submissions.
I tried espr1t's approach with buckets .. useful to me at least! :)
.. but it fails on example 8.
Unfortunately I can't reproduce the error, the list of values in the input is truncated.
It's correct on several random examples with either b smaller or larger than sqrt(N).
link to the C++code.
I wonder why it's incorrect. Does anyone see? Thanks a lot for your help!
Update: Example 8 is the only one which fails. I added a condition to treat it separately with the naive algorithm, and that passes the tests now.
1. First find if the graph has a cycle. If not return NO.
2. Now try removing a edge each time, and run a bfs to see if there is no cycle anymore. If there is no cycle anymore, try to find the nodes between the two nodes for which you removed the edge. There are our possible roots for the rooted trees. Check if indeed these are roots. If no return NO, else return FHTAGN.
Is there a better approach then this ?
else return NO
Having performed it you just check that only one loop was found and that the graph is connected.
However, m = n check is surely more elegant way :)
This graph has a single cycle and every vertices connected...if yes than FHTAGN else NO.
I did this through DFS.
поставим 1 патрон в крайнюю правую позицию(либо в любую другую и сделаем циклический сдвиг)
.........X
теперь рассмотрим циклические сдвиги барабана, которые являются для нас проигрышными
.-.-.-.-.X
если мы поставим в такие клетки патроны - нам от этого хуже не станет(шансы не изменятся)
т.е. можно смело превращать в вид
.X.X.X.X.X
дальше, каждый засунутый патрон уменьшает наши шансы, т.е. можно ставить в любые клетки
но т.к. нам нужна лексографически минимальная строка, то ставим их в конец этой строки
.X.X.XXXXX
по сути надо рассмотреть несколько случаев (четность/нечетность n, четность/нечетность k)
Ну можно например написать генератор прямо в решение. Сложность и время работы от этого должно пострадать очень не сильно. Я понимаю, что вы можете парировать тем, что это не дело. Я лишь предложил как вариант.
Both configurations give you the same change of surviving, but "...XX" is lexc. smaller.
I am from China.Happy birthday,connector.
生日快乐！
I have a suggestion that the popped-up window is too small when viewing others' source code during hacking and the source font is not suitable enough.I think the font "New Courier" is better.
Since I can't delete my comment, just smile for your attention :)
I have a suggestion that the window popped-up is too small when viewing others' sources during hacking and the source font is not suitable enough.I think the font "New Courier" is better.