Ссылка на страницу с результатами и задачами
Сегодня виртуально решали этот четвертьфинал и возникло два вопроса:
1) Зачем давать задачу I, которая в точности до символа копирует условие задачи с Osipovsky Cup 2014 (декабрь, Ковров), проходившего в центральном же регионе? Причем некоторые команды естественно присутствовали на этом соревновании, а некоторые нет (например команда занявшая 3-е место и не сдавшая её).
2) Я правильно понимаю, что задача E в предоставленных ограничениях не решается? :| Т.е. при циклах нулевого веса.
Других обсуждений, к сожалению, не нашел.
2) Забавно. Я даже не задумывался об этом когда решал. Видимо здравый смысл сработал где-то на подсознательном уровне. Но вообще конечно нехорошо что такие неоднозначности в условии есть.
1) Я думаю, что задачу I дали ошибочно. Уже после разбора мы увидели, что задачи совпадают (но не в точности до символа). До этого мы думали, что это похожая задача... 2) Если есть нули то у нас бесконечно много решений. Мы задали этот вопрос на разборе, нам ответили, что да, тестов с нулями не было и подразумевалось что циклов нулевого веса нет.
Да, на разборе сказали, что тестов с нулями не было. Однако, в 15 тесте, на котором мы получали WA, на вход дается нулевая матрица. Официальный архив с тестами
.
15 тест матрица 1000 на 1000 из нулей.
Но там не совсем понятное условие задачи. Нигде не написано, что пути должны быть простыми. И неоднозначно можно понять условие различия двух путей. В общем авторское решение считает пути 1-2-3-4 и 1-3-2-4 одинаковыми.
Поэтому проходили некоторые решения, которые на нули не обращали внимания.
.
Я неправильно написал про бесконечно много решений. Two routes are considered different if at least one city on the route is not the same as on the other route. То есть таких путей не бесконечно много и решение всегда есть.
Ну хотя да, если по хорошему вникнуть в это условие, то оно исключает ходы в саму себя и циклические пути.
P.S. Хотя нет, не исключает) Мы можем сходить по нулевой петле и вернуться в ту же самую вершину. Либо не ходить по ней.
Я думаю, что это условие лишь ограничивает размер путей(не больше количества вершин) и говорит о том как сравнивать два пути.
А ещё в задаче H решение (в том числе авторское) использует даблы, при этом ответ дискретный. И нигде не гарантируется, что если поменять данные на eps, то ничего не изменится.
Да, вы правы, я не придумал, как описать погрешность при вычислениях в условии задачи. На самом деле тесты генирировались так, чтобы сравнение ответа с высотой H по модулю было не меньше 0.01, я предполагал, что любые корректные вычисления в вещественных числах должны проходить.
Еще одна неточность в условии состояла в том, что не был описан случай с двумя цилиндрами, если все их радиусы равны R, а высоты различаются. Тут есть два варианта — один стоит на другом и один вкладывается в другой до основания. В авторском решении был первый случай, но по тексту условия и второй корректен.
В общем, мой первый опыт подготовки задач на серьезные соревнования оказался не слишком успешным.
круто я буду
Кстати, почему то поменяны в условии задачи K и J местами относительно того, что было на соревновании. Или так и задумывалось?
Ну, на сервере, на котором решали и уральцы, и команда NArFU, условия релевантны тем, которые были на соревновании.
Претензии по задаче E странные, условие вполне понятно сформулировано, никаких KSON-ов там нет.
Про задачу I странно, действительно, задачи совпадают. Когда я просматривал условия, то отметил, что задачи похожи, но предположил, что это "сиквел" той задачи. Кстати, в Коврове-2014 было не так и много команд из Центрального региона (РГАТУ2 и собственно ковровские команды); на самом деле жаль, так как набор задач, как мне кажется, вышел интересным.
А вот вопрос с задачей H (см. выше) неплохо бы исследовать. Там WA 14 у двух топовых команд УрФУ, ответы совпадают. Если есть контакты автора, могу переслать ему оба решения.
В задаче Е очень смутно дано определение того, какие пути называются различными. Судя по твоим комментариям, ты считаешь, что отличаться должны множества вершин. Решение, которое я сдал, на тесте
5
1 5
0 0 1 1 1
1 0 0 1 1
1 1 0 0 0
1 0 1 0 1
1 1 1 1 0
выводит 1 вместо 2 (пути 1-2-3-5 и 1-2-3-4-2-3-5).
Осмелюсь предположить, что в постановке с циклами нулевой длины и более-менее любым внятным определением отличающихся путей, эту задачу авторы решать не умеют.
Ну вот похоже, что авторы тоже так считают (судя по ответу на "нулевой" 15-й тест, да и на некоторые ненулевые тесты).
Хотя на этом тесте их решение тоже выдаёт 1. Так что проблемы не в условиях, а в решении; соответственно, в обсуждение вызывается и автор этой задачи.
Скорее всего в условии. Нужно было дописать, что пути должны быть простыми.
Ну или автор поставил более сложную задачу, но решил в итоге эту. В любом случае без автора на Opentrains это исправить не получится.
Плюс ещё ситуация с H кажется подозрительной. Ваша команда дорешивать H собирается?
наверное, но не сегодня
Я вроде как нашел в авторском ошибку в 60 строке. Надо бы пересудить. После ее исправления ответ начинает сходится с ответами участников.
P.S. Перетестировали.
Дак оно и сейчас сходится, смотря как понимать условие. Или оно начинает находить ответ для такого понимания?
Я про задачу Н.
Да, я автор задачи. Действительно, после соревнования выяснились пара проблем с условием и погрешностью вычислений. Перешлите решения, я попробую продебажить их локально. Почта [email protected]
Задача D — Teletype тоже оказалась баяном. В 2006 в Центральном ЧФ была аналогичная задача(G — Message).