UPD: ABBYY Cup 2.0 завершился! Свежая информация!
UPD: Публикуем разбор :)
И снова привет!
Напоминаем, что сегодня в 16 часов состоится долгожданный сложный дивизион ABBYY Cup 2.0!
Задачи будут сложными для полного решения, рассчитанные на ребят из Див1 Codeforces. Для участия не забудьте зарегистрироваться на контест!
Правила не изменились: в течение 5 часов участники должны будут решить 6 задач (одна из них эвристическая). Тесты разбиты на три группы (легкая, средняя, сложная) стоимостью в 20, 30 и 50 баллов соответственно. Засчитывается только полное прохождение группы тестов. При равенстве баллов штрафное время учитывается по правилам ACM. Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время. Контест будет рейтинговым для всех независимо от формы участия и рейтинга.
Всех участников мы ждем на Дне открытых дверей ABBYY, где расскажем о наших технологиях и вручим подарки. Лучшим поможем с организацией поездки, а также подарим ценные гаджеты.
Надеемся, решение задач принесет вам интеллектуальное удовольствие!
Удачи, и пусть победит сильнейший : )
Анонс ABBYY Cup 2.0 - Hard
are the problems ordered by the increasing complexity ???
yes
Когда будут подробности об "эвристической" задаче?
Во время контеста :) Все прочтете в условии.
За неудачные попытки дается штрафное время?
Видимо, ровно так же, как и в ABBYY Cup 2.0 - Easy, то есть да, по 20 минут.
Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время.It will be good that for each contest there will be a small info table in the post which will answer all standard questions about the contest, like "for whom it will be rated", "problems are ordered by difficulty or not", "score distribution mechanism", etc, so that people wouldn't ask same questions again and again in comments. Sometimes that information is specified in the text in different places, so gathering them all into one table will make it more easier to see all needed info at once.
A little sad that I'm gonna miss the last COCI round for this event :(
I hope you won't regret your decision to participate in ABBYY Cup :)
will it be rated for div 2 or not?
for all
I hope you won’t regret your decision to participate in ABBYY Cup :)
а почему на главной странице до контеста 5 часов, а на странице соревнований 30 минут?
Регистрироваться можно в любое время т.к. нет разделения на комнаты.
Вы путаете время до окончания регистрации и начала контеста.
will the registeration be opened in the contest time?
Yes.
yeah
Who can stop Perlik?? He submitted D2, 25 times & D3, 54 times now and it is increased.
Only ChuckNorris can
T_T..forget to register and become unoffical...
The ratings will be updated for officials and unofficials
Orz...
18 задач — аж глаза разбегаются...
Если не противоречит правилам, поясните пожалуйста, как во втором примере задачи A получается 40 ходов? Если противоречит, я подожду окончания соревнования.
Все вопросы по задачам лучше задавать через интерфейс раздела "соревнования"
Спасибо, что помогли разобраться с интерфейсом. Однако, во время соревнования я получил ответ, что то типа "без комментариев".
Прочитал разбор, с таким решением всё понятно, но ведь в условии сказано, или как минимум я так понял, что нужно в каждом конкретном случае k фиксировать и уж потом складывать.
Что я не правильно понял?
Спасибо, разобрался!
Эвристическая задача клевая.
Да и остальные тоже хороши.
Просто супер!!!
Как решать B3? :(
Строим граф компонент реберной двусвязности. Это дерево, строим на нем LCA. Тогда если две вершины в разных компонентах, то ответ — расстояние в этом дереве
Например, можно строить конденсацию графа по рёберной двусвязности (рёбра в новом графе = мосты в старом), затем искать расстояния через LCA, так как конденсация — дерево.
Но каак все так быстро это писали?
С помощью e-maxx, вероятней всего.
15-20 минут, не так мало что-бы такое написать.
Парочка дфсов, что туда еще прилепишь?:)
Я так и сделал. 23 минуты
С красными-то понятно) Но я видел пару фиолетовых, сдавших очень быстро, и долго-долго пытался придумать простое решение.
Ну это, по-моему, довольно простое решение
Там, несмотря на всю громоздкость, пишется всё практически не думая.
Если пишешь LCA впервые в жизни, приходится подумать)
да и в компонентах реберной двусвязности есть где набажить, если конечно каждый день их не пишешь
Понравились все задачи, кроме Д! Что туда нужно было пихать, что-бы зашел перебор?
Я делал так: Сгенерил все "хорошие" маски — те наборы чисел, к которым можно что-нибудь добавить, чтобы собралось n с правильной суммой. Ну а потом просто перебирал, какое число очередным поставить, отсекаясь, если в какой-то строке, столбце или по диагонали маска получается "нехорошая". Получил TL. Добавил random_shuffle. Прошло :-)
у меня шаффл на D3 доходил до 33-го теста максимум. Это за 8 попыток.
Перебор с доказанной асимптотикой.
У меня так: будем заполнять квадрат в таком порядке (элементы со * не надо перебирать, они определяются однозначно:
1 2 3 4*
5 8 9 10*
6 11 13 14*
7* 12* 15* 16*
Трудоемкость не больше 16*15*14*12*11*9*8*6*4. Наверно еще много само отсекается, когда нечего поставить.
Кажется так будет даже лучше:
1 2 3 4*
5 6 7 8*
12* 9 10 13*
11* 14* 15* 16*
Точно.
1##2
x34x
x5xx
x##x
где x — то, что ставим, цифры — что однозначно определяется, # — то что остается
переберем одну оставшеюся пустую, остальные однозначно восстановятся.
будет ли лучше такое?
Должно быть лучше.
А сколько народу проходит дальше?
Блин одной секунды не хватило что сдать F3. Послал в дорешивание прошло
Дорешивание ненастоящее.
В смысле оно не настоящее?
Там всё проходит ;)
Что-то не могу понять почему в задаче F не канает отсортировать строки, посчитать Lcp для соседних просто влоб, а потом имеет смысл перебирать только k смежных строк? Ведь тот же принцип что и в суффиксном массиве — наибольшей общий префикс двух строк будет равняться минимуму Lcp соседних строк в отсортированном массиве, которые лежат между нашими двумя.
5 4
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
b
cccccccccccccccc
cccccccccccccccc
Тьфу блин, каким местом думал... Спасибо)
Потому что например может быть такой тест a (100 раз) b (1 раз) c (100 раз). k=200. Очевидно, что надо взять 100 строк "a" и 100 строк "c"
Смежных?
5 4 aab aac bbb cca ccb
В F1 и F2 прошёл бор с динамикой, F3 хз как делать.
Very enjoyable competition, I do not regret missing out on COCI for this :D
I particularly enjoyed solving task E (E1 and E2 at that, I had no idea how to cope with the "noise" — but still, it was a very interesting task) :)
rng_58's 1637186 is very easy to read :)
We can apply a (say 5 x 5) "median filter" which can handle this kind of salt and pepper noise. Provided that the shapes are far enough from each other, there is only a small chance that some of them merge after filtering the image.
Как решать задачу C3? У меня никак не пропихивался nlogn.
Я запихнул n * sqrt(n) :)
У меня N*Log^2 прошел :)
Ну вы аццкие пихальщики, у меня NLogN с горем пополам за 980 мс.
Расскажите, как пихать NLog^2, как пихать n * sqrt(n), и кто придумал самое простое решение. А то у меня ужас в миллион строк.
Просто, разобьем все на циклы, для каждого заведем дерево фенвика, а потом бинпоиском будем искать левее элемента свободное вхождение, а потом, если не нашли, правее.
У меня сравнительно короткое решение.
Я держал для каждой группы независимых позиций в таблице (т.е. для групп вида 0+m*i, 1+m*i,...,gcd(h,m)-1+m*i) раздвоенный сет пустых мест (т.е., если свободно p, то свободно и p+size, и наоборот). Далее просто upper_bound для нахождения первого подходящего места. Ну и немного шаманства с map и прекальком индексов. 1640742
Если бы стлевский сет умел возвращать номер элемента в множестве то решение было бы в один цикл. Поскольку оно это не умеет то можно: 1) декартово дерево — тут все понятно как; 2) сделать как написано выше с фенвиком и бинпоиском; 3) сделать обычное дерево отрезков для суммы с хитрой операцией lower_bound которая каждый раз смотрит в левое поддерево берет там сумму начиная с элемента pos если не ноль идет в него иначе идет в правое. асимптотика n * log^2 n
эээ... зачем это все?
задача очень просто решается стандартным сетом в пару строчек
Воот, это-то я и искал, спасибо)
А как ты узнавал количество элементов которые ты перепрыгнул?
Там можно в сет хранить индексы свободных мест и при помощи lower_bound доставать ближайшее свободное. Вполне себе N log N. =)
UPD: Забыл сказать, что вначале все циклы надо перенумеровать внутри, чтобы стал порядок от 0, до h / gcd — 1.
Да я что-то не подумал перенумеровать. Так намного проще
Вот здесь напоролся на то, что lower_bound(myset.begin(),myset.end(),x) — совсем не то же самое, что myset.lower_bound(x).
я правильно понимаю, что это даже не скопилируется, потому что в сете итераторы не произвольного доступа?
В том-то и проблема, что скомпилируется, но работать будет не за O(logN), а за O(N).
Скомпилируется. И даже будет работать :)
Правда, из-за того, что итераторы не произвольного доступа, работать будет за линию, а не log.
Функции из algorithm на разные виды итераторов перегружены.
все перенумеровал, тогда искомое — это разность в индексах куда хотели встать и куда встали в итоге
Мой NlogN работает 580 мск.
Тысяча чертей. У меня nlog^2(n) доходил до 40 теста, а nlogn до 31го или 36го.
В данной задаче имеет значение, как осуществляется ввод: через scanf() или через std::cin. С использованием std::cin ловил TL, а через scanf прошло. При "200000 M 200000" разница выполнения на одном из тестов достигала 500 мс (1684547 и 1684581). Никогда на практике не использую scanf из-за его проблемности, но здесь такой случай, когда без него трудно справиться))
Конкурс на самый идиотский порядок сдачи. Подаю свою кандидатуру с:
А1-А2-А3-D1-B1-B2-E1-C1-F1-B3-E2-C2-C3...
Да, спасибо авторам, задачи, конечно, хорошие... Но слово Hard обломало мне весь контест.
Думал, что будут реально трудные задачи, и тактика "codejam" сработает. В результате, потратил кучу времени на написание лишних решений, да и в тех, которые "не лишние", немного намудрил.
И место черт знает где:)
I enjoyed the competition very much. I think we should have more of these 5 hour contests in which the solutions are judged during the contest time (i.e. ACM style rules).
The Magic Square is so interesting。I solve it for a long time。
"Тесты разбиты на три группы (легкая, средняя, сложная) стоимостью в 20, 30 и 50 баллов соответственно." А в тексте задач, другое количество баллов. Почему, это просто что-то правилось и забыли везде поправить, или для разных участников ...?
Получение 20 баллов — прохождение набора стоимость 20 баллов.
Получение 50 баллов — прохождение набора стоимость 20 баллов и набора стоимостью 30 баллов.
Получение 100 баллов — прохождение первых двух наборов, а так же набора стоимостью 50 баллов.
В условии числа указаны так, что если решение работает при таких ограничениях, то оно набирает как минимум столько баллов (проходя все те наборы, в которых ограничения не больше указанных).
Спасибо за столь быстрый ответ. Опять ДП :)
а когда будет пост про финал ABBYY Cup?
Ситуацию усугубляет то, что "ABBYY Cup 2.0 завершился!"
Извиняюсь, что поднял пост. Но есть существенные проблемы при написании виртуального контеста. Мои посылки не отображаются. Мой ник в таблице не отображается. Нет выпадающего списка с задачами во вкладке отправить.