IX открытый чемпионат Харькова

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

торт, медали, дипломы

Можно онлайнам тоже дипломы? Чтоб хоть память была на старости лет. Не сайт же внукам показывать:) С такими призами - лучше уж медальки вместо хостинга...

→ Ответить

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

Можно, я могу отсканировать диплом и выложить на сайт. Но всем рассылать по почте - это нереально :)

→ Ответить

steiner

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

Расскажите, пожалуйста, как это всё соотносится со вторым дивизионом opencup'а? Буду ли участники opencup'а автоматически включены в зачёт онлайн-тура этой олимпиады? А наоборот?

→ Ответить

Egor	13 лет назад, # \| +12 Я плохо знаю украинский, так что вопрос - можно ли онлайн участвовать не студентам? → Ответить

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

Да, конечно можно! там всё по русски будет (даже интерфейс), а в первом дивизионе ещё и на английском должны быть условия

→ Ответить

Egor	13 лет назад, # ^ \| +3 А что тогда писать в графу "учебное заведение"? Место работы? → Ответить

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

Судя по аватару, я думал Вы школьник :)

Можно ничего не написать - полное заполнение профиля является важным только для онсайт участников, т.к. им надо печатать дипломы.

→ Ответить

Egor	13 лет назад, # ^ \| +29 Ладно, сейчас всех напугаю и поменяю аватару на актуальную → Ответить

Egor	13 лет назад, # \| +1 Верно ли, что тестирование "повисло"? → Ответить

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

Тестирующая система явно не успевает за участниками.

Во втором дивизионе за 12 минут 1 проверенное решение на всю таблицу. При этом у нас уже 2 висит на проверке)

→ Ответить

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

← Rev. 3 →

+12

Отправили задачу L. Получили WA 14. Дебажили около часа, не успели еще две задачи нормально написать. А потом реджадж. Великолепно.

UPD: Одна из этих задач зашла, ~~а в другой буквально пару символов поменять остаетс~~я. А у нас отняли час, ~~и мы вторые, а не первые~~.

→ Ответить

pkhaustov

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

Это еще скажите спасибо, что я после такого же часа е**тни с этой задачей додумался переписать long long на int, зная с какой надежностью готовятся подобные контесты, и сразу же сообщил администрации. Я и так решал в гордом одиночестве и времени мне ни на что не хватало, так еще и целый час за просто так отобрали некачественной подготовкой задач. Когда же люди поймут, что задачи перед контестом должен решать не только автор.

→ Ответить

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

← Rev. 2 →

> переписать long long на int
Хочешь сказать, другие ответ выводили в int-ах, забывая о переполнении, а мы выводили в long long и получали WA?

→ Ответить

yahooo

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

это уже не в первый раз, помню тоже из-за этого падали

→ Ответить

Seyaua

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

+13

Привет, Паша :) Прошу прощения за сложившуюся ситуацию.

Немного объясню, что произошло. Задачи готовили я и брат, готовили в полигоне. Конечно, у нас было много решений и случайно получилось, что в model solution ответ выводился через %I64d, так как полигон на виндоузе. В полигоне незаметно, что это баг, поэтому и пропустили.

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

→ Ответить

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

Я обычно для избежания багов с выводом, когда не нужно выводить несколько мегабайт лонгинтов, использую cout.

P.S. А что, из Полигона на сервер открытого кубка вытаскиваются не уже готовые ответы на тесты, а только инпуты и model solution'ы? Жесть полная!

→ Ответить

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

Как минимум, можно было сгенерить тесты под виндой. Ведь было известно, что ejudge под линуксом вертится, и так же было известно про %I64d.
А еще лучше - писать Model solution на Java. По-хорошему все равно надо писать решение на Java, чтоб рассчитать TL. А тут еще и проблема с 64-битными числами исчезает, красота.

→ Ответить

I_love_natalia

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

Меня еще больше удивляет другой вопрос. А что, через после вытаскивания задач с полигона проверяется только main correct solution?! Остальные решения просабмитить (хотя бы на адекватность TL) сложно?!

→ Ответить

pkhaustov

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

Привет, Женя. Ну вот это говорит об уровне проведения опенкапа. Авторы задач не могут оперативно вносить исправления. Я думаю, что если бы вы с Димой видели WA14 у большинства участников, то обратили бы внимание на эту проблему.

→ Ответить

MikeMirzayanov

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

Но ведь если тесты сгенерировать через doall.sh, разве так как используется wine, тесты не окажутся сгенерены правильно?

→ Ответить

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

← Rev. 3 →

+17

Я на эту еб...ую задачу вообще почти весь контест угробил, с перерывами на сдачу всяких халявок из таблицы. Итого две задачи не успел написать =(((

О какой репрезентативности итоговой таблицы можно вообще говорить после такой жести? Некоторые, забывая про переполнения, получали ОК и шли дальше, а кто не забывал - ВА и тратил понапрасну кучу времени на поиск ошибок в собственном верном коде.

Про качество условий/примеров - вообще отдельная история. В задаче М без клара не разберешься что от тебя хотят (и даже тестов нормальных нет для демонстрации этого), в задаче О какая-то хрень вместо сампла и пояснения, в задаче S.

Ну надо начинать контесты хотя бы не в последний вечер перед днем проведения готовить-то! Я все могу понять, но вот скажите: сложно было потратить 30 минут перед контестом на вычитывание условий и проверку того, что там нет явной ботвы?

→ Ответить

Jokser

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

Так можно и особый вид контестов придумать . Так сказать "для гурманов". Нужно сдать неверное решение и угадать ошибку автора :)

→ Ответить

pkhaustov

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

Это избавит от невероятного по ощущениям эффекта "Нежданчика". Можешь себе представить мое удивление, когда, написав (int)res вместо просто res, я получил OK.

→ Ответить

Jokser

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

Я бы наверное долго и истерично смеялся...

→ Ответить

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

Мораль, ребята, такова: нефиг второй див решать)

→ Ответить

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

Да я вот тоже к этому выводу пришёл. Второй раз за сезон по полконтеста решаю решённую уже задачу.

→ Ответить

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

-19

А в первом опять были питерские задачи - ничуть не лучше. Там бы вы весь контест потратили на запихивание уже решенных задач.

Мораль, ребята такова: нефиг Питер и Харьков решать, лучше пойти погулять)))

→ Ответить

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

Сами по себе задачи-то классные, харьковский комплект мне больше всех понравился из всех опенкапов этого сезона.
А вот их подготовка мы сами видим на каком уровне...

→ Ответить

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

Я не спорю, что задачи были неплохие, но что это меняет для результата? Все равно самое правильное было пойти погулять)

→ Ответить

Romka

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

← Rev. 2 →

+19

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

Серьёзно? :) Вы бы, может, сначала порешали проблемсет, что ли, прежде чем так заявлять.

→ Ответить

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

-12

Решал предыдущий, хватило, спасибо. Дал себе слово еще хоть раз решать питерские задачи уже в другой жизни.

→ Ответить

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

+15

Зато на чемпе призы клевые. Если онсайт писать.

→ Ответить

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

-24

Кстати, чтобы проверить мою гипотезу, решать даже ничего не надо, можно просто прочитать пост Zhukov_Dmitry ниже. Цитирую: "В задаче C проходило, наверное, любое решение на Java, и почти ничего не проходило на C++. (это про div1 опенкапа :)". Без комментариев.

→ Ответить

Romka

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

+25

====================================================================

Выборка, конечно, репрезентативнее некуда. N <= 5 команд отписались о том, что не смогли сдать не самое оптимальное решение на С++, а смогли на Java, и это по одной-единственной задаче. Конечно, основываясь на этом, можно сразу же номинировать контест на "худший проблемсет года". Ведь участники не смогли сдать очевидное решение, какой ужас.

Читаем чуть ниже посты Ильи и Пети, и понимаем, что есть решения, которые отлично заходят на С++. Более того, с вероятностью 99.9% Гена сдал её на fpc, который вроде как медленнее С++. "Ну а если совсем тупой перебор не заходил - так это уж проблемы участников, нефиг лажу толкать ;)" (с)

→ Ответить

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

-34

========================================

Ну, на худший проблемсет года я ничего не номинировал. Просто заметил, что вряд ли этот контест должен отличаться от всех предыдущих - то есть с интересными задачами и неадекватнейшими таймлимитами. Ну и обычное для питерских контестов обсуждение "а как толкать ..." вроде бы подтверждало мою гипотезу. Если в конкретно этой задаче толкать ничего не надо было - я рад. Видимо, надо было в другой (например, в А). Ну потому что это ж Питер и они просто не могут себе позволить дать контест без хотя бы одной ботвы.

→ Ответить

nk.karpov

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

===============================================

Есть оптимизации извращенские, а есть идейные... в А как раз решение жюри с нормальными оптимизациями поэтому палево и не проходило

→ Ответить

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

=====================

"Идейная ботва", хм, прикольный термин, мне нравится =)

→ Ответить

tunyash

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

Да, у нас так и было.

→ Ответить

yahooo

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

+12

наверное не будет ни одного гран-при, в котором в условии не будет косяков

→ Ответить

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

Что-то не могу в первый уровень написать, странно.

Расскажите, пожалуйста, а как решать задачи Q (про вып. оболочку) и N (про даты).

Спасибо.

→ Ответить

Jughead

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

← Rev. 2 →

Q - хз. N - если P > 10 ^ 5, то бежим по всем числам которые кратны P и в тупую проверяем, если меньше, то динамика на цифрах числа.

→ Ответить

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

А как в динамике кратности учитывать?

→ Ответить

Jughead

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

f(i, r, l) i - сколько цифр осталось, r - остаток от деления на P префикса, l - флаг меньше/больше/равно

→ Ответить

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

А, остаток, точно. Спасибо большое.

→ Ответить

Timur_Sitdikov

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

← Rev. 2 →

Мы N решали так. Преподсчитываем в лоб для чисел от 0 до 10 ^ 6, сколько таких "хороших" чисел дает остатки от деления на P, равные 0 ... 10 ^ 6. Далее идем по первым 6 цифрам 12-значных чисел (включая числа с ведущими нулями), если они хорошие, находим для них кол-во подходящих вторых половин по похдодящему остатку от деления на P. Ну и всякие важные тонкости, например нельзя состыковать половинки вида 000001 и 000001 для множества цифр, не содержащего 0.

→ Ответить

olpetOdessaONU

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

У нас такое же решение, но не хватило 8 минут, чтоб его додебажить и Д. Обидно. Могло бы 9 зайти...

→ Ответить

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

Для нахождения выпуклой оболчки достаточно для каждого X, которых не более [0, 1000007) найти наибольший и наименьший Y. Но у нас возникла проблема в долгой генерации (Xi,Yi). Тогда найдем периоды, через сколько зациклится Xi и Yi - X_len, Y_len. Далее пробегаем по всем X из [0, 1000007), смотрим где он первый раз встретился, и дальше прыгаем по массиву Y с шагом X_len, беря индекс по модулю Y_len.

→ Ответить

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

Как J из второго решается (про диету Деда Мороза). Вся беда в точности, или вообще неправильное понимание условия? Решали и бинпоиском по коэфу кратности, и бинпоиском корня k-ой степени, и прямым взятием сишного корня...

→ Ответить

Nikolai

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

← Rev. 2 →

Я решал двумя бинпоисками, первый, если p > q, то от 0 до 1, второй, если q > p, от 0 до 100000. Eps=1e-15 у меня.

→ Ответить

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

Извините, а вы про какую задачу? Я что-то никаких диет не вижу...

→ Ответить

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

Там в их втором дивизионе несколько другой проблем-сет просто был, насколько я понял. Это не второй дивизион опенкапа.

→ Ответить

LesyaPhoenix

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

Бинпоиск? оО

 q=pow(P/(Q+0.),1/(k-1.));

 bn=Q*pow(q,n-1.);

 printf("%.5f\n",bn);

→ Ответить

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

Где можно добивать?

Такое же решение тоже оправляли, ВА1. Названия файлов проверяли, сэмпл и наши тесты проходило, тупые баги искала вся команда примерно час.

Словом, фэйл, решить 7/10 за 3 часа до конца, 9/10 за 2 часа до конца, и при этом не решить последнюю.

→ Ответить

LesyaPhoenix

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

На сколько я знаю, команда из моего универа пыталась сдать такое же решение, но только считая сразу член последовательности .

Q*pow(P/(Q+0.),(n-1.)/(k-1.));

И также ВА1 раз 11 подряд) Я не могу даже такой тест подобрать на котором оно челенджится. И это какой-то реальный фэйл.

→ Ответить

Fcdkbear

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

Что там с задачей C див1?

→ Ответить

gchebanov

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

← Rev. 2 →

У нас зашла только на Java. (это про opencup.ru )

→ Ответить

Zhukov_Dmitry

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

← Rev. 2 →

В задаче C проходило, наверное, любое решение на Java, и почти ничего не проходило на C++. (это про div1 опенкапа :)

→ Ответить

fetetriste

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

← Rev. 2 →

В задаче С не проходило немного недооптимизированное решение на Java и проходило дооптимизированное на C++

И это если решение типа $\text{[math]}$ , где b — индекс простого, считалось правильным. А то может там ещё какая-то хитрость есть.

→ Ответить

ilyakor

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

+11

Странно, у нас сразу зашло тупейшее решение на c++ (как только заработало за нормальное время локально - сабмитнули, никаких проблем с ТЛ не было). Делали так - meet in the middle по множеству простых, первый набор чисел (~1.5 миллиона) сортируем, второй - генерим "жадно" (сами числа не нужны, нужен только ответ, поэтому если пришли в состояние (n, {p_i}), где $\text{[math]}$ , где уже были раньше, то возвращаем ответ).

Ну а если совсем тупой перебор не заходил - так это уж проблемы участников, нефиг лажу толкать ;)

→ Ответить

cmd	13 лет назад, # ^ \| +5 Мы вот додумались до meet in the middle, но до бубна не додумались =) В итоге работало локально где-то 5-6 секунд на макстесте, ну и не зашло соответственно. → Ответить

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

Автор предполагал, что нужно придемать две оптимизации - такое запоминание и предподсчет чисел для нескольких первых простых.

→ Ответить

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

Можно подробнее про бубен? Я сделал так: генерим левую часть, сортируем её, перебираем правую, бинпоиск для нахождения количества валидных пар. На макс тесте было немного больше чем TL, но переписав на Java, все прошло. Генерация чисел и перебор - рекурсивные.

→ Ответить

ilyakor

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

Ну вот есть рекурсия для второй части. Там 2 параметра - n и сколько ещё простых, и возвращает она число (а в листьях рекурсии делает бинпоиск). Так вот, если $\text{[math]}$ , то сохраним то, что она возвращает, в массив, и при следующем вызове с такими параметрами сразу вернём ответ.

→ Ответить

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

← Rev. 2 →

Спасибо, кажется понял. Перебирается левая часть, сортируется, перебирается правая часть. В листьях перебора правой части надо найти upper_bound от целой части N / X. Я не сразу сообразил что, целая часть от N / X в некоторых листьях будет одна и та же.

P.S. На моем компе работает чуть дольше, чем без запоминания. Но на сервере - ОК :)

→ Ответить

Petr	13 лет назад, # ^ \| +18 Мы, конечно, писали на Java, но у Андрея на макстесте работало 0.1s, кажется. Так что и на плюсах должно было заходить :) → Ответить

AlexanderBolshakov

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

Вы - это все-таки вы :)

→ Ответить

KADR	13 лет назад, # ^ \| +8 А можно посмотреть на код, который на макстесте 0.1с работает? → Ответить

Petr	13 лет назад, # ^ \| +5 Правда ваша - похоже, перепутал эту задачу с какой-то другой. На самом деле работает 1.1s: http://pastebin.com/3FTvcHPh → Ответить

Petr	13 лет назад, # ^ \| +10 Хм, в этой версии есть переполнение инта, странно, что она работает. Вот вроде без бага: http://pastebin.com/2Twssz4p → Ответить

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

Вообще какой-то странный эфект. Автор задачи - Burunduk1, который все-таки пишет на плюсах.

→ Ответить

Anarivu

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

+18

скоро ли будет проведен реджадж по С (про хоровод)?

и когда разморозка?

→ Ответить

CherryTree

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

Расскажите пожалуйста как решать C и G первого дивизиона.

→ Ответить

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

G: Динамика по профилю с изломом. Профиль - набор из 0 (клетка белого цвета с белыми соседями), 1(клетка белого цвета с 1 черным соседом) и 2(клетка чёрного цвета). На очередное место пробуем поставить черный квадрат. Если после этого меняет свой цвет одна из двух соседних клеток (соседняя вверх или влево), то тогда мы не рассматриваем такой переход из этой маски, потому что вместо того, чтобы сначала ставить белый квадрат, а потом принудительно закрашивать его черным, мы в неком другом профиле сразу поставили чёрный.

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

O(3^W * W * H * W)

Вот

→ Ответить

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

← Rev. 2 →

А от куда а вас еще одно *W взялось?

UPD. А по коду понял. Можно избавиться от *W, если заранее предподсчитать что происходит при постановке какой клетки рядом с какими.

→ Ответить

Ripatti

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

G еще можно запихать:D Дп по обычному профилю в лоб. Заметим, что валидных профилей толщины 1 - около 2000, профилей толщины 2 - около 100000, а толщины 3 - около 8*10^7. Предпросчитаем все валидные переходы для профилей толщины 3 в виде [номер профиля толщины 2]->[номер профиля толщины 1] и запишем в массив векторов. Будем считать dp[n][профиль толщины 2], используя предпросчитанный массив. Как считать - вроде бы очевидно)) Итого решение за O(n * 8*10^7) с мелкими хаками. Это работает около 4с.

→ Ответить

luckyi

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

так в Харьковском див1 14 тест задачи Хоровод уже исправленный или нет?

→ Ответить

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

На дорешивание опенкапа сдавать можно

→ Ответить

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

А вообще WA 14 - это OK после реджаджа с почти 100% вероятностью.

→ Ответить

niyaznigmatul

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

Кто-нибудь знает как предполагалось решать задачу А с Гран-при Петергофа?

→ Ответить

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

Бфсом с двух концов.

→ Ответить

Petr	13 лет назад, # ^ \| +14 Ух ты! Зашло в дорешивании бфсом с двух концов. А почему это быстрее, можно как-то осознать? Наверное же можно искуственно сделать, чтобы именно в среднем слое было мало состояний? → Ответить

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

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

→ Ответить

avm	13 лет назад, # ^ \| 0 Не уверен, что такие тесты существуют. IMHO, если в поиске с двух сторон, расширять ту из половин, в которой на предыдущем ходу было меньше вершин, то это должно ускорить скорость нахождения решения. → Ответить

1a1a1a

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

а можно где-то досдавать задачи ?

→ Ответить

AlexanderBolshakov

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

На опенкаповском сайте есть кнопочка "Дорешивание".

→ Ответить

Monyura

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

Как скоро в дорешивание появятся задачи IX чемпионата?

→ Ответить

Prestige

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

-17

Может кто-то дать пароль с опен капа?

→ Ответить

Hohol

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

+25

Снарк может.

→ Ответить

Scorpy

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

← Rev. 2 →

Кто-нибудь что-нибудь знает про объединение результатов?

→ Ответить

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

← Rev. 2 →

Кто знает, как решалась Е div 1? Мы пытались пропихнуть динамику по вектору (количество компонент-деревьев каждого размера) + количество компонент с 1 циклом, но там выходило порядка 8М состояний, что едва ли вписывалось в МЛ и работало несколько минут на макстесте:(

→ Ответить

Petr	13 лет назад, # ^ \| +16 У меня считалось количество компонент валентности 1 каждого размера - таких состояний 1.3M (каждая компонента имеет валентноть 0 либо 1, но компоненты валентности 0 нам не интересны - только их суммарный размер, который получается вычитанием). → Ответить

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

М-да, это надо обладать особым талантом, чтобы ввести левый параметр в динамику, который все усложняет и никому не нужен:(

Спасибо!

→ Ответить

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

Внезапно! После того, как я начал всегда проводить ребро от компоненты самого большого размера, а не самого маленького, количество состояний на тесте "50 0" упало с ~1.295М до 1276. Правда, получает ВА по точности (при умножении на 2⁴⁹ 9 знак теряется), но ВА 60 показывает, что это верное решение. Интерестно, знали ли о нём авторы:)

→ Ответить

Joshik

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

Нас этот результат тоже поразил. Все оптимизили и оптимизили и тут вот вдруг решение стало работать бесконечно быстро:)

→ Ответить

Gassa

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

+18

Да, так действительно в очень много раз быстрее. Теоретически, правда, не знаю, как хорошо оценить. Но интуитивно (а также если при отладке вывести все просмотренные состояния) понятно: например, из разбиения на слагаемые 50 = 1 + 1 + 1 + ... + 1 не получается других размера ровно 50, кроме 50 = x + 1 + 1 + 1 + ... + 1, то есть всего 50 из 204 226 разбиений, следующие тоже получаются не более чем с двумя числами, отличными от единицы, и так далее. А если проводить ребро из самого маленького слагаемого, получаются чуть ли не все разбиения на слагаемые.

Правда, самый долгий для такого решения тест — не 50 0, а что-то типа разбиения 50 = пара троек + десяток двоек + сколько осталось единиц. Но даже на таких тестах работает очень быстро (не оптимизированное решение с map <vector <int>, int> [51] укладывается в 0.4 секунды).

Кстати, в этот раз жюри для разнообразия было “добрым” и ставило ограничения в большинстве задач по не самым оптимальным даже асимптотически решениям.

→ Ответить

caustique

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

Вроде B рассказывали на разборе, но интересно было бы еще раз послушать решение.

Кроме того, вопрос: есть ли полиномиальное решение для произвольного графа, а не только дерева, для такой же задачи?

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

→ Ответить

Zhukov_Dmitry

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

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

Решалась точно так же, только сначала двусвязные компоненты сжимались в вершины и получалось дерево.

→ Ответить

Zhukov_Dmitry

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

В задаче B для произвольного графа, наверное, тоже работает.

→ Ответить

good_mood

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

и как же решать задачу В? для тех, кто не смог попасть на разбор

→ Ответить

niyaznigmatul

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

Заметим, что если в дерево добавить ребро vu, то все ребра на пути по дереву из v в u перестают быть мостами.

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

Это Heavy-Light Decomposition c деревом отрезков с массовыми операциями.

→ Ответить

caustique

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

Burunduk1 рассказывал более простое, по его словам, решение с LCA, но упомянул и это, сказав, что вы его сдали.

Есть ли у вашей команды идея решения с LCA (и что-то там было про дерево из 4*k вершин)?

→ Ответить

niyaznigmatul

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

Хмм.. На контесте я сдал то решение, которое описал выше. Ну в решении нужно было lca юзать, для того, чтобы разбить путь в дереве, на два вертикальных пути.

Какой-то идеи про LCA и 4 * k вершин не было.

→ Ответить

Joshik

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

+16

Более простое решение с LCA:

1) Разобьем каждое добавляемое ребро <v,u> на 2: <v,lca(v,u)> и <u,lca(u,v)>

2) Для каждой вершины предпосчитаем время входа и глубину.

3) Возьмем в дереве только интересные вершины - концы добавляемых ребер и lca соседних в порядке обхода DFS'a пар таких вершин (для этого просто сортировали ребра). Сожмем ребра.

4) Теперь запустим DFS на графе из этих вершин и решим задачу втупую (посчитаем кол-во покрытых ребер). Мы на самом деле не запускали DFS, а эмулировали его, отсортировав интересные вершины по времени входа.

→ Ответить

Petr	13 лет назад, # ^ \| +8 Дерево отрезков не нужно: нам ведь просто нужно посчитать длину объединения отрезков оффлайн :) → Ответить

Romka

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

На самом деле разница небольшая в масштабах всей задачи, ведь из дерева отрезков нужна только одна функция, set на отрезке, а это не больше 10 строчек.

→ Ответить

tiirz

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

С призами для онлайн учасников тишина?)

→ Ответить

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

+22

А можно выспаться? пожалуйста!

Организация Чемпионата для онсайт участников, а их было около 300 человек, - это несколько бессонных дней и ночей.

Всё что было обещано - будет

→ Ответить

Anarivu

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

+11

а дорешивание будет где нибудь открыто?

→ Ответить

Scorpy

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

А можно узнать, что произошло с задачей E у команды ХНУ им. В.Н.Каразина: Челноков, Гризун, Подлесная ?

→ Ответить

sdya

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

← Rev. 2 →

Отправка была за 10 секунд до конца контеста и тестирующая система не успела загрузить себе решение (поскольку ее выключили почти сразу после контеста). В итоге решение было протестировано позже (примерно в 20 часов), когда систему снова включили. Решение оказалось правильным.

→ Ответить

sholeg

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

С одной стороны, нельзя не порадоваться за такое везение команды (жаль, только что до награждения всё не прояснилось)....
Но всё таки осталась неясность. В таблице сразу после разморозки у этой команды было 3 неудачных отправки, последняя - в 4:59. После "окончательного подсчета" - оказалось 3 неудачных отправки + 1 удачная в 4:59. Внимание вопрос: на последней минуте было 2 сабмита или один?
И ещё: на закрытии одна из команд получила специальный приз за удачный сабмит на последних долях последней секунды контеста. Почему же не обработался тот, что отправлен "за 10 секунд до конца контеста"?
Наверное, я сам тут ответил на свой вопрос, но было бы приятно получить авторитетное подтверждение. :)

→ Ответить

sdya	13 лет назад, # ^ \| 0 Да, действительно, было 2 отправки в 4:59:10 и 4:59:50. И вторая из них была последней успешной отправкой на контесте. К сожалению, не я отвечал за тестирующую систему, поэтому не знаю причины, по которой она не успела загрузить сабмит. → Ответить

aRSeniy

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

Я ни капельки не удивлен тем, что мой сабмит проверили через 6 часов. Это нормальная ситуация! Как обычно идеальная организация! Но теперь без "слешей" :) Слава Богу задачи готовили хорошие ребята.

Кстати отправки по E у меня одинаковые, но одни получали ТЛ, а последняя прошла. Та же ситуация с J: 6 сабмитов одного кода 3 ТЛ и 3 ОК (причем прошли они за 0.1 сек из 1 допустимой) :)

В общем завидую тем, кто сдавал задачи в джадже, а не в этой великолепной ситсеме!

→ Ответить

avalizada

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

How to solve problem I ?
You could write answer in russian.:)

→ Ответить

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

Заведем массив used[v][n] - были лы мы в вершине v так, что когда пришли в нее мы уже прошли по n ребрам, которые сопадают с нужной последовательностью. В цикле для всех непосещенных used[v][0] запускаешь такой дфс (например рекурсивный, второй параметр - глубина рекурсии). Если пришли в состояние used[v][k] - выводишь текущий путь. Так как надо найти лексиграфически наименьшее, то списки смежности для всех вершин надо заранее посортировать.

→ Ответить