TopCoder Open Round #1

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

Ну зачем, зачееееем? :'( Зачем вот сейчас в спонсорах TCO появился логотип Intel? То есть я не получу не то что гипотетической поездки на онсайт, но даже вполне реальной футболки, аналогичной прошлогодней, потому что она ведь даётся за участие в третьем раунде, а у меня как раз к тому моменту с "Интел" уже будет подписан трудовой договор. АРГХ!!!

P.S. Ну и, кстати, вот тут же на главной странице сайта TopCoder висит логотип AMD. Что называется, узрите, товарищи, наглядно лютую, бешеную капиталистическую конкуренцию :)

→ Ответить

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

← Rev. 2 →

+37

flags: humour
Меняю право участия в TCO на трудовой договор с Intel.

→ Ответить

Egor	13 лет назад, # ^ \| +2 Ну, в спонсорах TCO его пока-что нету. Хотя будет наверняка, да → Ответить

Egor	13 лет назад, # ^ \| +20 Блин, пока отходил от компа - уже появился → Ответить

unprost

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

Будешь у них как физик-ядерщик, или как программист? :)

→ Ответить

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

+21

Или как философ? :)

→ Ответить

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

Не вправе рассказывать. Обратите внимание, например, на это.

→ Ответить

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

Да не, всё в порядке, я придумал, как избавиться от необходимости праведно гневаться на Intel. Достаточно просто слить :)

→ Ответить

Scorpy

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

← Rev. 2 →

-12

А условия узнать можно?
P.S. Похоже бессмысленный вопрос, потому что те, кто их знают сюда не зайдут в ближайшее время. :)

→ Ответить

Egor	13 лет назад, # ^ \| +3 Казалось бы если знать правила топкодера вопрос еще и не очень корректный → Ответить

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

-17

Да... Весело в одной руме с Петей быть) Смотрю - уже 3 250ки упало. Полистал лог - ага, Петя:)

Смотрю, четвертую уже завалили...

А Петя только открывает-закрывает 250 по своей схеме (по рейтингу автора от худших к лучшим).

Пятый автор остался без 250. Моя очередь все ближе.

Ага. Открыл мою. Ждем. Руки трясутся как на систестах. Ура! Закрыл! Значит, может быть, правильно:)

→ Ответить

Egor	13 лет назад, # ^ \| +8 Я думаю все челленджи на ответ 2 * длину → Ответить

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

-7

Судя по сорсах тех авторов - да:)

Мне на самом кодинге показалось, что такого ответа быть не может, но я вообще тупил с задачей сильно))) Я сдал 250 медленней, чем 500. Хорошо хоть мое решение так написано, что проходит и такой крайний случай.

→ Ответить

Egor	13 лет назад, # ^ \| +14 init = oxox goal = ooxx → Ответить

zurg	13 лет назад, # ^ \| 0 да-да, это хороший тест=) такой же юзал! → Ответить

acherepanov

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

-7

а у меня был такой:
init = ooxx
goal = oxox

=)

→ Ответить

Kenny_HORROR

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

Ага. У меня на этом 3 челленджа, при этом моя упадет на нем же. =(

→ Ответить

Egor	13 лет назад, # ^ \| 0 у нас в комнате всего 3 и 2 из них я упустил, хнык → Ответить

sas4eka

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

Меня именно так и сломали. Надеюсь на вторую задачу :)

→ Ответить

NKolotey

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

Тоже протупил в этом месте. Условие в цикле > 0 вместо >= 0 написал, в итоге такой тест бы не прошел. Опомнился через полчаса, пофиксил, но уже сдал повторно только за 101 очко. Fail

→ Ответить

Petr	13 лет назад, # ^ \| +1 Все кроме одного - один товарищ зачем-то убирал сначала общий префикс. А вообще мне повезло с комнатой, да - в большинстве столько людей не набажили ) → Ответить

Gerald

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

Расскажите кто нибудь вкратце как тыщу решать.

→ Ответить

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

+13

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

→ Ответить

Gerald

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

мне почему то казалось что их будет много... хм...

→ Ответить

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

50⁴

→ Ответить

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

Из будет ~ 50⁴. Общая сложность решения ~ 50⁵. Компьютеры быстрые :)

→ Ответить

Egor

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

Решение за 50^4

У нас не более 50 не вайлдкардов в каждом разряде с весом 1 и все остальное с весом 1000 - сколько-то. Делаем таблицу 4й степени с количествами. Перебираем запросы в порядке убывания цены. Проходим по таблице и суммируем все ячейки, которые включает данная маска, при этом в самих этих ячейках ставим 0. Тогда у нас либо будет не более 50^3 таких ячеек, либо запрос вида *.*.*.* и после этого остальные запросы можно не обрабатывать

→ Ответить

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

у меня за 50⁵, 1.5 секунды на макстесте

→ Ответить

Egor	13 лет назад, # ^ \| 0 У меня 50^5 не проходило на сервере, проверял → Ответить

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

C++ рулит =)

→ Ответить

Egor	13 лет назад, # ^ \| +32 В С++ с моими кривыми руками я бы выстрелил себе в ногу ;) → Ответить

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

-16

+100500 ;)

→ Ответить

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

-6

А я взял «главный вопрос жизни, вселенной и всего такого» :)

→ Ответить

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

У меня даже в 2 раза быстрее получилось, поэтому я вообще не беспокоилась.

→ Ответить

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

-21

Пугали - трудно пройти дальше, трудно пройти дальше!

Одной задачи хватает, при том не феноменально быстро сданной)

→ Ответить

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

+10

ура, красный

→ Ответить

Connector

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

Мои поздравления ))

→ Ответить

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

спасибо :)

повезло на самом деле, у меня в 500-ке обращение к несуществующему элементу вектора =)

→ Ответить

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

Поздравляю.

А у меня скромные +93, за последние 40 дней в сумме +374, но до красного еще почти столько же:(

→ Ответить

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

зато хороший потенциал =) даёшь за 40 дней - в красные? :)

→ Ответить

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

Матчей маловато) Особенно с учетом того, что на Algorithm Round 4 я не надеюсь. Было 7 матчей за 40 дней, а теперь только 5.

Но, в любом случае - постараюсь)

→ Ответить

Jacob

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

← Rev. 2 →

+28

Читайте новый роман Жюля Верна "В ~~красные~~ таргеты за 80 дней"

→ Ответить

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

Петр справился за 57

→ Ответить

Jacob

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

+16

Думаю, он специально это сделал из-за особого сакрального смысла этого числа.

→ Ответить

sas4eka

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

При этом он ещё и 3 SRMа пропустил

→ Ответить

maksay

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

Я ошибаюсь, или опять был установлен новый рекорд рейтинга? (Выше всего на 3, но всё же:)

→ Ответить

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

-7

не ошибаешься

там какой-то серый в чате с ума сходил по этому поводу

→ Ответить

k-va	13 лет назад, # ^ \| +8 Позабавило "всего на 3", примерно как сказать о прыжках в высоту "улучшил мировой рекорд ВСЕГО на 1 см.". Тем более, что здесь сложнее: оступись с таким рейтингом в одном раунде, протеряешь баллов 150, и начинай по новой... → Ответить

Romka

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

+11

Кое-кто недавно, к сожалению, именно так и сделал =(

→ Ответить

1a1a1a

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

-40

это Вы о ком ? :)

→ Ответить

NKolotey

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

Алматинцы есть? Сегодня чёт все наши отстрелялись ужасно, может из за погоды? Когда так атмосферное давление пляшет, как всю последнюю неделю, у меня чёт голова взрывается, глазами пошевелить больно, кого-нибудь ещё такая же беда преследует?

→ Ответить

baukaman

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

Да тур ужас пришелся, я увидел 250 и сразу запаниковал использовать Java или С++
потом на с++ все таки решился, набрал 194, сделал +50 на челлендж. И тут затупил
Я то в 850 то проходил тогда... но нет мне надо было еще -150 не челленжде сделать.

и прощай ТСО 11

→ Ответить

pva701

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

кто нить может рассказать как решать 500? А то придумал решение за

2^(n/2)*n (или что-то тип того), что скорее всего не проходило бы по времени.

→ Ответить

Egor	13 лет назад, # ^ \| 0 Факт - если в следующей части идет дождь, то мы идем в послеследующую, иначе - в следующую → Ответить

naagi

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

У меня лиса в другую сторону смотрела.
Если i-я часть чистая, то мы в нее идем всегда, а если грязная - идем только тогда, когда (i-1)-я тоже грязная (из (i-2)-й).

→ Ответить

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

Если на дорожке сухо, потом k раз грязно, а потом опять один раз сухо - k/2 раз придётся прыгнуть в грязь. Разобьем путь на несколько таких дорожек. Понятно, что случайная величина - кол-во прыжков в грязь - равна сумме случайных величин типа такой: "если в i сухо, потом до j грязь а в j опять сухо, то (j-i-1)/2, иначе 0". По каждой можно отдельно посчитать мат. ожидание, оно тривиально - (j-i-1)/2 * (вероятность появления такой дорожки).

→ Ответить

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

Вот да, я как раз на подобном решении и потерял 25 очков и прохождение во второй раунд. Но почему мы можем считать матожидания для таких дорожек независимо? Ведь сами события наличия дорожек - они зависимы.

→ Ответить

nk.karpov

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

← Rev. 2 →

Так как матожидание линейно даже для зависимых величин?

→ Ответить

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

← Rev. 2 →

Гы, спасибо. Мда, вот так никогда и не знаешь, какой именно прекрасно тебе известный факт из матчасти ты забудешь в следующий раз...

→ Ответить

RodionGork

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

Я 50 минут над ней тупил... В последние 30 секунд заменил Math.min(c[i-2],c[i-1]) на просто c[i-2] в одной строчке... В последние 15 секунд протестил, в последние 5 отослал. К моему большому удивлению оказалось правильно.

Но я до сих пор не понял почему. Одно скажу - к 30 годам мозги тупеют. У меня это не первый случай когда я не могу сразу обосновать или доказать решение. Бесит меня это до крайности.

Буду наверное в понедельник на работе разбираться.

→ Ответить

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

Создал массив, в каждый элемент которого записывал среднее число попаданий в лужу далее по улице. Заполнял с конца. Тогда в нулевой ячейке всплывет ответ. Как справедливо заметил Egor (Да как же тут копировать ссылки на персональные страницы?!) Если в следующей клетке сухо, идем туда, иначе перепрыгиваем. Т.е. среднее число попаданий в лужу в i-й клетке будет равно ans[i] = (1-p[i+1])*ans[i+1] + p[i+1]*(1-p[i+2])*ans[i+2] + p[i+1]*p[i+2]*(ans[i+2] + 1). В последнем случае персонаж попадает-таки в лужу, поэтому к среднему числу луж, в которые он попадет далее, надо добавить единицу.

Мне известно ещё совершенно безумное решение по формуле включений\исключений, абсолютно очевидное ввиду терминов тервера, но понять его интуитивно я так и не смог =)

→ Ответить

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

Тервером мат. ожидание разбивается на сумму тривиальных мат. ожиданий. Что там с включениями исключениями, интересно?

→ Ответить

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

← Rev. 2 →

Что-то типа такого. Возьмем две соседние лужи, посчитаем вероятность, что они обе есть и прибавим к ответу. Но конфигурации вида ### мы посчитали дважды, поэтому посчитаем количество их и вычтем. Теперь комбинации вида #### мы посчитали трижды с плюсом и дважды с минусом, а надо дважды, поэтому прибавим их и т.д.
P.S решение не мое, а IrisM

→ Ответить

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

Извращенцы, я-то анализировал комбинации типа .#######. :)

→ Ответить

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

← Rev. 3 →

А как быть с тем, что в конфигурации ### мы попадем один раз, в #### - два, в ##### - тоже два, а в ###### -три? Т.е. ответ зависит от четности длины конфигураций.

P.s. Видимо это недокументированная фича формулы включений\исключений.

→ Ответить

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

Я же описал, как быть. Вот в ### мы попали 2 раза, а надо 1, поэтому скомпенсируем. Вот в #### мы попали 1 раз, а надо 2 - скомпенсируем. Вот в ##### мы попали 3 раза, а надо 2 - скомпенсируем и т.д. Там как раз все как надо выходит.

→ Ответить

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

← Rev. 2 →

Ага, спасибо, вижу. Но в голове не укладывается =)

UPD. Я понял. Это не формула включений-исключений. Спать надо ночью.

→ Ответить

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

← Rev. 2 →

Рассмотрим индикаторы события "персонаж вляпается в i-ю лужу". Матожидание суммы индикаторов действительно превратится в сумму матожиданий, вот только как их посчитать? Матожидание индикатора равно вероятности, с которой наступает исследуемое событие. В то же время вероятность, с которой персонаж попадет в лужу в любом наборе из 2, 3, ... подряд идущих луж нам известна и легко считается. Поэтому сумму вероятностей заменяем вероятностью суммы, выражая сумму вероятностей по формуле включений\исключений.

P.s. Снова перестал понимать это решение. Буду благодарен, если кто-нибудь объяснит, что я тут понаписал =)

P.p.s. Это бред.

→ Ответить

sas4eka

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

← Rev. 2 →

Мои мысли при написании решения(на языке луж =) :

Пусть r[i] = road[i]/100 - вероятность того, что i-я клетка является лужей.

d[i] - вероятность что персонаж обязан "вляпаться" в i-ю лужу. Значит, он уже не "вляпался" (вероятность этого равна 1 минус вероятность "вляпаться") в предыдущую, которая тоже должна быть лужей. То есть d[i] = r[i-1] * (1 - d[i-1]);

r[i]*d[i] - вероятность того, что i-я клетка окажется лужей, и при этом он в неё "вляпается" (вероятность одновременного наступления независимых событий равна произведению вероятностей)

Ответом будет сумма этих вероятностей по всем клеткам.

P.S. как-то я сам слабо верю в то, что написано, но это прошло все тесты.

→ Ответить

baukaman

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

получается решение за О(N) жестко

а какими изначально значениями надо заполнять конечные клетки ?

→ Ответить