На всякий случай напоминаю расписание раундов Google Code Jam.
Предлагаю после окончания раундов обсудить здесь задачи и решения.
Round 1A: 21.05.2011 05:00 MSK
Round 1B: 21.05.2011 20:00 MSK
Round 1C: 22.05.2011 13:00 MSK
Продолжительность контеста - 2 часа 30 минут.
К участию допускаются участники, прошедшие квалификацию (набравшие >25 баллов в 24-часовом квалификационном раунде).
В Round 2 проходят первые 1000 участников из каждого раунда.
- Если вы прошли отбор в одном из под-раундов, то вы не сможете участвовать в последующих под-раундах.
- Если вы не прошли отбор в под-раунде, то вы сможете принять участие в следующих под-раундах, если они еще останутся.
Например: вы не прошли отбор в Round 1A, тогда вы еще сможете принять участие в Round 1B и 1C. Если вы пройдете отбор в Round 1B, то уже не сможете принять участие в Round 1C, зато сможете участвовать в Round 2.
Предлагаю после окончания раундов обсудить здесь задачи и решения.
P.S. Во избежание неприятных ситуаций, прошу не обсуждать задачи вплоть до окончания текущего раунда.
Ничего не понял ><
Конкретно интересует насколько умный наш противник? Например, были слова aabc(его загадали) и aaad, он говорит букву a, после этого aaad останется допустимым словом?
Решаем отдельно для каждой последовательности букв.
Для каждого из 26 ходов делаем map<string,int> (всего 26 мэпов), который говорит, сколько есть слов, которые перед этим ходом будут иметь заданную маску, и при этом имеют в себе букву, которую на этом ходу назовет Шон.
Затем, имея эту карту, идем по словам, для каждого слова имитируем игру -- построенная карта нам подсказывает когда Шон будет делать ход, а когда нет.
Такое решение работает 7:20 секунд на большом тесте :о)
Мелкая С решается жадно -- если есть фигня, которая дает ход -- играешь ее. Дальше на каждом ходу либо играем лучшие (по количеству добавляемых очков) Т карточек, забивая на то, сколько карт они добавляют, либо играем лучшую карточку, дающую еще карту, и продолжаем рекурсивно. Так как в первом случае ходов больше не остается, решение не получается экспоненциальным.
Большое решение я писал динамикой, храня последнюю разыгранную карту, не дающую ход (дающие ходы играем сразу как берем). А правильно было отдельно хранить последнюю, дающую один ход, и последнюю, дающую два хода.
если осталось одно слово в векторе, то чувак уже ошибаться не будет и ответ это (0, v[0])
иначе построим для каждого слова из вектора битовую маску позиций, где стоит буква L[pos]
разобъём все слова на несколько множеств, в которых эти маски совпадают.
запускаем рекурсию на этих множествах со сдвинутой позицией pos, выбираем наилучший ответ.
ну и не забыть что в случае нулевой маски и количестве множест большем чем 1,
чувак пытался угадать букву и не угадал (т.е. произошёл промах)
не понял объяснения. "либо мы играем лучшую карту из 2й очереди.", а что мешает нам потом очистить все очереди? или это переход дп объясняется?
PS: 1 x 0 имеется в виду c x t ?
PS да
Можете выложить условия здесь?
P.S. Просто я уже отобрался и не могу участвовать, а порешать хочется.
P.S.S. Если это запрещено правилами, то не стоит :).
Не тудаДавайте новую тему вообще для раунда 1B
Должно 5e19 проходить, если я ничего не путаю.А тему можешь сам создать :).UPD. Ой, бред написал. 5e11.
Должно проходить 5e11, да.
Поиском в ширину :)
Сначала заметим, что ответ - это минимальное число сторон среди всех получившихся многоугольников.
Затем поставим какие-нибудь два разных цвета на соседние вершины и научимся красить многоугольник, у которого две вершины уже покрашено.
Все многоугольники, у которых появилось покрашенное ребро, заносим в очередь на покраску.
Такую ересь написал на это место, что оно упало и потом еле нашел глюк. Неправильные ответы были только на больших тестах (>200 вершин). Короче, у меня глючило если разность цветов этих вершин не взаимно проста с ответом. А такое могло возникнуть только при специальных условиях, так как обычно она взаимно проста и меняется только в специальных случаях. Намучился вобщем.
Скажу только по первому если у нас вершины покрашены в цвета A и B и ответ K>=3, то делаем перестановку чисел от 1 до K, которая начинается на A, B и циклически ее размножаем на наш многоугольник. Если последнее число оказалось равно первому, то меняем его на какое-то не равное первому и предпоследнему (такое найдется так как K>=3)
Пример
K=4 многоугольник из 9 вершин начинается на 3 1
получаем сначала
3 1 2 4 3 1 2 4 3
потом последнюю тройку меняем например на 1
3 1 2 4 3 1 2 4 1
если перевести во время, то будет
6 10 6 10 6 10 6 10
первые 20 часов летим с 0,5 скоростью
за это время пролетаем первые 2 планеты и 4 часа во второй
у нас остаются в часах
0 0 2 10 6 10 6 10
ускоряем в два раза две 10
0 0 2 5 6 10 6 5
20 + 2 + 5 + 6 + 10 + 6 + 5= 54
Пишешь первую, пишешь переборы по 3й и 2й (или нормальное решение по второй), укладываешься в 1:58 и проходищь)
Сложность на 1 тест будет O(10^5.3333 * 10^4)
получало Incorrect, а при выводе 10 - Correct, при том же самом решении.
А можно писать код в Far'е.
Там достаточно посмотреть в правый верхний угол и сразу видно, какой код у символа - ещё 15-20 секунд экономии :)
не могли бы найти лажу в этом коде по задаче С ?
:)
Смотрим сколько осталось лететь до каждой планеты через время t, берём L максимальных времен и делим их пополам. Вроде очевидно. :-)