Доброго дня, Codeforces!
Спешу обрадовать всем тем, что в списке соревнований появилось новое соревнование для div1 участников. Это соревнование является трансляцией Саратовской командной олимпиады школьников по программированию и поэтому будет проходить по правилам ACM-ICPC. Специально для div1 участников мы немного усложнили школьную олимпиаду, чтобы всем было интересно решать задачи.
Соревнование — индивидуальное, оно будет рейтинговым для обоих дивизионов.
Обратите внимание, что время начала соревнования отличается от обычного. Также обратите внимание, на необычную продолжительность соревнования.
До встречи на Codeforces Round #145! Надеюсь, что все найдут время поучаствовать в соревновании.
UPD. Соревнование закончено, скоро появится разбор.
Идея соревнования интересная, однако время и день недели выбраны неудачно...
Для первого дива, также как для второго 3,5 часа. Или всё-таки 2 часа?
I don't understand why there are so many negative comments about the time. This contest is a translation of the real competition for school students in Saratov, and it will be held at the same time. So the time can't be changed. If you can't participate, because you go to school and so on, you can solve a virtual contest later.
Почему бы такое время ни было выбрано, оно выбрано удачно!
-
Because problemset in div1 and div2 differs :-)
Thx..
а почему для див2 3.30, а для див1 2 часа? все таки, как я понимаю, оригинальная олимпиада шла 5 часов?
Только не шла, а будет идти.
А в чем будет заключаться "небольшое усложнение" для div1? БОльшие ограничения / нет халявок / меньше времени / комбинация вышеперечисленного?
Если я правильно понял, для второго дивизиона задачи будут не такие уж легкие,т.к на их решение дано 3 часа 30 минут.
Просто задач будет много, т.к. это будет трансляцией командной олимпиады. Участниками из первого дивизиона, осмелюсь предположить, будут предложены ты же самые задачи, за исключением откровенных халяв(какие всегда есть на школьных командных контестах). Получается, что задачи школьные + их количество меньше, чем для участников 2-го дива. Поэтому 1 див пишет 2 часа, а второй 3,5.
Понятно.
x( i'm at school too beside there is no point in virtual contest :((
I don't know what about others but for me the time is so lucky ) thanks.
обычно в див1 еле 500 человек собирается, а в такое время 250 собирется, и то хорошо будет...
%username%, забей на школу!
Я забью на все, кроме двух уроков :)
А в див2 в этот раз будет около 1500 участников.
меньше народа,
меньше нагрузка на сервербольше кислорода.Это не страшно , ведь есть ещё виртуальное участие в котором они могут поучаствовать)))
Can anyone tell how many problems there will be for div-2? I haven't ever participated in a 3:30 long contest in Codeforces before so i do not know... Thnx..
I think the author will update the number of problems in both divisions right before the contest.
Собираемся командой тренировку виртуально писать. Время частично пересекается с этим контестом. Во время официальных соревнований сервер не сильно виртуальным участникам будет тормозить?
Как показывает мой опыт, во время контеста все сравнительно хорошо, но очень сильные проблемы начнутся во время системного тестирования (вероятней всего, попытки с вирт. контеста имеют меньший приоритет, и поэтому их тестирование начнется только после окончания системного тестирования).
P.S. Это относилось к обычным раундам. Если раунд по правилам ICPC, то, вероятно, там вообще не будет никаких заметных проблем.
а мы с другом ради этого контеста вообще в школу не идем =)
Будет ли возможность писать командой вне конкурса? Хотелось бы потренироваться перед своим отбором на ВКОШП.
Для школьников время подобрано не очень удачно, но можно поучаствовать и виртуально.
поэтому и серый.
кажется, кто-то сегодня слишком разговорчивый =)
конкуренцию не выдерживаешь?
Серый потому что новичок=)
А это не одно и то же?
Новичок — это "начал заниматься месяц назад". А до серого еще надо успеть упасть... Так что это далеко не новичок.
Посмотрел в профиль на дату написания первого контеста — подтвердило мою мысль.
1 раз? Это же так ужасно. Из-за того, что ты пропустишь, безусловно, начнется конец света.
От 1 дня еще никогда ничего не менялось. Тем более, что контесты (ИМХО) интереснее обучения в школе/универе, где рассказывают некоторые странные (бывает) предметы.
Почему регистрация заканчивается за 5 минут до начала?
потому что на комнаты не надо разбивать!
Я надеюсь это сарказм.
Вообще непонятно, почему меня заминусовали, ведь вопрос по делу. В ACM контесте нет смысла заканчивать регистрацию заранее.
Нравятся зареганные в div 2, english2 и bequcha6)) Зачем столько ботов писать??
А кто это такие? Их кол-во зашкаливает. bequcha20, new10, english10. Это один и тот же участник, или это разные люди/команды?
That's a great idea...
It'll take place at 4AM here in Brazil. But, I found time to participate in the competition, it's a good way to learn.
What is it mean ACM-ICPC rules? I can't find about ACM-ICPC rules. Can you explain or give a link for me please?
Here ACM-ICPC rules means, there will be no pretest or pending submission. You will get "Accepted" or "Wrong Answer" as a verdict right after submission and it will be final.
But the Duration of contest or Number of problems may differ from usual. :-)
Why durations of div1 and div2 are different? (div1 2h, div2 3.5h)
Sorry, i haven't see previous post. I know it now.
Will the problems be sorted according to the difficulty?
In ACM-ICPC, the problems are never sorted. So I am guessing no :)
Прогуливать школу для участия — это весело, йоу!
школьники сегодня будут разрываться между желанием написать контест и не получить нагоняй в школе за прогулы, судя по многочисленным комментариям? =)
А что там разрываться, кому нужен этот нагоняй?
Я отсидел половину уроков (по-нашему контест в час дня) и свалил. Оказалось не зря — остальное время в школе была скукотень. Спасибо тебе, Кодфорсес!
Жаль, все-таки, что на эти хорошие задачи попалось далеко не самое лучшее время.
Решил первые две задачи дома, потом одну по дороге на пары, затем одну быстро до пары хотел написать, но на скорую руку ошибся и тут понеслось. :]
и спасибо тем кто решили провести контест именно в это время)
Love it..
w.t.f?
I hope this will be a good practice session for the upcoming regional in my country next month :)
Но зачем?
Задача E — можно было просто делать directed MST в чистом виде? Ставим ребру 0, если оно в порядке, и 1, если его надо отремонтировать?
Да, я видел UPD2, но эта задача отсутствует в наборе задач для div2, поэтому вряд ли им сильно поможет ее обсуждение.
Но задачи E и F можно же обсуждать? Как Е решается? Вот сконденсировали мы по хорошим ребрам — что дальше?
Все, нашел уже статью
Контест не писал, но разве не зайдет стандартный алгоритм?
алгоритм двух китайцев
Я его не знал, к сожалению
В статье по ссылке написано, что это работает за O(nm).
Вот здесь написано, что можно быстрее.
Я написал какую-то хрень, которая валится на таком тесте:
Тем не менее, оно прошло.
неверное решение)
Ну это тебе повезло с тестами, как и мне. Вот контрпример:
Ответ 2, а твое решение говорит -1.
UPD: Кстати, что интересно — этот тест валит все зашедшие решения, кроме решений tourist и YuukaKazami.
спасибо! уже сам понял что лажу написал)
Вопрос по F. Нужно ли было достраивать вторую часть палиндрома, заюзав персистентность и разворот на отрезке? Или проходило без этого?
Можно было в дереве отрезков хранить сколько раз каждая буква встречается на отрезке. Палиндром разбивается не более, чем на 53 куска, каждый из которых представляет отрезок из подряд идущих одинаковых букв. Для каждого такого отрезка делаем запрос в дереве на то чтобы установить значение на отрезке равное данному.
Я делал тоже самое, только дерамидой. Почему-то про дерево отрезков я забыл :(. А зря, решение проще...
У меня решение такое — в каждой вершине дерева интервалов храним количества и отсортированы ли символы в какую-то сторону. Тогда при реквесте если мы попадаем в вершину с отсортированными буквами — проталкиваем эту сортировку вниз. При палиндромировании потом просто проставляем для отрезка нужные буквы и сортировку. Работает за
. При желании можно ускорить до 
Итак, как решать F(div 2)?
Динамика dp[i][j][k] минимальная непривлекательность которую можно набрать покрасив i досок, использовав j красной краски и k 0-если последняя доска красная или 1-если зелёная. http://codeforces.com/contest/234/submission/2368725 http://pastebin.com/xg5wv7e5
Динамика f(i, k, c) — мы рассмотрели префикс длины i, потратили на этом префиксе a первой краски, последняя доска была покрашена в цвет c. Переходы понятно какие — либо следующую доску красим в первый цвет, либо во второй. Почему не нужен параметр b — сколько краски второго типа потрачено. Да потому, что b выражается через a и сумму всех длин на префиксе длины i.
Как решалась D(div.2)?
Желательно, самым коротким способом.
Не знаю, мой самый короткий или нет, но всё же. Для каждого фильма высчитать минимальное и максимальное возможное кол-во любимых актеров. Дальше установить планку — максимум из минимумов. Те фильмы, чей маскимум меньше этой планки — однозначно нелюбимые. Если для какого-то фильма его минимум не меньше, чем максимумы у всех остальных, — он однозначно любимый. Все остальные могут быть и любимыми, и нелюбимыми.
Считалось минимальное и максимальное кол-во любимых актеров, которое могло быть в фильме.
Можно подсчитать кол-во нулей(n0), кол-во любимых актеров(n1) и кол-во остальных для фильма(n2).
Тогда max=n1+(n0>p)?p:n0; min=n1+(n0-t>0)n0-t:0, где p=k-n1 (кол-во любимых актеров, про которых неизвестно, играли они в данном фильме или нет), t=m-k-n2 (кол-во остальных актеров, про которых неизвестно, играли они или нет).
Дальше можн осравнить каждый фильм с остльными и проверить:
если min(i)>=max(j) для всех i!=j, то выводим 0.
Если max(i)<min(j) для какого-то j!=i, выводим 1.
В противном случае выводим 2.
А как С делалась?
Предпросчитываем количества дней до каждого с положительной и нулевой температурой. Дальше, идем с конца, все время обновляя счетчики количеств дней с отрицательными и нулевыми температурами перед нами. Ответом будет являться минимальная сумма всех этих параметров для каждого дня.
Код.
Двумерная динамика. dp[i][j], где i означает длину префикса, j — либо 0, либо 1. То есть будем так считать: сколько для i-ой позиции нам нужно сделать замен, чтобы слева были все отрицательные, включая позицию, а справа были все положительные. Потом просто проходим и ищем минимум из суммы. Могу похожую задачку накинуть, если хотите
UPD. А вот и она.
У меня D упала на 7 тесте? Кто-нибудь знает тест?
например, что-нибудь вот такое
~~~~~
2 1
1
2
a
1
2
b
1
0
~~~~~
Второй фильм в любом случае будет хорошим
UPD: Тест был неправильным, я его исправил
Ответ напиши и в 3 строке место 1 не 2?
действительно 2, ответ 2 0
Спасибо за хороший тест.
Аналогично, хотя ход решения правильный.
А когда тесты откроются?
H (Div. 2) оказалось подозрительно простой.
А можете объяснить вкратце?
Раскладываем карты группами.
Начинаем с нижних карт. Сперва сбрасываем в колоды карты, уже повёрнутые рубашкой вверх.
То есть, если имеем изначально две стопки:
1 1 0 1 0 0
1 1 1 0 0 1 1
Вначале сбрасываем карты-нули.
Получаем:
1 1 0 1
1 1 1 0 0 1 1
0 0 ("результирующая колода")
Далее сбрасываем туда все карты-единицы:
1 1 0
1 1 1 0 0
1 1 1 0 0
При этом стоит записывать, сколько карт было переведено в результирующую колоду в отдельный массив. (2 3 и т.д.)
И так далее, пока не разберём в колоду все карты. Несложно убедиться, что при такой "сортировке" карты, которые были сверху внутри начальной колоды, остаются в таком же положении относительно друг друга и в результирующей.
В итоге имеем такую колоду: 1 1 1 1 1 0 0 0 1 1 1 0 0
И массив, указывающий количество секторов:
2 3 3 5
Теперь наша задача перевернуть все карты.
В начале переворачиваем 5 верхник карт-единиц. После этого переворачиваем эти же 5 верхних карт + 3 нижних. Далее переворачиваем только что перевёрнутые вместе с сектором, который находится под ними.
И в итоге имеем колоду, в которой все карты лежат рубашкой вверх, то есть, имеют значение 0.
Зафиксируем тип карт (вверх или вниз рубашкой) которые будут идти в начале колоды. Теперь понятно, как надо слить две колоды — действуем жадно, если можем в новую колоду добавить карту такого же типа, то добавляем, если не можем, то меняем тип карты. Теперь есть колода из n + m карт, научимся приводить её к требуемой за минимальное число операций. Можно заметить, что для каждого i такого, что цвета типы карт на позиции i и i + 1 отличаются, нужно будет применить операцию к префиксу длины i. Ещё надо не забыть, чтобы в конце у всех карт тип был 0, если не так, то надо применить операцию ко всей колоде. Теперь переберём тип, запустим этот алгоритм, найдём минимум, выведем. Если что, вот мой код: 2371242
После контеста у меня возник вопрос: с какой целью было решено разделить участников на два дивизиона и поставить для див1 всего 2 часа? Учитывая состав див1 (извиняюсь, людей, способных за 2 часа сдать все 6 задач, очень мало), места распределялись согласно скорости решения первых 4 халявок. Мне одному это кажется несправедливым?
Can someone explain me why need big time,
а дорешка второго дивизиона будет?
Nice contest. It was worth waking up early.
Is this contest rated?(I believe it's rated contest)
"This Competition is individual, it will be rated for both divisions."
thank you,I have missed it...
I skipped my class to play in the contest. XD!!!!
Watch Out! We've got a badass over here
Contest is over now, but I still can't see the solutions of other participants. Kindly fix this.
I need upsolving. pls be fast
Eagerly waiting for the rating to change....why is it taking so long today :(
:-w
Почему так долго не пересчитывается рейтинг?
Есть предположение, что команда Codeforces сейчас занята проведением олимпиады для школьников. Возможно проводят разбор, принимают апелляции, готовятся к награждению.
Почему рейтинг так долго не меняется ?
Да какая разница? Неужели ты контесты ради рейтинга пишешь? Когда поменяется — тогда и поменяется.
Нет я пишу контесты что-бы опыта и знаний новых набраться, а за рейтинг просто так интересно!!!
Они нас забыли :-((
Я не против подождать, но со стороны администрации выглядело бы правильней заранее предупредить об возможной задержке и том, какова примерная ее продолжительность.
Я думаю не было в их планах задерживать рейтинг!
Синий. Наконец Оо
Не беспокойся, я в прошлый раз тоже так говорил — и вот где я)))
i can't view others submissions nor has the rating changed , why is it taking so long
The problem E can be modeled as Minimum Arborescence.
But I used to know the algorithm of it is O(VE)...
With nothing to do at last so I write one for a try...
But to my surprise it passed...
And I found the actually complexity of that is indeed O(E logV)....
here's a link:http://en.wikipedia.org/wiki/Edmonds'_algorithm
Maybe it's helpful.
I found my implementation is still O(VE) :( ...
Thank for cherudim to give me such kind of tests.
Anyway...There's fast implementation as O(E logV).
Will there be an editorial ?
задача http://codeforces.com/contest/234/problem/D Вот этот тест. Кто нибудь может объяснить почему вердик такой? Я не понял. Заранее спасибо
100 1 1 2 ab 17 0 0 0 0 0 0 0 0 0 0 0 2 3 4 5 6 7 abb 1 2 Вывод 2 2 Ответ 0 2
в ab может быть, а может и не быть любимых актеров.
если есть — то ab — любимый, abb — нет.
если нет — то ab — любимый, abb — тоже любимый.
вот и получаем: abb — всегда любимый (т.е. 0), ab — может любимый, а может и нет (т.е. 2).
Возникла проблемка с задачкой С из div2, делал следующее:
Вот например тест:
оба счетчика дают 4, а можно поменять знак второго и предпоследнего элемента и получить ответ 2.
Спасибо!
Could someone please tell me how to solve Div.2 H / Div.1 D problem Merging Two Decks?
Many solutions to 240E - Road Repairs are wrong including mine. wuyiqi told me a test: 3 3 2 3 0 1 3 1 3 2 1
It is guaranteed that there is not more than one road between the cities in each direction.
I think there can be two roads between two city while they are in different directions.
Some pairs of cities have monodirectional roads built between them.
Many solutions to 240E — Road Repairs are wrong including mine like this: 4 4 1 2 1 2 3 0 3 4 1 4 2 0 mamy solutions output -1.but the answer is 2 1 3
Когда будет разбор?
Hi A short-solution programming contest will hold on October 24 at gpac.blog.ir For more information go to the link.
I'm still waiting for your editorial :(
Will there by editorial for this contest?
How's the editorial coming? I'd love to read something about E ;)
I found the tag "greedy" after I solved problem E in O(V+E). Is it true that there is a correct (not accepted) greedy solution for this problem? How? I hope someone or the editorial would tell me something about it.
try 3 3 1 2 1 2 3 1 3 2 0
Could you please upload the editorial ?
How's the editorial coming?
By train :P
By a toy* train.
i don't think the statement of problem e satisfy the truth.
There is no editorial until now !!! :/ Will it be published ??? Or already published in any other blog ???
Why am I getting a TLE on the 1st test case
http://ideone.com/0PewNN
Please help
Can anyone tell me how the answer for "Cinema" for this test case is 0, 2: 100 1 1 2 ab 17 0 0 0 0 0 0 0 0 0 0 0 2 3 4 5 6 7 abb 1 2 The 1st movie need not contain his favorite actor hence I think the answer is 2, 2. Pls. help
I like this contest 52150518:)
my AC code(cpp):52150518
234E - Champions' League