Давайте обсуждать задачи. Но прежде давайте сыграем в игру: угадайте, какой вердикт по задаче С получает посылка
cout << "! 1 2 3 4 5 6 7 8 9 10 11" << endl
А также посылка №2
cout << "! 10 9 8 7 6 5 4 3 2 1 а может так?" << endl
Давайте обсуждать задачи. Но прежде давайте сыграем в игру: угадайте, какой вердикт по задаче С получает посылка
cout << "! 1 2 3 4 5 6 7 8 9 10 11" << endl
А также посылка №2
cout << "! 10 9 8 7 6 5 4 3 2 1 а может так?" << endl
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
TL?
Нет, не TL)
Задача I не блещет оригинальностью. Впрочем, я не против малоизвестных интересных баянов; но не очень хорошо, когда они могут сильно повлиять на топ standings.
Как С по-человечески решается? А то у меня уж слишком много рандома в решении.
Пошаффлим и пройдём с посорченным списком из 10 минимальных элементов. Сначала сравниваем с максимумом, если прокатывает — вставляем бинпоиском. Понятно, что почти всегда будет 1 сравнение на элемент (т.к. максимум из 10 минимальных обычно меньше рандомного элемента).
Точной оценки у нас не было, интуитивно кажется, что будет что-то порядка
сравнений, но доказывать не умеем.
Прикольно. А я сразу вставлял бинпоиском и тратил в среднем по 3 операции на вставку. Поэтому запускал эту штуку только после того, как количество элементов становилось меньше ~70, а до этого резал рандомом.
с какой вероятностью нам нужен будет бинпоиск, когда мы добавляем k-ый элемент?
.
Т.е всего нам бинпоиск потребуется в среднем
раз. Это вроде около 70.
Ну и оценка получается если я не туплю n + O(klognlogk), где k из числителя, logn из ряда и logk из бинпоиска.
Ну там для рандомного порядка индексов надо просто искать k минимумов обычным методом вставок. Почему-то сразу верилось, что такое успеется за указанное ограничение. Как-то интуитивно опирался на то, что 700 намного больше корня из n.
P.S. Редкий случай, когда в div2 задачу сдали быстрее, чем в div1. Пойду возьму с полки пирожок.
Редкий случай:
В отличие от задачи С, задачи D и F в двух дивизионах слишком отличались ограничениями.
Да... Из-за ограничений, мое решение по F двумя тринарниками даже близко бы не прошло тесты.
Теперь понятно. Я этого не знал, извиняюсь.
Строим дерево отрезков за n-1. Потом за klogn узнаём минимумы.
Двоичную кучу можно за O(n) построить.
Есть другое решение: Ищем вначале 1, потом 2, ... всего 10 итераций поиска минимума. Все время храним для каждого числа список тех, которых оно оказалось больше в результате сравнения. На каждой итерации берем все числа, которые оказались больше только предыдущих минимумов и устраиваем между ними чемпионат на выбывание. Каждый чемпионат проходит за количество кандидатов-1 сравнений. На первой итерации будет n кандидатов. На каждой следующей логарифм, тк глубина дерева в чемпионате логарифмическая, а кандидатом может быть только тот, кто проиграл лишь предыдущему минимуму
Расскажите, пожалуйста, решение A и F.
В А две динамики:
D1[k][mask] = наименьшая пара чисел (количество шагов; занятое место на последнем шаге) необходимые для того, чтоб k-тый грузовик вывез все предметы помеченные в битовой маске mask. Пересчитывается перебором последнего предмета, помещенного в грузовик.
D2[k][mask] — наименьшее количество шагов необходимых для того, чтоб первые k грузовиков вывезли все предметы помеченные в битовой маске mask. Пересчитывается перебором всех подмасок соответствующих грузу, перевезённому последним грузовиком.
Плюс восстановление ответа.
А: Найдём ответ для каждого подмножества предметов и для каждого контейнера динамикой по битмаскам (dp[i][bit]). А потом рекурсией с отсечением по ответу переберём контейнер для каждого предмета. Жутковатый код: http://pastebin.com/5VUN0Vds
Задача F почти идентична задаче поиска описанной окружности минимального радиуса для множества точек.
Общая схема решения:
Рассмотрим точки в случайном порядке.
Будем наращивать ответ. Если очередная точка уже лежит в ответе, то переходим к следующей, в противном случае говорим, что она обязательно должна входить в новый ответ. Вероятность этого события 3 / i.
После фиксации одной точки, идём сначала и ищем две новые точки для ответа таким же способом. На этот раз вероятность ошибки 2 / i.
Для двух фиксированных точек опять идём сначала и подбираем третью. Итоговая сложность — O(n), так как матожидание сложности каждого шага константное.
По трём точкам искать подходящую окружность уже скорее техническая задача: строим прямые или окружности Аполлония и пересекаем.
Я это и написал, и получил бревно. Не очень ясно, что делать дальше :)
Например, что делать, если из-за точности окружности Аполлония не пересеклись?.. Вы это как-то специально обрабатывали?
Есть еще случай "тупоугольного треугольника". Когда ответ это не персечение окружностей, а один из ответов для пар. Скорее проблема в этом.
С точностью там конечно грустно. Когда мы увидели твой тест сидели и долго думали. Потом я отошел от ответа на 10^{-9} в случайную сторону и совсем оно не прошло. Собственно клар дальше видели. Но это мы конечно не правы в любом случае.
Это как то должно совсем некисло расколбасить точность. Мы отдельно брали ответы для пар и нам казалось что это покрывает всякие плохие крайние случаи (кроме случая когда нет окружностей, а надо пересекать прямые).
А поделитесь кто-нибудь, пожалуйста, правильным решение по лабиринту.
Пусть N = max(10, H, W), H, W — максимальные ширина и высота куда мы зашли. Сделаем бфс с нашей клетки до клетки (N, N), но можем использовать квадрат N + 1xN + 1 с учетом найденных стен. N + 1 берем для того, чтоб нормально увеличивать N и до клетки (N, N) всегда можно было дойти.
Именно бфс?
С клетки идем в следующую так, чтобы уменьшить расстояние до (N, N). То есть на каждом шаге делаем новый бфс. Код
Примерно понятно, спасибо.
Не знаю, правильное ли, но зашедшее решение(в дорешку):
Считаем, что там где еще стен не видели — стен нет. Поддерживаем maxn — максимум встретившейся координаты. Если мы в клетке maxn, maxn, то ++maxn Делаем bfs из клетки (maxn, maxn). Пытаемся перейти из текущей вершины в ее предка в bfs'е (т.е пойти по кратчайшему пути)
А кто-то умеет оценивать число ходов в таком bfs'е? Мы, когда это отправляли — не умели:) При больших n из-за большого числа стен маршрут будет почти однозначным и мы не будем делать лишних ходов? 5*N+300 это интуитивно довольно мало — учитывая то, что за ход считаются еще и неудачные удары об стенки.
Ну я бы не сказал, что это так уж мало. Казалось бы, нам нужно 2N ходов + иногда 1 из двух кратчайших ходов закрыт(где-то 2N/3), а вероятность, что нас заставят вернуться хотя бы на 1 клетку назад всего 1/9
У меня были подозрения по поводу того, могут ли образоваться длинные тупиковые ветви, в которые мы сначала зайдем, а потом вынуждены будем возвращаться назад. Трудно представить, как выглядит случайный на треть заполненный лабиринт, если честно. Спасибо, с таким объяснением сомнений стало меньше.
Кстати, по поводу результатов на практике — наше решение падает на 75 тесте при ограничении в 1012 ходов, на 81 тесте при ограничении в 1013 ходов, и проходит при 1014 ходов.
В Div2 (за n2 + 1000 шагов) можно было просто устроить обход вдоль стенки. Он на 200 × 200 занимает 2500-3000 шагов без оптимизаций и ~2000, если немного улучшить.
В Div1 (за 5n + 300 шагов) для 200 × 200 надо было уложиться в 1300 шагов, поэтому такое решение уже не должно было пройти. Тут помогает заметить, что лабиринт квадратный, а значит, нам надо идти примерно вдоль главной диагонали. Будем запоминать, где мы уже видели стены, и искать следующую не посещённую клетку, в которую хочется пойти, каким-нибудь поиском в ширину (я просто на каждом шаге заново просматриваю 100 клеток, достигнутых поиском в ширину из текущей; а можно запускать новый поиск, только когда мы пришли к промежуточной цели или уткнулись в стену). В клетки ближе к главной диагонали и дальше от начала координат больше хочется пойти. У меня весовая функция клетки — это
row + col - abs (row - col). Такое решение обычно проходит лабиринт 200 × 200 за 800-1100 шагов.Поскольку в лабиринте всего треть стен, и он случаен, нам удастся идти, не сильно отклоняясь от главной диагонали. Для маленьких размеров возможны выбросы, но там спасёт константа 300 (шагов).
.
Есть как минимум четыре способа использовать такие (вероятностные) соображения на соревновании:
Знать по опыту.
Поверить.
Проверить программно.
Доказать аналитически.
Первое могло помочь любому, кто строил лабиринт алгоритмом Краскала. На соревнованиях задача про такое построение была как минимум на одном из недавних контестов Petr-а в Петрозаводске.
Второе очень легко использовать, но правильное применение (чему верить? чему не верить?) требует, опять же, опыта.
Третий способ занимает компьютерное время, но в целом тоже не очень сложен: написать генератор лабиринтов, повыводить их и просто посмотреть глазами (или даже посчитать какие-нибудь метрики). Алгоритм Краскала умеют реализовывать многие. При подготовке задач для меня это основной способ проверки вероятностных соображений.
Четвёртый способ обычно требует сильной математической подготовки. Можно делать грубые прикидки, как в этом комментари, но не всегда получается правда. В этом самом комментарии, например, оценка в 1/9, судя по результатам программ, получилась довольно сильно заниженной — она не согласуется с тем, что для 200x200 часто требуется ~1000 ходов.
Кстати, об альтернативном пути для дорешивания этой задачи: ничто в условии (а также в интеракторе) не запрещает пойти через лес.
Ахахахах, кто-нибудь так сдал?
К сожалению, нет — я нашёл только, что первый тест так разок прошли.
Огонь =)
А как можно пройти первый тест, но не пройти все остальные? Вряд ли даже жюри умеет проходить любой тест за 2n + O(1) шагов =)
Там какое-то решение со сложной логикой с закомментированными кусками. Вот, один раз ему повезло поплутать и прийти за 149 шагов. Во втором тесте тоже пришли, но плутали 2613 шагов уже.
Девиз сегодняшнего раунда: Интерактивные задачи — это проще, чем кажется.
Ну как сказать. Мы же не знаем, что там в лесу.
Подскажите, почему в задаче Е (grammar) в 3-ем примере ответ NO?
Потому ли что невозможно написять небезконечного слова?
J?
Обозначим за x вес на ребре после добавления потенциалов. В каждой компоненте связности (слабой) поставим 0 в одну из вершин. Далее идем по ребру в любом направлении и однозначно восстанавливаем во всех вершинах значения в виде (Ax+b), иногда попутно получая равенства ax+b=cx+d, из которых находим x. Если получили несколько таких значений x(или не разрешимое уравнение) — все плохо. Если ни одного — тогда можно взять x = 0 (или любому другому числу)
Спасибо.
А какое авторское решение задачи G?
А еще у вас что-то не так с чекером. У нас было два решения, которые выдавали разный ответ на тест 8 (одно из них -1, а другое какую-то конструкцию). Оба решение проходили этот тест и получали WA9.
Сейчас я вижу в системе четыре ваши посылки, и у всех на восьмом тесте ответ -1 — как и у жюри. А на девятом, действительно, WA, причём разные (один раз -1, три раза не -1).
Ой, действительно, я перепутал. 8-й это видимо тест с нечетным n и a = 1.
А как все-таки правильно решать задачу? (Я уже получил АС, но решение получилось с разбором кучи случаев, есть ли там красивое решение?)
Некоторое вдохновение, чтобы решать задачу, можно почерпнуть в статье Константина Кнопа о взвешиваниях без разглашения. Собственно, идея задачи и получена из этой статьи и смежных текстов.
Описание своего решения я оставлю в правке. Но наверняка есть много более красивых способов.
Посылка с текста блога получает ОК, и вообще можно вывести любые 10 чисел и получает OK. Интересно, как жюри допустило такую ошибку?
И еще, как объяснить то, что контест на яндексе начался на 15 минут быстрее?
Это --ц, господа.
На yandex или где?
Не слишком удивелен если честно. Там интерактивы работают никак. Призывается lperovskaya. В ejudge и на онсайте работало нормально.
Раз упомянули онсайт — когда ждать размороженную таблицу? :)
И еще, кто-то может объяснить, почему всегда после подобных соревнований монитор opencup никак не отображает тот факт, что он еще далеко не окончательный? Например, можно сабмиты за последний час с онсайта отобразить хотя бы желтыми квадратиками. С этим есть какие-то технические трудности, или так специально делают?
Это вопрос к снарку, а не ко мне. Размороженный монитор вот. Олег его почему-то еще не смерджил. Вопросики в заморозку там тоже есть. Почему их не экспортит не знаю. Вообще онсайт начинается не слишком синхронно с кубком обычно.
Несколько минут назад: http://acm.math.spbu.ru/cgi-bin/monitor.pl/m141214.dat .
Слушайте, я опять вот нагнетаю, но зачем тогда этот Яндекс.Контест нужен вообще?
Интерактивки не работают, время рантайма он нормально замерять не умеет, нужно на опенкапе две системы поддерживать, какие-то непонятные различные времена старта из-за этого
Как-то много проблем с непонятной целью в итоге.
Он нужен яндексу. Можно воспринимать это так — яндекс спонсирует студентам поездки, а студенты тестируют ЯК. Желающим никто не запрещает писать в ejudge, так что все честно. Проблемы с мерджингом standings рано или поздно пофиксятся я думаю.
Еще там вроде с подсчетом МЛя были проблемы (что-то типа размер входного файла к нему добавлялся), если я ничего не путаю.
Контест начался на яндексе раньше из-за проблем с ejudge я так понимаю. Почему не отложили синхронно — не знаю. По поводу задачи C — это бага дорешки или на контесте тоже был кривой чекер? Будет ли rejudge?
Бага yandex.contest Чекер был и есть нормальный. Остальное решать snarknews.
Я думаю, Олегу по меньшей мере надо протестировать сабмиты по интерактивкам в еджадже, чтобы мы знали реальные результаты сабмитов. А дальше по тому, кого и как заффектило, принимать решение о том, как именно пойдут результаты в зачёт.
Павел, а поясни в чем было дело. Вот я уже сто раз нарывался на сложности из-за того, что все по-разному поддерживают интерактивки. Палевно это, надо унифицировать!
Проблемы в системе вида "никогда не смотрим на результат работы чекера" и "никогда не смотрим на результат работы интерактора" — это просто ошибки, которые надо исправить, а не нюансы поддержки интеракторов. Обсуждаемая система ещё не в той стадии, чтобы надо было унифицировать нюансы, к сожалению: чтобы унифицировать, надо сначала поддержать.
А мне кажется надо выработать общий стандарт как должно быть, а тех кто не поддержит (из основных игроков: Codeforces, ИТМО, СПбГУ, Яндекс.Контест, ejudge) укорять и называть недоразвитыми. Тогда быстренько поддержат и будет счастье :-)
Ну, есть несколько постов на CF о состоянии интерактивных задач на ~2012 год. Системы ejudge (версия Снарка) и testsys (СПбГУ) с этим более-менее справляются. С тех пор точно произошёл прогресс у Паши Абизяева, повлиявший на ejudge Снарка, но я не знаю деталей. Было бы здорово, если бы об этом кто-то написал пост.
По-моему там остались какие-то открытые вопросы (типа что произошло интерактор вернул PE так как упало решение или решение упало по RE так как интерактор сказал PE и неожиданно закрыл пайп). Плюс ИТМО только поддерживает как-то не так. Короче, имеет смысл оживить дискуссию.
Кроме того, я думаю отличная идея сделать модельную задачу (с кучей решений), которая будет демонстрировать все случаи разных вердиктов и ситуаций. Типа правильно система все вердикты выдает по задаче — значит ОК.
Да, сделать модельную задачу — это отличная мысль.
Хм, а можно больше конкретики? Я видел прекрасно работающие интерактивные задачи на я.контесте, значит, он их в каком-то виде таки поддерживает.
И да, что такое "результат работы интерактора"? stdout? stderr? созданные файлы? отправленные сетевые пакеты? Или имеется в виду код возврата?
Странное утверждение. Казалось бы, сначала должен появиться стандарт, а потом уже все должны его поддерживать, а не городить страшные велосипеды.
Из моего небольшого опыта с интеракторами на яндекс-контесте:
(1) Перед предыдущим чемпионатом университета выяснилось, что новая версия, в которой была улучшена поддержка школьных задач, почему-то проверяет мою интерактивную задачу только на первом тесте. Получившееся решение — откатить на предыдущую версию.
(2) На этом чемпионате университета было, видимо, несколько проблем (видимо — потому что я не уверен, что понял всё правильно). Во-первых, чекеры в интерактивных задачах, видимо, вообще не запускались (на предыдущем чемпионате с чекером return 0 это было неважно). Это выражалось в строчках лога типа
Здесь
ok (got to destination)— это комментарий интерактора. По плану интерактор выводил в выходной файл количество шагов, чекер читал его и сравнивал с лимитом, после чего выдавал ok/wa со своим комментарием видаwrong answer 31 x 31, steps 479, limit 455. Вообще, лог приведённого выше вида вызывает больше одного вопроса.Помогло встроить чекер в интерактор, это изменение делалось всего в пару строк. После чего, видимо, оказалось, что работает только один из вариантов testlib-exitcode-interactor и ejudge-exitcode-interactor в настройках интерактора.
Поскольку общее впечатление было, что в задаче D всё вообще не работает — настолько, что первые несколько посылок в яконтест я проверял перепосылкой в testsys — сообразить, что в задаче C может быть та же проблема с чекером, не сложилось.
В результате исследования свойств реализации интерактивных задач на платформе Яндекс.Контест выяснено, что в данный момент интерактивные задачи реализованы следующим образом:
Даже в случае кода возврата интерактора 0 чекер не запускается.
При завершении интерактора решение участника всегда убивается (то есть варианта "завершить интерактор и подождать, не случится ли TL/RT" нет).
Результат проверки посылки определяется кодом возврата интерактора, при этом используются только "testsys exitcodes" (то есть 0 = Accepted, 1 = WA, 2 = PE, остальное — Fail aka JE aka Crash).
Таким образом, реализовать интерактивную задачу на данный момент можно в случае, когда вся проверка делегирована интерактору. В случае наличия чекера его придётся интегрировать в интерактор, поставив в качестве чекера заглушку return 0; (чтобы работало и после предполагаемых исправлений).
Информация до разработчиков доведена; через какое-то время, скорее всего, ситуация с незапуском чекера будет исправлена.
К сожалению, OK не снимаются.
Задержка была со стартом D2, из-за чего условия были открыты только в 11-55 (практика показала, что если открывать на раздачу только Div1 условия, их раздают и Div2 и случается путаница). D1 был готов там и там.
Что касается интерактора по C. Сейчас ситуация проверяется, но результаты Гран-При вряд ли будут изменены — снятие OK после контеста, увы, не является допустимым действием. Единственный возможный вариант изменения результатов — снятие заведомо неверных решений типа того, что приведено в тексте сообщения.
Считать раунд зачётным, если в нём из столбца плюсов по C большое количество окажется нечестными, так же едва ли является допустимым действием.
В любом случае, хочется знать реальные резльутаты сабмитов по задачами.
Хотя бы для статистики можно будет узнать, какие решения по С на самом деле прошли, а какие — нет? Или, на худой конец, сколько — не указывая конкретные команды.
Не прошло у двух команд за пределами Top30, включая топикстартера. У остальных все сданные на контесте сабмиты прошли на ejudge. Отправленные для прикола в upsolving не прошли.
Так что на распределение очков как обычного, так и спонсорского зачёта сбой повлиять не должен никак.
Кстати, в случае каких-то нестыковок (неправильная склейка команд и так далее) по спонсорскому зачёту (второй промежуточный финиш) желательно сообщить до завтрашнего вечера. Вышеуказанную ссылку можно считать предварительным вариантом.
Было немного неочевидно, что делать, если получаешь PE на втором тесте. А когда стало понятно, что заходит любая чушь — интерес отлаживать решение пропал.
Расскажите пожалуйста K.
В дорешку зашёл 600-строчный код от e-maxx. Но мне почему-то кажется что кто-нибудь писал что-нибудь проще.
Первые степени простых не влияют. Поэтому можно искать только простые делители до 10^6. То, что осталось достаточно провеирть на квадрат, если не квадрат, то можно считать одним большим простым числом.
Спасибо. Вот именно этой проверки на квадрат мне и не хватило до акцептеда. Глядя на табличку в Div2, думаю не мне одному.
А E решается без симплекс-метода/метода эллипсоидов?
Прелположим, что все правила в грамматике имели бы в правой части не более одного нетерминала. Тогда для правила A — > Baa..abb..b проведем ребро из A в B веса, равного разности количества букв "b" и букв "a" в правой части, а для правила A — > aa..abb..b проведем ребро из A в специальную вершину-сток T с понятным весом. Получилась задача о поиске кратчайшего пути из стартового нетерминала S в T с отрицательными весами. На помощь приходит алгоритм Форда-Беллмана.
Теперь обобщим. Для каждого нетерминала X будем считать его "расстояние" — минимальную разность числа букв "b" и "a" среди конечных слов, выводимых из нетерминала X. Инициализация простая: если из нетерминала X выводится какая-то строка только из терминалов, то это и будет начальное "расстояние". Теперь будем n раз делать релаксацию: будем бежать по всем правилам и если оказалось, что во-первых, для всех нетерминалов в правой части правила уже посчитаны какие-то "расстояния" (то есть можно вывести хоть какое-то конечное слово), а во-вторых, суммарные "расстояния" в правой части плюс разность числа букв "b" числа букв "a" в правой части меньше, чем текущее "расстояние", то обновляем "расстояние" до нетерминала в левой части.
В конце проверяем, есть ли отрицательный цикл, и достижим ли он из стартового нетерминала. Сами расстояния храним в длинном числе.
Вопрос в том, сколько же итераций нужно сделать "Форду-Беллману". Точно не больше n + m, и есть идея (подтвержденная на контесте Accepted-ом), почему n: предположим, что ответ конечен. Построим вспомогательный граф, в котором проведем ребро между нетерминалами X и Y, если мы в какой-то момент при выводе оптимального ответа воспользовались правилом, где X в левой части, а Y — в правой. Может быть, используя этот ацикличный граф, можно доказать, что итераций надо n.
Часть про один нетерминал в правой части понятно. А как потом вы ищете отрицательные циклы — неясно, там же какой-то мультиграф. Или имеется ввиду, что если после m+n (ну или n, если удастся доказать) итераций что-то продожает релаксировать, то есть отрицательный цикл? Кстати, я даже m+n не умею доказывать, что хватит
Да, если после n итераций что-то прорелаксировалось, то считаем, что есть отрицательный цикл. Говорим, что из A достижимо B, если существует последовательность правил, которую можно применить к A такую, что в какой-то момент появится нетерминал B, и при этом вывод можно будет довести до строки из терминалов.
Про n + m итераций: построим полное дерево вывода. Утверждается, что на пути от корня до любого из листьев мы не воспользуемся одним и тем же правилом вывода (опять же, все в предположении, что ответ — конечный, т.е. нельзя получить строку со сколь угодно маленькой разностью).
Кстати, по поводу n итераций.
Пусть существует конечная оптимальная строка (т.е. та, которая минимизирует разность числа букв "b" и числа букв "a"). Рассмотрим дерево вывода этой строки, причем выберем то, в котором число переходов минимально. Докажем, что в этом дереве нет пути от корня до листа, в котором какой-то нетерминал встречается дважды.
Действительно, пусть такой путь нашелся, то есть в оптимальном дереве встретился нетерминал A (_нетерминал-отец_), и в его поддереве нетерминал A встретился снова (_нетерминал-сын_). Тогда посмотрим на окончательную строку, получаемую из нетерминала-отца, пусть в ней разность b и a равна x, а для нетерминла-сына она равна y.
То есть, если существует конечный ответ, то в дереве вывода на пути от корня до листа все нетерминалы различны, а значит каждый путь от корня до листа имеет длину не больше n, а значит n итераций релаксации достаточно.
Я тупанул, конечных достаточно как раз.
Хм, вот что непонятно. С ограничениями в условии задачи можно построить такую грамматику, что "расстояния" будут огромными, т.е. надо использовать BigInteger. Но тогда непонятно, как n итераций успевают с такими огромными BigInteger'ами.
Мы написали примерно такие же итерации на контесте (в int'ах), но получили WA42, и, подумав про переполнение и BigInteger, забили на задачу.
Мы понадеялись на лучшее:) И немножко пооптимизили длинку (от которой, кстати, нужно только сложение и вычитание).
Плюс стоит заметить, что у нас "расстояние" не может быть сильно положительным (нет смысла генерировать кучу букв b), а если оно сильно отрицательное, то оно уже - inf.
К тому же, есть ограничение на размер инпута (5МБ).
Странно, что никто из Div.2 нерешил. Ведь ограничения совсем маленькие: 1 <= n, m <= 2, 0 <= k <= 3.