The 2012 All-Ukrainian Collegiate Programming Contest

12 лет назад, # |

Согласно приглашений, полученных 23.08.2012, по Центральному региону (Сумы) расписание таково:

05.09.2012, 15:00: открытие, жеребьёвка

05.09.2012, 16:00: пробный тур

06.09.2012, 10:00: основной тур

06.09.2012, ориентировочно 18:00 но гипотетически может изменяться в зависимости от текущей ситуации: награждение и закрытие

Насколько понимаю, пробный и основной туры неминуемо одновременно по всем регионам.

05.09.2012, 16:00: пробный тур 06.09.2012, 10:00: основной тур

→ Ответить

Rubanenko

12 лет назад, # ^ |

← Rev. 2 →

Извините, возможно, это глупый вопрос, но что представляет в данном случае жеребьевка и зачем она нужна?:)

→ Ответить

tiirz

12 лет назад, # ^ |

Для распределения команд по компьютерам и аудиториям.

→ Ответить

12 лет назад, # |

Открытие только что началось

→ Ответить

12 лет назад, # |

Где можно будет online поболеть за команды?

→ Ответить

ballon

12 лет назад, # ^ |

думаю тут, или тут можно будет.

→ Ответить

12 лет назад, # ^ |

Пока что ни там, ни сям не доступно :(
И организаторы молчат...
Будем надеяться, что кто-то осведомлённый откликнется! :)

→ Ответить

12 лет назад, # ^ |

Похоже, что онлайн-результаты тут

→ Ответить

12 лет назад, # |

+12

Был весьма странный проблемсет. 3 задачи, которые мы пихали, но так и не допихали, выглядят вообще элементарными, при этом входят они довольно случайным образом у разных команд (могут входить у довольно средних и не входить у очень сильных). Что ещё больше озадачивает, те, кто сдали эти задачи, делали то же, что и мы.

→ Ответить

12 лет назад, # ^ |

Задачи C, E, G ? Отпишитесь, плиз, когда выясните в чём дело!

→ Ответить

12 лет назад, # ^ |

Мы пытались сдавать 3 разных трактовки задачи Е и только последняя зашла дальше 1 теста. Причем, как по мне, они все подходили под условие.

→ Ответить

RomaWhite

12 лет назад, # ^ |

А какая трактовка в Е правильная?

→ Ответить

12 лет назад, # ^ |

Нужно найти количество способов выстроить в очередь именно те k человек, которые даны в начале инпута. Люди, которые не встречаются во входных данных, вообще на ответ не влияют.

→ Ответить

mylyanyk.ivan

12 лет назад, # ^ |

Саме те, на чому ми отримували ВА. Шкода, трішки не хватило часу, щоб здати "правильний" розвязок.

→ Ответить

ibra

12 лет назад, # ^ |

именно так и было у большинства тех кто получал ВА по Е

→ Ответить

12 лет назад, # ^ |

C ещё ладно — там тайм лимит 0.5 (Внимание, вопрос: зачем? Автор знает решение за n^2 или ждал именно оптимальные n^2 log n?) и при наличии времени можно было её впихнуть. Но с остальными двумя — ВА и это вводит в ступор. Ещё больше удивляет 3 аксепта по Е (наверно, она всё-таки решалась персистентной дучей по неявному ключу или минкост-максфлоу на суффиксном дереве, а наивные люди какие-то цепочки строили, факториалы считали...). С G тоже не понятно — команды с отличными математиками имеют по ней минусы, а с первой попытки её вообще никто не сдал. Такое ощущение, что оригинальные задачи оказались слишком простыми (так и есть), более сложных не нашли или не захотели искать и поэтому для усложнения в условие был заложен дополнительный скрытый смысл, который обнаруживается только при тщательной вычитке.

→ Ответить

12 лет назад, # ^ |

+14

Просто во всех задачах есть вырожденные частные случаи и т.п. Нужно было аккуратно все рассмотреть или написать брутфорс и сверить с ним свое решение на рандомных тестах.

→ Ответить

12 лет назад, # ^ |

← Rev. 3 →

-29

Насчёт C: я (автор) решения более быстрого чем $\text{[math]}$ не знаю, но мне удалось построить совокупность оптимизаций, с которыми всё укладывается где-то в 0,170 сек; а совокупность оптимизаций, с которыми всё укладывается в 0,300--0,350 сек, как по мне, относительно простА. Вот если б таки появились именно на эту задачу решения на джаве, было б стрёмно.

UPD: а все ли, кто говорит, будто у них не прошло $\text{[math]}$ , уверены, что их решение ни на каких входных данных не превращается в n³?

→ Ответить

Egor

12 лет назад, # ^ |

+17

Есть такое мнение что ТЛ менее 2 с, а так же дробный ТЛ — зло. Всегда можно чуть-чуть увеличить ограничения (и таки при этом проще будет отделить куб)

→ Ответить

12 лет назад, # ^ |

Я с этим почти согласен, но не согласны люди, организовывающие техническое обеспечение :( По их мнению, необходимость делить проверку между несколькими серверами — бОльшее зло, чем time-limit-ы в 0,5 сек.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Вот объясните мне, за что минуса!

За то, что поставили time-limit втрое выше авторского решения? Или за то, что он всё равно маленький? Или минусуют меня за то, что команда технического обеспечения не считает целесообразным делить проверку между физически разными компами? Или за то, что я сделал задачу, в которой участник очень даже может думать, будто написано решение за $\text{[math]}$ и не видеть что оно на самом деле за n³?

Контрпродуктивная ситуация, причём уже не первый раз: только напишу что-то по результатам тура где играли мои задачи, так сразу одновременно и минуса и отсутствие конструктивной критики (во всяком случае в плане того, что мог бы сделать я сам, а не команда технического обеспечения).

Ну давайте я уйду из всего этого, и увеличится процентное соотношение задач авторов, которые пихали в тесты лишние слэши (на прошлогоднем финале Украины & SEERC) и совершенно по этому поводу не парились, может так всем будет лучше.

→ Ответить

yarrr

12 лет назад, # ^ |

← Rev. 2 →

+13

Я надеюсь, ваши оптимайзы с такими же запасами и на Джаве заходят?

→ Ответить

12 лет назад, # ^ |

Немного конструктивной критики. Насколько я понял из Вашего поста, решения на Джаве по задаче С проходить если и должны, то впритык (если я Вас неправильно понял, простите). Это не очень хорошо, учитывая, что Джава — официально используемый язык АСМ и решение на нём должно существовать.

А ещё я утверждаю, что я писал именно n^2 log n (не очень оптимально, но всё же) и получил ТЛЕ.

Посудите сами: отсортируем массив весов и массив рёбер (n^2 log n), рёбра создадим без дубликатов, т.е. их до 500000. Для каждого ребра (n^2) вершины, инцидентные ему (n^2), запихнём в вектор, соответствующий весу этого ребра (изначально заведён массив из 10^6 векторов, lower_bound (n^2 log n) ищет первое вхождение веса ребра в массив весов и говорит, что вектор с таким же индексом отвечает за этот вес), затем добавим все рёбра (каждое ребро — не более раза, а значит суммарно n^2) с текущим весом в граф и запустим dfs только от вершин в текущем векторе (так же суммарно n^2). После того, как запустили dfs, почистим вершины, которые находятся в текущем векторе (а значит, ребра не накапливаются с одной стороны и мы проходимся по каждой вершине ровно столько раз, сколько рёбер ей инцидентно с другой стороны).

Я не снимаю с себя ответственности за неоптимальность кода — слишком много добавлений в векторы, можно было использовать 1 вектор вершин, а не 10^6, можно было сортировать рёбра в каждом списке инцидентности, а не глобально (увы, времени оптимизировать особо не было — ещё 2 задачи висели), но на асимптотику это не влияет, а именно она у Вас вызывает сомнения.

→ Ответить

Edvard

12 лет назад, # ^ |

+40

Я конечно сторонний участник дискуссии, потому что на контесте не был и эти задачи не решал, но кажется немного подозрительной фраза "... но мне удалось построить совокупность оптимизаций ..." из этого следует, что было написано решение, а потом оно просто нахачивалось. Делать таким образом задачи не очень хорошо, хотя бы потому что почти в любой задаче можно взять решение которое работает 2с и нахачить его так что оно будет работать 100мс и после этого поставить ТЛ 250 мс.

→ Ответить

mihnevsev

12 лет назад, # ^ |

-11

Контест мне тоже не понравился, задачи собирались спехом, галопом от разных авторов, разного уровня профессионализма авторов, не вычитывались, не проверялись. Контест не сбалансирован, вообщем из года в год ситуация как по составлению задач, так и по организации контеста не меняется.

Я вчера лично разговаривал с девушками из ОНУ, юнаками зі Львова и с братьями Соболевыми, так уровень проведения второго этапа страдает, а в случае, как сказал Дима, Луганска, так хуже провести было просто невозможно.

Но зная что за всем этим стоит т.Мисюра и зная, что его уже давно пора списывать на заслуженный отдых, так как он не справляется с требованиями к мероприятиям такого уровня, то призываю, просто заклинаю все команды, которые попали в топ 20 ехать только в Бухарест, голосуем против Винницы ногами, собираем деньги и едим туда, где организация более-менее.

И еще давайте вместе поищем, попросим, подумаем над тем кто у нас в Украине смог бы организовать все так, чтобы задачи были достойны и интересны, уровень организации не страдал, организаторы хотели и могли бы сделать праздник, чтобы было не стыдно туда пригласить иностранные команды и спонсоров, неужели на Украине нет таких людей? Надеюсь, что есть!!!

→ Ответить

12 лет назад, # ^ |

+40

"Я вчера лично разговаривал... с братьями Соболевыми"... Насколько я знаю, Дмитрий Соболев в данный момент находится на стажировке в Facebook. Вы ведете репортаж из Америки?..

→ Ответить

mihnevsev

12 лет назад, # ^ |

-29

Да, Дрюк он и в Луганске Дрюк! Ну и зачем было палить отличную команду из-за того, что они писали без Димы, а теперь их дисквалифицируют и не допустят к финалу.

→ Ответить

maksay

12 лет назад, # ^ |

+35

Какой фееричный бред..

Народ, перестаньте кормить тролля.

→ Ответить

12 лет назад, # ^ |

+18

Хм. Вы можете назвать хотя бы одну команду, которая была дисквалифицирована по этой причине за последние N лет?

→ Ответить

Edvard

12 лет назад, # |

А есть ссылка на монитор?

→ Ответить

Monyura

12 лет назад, # ^ |

Борд
А у меня тем времнем вопрос к участникам, ни кому задача J не показалась знакомой? Не могу вспомнить, где видел что-то похожее...

→ Ответить

partisan

12 лет назад, # |

Где можно достать условия задач?

→ Ответить

12 лет назад, # ^ |

Здесь

→ Ответить

RuTubeHeroes

12 лет назад, # |

+16

А где-нибудь можно порешать этот контест?

p.s. может кто-нибудь добавит в тренировки, если у него есть тесты?

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

AWPRIS то ли договаривается то ли уже договорился получить полный комплект тестов и провести зеркало этого соревнования на e-olimp.com.ua Только вот когда оно будет...

→ Ответить

12 лет назад, # ^ |

+17

e-olimp — это хорошо, но тренировки на Codeforces — предпочтительнее, т.к. их может запускать каждый в любое время, а на означенном сайте такими возможностями обладают только руководители групп. А ещё у господина Присяжнюка есть удивительное мнение о том, что перед соревнованием и зеркалом стоят разные задачи, авторское решение не обязано проходить в ТЛ и если по задаче нет чекера, то участнику следует угадать решение автора. Вкупе с не очень быстрым сервером это порой создаёт задачи, которые надо оптимизить часа 3.

→ Ответить

Fcdkbear

12 лет назад, # |

Расскажите кто-нибудь как решать D и F, пожалуйста. По поводу задачи D — буду рад, если кто-нибудь еще и условие полностью обьяснит.

→ Ответить

knightL

12 лет назад, # ^ |

← Rev. 2 →

Задачу F можно решить при помощи БФСа. состояние — где мы можем сейчас находится. поэтому состояний максимум 2^(n*m). Ну и чтобы быстро совершать переходы по командам D,L,R,U нужно воспользоваться битовыми маскам (что-то похожее на http://codeforces.me/problemset/problem/97/D ). Чтобы ответ был лексмин, в очередь нужно класть сначала переход по D, потом по L, R и U. В итоге сложность при аккуратной реализации получится порядка 2^(n*m)*4

→ Ответить

Fcdkbear

12 лет назад, # ^ |

Спасибо, понятно.

→ Ответить

12 лет назад, # ^ |

Кстати, мне одному кажется, что из условия задачи F неочевидно, что выводить в случае, когда есть только стены? С одной стороны, выходов нет, достичь их нельзя, поэтому NO SOLUTION. С другой — стартовать тоже неоткуда, поэтому никуда идти не надо и ответ — пустая строка. Мне кажется, что либо условие задачи двусмысленно, либо такой тест некорректен.

→ Ответить

bayleef

12 лет назад, # ^ |

← Rev. 2 →

+16

Задача D.

Условие. У нас изначально есть куб. Просто единичный куб со значениями только в вершинах, равными 1. На каждом шаге мы все имеющиеся у нас кубы делим на 2 по каждой координате — итого на 8. При этом у новообразовавшихся вершин значение получается из суммы "соседних". На самом деле, если соседних изначально не было, то это или сумма 4х чисел в углах грани (если новая вершина ставится в центр грани), или сумма всех 8и вершин куба ( если ставится в центр куба).

Найти сумму всех получившихся чисел после n разбиений.

Решение.

Из ограничений довольно ясно, что придётся возводить матрицу в степень. У нас была матрица 4*4. Эти 4 координаты — сумма элементов в углах исходного куба, на рёбрах, на гранях и внутри соответственно. Матрица переходов получилась такая: $\text{[math]}$

Уже после контеста я вывел формулу, дающую тот же ответ: (3ⁿ + 1)³.

Оффтоп: похожее было в задаче A раунда 118, где одни люди возводили в степень матрицу, а другие — двойку. Нет ли какого-нибудь общего алгоритма, заменяющего возведение матрицы в степень с последующим умножением на вектор и поиском суммы элементов результата на возведение в степень числа или матрицы меньшего размера (возможно, с какими-то константными операциями)

→ Ответить

Fcdkbear

12 лет назад, # ^ |

Спасибо, буду разбираться.

По поводу условия. Там есть такая строчка "We will split the cube into 8 equal cubes and assign to new vertices numbers equal to the sum of numbers in adjacent vertices." Для меня както не очевидно, почему из нее не вытекает, что значение в центре верхней грани первоначального куба зависит не от всех значений на серединах ребер этой грани.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

-10

Похоже, тут имел место случай (не очень уж редкий, особенно, если язык условия — не родной для автора и/или контестанта), когда эффективнее не разбираться в тексте условия, а посмотреть на сопровождающие рисунок+input+output.
Для того они и приводятся!

Минусующие — хотите сказать, что вам такие задачи не попадались? ;)

→ Ответить

partisan

12 лет назад, # ^ |

+13

Да, есть. Но не всегда это реализуемо на практике.

Допустим, имеется рекуррентность f(n) = a(1) * f(n-1) + ... + a(k) * f(n-k). Составляем характеристическое уравнение заменой f(m) -> q^m: q^n = a(1) * q^(n-1) + ... + a(k) * q^(n-k) или q^k = a(1) * q^(k-1) + ... + a(k). Получаем уравнение k степени с корнями q_1, q_2, ..., q_k, c учетом кратности и комплексных корней. Если все корни различные, общее решение рекуррентности выписывается в виде f(n) = c(1) * q_1 ^ n + c(2) * q_2 ^ n + ... + c(k) * q_k ^ n, где c(i) определяются из начальных условий. Другие случаи рассмотрены здесь http://en.wikipedia.org/wiki/Recurrence_relation#Solving.

Применение на практике — если повезет с корнями характеристического полинома. Например, для чисел Фибоначи f(n) = f(n-1) + f(n-2) корни иррациональны и точный ответ с использованием формулы получить непросто. http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

→ Ответить

alexey.shchepin

12 лет назад, # ^ |

+10

Для этой матрицы можно было легко перейти к степеням, потому что она получилась треугольная, а значит ответ можно представить в виде линейной комбинации степеней элементов на диагонали. Т.е. если на диагонали стоят b₁, b₂, ..., b_m, то характеристический многочлен будет равен (x - b₁)(x - b₂)...(x - b_m), и поэтому a_n = c₁b₁ⁿ + c₂b₂ⁿ + ... + c_mb_mⁿ.

→ Ответить

Prestige

12 лет назад, # |

+19

А я кину камень в огород организации...

→ Ответить

12 лет назад, # |

А кто как различал фигуры в задаче А?

→ Ответить

Squire

12 лет назад, # ^ |

С помощью хеша. Мы использовали степени 3-ки.

→ Ответить

12 лет назад, # ^ |

Мы тоже хешировали, хотелось бы и другие способы узнать.

→ Ответить

12 лет назад, # ^ |

Ну, действительно получалось, что одновременно и по времени работы программы, и по затратам на её написание, трудно найти что-то лучшее, чем хэши (с частичной, не до конца честной проверкой при коллизиях). Правда, это всё же действительно спокойно и уверенно только за счёт возможности многократной сдачи — если последствия неправильного учёта коллизий таки проявятся, можно пересдать с друг(ой/ими) хэш-функци(ей/ями).

А ещё альтернативные способы, которые абсолютно гарантированно правильные:

1 этап. при обходе фигуры в ширину/глубину получить некоторое "слово" (или из относительных координат клеточек, или из последовательности в стиле "пихнули в очередь направление вниз, пихнули в очередь направление влево, закончили рассмотрение всех соседей текущей клеточки, ... ... ...")

2 этап, 1 вариант. Пихать эти слова в котейнер set. Может казаться, будто тут одновременно и дорогое сравнение строк, и большое количество фигур, и ещё накладные затраты на сам set (логарифм с большИм константным множителем). Но на самом деле суммарная длина всех строк ограничена размерами поля, посему они не могут быть одновременно и очень длинными, и в очень большом количестве. Так что подобные решения пропихиваются относительно легко, а если ещё сравнивать строки сначала по длинам, а потом уже для одинаковой длины лексикографически, то всё вообще гарантированно получается.

2 этап, 2 вариант. Пихать эти слова в рукописный бор (trie). Хотя теоретически это решение должно бы быть асимпотически лучшим всех рассмотренных ранее, на практике оно почему-то немножко даже проигрывает. Но тоже сдаётся.

→ Ответить

12 лет назад, # ^ |

По поводу коллизий мы долго не думали, 2ой хеш вполне хорошо сработал. А за 2 альтернативных варианта спасибо.

→ Ответить

Rubanenko

12 лет назад, # ^ |

А какой там был МЛ? Довольно глупо, что я не мог взять еще один массив размером со входные данные, из-за чего получал МЛ 14-15 тест.

→ Ответить

12 лет назад, # ^ |

Довольно странно, потому что в кларах было написано, что на все задачи МЛ 256Мб.

→ Ответить

knightL

12 лет назад, # ^ |

+14

По каким-то загадочным причинам решения, у которых было переполнение стека, получало МЛ. По крайней мере с нашим решением было так. Мы убрали все сеты, большие лишние массивы и т.д. и локально решение потребляло максимум 20 метров, но оно не проходило, пока мы не заменили рекурсивный дфс на нерекурсивный.

→ Ответить

12 лет назад, # ^ |

А как, собственно, должен отображаться участнику stack overflow? Признаюсь, что именно этот вопрос я как-то до сих пор пропускал мимо внимания. Впрочем, и на этом туре от меня это вроде бы никак не зависело.

И, разве совсем уж нелогично и неожиданно выглядит, что рекурсия глубиной более миллиона таки ломается? 14-й тест был 1162*1226, примерно 77% клеточек звёздочки:

for(int i=0; i<N; i++)
	for(int j=0; j<M; j++)
		data[i][j] = rand()%100 < 77 ? '*' : '.';

15-й тест — 1206*1153, аналогичным образом обеспечено что примерно 98% клеточек звёздочки. Неужели в этих тестах есть какой-то хитрый и неожиданный подвох???

→ Ответить

dalex

12 лет назад, # ^ |

+15

Ну вроде как везде Stack Overflow это Runtime Error

→ Ответить

12 лет назад, # ^ |

Это везде по-разному и вообще трудноуловимо, т.к. нужно правильно интерпретировать сигналы. Например, на КПИ-Опен под МЛЕ скрывался выход за границы массива.

→ Ответить

qwerty787788

12 лет назад, # |

А кто-нибудь знает, как решалась задача J (про мат. ожидание количества точек попавших в круг)?

→ Ответить

12 лет назад, # ^ |

По идее, должен знать ее автор, Виталий Неспирный;)

→ Ответить

Squire

12 лет назад, # ^ |

Очень бы хотелось почитать авторский разбор задач (если это вообще возможно).

→ Ответить

12 лет назад, # ^ |

У меня была идея рандомно выбирать 3 точки и считать ответ за O(n) на протяжении 2х секунд. Дело в том, что в задаче ответ нужно вывести с точностью до сотых. Поэтому по ЗБЧ возможно бы и зашло, хотя я далеко не уверен в этом. Ничего другого в голову больше не пришло. Но руки не дошли написать это, мы Е пытались сдать.

→ Ответить

12 лет назад, # ^ |

Не, рандом — это от лукавого;)

→ Ответить

http://icpc.baylor.edu/public/worldMap/reservationList.icpc;jsessionid=028C66953D9EFC10F329B0E028190381?contestId=1326

12 лет назад, # ^ |

Мы в последние 10 минут написали это и получили ВА 7.

→ Ответить

qwerty787788

12 лет назад, # ^ |

← Rev. 2 →

Быстро написанный чекер ошибается даже в знаках перед запятой;)

P. S. т. е. если эту программу запустить два раза, то будут сгенерированы два одинаковых набора точек, а ответ будет отличаться.

→ Ответить

Seyaua

12 лет назад, # ^ |

+13

Вот на этом контесте задача H совпадает с задачей J с данного контеста.

К сожалению, видео-разбора быстро не смог найти, но совершенно точно помню, что задача решалась формулой (все доказательство было в некоторой статье), в которой использовалось количество выпуклых четырехугольников, которые можно построить на заданных точках. А количество выпуклых четырехугольников — это тоже известная задача, была и в Петрозаводске и на зимней школе в Харькове.

→ Ответить

mihnevsev

12 лет назад, # |

+31

Я только что посмотрел список зарегистрированных на румынский полуфинал и у меня возник вопрос, почему им можно регистрировать по 4 команды от университета(например Babes-Bolyai University), а на украинском полуфинале действует жесткое ограничение не больше 3 команд от вуза, почему украинские правила жестче мировых? опять чувствую руку т.Мисюры!

→ Ответить

kasitan

12 лет назад, # |

Кто вчера участвовал в финале 2й лиги в Харькове? http://ejudge.hneu.net/ Подскажите, пожалуйста, какой-нибудь логин/пасс для дорешивания

→ Ответить

Prestige

12 лет назад, # ^ |

Где можно посмотреть условия и результаты?

→ Ответить

I_love_Tanya_Romanova

12 лет назад, # ^ |

http://olymp.hneu.net/new/ — вот сайт.

→ Ответить