Добрый день!
Мы успешно пережили уже две недели нового семестра и рады поприветствовать вас на очередном рейтинговом раунде Codeforces для участников Div. 2. В нем как всегда могут принять участие все желающие.
Этот раунд подготовлен командой из трех человек: Gerald, NALP и Polichka. Мы благодарим за помощь в подготовке раунда и переводе задач Артема Рахова (RAD), Михаила Мирзаянова (MikeMirzayanov) и Марию Белову (Delinur).
Сегодня Петя запутался в таблицах:-( И вы можете помочь ему! Это же так просто!
Распределение баллов по задачам следующее: 500-1000-1500-2500-2500
Всем легких решений и высокого рейтинга!
UPD:
Всем спасибо за участие!
Разбор задач доступен по ссылке: Разбор задач
будем надеяться
А когда там был последний unrated? Я так уже и не помню. Так что не надо авторов укорять :)
где вы видите укор? вообще плохого ничего не имел ввиду
Возможно, я неправильно понял.
Но тогда зачем было вообще о своих надеждах писать? Все стабильно же.
ну наверное вы правы, спорить не буду
вспомнилось с баша
xxx: Маленький Петя очень любит подарки. Его мама подарила ему на день рождения две строки равной длины, состоящие из больших и маленьких букв латинского алфавита. Теперь Петя хочет сравнить эти строки лексикографически. Помогите Пете выполнить сравнение. (facepalm)
yyy: Помогите Пете не закончить жизнь суицидом :D
из этих авторов так и прут контесты :)
Это лучше, чем когда ни из кого ничего не прет :)
безусловно :)
я смотрю, теперь можно зафейворить комментарии, и кнопку "ответить" переместили, интересно :)
Странно, что это работает в "безопасном режиме"
хм, вот только интересно, где это "Избранное" можно просмотреть)
только что можно было в профиле, в "блог" вкладке, сейчас уже нет
В профиле есть вкладка : "Избранное".
Да и кнопку "Ответить" в адекватное место перенесли :)
только почему то теперь она наползает на коммент — например мой первый коммент в этой теме
Хром 17, Убунту 11.10, ничего не наползает
У меня не наползает. Win XP Chrome 17.0.963.56
понятно, снова опера ущербная... достала уже
думаю, не стоит разводить холиваров
Никто и не разводит...
Наверно это больше не Опера ущербная, а сайт ущербный... У дива "Ответить" прописан стиль "position: relative; top: -2em;", так что Вы хотите? Наверно так задумано :)
У меня наползает. Firefox 10, Win 7.
Тоже наползает Win7 Хром 16.0.912.77m (правда хром щас вовсю предлагает перезагрузить его в связи с установкой обновлений)
После перезагрузки перестало наползать
Наползает. Firefox 10, Xubuntu 11.10
Что-то мне кажется что эта функция должна была появиться не сейчас :) А сейчас она открылась непреднамеренно в связи с ребутом сервера или что-то в этом роде..
Good luck to everybody :)
if it is Easy for all , it is not easy for anybody ! :P
предупреждение про лонги в Си++ невозможно не заметить :) Но нужно ли это другим кодерам, например на Яве?
Про уехавшую вниз кнопку Ответить вроде уже писали.
По D как минимум 15 штук.
А первые три (B и C) задачи зачем так сильно затыкать?
Не знаю, не спрашивал.
Кстати, по-моему B и C — две задачи, а не три :)
Имеется в виду "в особенности B и C".
Радоваться надо, по-моему
Ну это смотря кому. Взломы — неотъемлеммая часть codeforces. Считаю, что не надо так претесты загибать по большинству задач.
А от просматривания кучи странного кода по D или от поиска ошибки в A удовольствие ниже среднего.
Все задачи про поле n на m ))
Возможно, причина в этом?
Сегодня Петя запутался в таблицах:-( И вы можете помочь ему! Это же так просто!
good luck
Участник Jolin: задачи D и E сданы в подозрительное время.
действительно странно. а может, он просто хотел народ повеселить? типа, хоп, и в топе оказался))
Честно говоря, сомневаюсь :)
I hope C won't be tricky!
В последней поток?
Очень похожую задачу видел на одном сайте в разделе "ДП по профилю".
Согласен, что ограничения намекают, но идея с потоком минимальной стоимости кажется очевидной.
Все так же очевиден поток или в разборе просто наврали, а я ошибся? =)
Я, похоже, умею делать с помощью Флойда + мин. ост. дерева
Можно поподробней? Что есть ребрами, а что вершинами?
Сначала флойдом считаем из любой клетки в любую, цена для x -> y — количество цветов в y, потом на данных важных клетках строим дерево, для них рёбра — минимальные расстояния между ними после флойда. Наверное, как-то так.
Та не....такое упадет 100%
А что вы будете делать, если ребра будут пересекаться?..Сам думал над таким решением.
Скорее всего ребра будут только единичными и не будут пересекаться, как я понимаю.
Если рёбра пересекаются, то это уже не минимальное дерево.
Если бы стоимость в клетках была одинаковая, то вы были бы правы, но в случае данной задаче может случиться такое, что ребра могут пересекаться..Может я не так понимаю вашу идею. Расскажите, пожалуйста, ее подробнее.
UPD: я правильно понял вашу идею. С ней будет такая проблема, которую я описал.
у меня ва2 подобное получает)
какие рёбра конкретно будут пересекаться? приведите пример, пожалуйста.
3 3
100 100 100
100 1 100
100 100 100
3
1 2
3 2
2 1
Насколько я понимаю, точка (2,2) будет учитываться 2 раза. Поправьте меня, если это не так. P.S : как сделать перевод строки?
<br />
А что мешает аккуратно вносить участки в ответ, дабы не было повторений? Суть ошибки "будут пересечения" в том, что можно найти легкие ребра, которые не будут пересекаться и внести их в ответ, хотя на самом деле нужно внести два ребра, которые немного тяжелее, но, благодаря тому, что они пересекаются, потери получаются меньше.
А как вы предлагаете все это реализовать?
не понимаю, почему; в дереве будут следующие рёбра: между первой важной и второй (это гипотетическое ребро, появится после работы флойда) и между первой и третьей (также гипотетическое).
It was my first contest , I really enjoyed it :)
1 час 21 мин 8 сек искал ошибку в коде: перепутал n и m =)
Хороший тур я аж растерялся сначала)
Оп, еще один такой же, как я) Тоже минут 15 искал эту багу :\
На чем ломали в А?
На банальных опечатках по сути. Я ломанул на том, что человек неправильно находил максимум в столбце.
Я ломал на том, что участник находил не максимум, а минимум :)
Кто там говорил про жесткие претесты? Оо
Ну..во 2-ой и 3-ей задаче были действительно сильные претесты.
To the team of three writers: you guys are really productive. Thank you all.
Спасибо за контест!) одинаковыe решения: 1212025 1212192 :( всю статистику портят..
а, ну тогда с этим сударем все ясно
А Вы надеялись, что это реальная Jolin Tsai? ;)
кто знает)
Ещё и не прошли.
I think that C was easier than B :-/
I realized too late, that result for B is bigger than long (I'm dumb, message "Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator." in statement didn't help me too) :-/
I think they both are easy.
I'm not telling that they are not easy, but I think that it is more difficult to implement B than C — I used one loop and 7 conditions in B and just 4 loops without any condition in C (I do not like line metric).
"easy-ness" is a relative term btw.
That's why I wrote "I think...", it's just my opinion. Opinion of problem writers is clearly different. I just wanted to let them and others to know, nothing more, nothing less...
Cool.:D
but still u need some combinatorics to solve C
I don't think so, or maybe it's so trivial that I do not consider it as combinatorics, because it is such straight...
Yeah, of course C was easier than B, that's why some people submited it before B.
I failed here, because when I saw C first time, I didn't see it's ease.
So I submit it after debugging B and lost loads of points :(
Same here. I saw that coders are submiting C, but when I read the statement, I didn't see the solution in the moment.
500-1000-1000-2500-2500 would be better.
раунд был написан неудачно.. почему я такой невнимательный..
Поддерживаю на все 100, та же проблема. Хоть надеюсь, что регулярное участие в контестах научит все-таки этой мудрости — внимательности. Потому что путать n с m и не видеть простейшее решение задачи, которое пишется за 2-3 минуты это не есть гуд.
точно точно
Всё таки такие D и E не решаемы для Div2. По крайней мере, D можно было и попроще сделать.
Да. Я решил первые три задачи примерно за 25 минут, остальное время пытался решить D, но безуспешно.
А ты Div1, что уж говорить о нас))
Я стал Div.1 только что, после этого раунда(до этого был синим).
понятно))) С почином. Жаль, я не воспользовался возможностью хорошо подняться.
I made an unsuccessful hack to this code thanks to lack of syntax highlighter in the hacking window. :(
Yeah, it really sucks that there is no syntax highlighting while hacking...
On the other hand in last TC SRM my unseccessful challenge was because I missed that small L is same as 1 (and there is highlighting, but not for this case) :-/
Стандартный вопрос: когда будет разбор? upd уже есть
у этих ребят он обычно сразу появляется.
The problem D only 5 AC during this 2 hours! :O
I think, maybe it's not difficult to solve the problem D , but it's hard to understand it's meaning. ( Maybe I have a big problem with English — -.)
Problem D: I thought it to solve like this, is it correct:
Find x number of potential vertical lines, and y number of horizontal lines. if x > 4 or y > 4 , return "NO"; else proceed as: take C(x,2) * C(y,2) possible combinations of those lines and test whether these lines can be part of frames in O(n^2) .
Overall complexity : C(4,2) * C(4,2) * O(n^2) .
The number of the potential vertical (or horizontal) lines can be more than 4, even if the answer is "YES".
For example: ('x' instead of '#' because of Markdown)
5 5
xxxxx
xxxxx
xx.xx
xxxxx
xxxxx
Here only 4 potentials are there. (Those having atleast 3 consecutive X)
May be my algo. is wrong, can there be more than 4 potential lines?
what about that:
****
****
****
****
****
****
answer is "yes"
Oh, yeah. My algo is wrong.
In this case we can check both rows and columns, if answer is yes then I think either rows or columns will have at most 4 lines containing potential sides, so that it can be rotated 90 degrees and solved in the same way.
Test for two rectangles could be done in O(n+m) with preprocessing O(n*m), since two following conditions seems to be enough:
1. all of points in rectangles are in our table [O(n+m)];
2. perimeter of rectangles' union equals to amount of #s in table [O(1)].
Контест превратился в гонку кодеров, кто быстрее запрогает 3 халявы — A,B и C. А с учётом того, что я опоздал на час, я был заведомо выключен из этой гонки))
Вот действительно; такая халява, а я почему-то даже не думал о скорости.
Сдается мне, джентельмены, это была комеди^W, э-ээ, кхм, по-моему, раунд был немного несбалансирован.
Похоже на то. Думаю, можно было убрать первую, добавить гроб и получился бы Див1 неплохой.
По-моему, не очень. Для Див-1 это было где-то как 250, 500, 750, 2000, 2000. Нормальной С div1 среди этих задач вроде нет. Сугубо ИМХО.
А по-моему задача B была тяжелее, чем C :)
В чуть сложнее в реализации, С чуть сложнее в плане идеи. Задачи примерно одинаковы, но так как С более идейная, то она поэтому и С.
Как это нет? по твоему D и Е этого раунда не тянут на нормальную C div 1??
По-моему они перетянут на нормальную С див 1. Я написал, что имхо они скорее Д.
Согласен. Первые три были слишком простые, последние — слишком трудные.
I guess because of my English, I got extremely confused with this line "You wonder how many different names Vasya can write instead of name number 1" (Problem C). What the problem writer meant with "instead of name number 1"?
On the place of the first name.
He meant: After Vasya performs all his operations, how many possible strings can be at the place where the first name was initially.
А Вы заметили, что в анонсе нам обещали помощь Пете, а помогали в итоге Васе. =)
А вот это действительно прикол)
Интрига:Р
UPD. Извиняюсь, не нашёл ничего по поиску на "Вася", поэтому написал.
When will the safe mode end?!
Btw, it's going continiously since R107...
And safe mode still did not ended completely: for example, country rating and contests participated by particular coder still show "Do not panic" page...
Вам не кажется, что господин pankajnitt нарушает правила виртуального контеста?
чем же он нарушает?
This contest have 3 easy problem and 2 difficult problem. This contest doesn't have any medium problem. I think it's very bad.