Google Code Jam 2011: Round 1

13 лет назад, # ^ |

Ну наверное еще сказывается, что пишешь рано :) По крайней мере в 1А у меня это сильно повлияло.

→ Ответить

mastersobg

13 лет назад, # ^ |

Кстати, сколько себя помню, я ни разу в 4-5 утра не писал успешно. Всегда обидные тупняки, фейлы и баги))

→ Ответить

13 лет назад, # ^ |

+1) Поэтому уже давно не пишу в это время. в 1А просто подумал, что будет просто, но ошибся)

→ Ответить

13 лет назад, # ^ |

Не знаю как 1A, 1C был проще 1B в смысле прохождения, что и понятно: -2000 участников с первых двух раундов.

→ Ответить

13 лет назад, # |

Контест начался!

→ Ответить

13 лет назад, # |

А там в табличке уже окончательные результаты по Large сабмитам стоят?

→ Ответить

13 лет назад, # ^ |

При окончании контест сразу поднялся на почти 100 мест=> Видимо да

→ Ответить

13 лет назад, # ^ |

Так там же только сверить файл с эталоном. Это не очень нагружает систему. А перепосылать large все равно нельзя. Вот они и тестируют по ходу контеста.

→ Ответить

mmaxio

13 лет назад, # |

Объясните, пожалуйста, толком условие задачи B

→ Ответить

13 лет назад, # ^ |

Вы загадываете слово из списка.

Второй человек называет буквы в каком то порядке, если они соответствуют хотя-бы какому-то слово из словаря, которые еще подходят под то, что есть)ранее названные буквы на тех же местах, что и в загаданном слове)

→ Ответить

mmaxio

13 лет назад, # ^ |

Ничего не понял ><

Конкретно интересует насколько умный наш противник? Например, были слова aabc(его загадали) и aaad, он говорит букву a, после этого aaad останется допустимым словом?

→ Ответить

13 лет назад, # ^ |

нет, он понимает, что это не верно(если верить анонсу)

→ Ответить

ballon

13 лет назад, # ^ |

Нет.

→ Ответить

13 лет назад, # |

Хехе, одной хватило

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-7

А что сложного в B-small — перебор за О(n^2*m*26) вроде бы просто пишется?

→ Ответить

13 лет назад, # ^ |

Вроде бы просто, но еще руки кривыми бывают) Что-то не зашло

→ Ответить

13 лет назад, # ^ |

Зашло в практис чуть исправленное

→ Ответить

13 лет назад, # |

-9

А у меня палиндром — 474 =)

→ Ответить

13 лет назад, # |

Что - то я видимо утром туплю. Объясните, пожалуйста, как нормально сдавать B-hard? Я делал всякую муть с хешами и масками, но это было оочень долго)

→ Ответить

Nyatl

13 лет назад, # ^ |

Я в map кидал хеши открытых букв для каждой строки, потом для каждого хеша ставил метку, есть ли в какой-нибудь строке с таким хешом очередная буква. По времени у меня отработало за минуту, но я ошибся в подсчёте хеша.

→ Ответить

natalia

13 лет назад, # ^ |

Фиксируем последовательность букв. Идем по ней. Обрабатываем все слова одновременно. Для каждого из них храним, что уже отгадали. На каждом шаге пытаемся делать переход во всех словах, сортируем их и объединяем в группы. Асимптотика M*N*logN*длину строки.

→ Ответить

13 лет назад, # ^ |

Ясно, спасибо! Что - то, конечно, затупил)

→ Ответить

AlexSkidanov

13 лет назад, # ^ |

Решаем отдельно для каждой последовательности букв.

Для каждого из 26 ходов делаем map<string,int> (всего 26 мэпов), который говорит, сколько есть слов, которые перед этим ходом будут иметь заданную маску, и при этом имеют в себе букву, которую на этом ходу назовет Шон.

Затем, имея эту карту, идем по словам, для каждого слова имитируем игру -- построенная карта нам подсказывает когда Шон будет делать ход, а когда нет.

Такое решение работает 7:20 секунд на большом тесте :о)

→ Ответить

13 лет назад, # ^ |

Спасибо, Шурик) Но так то 7:20 - критично немного :) А С ты как делал?

→ Ответить

AlexSkidanov

13 лет назад, # ^ |

Мелкая С решается жадно -- если есть фигня, которая дает ход -- играешь ее. Дальше на каждом ходу либо играем лучшие (по количеству добавляемых очков) Т карточек, забивая на то, сколько карт они добавляют, либо играем лучшую карточку, дающую еще карту, и продолжаем рекурсивно. Так как в первом случае ходов больше не остается, решение не получается экспоненциальным.

Большое решение я писал динамикой, храня последнюю разыгранную карту, не дающую ход (дающие ходы играем сразу как берем). А правильно было отдельно хранить последнюю, дающую один ход, и последнюю, дающую два хода.

→ Ответить

goo.gl_SsAhv

13 лет назад, # ^ |

← Rev. 3 →

я написал рекурсию (макс_количество_промахов, индекс_сложного_для_угадывания_слова) S(v - вектор_индексов_слов_которые_подходят, pos - позиция_в_списке_L)

если осталось одно слово в векторе, то чувак уже ошибаться не будет и ответ это (0, v[0])
иначе построим для каждого слова из вектора битовую маску позиций, где стоит буква L[pos]
разобъём все слова на несколько множеств, в которых эти маски совпадают.
запускаем рекурсию на этих множествах со сдвинутой позицией pos, выбираем наилучший ответ.
ну и не забыть что в случае нулевой маски и количестве множест большем чем 1,
чувак пытался угадать букву и не угадал (т.е. произошёл промах)

работает 15 сек

→ Ответить

Ferlon

13 лет назад, # ^ |

Да я вот так же сдал в дорешивании, но у меня работало минуты три. Чем хорош GCJ - можно вести себя естественно, а не делать вид, что руки у тебя растут из плеч O:-)

→ Ответить

madkite

13 лет назад, # ^ |

Такое же решение, только с небольшими оптимизациями (типа использования вместо самой строки хеш, который на длине до 10 можно сделать уникальным, использования одного map-а вместо нескольких в котором перезаписываются только изменённые значения, ну и вместо количества - set) и на Java у меня решает B-large за 15 секунд.

→ Ответить

13 лет назад, # |

А на чем у людей A-large слетел?

→ Ответить

kormyshov

13 лет назад, # ^ |

скорее всего long long

→ Ответить

Alex_KPR

13 лет назад, # ^ |

у меня упала из-за вот этой строчки:

if ((pg==100 && pd==100) || (pg<100 && pg>1) || (pg==0 && pd==0)) ans=true;

→ Ответить

L.I.S.

13 лет назад, # |

А С easy решалась перебором количества добавленных, предварительно выкинув все карты которые увеличивают количество ходов?

→ Ответить

Egor	13 лет назад, # ^ \| ← Rev. 2 → 0 C easy решалась симуляцией + после каждого хода смотрим, не надо ли взять все оставшееся 0 x 0 картами → Ответить

goo.gl_SsAhv

13 лет назад, # |

как решалась C large?

→ Ответить

Egor

13 лет назад, # ^ |

Заведем 3 приоритетные очереди - будем хранить очки для имеющихся карт вида 0 x 0, 1 x 0 и 2 x 0. При добавлении карты если у нее t != 0 сразу ее играем, иначе добавляем в соотвествующую очередь. Дальше либо мы играем сколько можем карт из 0й очереди и на этом все, либо мы играем лучшую карту из 1й очереди и тогда очищаем вторую, либо мы играем лучшую карту из 2й очереди. Доказывать почему это проходит по времени я не умею, но тем не менее

→ Ответить

goo.gl_SsAhv

13 лет назад, # ^ |

← Rev. 3 →

не понял объяснения. "либо мы играем лучшую карту из 2й очереди.", а что мешает нам потом очистить все очереди? или это переход дп объясняется?

PS: 1 x 0 имеется в виду c x t ?

→ Ответить

Egor	13 лет назад, # ^ \| ← Rev. 3 → 0 Никакого ДП нету, есть перебор по сути. Просто мы говорим, что если мы играем карту 1 x 0, то никакую из текущих карт 2 x 0 мы уже не сыграем PS да → Ответить

13 лет назад, # |

Для спавших и непрошедших: Через час второй раунд.

→ Ответить

13 лет назад, # |

← Rev. 2 →

Тем кто пишут.
Можете выложить условия здесь?

P.S. Просто я уже отобрался и не могу участвовать, а порешать хочется.
P.S.S. Если это запрещено правилами, то не стоит :).

→ Ответить

http://code.google.com/codejam

13 лет назад, # ^ |

Справа сбоку есть несколько ссылочек, одна из них — Read the problems.

→ Ответить

13 лет назад, # ^ |

Спасибо, не увидел.

→ Ответить

13 лет назад, # |

← Rev. 2 →

Не туда

→ Ответить

13 лет назад, # |

Какие ошибки можно сделать во втором туре в 2-large?

→ Ответить

dalex

13 лет назад, # ^ |

Наверное, слишком маленькая верхняя граница. 1e20 проходит
Давайте новую тему вообще для раунда 1B

→ Ответить

shevchen

13 лет назад, # ^ |

Она самая. 1e8 -> 1e12 = AC

→ Ответить

Vaness

13 лет назад, # ^ |

Я вообще как-то плохо определял верхнюю границу. Из-за этого g++ ругался, говорил что не влезает в стандартный тип, хотя в действительности все влезало. Вот потому например я запорол ее.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Спасибо. ~~Должно 5e19 проходить, если я ничего не путаю.~~ А тему можешь сам создать :).

UPD. Ой, бред написал. 5e11.

→ Ответить

dalex

13 лет назад, # ^ |

В моих тестах максимальный ответ: 499999500000.000000000000
Должно проходить 5e11, да.

→ Ответить

13 лет назад, # ^ |

Кажется у них неправильный разбор. Там бинпоиск до 10^10.

→ Ответить

Petr	13 лет назад, # ^ \| +35 Упс. Спасибо, поправили :) → Ответить

I_love_Tanya_Romanova

13 лет назад, # ^ |

Я что-то начудил с бинпоиском, в результате small сдал с поиском до 10^9, а large сдать не успел - увидел, что у меня подозрительно бинпоиск сходится к верхнему пределу (10^9), начал исправлять, сначала просто типы поменял и пределы, потом еще что-то... А он перестал сходиться вообще:)

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Зачем 1e20? Можно же целочисленно все делать.

→ Ответить

Kandyman

13 лет назад, # ^ |

Может быть минимальная и максимальная граница бинарного поиска?

→ Ответить

MikeMirzayanov

13 лет назад, # ^ |

+13

B-large? Прочесть D в переменную типа int, а затем получить переполнение при вычислении последнего чела, которые выходят из точки i:

forn(i, n)

{

double first = max(p + d, segs[i].first);

double last = first + d * (v[i].second - 1);

if (last > segs[i].second)

return false;

p = last;

}

→ Ответить

Vashegin.Roman

13 лет назад, # ^ |

Да, та же самая ошибка :( обидно, но прошел и со Small

→ Ответить

Jokser

13 лет назад, # ^ |

У меня бинпоиск, если писал r-l>1e-6 зацикливался. r=1e12 ставил. Переписывал на long double. Менял границы. В итоге получил Time Expired. Хотя надо было просто поставить 100-200 итераций бинпоиска, что до меня дошло только после.

→ Ответить

GeLo	13 лет назад, # ^ \| 0 У меня сначала та же проблема была. Потом оказалось, что ответ - целое или полуцелое число, так что r - l > 1e-3 спокойно проходит:) → Ответить

Vashegin.Roman

13 лет назад, # ^ |

Ну это известный способ..

→ Ответить

gchebanov

13 лет назад, # ^ |

Аналогично. Но я, потом все на long long'и заменил (и координаты в 2 раза).

→ Ответить

Igel_SK

13 лет назад, # |

В B-large мое решение, получившее wrong, валится на одном единственном тесте и более того, получает accept на дорешивании..

→ Ответить

13 лет назад, # ^ |

-8

Плохие тесты?

→ Ответить

Igel_SK

13 лет назад, # ^ |

Видимо, да. Я, правда, не понимаю, почему мое решение дает wrong, но оно его дает. Идея была в том, что вместо бинарника по времени я пускал тернарник по тому, насколько влево мы сдвинем самую левую точку. Функцией для тернарника было минимальное время, которое на это понадобится. Видимо где-то в ее вычислении я и допустил ошибку. Странно только, что проходит все тесты, на которых мне удалось проверить, кроме одного.

→ Ответить

Igel_SK

13 лет назад, # ^ |

Нашел еще один тест из in-файлов контеста, на котором мое решение падает. Значит, тесты нормальные. Только на инпуте из дорешивания их нет.

→ Ответить

chavit

13 лет назад, # |

Кто как решал 2С large?

→ Ответить

Zhukov_Dmitry

13 лет назад, # ^ |

Поиском в ширину :)

Сначала заметим, что ответ - это минимальное число сторон среди всех получившихся многоугольников.

Затем поставим какие-нибудь два разных цвета на соседние вершины и научимся красить многоугольник, у которого две вершины уже покрашено.

Все многоугольники, у которых появилось покрашенное ребро, заносим в очередь на покраску.

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

-8

...научимся красить многоугольник, у которого две вершины уже покрашено...

Такую ересь написал на это место, что оно упало и потом еле нашел глюк. Неправильные ответы были только на больших тестах (>200 вершин). Короче, у меня глючило если разность цветов этих вершин не взаимно проста с ответом. А такое могло возникнуть только при специальных условиях, так как обычно она взаимно проста и меняется только в специальных случаях. Намучился вобщем.

→ Ответить

winger

13 лет назад, # ^ |

+11

На такие задачи полезно делать как можно больше assertion-ов, меня это пару раз спасало на large-тесте. За 8 минут почти любой мелкий баг можно исправить, главное его обнаружить

→ Ответить

Edvard

13 лет назад, # ^ |

3 вопроса:

1) Как красить многоугольник у которого две вершины покрашены.

2) Почему у многоугольника будут покрашены только 2 вершины, ведь в то время как многоугольник лежит в очереди может ещё какие-то вершины будут покрашены.

3) Почему мы всегда можем так красить, т.е. почему не может случиться такого, что мы красим красим, а потом появляется многоугольник который мы уже не можем покрасить используя все цвета.

Надеюсь вопросов не очень много))

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

На все эти вопросы очень хорошо отвечено в разборе.

Скажу только по первому если у нас вершины покрашены в цвета 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

→ Ответить

13 лет назад, # |

у меня одного не показывает задачи с ошибкой 503 ??

→ Ответить

iRomchig

13 лет назад, # ^ |

положили сервер, блин((

→ Ответить

13 лет назад, # |

как можно на С вывести символ '\' ??? О_о

→ Ответить

13 лет назад, # ^ |

+10

'\\'

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

спасибо большое!

P.S. все равно слил, ибо от детских ошибок типа определения в цикле переменной, совпадающей со счетчиком цикла, видимо не отучился :(

→ Ответить

ss.nurboolean

13 лет назад, # ^ |

-30

char ch;

ch='\';

cout<<ch;

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

+21

а теперь попробуйте это скомпилировать.

→ Ответить

kuzmichev_dima

13 лет назад, # |

Вопрос по B: поясните первый пример, пожалуйста. Я не понимаю

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

у нас расстояния 3 5 3 5 3 5 3 5
если перевести во время, то будет
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

→ Ответить

Timus

13 лет назад, # ^ |

20 часов пройдет когда мы проедем 2 полных участка ((3 + 5) / 0.5) и 1 неполностью (2 / 0.5). Построим "ускорители" на 2 последних отрезках длины 5. Мы проедем их за 10ч + 2ч на остаток отрезка выше + 10ч на ещё 1 отрезок длины 5 + 12ч на 2 отрезка длины 3 + 20ч = 54 ч.

Лучше всего это нарисовать.

→ Ответить

pva701

13 лет назад, # ^ |

← Rev. 2 →

case#1: ставим ракетоноситель на планеты 3 и 5, до планеты 3 долетаем за 22, там на ракетоносителе (он уже готов) долетаем до 4й за 5: 22+5=27, потом от 4й до 5й летим своим ходом за 6: 27+6=33 потом на 5й планете берем ракетоноситель и долетаем до 6й за 5: 33+5=38 ну и от 6й до 8й долетаем за 16: 38+16=54 вот так.

P.S не заметил, что уже объяснили

→ Ответить

kuzmichev_dima

13 лет назад, # ^ |

О, значит я условие задачи неправильно понял... ( Я думал, что мы заказываем турбо, находясь на планете, а потом, как только он появляется, сразу используем его

→ Ответить

13 лет назад, # |

Третий раунд очень простой для прохождения получился.
Пишешь первую, пишешь переборы по 3й и 2й (или нормальное решение по второй), укладываешься в 1:58 и проходищь)

→ Ответить

agul	13 лет назад, # ^ \| 0 Действительно, получилось достаточно просто. Первая - однозначно халява; перебор в мелкой третьей загнать было просто. А во второй решение само по себе не сложное. Разбор по задаче С впечатляет :) → Ответить

MBabin

13 лет назад, # ^ |

Ее можно было делать почти влоб - для каждого делителя максимального числа просто влоб его проверить за O(10000). Ну и + еще 1 случай про LCM всех чисел.
Сложность на 1 тест будет O(10^5.3333 * 10^4)

→ Ответить

13 лет назад, # ^ |

за сколько у вас отработала на large? )

→ Ответить

MBabin

13 лет назад, # ^ |

Меньше минуты

→ Ответить

http://pastebin.com/Zqq8YCDp

13 лет назад, # ^ |

← Rev. 2 →

может кто-нибудь глянуть мою B? я ошибок не вижу (и делал, как оказалось, вроде по разбору), но где-то какой-то мелкий баг, видимо, ибо кушать не захотело.

upd: после небольших шаманств по совету yarr.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

0 ≤ t ≤ 10^{11, как минимум.}

Может и другие переполнения есть. Плюс даблы не ок, оно без них решалось, т.к. ответ целый же :)

→ Ответить

13 лет назад, # ^ |

про переполнение-спасибо. дырявая моя башка.

с даблами -да. почему-то в спешке так написал, видимо, в качестве очередной попытки после того, как первый раз не зашло

→ Ответить

13 лет назад, # ^ |

у меня например при выводе 10.000000
получало Incorrect, а при выводе 10 - Correct, при том же самом решении.

→ Ответить

13 лет назад, # ^ |

а можешь куда-то выложить свой аутпуст и из текущего практиса? (я так понимаю, инпут сейчас один на всех)

→ Ответить

13 лет назад, # ^ |

Small: http://pastebin.com/w23AmLKN

Large: http://pastebin.com/sRGEiH62

Код: http://pastebin.com/xwaePadN

→ Ответить

13 лет назад, # ^ |

пасиба :)

→ Ответить

13 лет назад, # ^ |

Почему то у мнея ОЧ долго сортировало вектор с 10^6 элементами c кастомным компаратором, пришлось переписать - в итоге не успел кинуть)

→ Ответить

13 лет назад, # ^ |

в таком случае, кто-нибудь, выложите пожалуйста output для C-small

хоть разберусь, возможно

→ Ответить

http://pastebin.com/nQvF6rpm

13 лет назад, # ^ |

→ Ответить

13 лет назад, # ^ |

← Rev. 5 →

спасибо!

нашел несоответствие, сейчас буду фиксить

P.S. нашел. придурок я редкостный...

→ Ответить

13 лет назад, # ^ |

а можно еще large? :)

Incorrect почему-то :(

в чем вообще, кроме времени и лонгов (которые я в small тоже использовал, кстати), может быть разница между small и large?

→ Ответить

13 лет назад, # ^ |

думаю в large могут быть простые числа порядка 10^16 при перемножении которых будет пхохо)

→ Ответить

13 лет назад, # ^ |

просто я при перемножении чисел считаю их log10 (конкретно, НОКов), и если их сумма больше 16, пишу h+1 и забиваю на этот НОК

→ Ответить

13 лет назад, # |

← Rev. 3 →

Удалено (туплю).

→ Ответить

agul	13 лет назад, # ^ \| +4 Если английский знаете хорошо, то посмотрите здесь: http://code.google.com/codejam/contest/dashboard?c=1128486#s=a&a=2 → Ответить

DimaPhil

13 лет назад, # |

Минут пять думал, как выводить символ '\', потом забил и вывел char(92). Только после контеста вспомнил, что можно выводить так: cout << '\\';

→ Ответить

dalex

13 лет назад, # ^ |

-8

Если уж не знаешь/забыл как выводить - можно нагуглить "ASCII Table", это занимает секунд 15-20, а не 5 минут

→ Ответить

Zhukov_Dmitry

13 лет назад, # ^ |

А можно писать код в Far'е.

Там достаточно посмотреть в правый верхний угол и сразу видно, какой код у символа - ещё 15-20 секунд экономии :)

→ Ответить

13 лет назад, # |

← Rev. 5 →

-8

не могли бы найти лажу в этом коде по задаче С ?

полконтеста затупал над этим, но сейчас вроде исправил и в Practice не сдается :(

UPD не актуально

→ Ответить

13 лет назад, # ^ |

Всмысле? Ты ссылку на код вернуть хочешь?

Вот она:

http://pastebin.com/camNzwRu

:)

→ Ответить

13 лет назад, # ^ |

спасибо))

да я что-то вообще сейчас затупил с комментом :D

теперь он в нормальном состоянии

→ Ответить

pva701

13 лет назад, # |

-7

А B-large решалась жадно?

→ Ответить