Стартовала традиционная летняя серия индивидуальных соревнований SnarkNews Summer Series-2013. В этом году раунды серии также являются тренировочными раундами для участников турнира Яндекс.Алгоритм, а сама серия проводится на той же системе Яндекс.Контест. Доступно расписание серии.
Участвовать в серии могут все, кто имеет логин на Яндексе. Соответственно, для регистрации нужно зарегистрироваться на Яндексе и войти хотя бы в один из раундов серии. логин и пароль от почты и являются логином и паролем на вход в систему Яндекс.Контест.
В правилах серии есть ещё некоторые изменения: условия задач в этом году впервые будут предложены как на русском, так и на английском языках; кроме того, школьный зачёт заменён юниорским — для участников, которым на 1.09.2013 не исполнилось 18 лет.
Первый раунд закончился, как решать А и Е?
До 15:20 подождать стоит, наверно
Да, точно, не подумал, что закончить можно позже чем в 14:00.
Кстати, неплохо бы вернуть фичу "показывать, кто сейчас пишет контест и сколько времени у него прошло".
Такая фича есть, нужно зайти через contest.yandex.ru. Сейчас видно, что контест пишет eatmore и у него сейчас идет
59минута.Ну хотя бы что-то. Там зато не показывается, кто в каком режиме сдавал.
E — можно делать следующий образом (во время контеста не успел). Вначале найдем как соотносятся масштабы, это можно сделать используя соотношение длин кратчайших сторон каждой из ломаных. Пусть мы нашли это соотношение (т.е. при желании можно сделать одинаковый масштаб, но лучше просто потом использовать его, чтобы всё было в целых). Дальше надо сказать правда ли, что существует такой обход второй ломаной, что они совпадут с первой с точностью, до поворота или переноса. Это можно сделать следующим образом выпишием длины сторон (или например квадраты длин сторон), чередуя с углами (или можно например использовать векторное произведение или ещё какую-то функцию от угла) для каждой из ломаных. Получим 2 некоторых "строки", для которых надо сказать, правда ли, что существует циклический сдвиг второй, что они совпадут и найти этот минимальный сдвиг. А это можно сделать при помощи КМП или z-функции.
A — посмотрим на последнее удаление, т.к. всех остальных солдат уже нету в строю, необходимо, чтобы они шли подряд. Теперь если мы найдем последнее удаление, можно выкинуть этих солдат и решать аналогичную задачу для оставшихся, т.к. они будут заполнять пустое пространство и их можно игнорировать. Теперь задача свелась к тому чтобы поочередно выкидывать из строки подряд идущие символы необходимого вида. Это можно сделать при помощи стека.
А как насчет строки "WVWVVVWVWVVV"? Если я правильно понял решение, ответ будет содержать несвязные отрезки.
UPD у mexmans все правильно, я написал чушь.
1ый отряд, который мы найдем будет2,3,4,2ой отряд будет1,5,6,3ий отряд8,9,10,4ый7,11,12. Порядок же применения удалении этих солдат обратный.1ое удаление7,11,12, мы его можем произвести, т.к. между7и11солдатами нету пустых мест,2ое удаление8,9,10они идут подряд все ок,3ье удаление1,5,6, между1и5нету пустых мест. И последнее удаление2,3,4, тут тоже все ок. Надеюсь я ответил на твой вопрос.Извини, я неправильно прочитал условие (а понял вообще хуже некуда). Спасибо тебе за подробный ответ!
Removed (под спойлером ошибочный тест).
Удаляем по-порядку (1,2) (3,6) (4,5) (7,10) (8,9)
Спасибо, кажется я смог до конца понять (тест который я приводил запутал меня после, того как нашел его).
I'll just leave it here
А какое это имеет отношение к раунду? Там вроде только про 4 числа похожая задача, но она настолько простая, что не вижу в этом ничего страшного.
А так?
Мне кажется, что решение из этого архива неверное. http://acm.ashland.edu/2009/Problem-Set/Solutions/A.java Как он может учитывать случаи, когда промежуточный результат не делится нацело? Пример: 1 3 4 6 24 = 6/(1 — 3/4) и без дробей это никак не составить.
Да, похоже тесты слабые. Но этот — не очень подходящий, я умею получать 21 = 1*(4*6-3).
Ниже от cerealguy 21=8*((13/8)+1)
Так задача-то другая, в частности в условии написано
Division can be used only if the divisor evenly divides the dividend.Спасибо, теперь разобрался!
Еще http://e-olimp.com/problems/1749
А вот это уже не круто, даже семплы такие же)
На следующих раундах буду гуглить фразы из условия.
Это, конечно, сарказм, но смысла гуглить в любом случае немного.
Все раунды SN*S состоят из "баянистых" задач, уже где-то использованных, и это довольно известный факт, но контесты от этого хуже не становятся. Задачи уже кто-то прорешивал, багов мало. Эта серия соревнований — просто интересные тренировки. Никакого профита/удовольствия от читерства на соревновании, которое держится исключительно на честности участников (целая неделя виртуального контеста) испытать не получится.
А еще некрасиво себя чувствую, отвечая на вопрос "Уверен ли я, что комментарий на английском языке". Было бы хорошо иметь возможность продублировать комментарий на двух языках или отправить русский коммент в английскую ветку отдельно.
Сдал задачу D поиском в ширину. Начинаем из тех вершин, где можно зайти во дворец, при этом не переходим по тем ребрам, которые можно заблочить с той стороны. Почему это верно? Кажется, что это не всегда бывает верно.
Построим ориентированный граф (раздвоим каждый коридор) и удалим те дуги, которые можно закрыть (предположим, что они сразу закрыты). Тогда безопасными останутся только те вершины, которые недоступны из внешних вершин (в которые можно попасть снаружи). Понятно, что опасная вершина не сможет стать безопасной, также как и безопасная стать опасной (все пути в нее из опасных вершин можно перекрыть).
Мне было неочевидно, почему бургомистр сможет вернуться в укрытие после того, как закроет все необходимые двери.
Тесты с первого раунда как-то можно посмотреть?
Да, на http://contest.yandex.ru/
Задача С. Почему во вводе локомотив считается вагоном, а в выводе нужно число вагонов без учета локомотива? Как до этого можно догадаться, кроме как придумывая разные варианты того, что могут спрашивать в задаче, и проверяя на соответствие примерам? Как после того, как догадался, быть достаточно уверенным, что правильно понял, чтобы заслать вслепую? Такое условие не кажется логичным, поскольку не отличает случаи, когда может проехать локомотив и не может проехать ничего.
Задача E. Является ли следующий тест корректным?
Если да, то был ли подобный тест в наборе? Если не было, то почему?
Если нет, то почему об этом не сказано в условии?
Мое решение в дорешивании получает вердикт "не удалось протестировать".
Слабые тесты. Решение, в котором все промежуточные вычисления делаются в целых числах, получает AC, хотя должно падать на тесте
В C я вообще полконтеста думал, что можно произвольно переставлять вагоны, оставляя локомотив первым.
Про C все было написано довольно четко, в том числе в описании ввода -
Да, про задачу B удивило, что ее так активно чисто сдают, неужели все сразу сообразили, что в целых не получится...
Как посмотреть результаты раунда, которого я не писал?
Очки за разделённые места не делятся...
как решать D из третьего раунда?
Заметим, что если мы построили тройки чисел, то теперь если мы отсортируем все первые числа, все вторые числа и все третьи числа, то новый набор троек тоже будет валидным. Теперь переберм двоичным поиском ответ, возьмем в качестве первого числа все меньшие, в качестве третьего — все большие, а средние будем пытаться подставить в порядке возрастания
А задача A? динамика по профилю с какими-то хитростями?
Зачем с хитростями? Там же TL 24 секунды. У меня на джаве предподсчет ответов для всех возможных (N, M, k) работает 9 секунд. Единственное, что может быть необычно: у нас много состоний и переходов, которые нам не подходят, поэтому можно вначале построить граф, где вершины — маска одной строчки поля, а ребро между вершинами, если одна строчка может находится рядом с другой. Ну а дальше обычная динамика по профилю.
Кстати, никто не заметил, там изначально 24 секунды было? Просто, когда я думал как решать, мне показалось, что там около 6 секунд было.
Когда я писал, точно было 24, но, самое обидное, я заметил это сразу после конца контеста, последние несколько минут которого я потратил на то, чтобы запустить предподсчет у себя на компе и сохранить в виде готового массива с ответами (и в итоге нехватило совсем чуть-чуть времени, чтобы получить АС) :(
А если бы в телескопе нужно было 4 линзы, то задача бы решалась? А если k?
Тоже двоичный поиск, и тогда k - 1 раз выбираем следующие: вторые, третьи, и.т.д. линзы из невыбранных, причём по возможности наименьшие. Я думаю, это работает, т.к. нет смысла брать линзу больше, чем можно взять.
Отличное условие в C!
"Первая строка входа содержит целое число T — количество тестовых примеров." -- в условии
С нулями в семпле, причём правильно с нулями. А можно ли как-то попытку снять за это?
UPD: Сняли, спасибо :)
По просьбам участников петрозаводских сборов раунд продлён до 2 сентября 15-00, так что просьба воздержаться от обсуждения до окончания раунда.
Ок!
А сборы это форс-мажор?