Раунд кончится в понедельник, 12 августа, в 14-00. Можете считать это небольшой напоминалкой (вход в контест).
Но пост не об этом. Кто вычитывает тексты условий? Уже второй раунд подряд нам предлагают такую ересь from my heart (задача C из Round 1, задача F из Round 2), что ну просто вообще невозможно понять, что от тебя хотят. Может, стоит назначить отдельного человека или даже группу людей, которые будут читать условия и гарантировать, что они понятные?
С пониманием задачи F из раунда 2 у меня проблем не возникало, но вот с задачей C раунда согласен на все 200%.
Более того, в условии одной из задач третьего раунда, когда я его вчера писал, была откровенная опечатка, делающая условие некорректным. Пришлось на свой страх и риск угадать правильный вариант, но, тем не менее, на понимание ушло порядочно времени. Я сразу написал снарку, эта опечатка уже исправлена, но чтоб я ещё хоть раз писал так раунд в самом начале срока... Пусть грабли собирает кто-нибудь другой.
Я в целом согласен с тезисом, что среднее качество условия на этом контесте ниже, чем хотелось бы.
А кто-нибудь знает, где можно посмотреть окончательные результаты 1 раунда?
Ну так в контесте же есть standings: http://algorithm.contest.yandex.ru/contest/328/standings/
Ок, спс) на http://contests.snarknews.info/ ссылку не нашел)
Скройте, пожалуйста, пост в черновики до окончания раунда: в комментах появились условия некоторых задач.
Написал Майку, попросил прибить комментарий. Дико извиняюсь перед всеми, кому испортил удовольствие, перепутал даты.
Расскажите, пожалуйста, о чём просят в В.
Два игрока играют на дереве. Изначально в вершине 1 стоит фишка, и эта вершина покрашена в черный цвет.
Первый игрок за ход красит любые k вершин, второй игрок передвигает фишку в любую из смежных вершин. Если второй ставит фишку в непокрашенную вершину, он выигрывает. Если все вершины покрашены, выигрывает первый.
Во вводе дано дерево. При каком минимальном k первый имеет выигрышную стратегию?
Кому интересно, переводы условий остальных задач:
A. Есть строка из символов V и W, за одну операцию можно выбрать несколько непересекающихся пар соседних символов и одновременно поменять местами символы в каждой паре. За какое минимальное число операций можно получить из первой строки вторую?
C. Есть два множества по n точек внутри квадрата со стороной 1. Найти минимум по всем паросочетаниям максимума (расстояние первой точки пары до границы) + 2 * (расстояние между точками в паре) + (расстояние от второй точки пары до границы).
D. Есть множество плохих символов и прямоугольник из r*c символов. Найти максимум отношения (число плохих)/(число всего) по подпрямоугольникам, у которых каждая сторона >=m
E. У нас есть число n. Изначально n = 1. За один ход можно выбрать d — делитель n, заплатить d рублей и заменить n на n + n/d. За какую минимальную стоимость можно получить число K?
F. Есть доска n*m и клетка (x,y). Найти кратчайший путь, который начинается и заканчивается в (x,y), и проходит по всем клеткам хотя бы один раз, и вывести его длину минус 1.
Ааа, это многое объясняет... Теперь я понимаю, как моё решение смогло не зайти. Но как тогда понимать эту фразу из условия?
Казалось бы, это явно противоречит пониманию с паросочетаниями? Эх, видимо, тактика "не читать бредовые легенды" не всегда прокатывает :(
Я получил OK, соединяя пару деревьев ребром если между ними околонулевое расстояние.
Не противоречит. Если К деревьев находятся в одной точке, то их координаты будут написаны К раз.
Ну это только если "правильно" интерпретировать написанное. Формально, одной только первой части фразы ("любое дерево из первой расстановки может оказаться на месте любого дерева из второй расстановки") достаточно для противоречия, т.к. в переводе на русский это означает "рассматриваются произвольные отображения" (и про то, что что-то должно быть сюръективным или инъективным, в контексте этой фразы ничего не написано).
Оффтопик — очень жаль, что мало кто из авторов задач следует стратегии "писать любую ахинею в легенде, а потом нормальную математическую формулировку в конце легенды или в формате данных". Это бы существенно упростило парсинг жутких текстов.
Как можно понять в F, что чувак начинает там же, где и должен закончить? Что за бездарные условия?
А еще чтобы проверить 1 x 1 = 1 вариант рассадки, нужно 0 просмотров.
и что последний просмотр он осуществит с того же места, которое занимал во время премьеры.где кончается путь — понятно, но где написано как соотносится премьера с началом пути? откуда следует, что не может быть такого: чувак посмотрел премьеру и через год только поговорил с владельцем и бла-бла-бла по легенде?
Вот хз если честно. Тот факт, что в инпуте вообще присутствует позиция чувака, явно намекает на то, что спрашивают не про цикл. Видимо, не стоит искать логику в условиях SNSS.
Эх, вот почему задачи не дают сразу в таком виде... После твоего комментария сразу сдал в дорешку:)
Расскажите, как решается эта задача?
Представим себе другую задачу: пусть k фиксировано, и есть дополнительный параметр m — первому игроку разрешается дополнительно закрасить m вершин на самом первом ходу.
Тогда найти такое m, при котором первый будет выигрывать, можно динамикой по дереву. Остается лишь бинпоиском найти минимальное k, для которого m(k) = 0.
код на Java
Кажется, Снарк нанял ребят с Тимуса писать ему условия.
+1
Интересно, мне одному кажется, что на SNSS/SNWS условия всегда были такими? Как и сам стиль задач, который по сути является блицом на стандартные алгоритмы, а не нормальным контестом. И задачи всегда брались из каких-то левых, но вполне себе открытых источников и потому время от времени для некоторых участников задачи оказывались известными. Ничего особенного, как мне кажется, не произошло.
Ну просто количество непонятных условий за эти два раунда уже превысило их количество за предыдущие два года, а так ничего особенного не произошло.
Я не против баянов, тем более, что, к сожалению, для меня задачи редко такими являются. А вот эти легенды... Иногда они даже нужны, как в задаче В на этом раунде, но в большинстве случаев это похоже на попытку усложнить жизнь участникам. Можно ведь и совмещать легенду и формальные объяснения, как это делают практически везде.
А как решать А?
Втупую проэмулируем:
0. Будем ставить на место Vшки, остальные встанут сами. Пусть их N штук. Очевидно, что k-ая в первой строке Vшка станет k-ой во второй строке.
1. Сформируем N пар (from, to), каждая обозначает, что Vшку, которая сейчас в позиции from надо довести до позиции to.
2. Тогда пошагово будем сдвигать всё, что можем на один шаг ближе к цели. Понятно, что порядок не важен — всё равно никто никому не помешает, если этого можно избежать (мешать можно только вовремя не сходив).
Выходит грубо куб, на деле быстрее — залетает за .2 на джаве.
Слава полным наборам тестов! По F АС получает и решение, которое на 1 10 1 5 выводит 18, и решение, которое на 1 10 1 5 выводит 10.
Разные тесты для разных трактовок условия! Пройди хотя бы один из двух и получи плюсик
Объясните пожалуйста. Есть вот такой код. На компиляторе : GNU c++ x32 (4.6), получает ва2. На компиляторе: GNU c++ (4.6), ОК. Скажите что дает такую разницу на примере этого кода? Не хотелось бы снова с таким столкнуться. Спасибо.
x.cpp: В функции «int query(int, int, int, int)»: x.cpp:56:21: предупреждение: неиспользуемая переменная «r» [-Wunused-variable] int r = 2; ^ x.cpp: В функции «int main()»: x.cpp:104:57: предупреждение: сравнение плавающих значений при помощи == или != ненадежно [-Wfloat-equal] } else if (t == maxx && (x * y) > sz) { ^Спасибо, первое предупреждение не повлияло ж? Надеюсь. А второе, оно не перегружено на сравнение с погрешностью? Получается что в GNU c++ (4.6) перегружено на проверку с погрешностью? Или мне просто повезло второй раз и впреть нужно даблы сравнивать только самописной функцией?
Первое предупреждение я привёл потому, что это похоже на логическую ошибку. Насчёт второго — да, повезло, числа с плавающей точкой на равенство лучше проверять с эпсилоном.
А как доказывать решение задачи Е?
Почему-то в дорешке нельзя послать задачу, выдаёт "Bad request :) ".
Вместе со смайликом?
Конечно :).
Прошу прощения, работаем над ошибкой.
Не только в дорешку. Вовремя я третий раунд начал...
Старый интерфейс работает в основное время тура. http://contest.yandex.ru/contest/Contest.html?contestId=330