SRM 528 - Codeforces

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

Да, сейчас все работает.

→ Ответить

ivan.popelyshev

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

А я напоминаю что арена показывает неправильное время, которое на час опаздывает.

→ Ответить

Jokser

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

У меня правильное. 19-07 по Москве, СРМ в 20-02 в арене 9-07, старт в расписании 10-02.

→ Ответить

Egor

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

Это лечится установкой обновления таймзон для Джава

→ Ответить

Gassa

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

Сменил Java 1.6.0_29 на 1.6.0_30, помогло.

→ Ответить

Sultan

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

← Rev. 2 →

+19

Я один не могу зайти в комнату?

UPD: Отлично, зашел, зато теперь не могу открыть задачи.

→ Ответить

cmd

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

не один

→ Ответить

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

не волнуйся, ты не одинок...

→ Ответить

L.I.S.

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

+28

Ждем 528.5?

→ Ответить

agul

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

Да вроде не должно быть - они отложили контест на 15 минут.

→ Ответить

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

я внутри...

→ Ответить

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

но толку нету, низя задачки открывать....

→ Ответить

ivan.popelyshev

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

Задачи не открываются :( Видимо таймер у них там сбился.

→ Ответить

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

+21

Основная проблема всех сканлайнов - главное не забыть событие открытия :-)

→ Ответить

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

Надеюсь задачи так не подведут.

→ Ответить

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

Ср дек 28, 7:17 PM MSK CODING

Перенесли на 15 минут

→ Ответить

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

кекеке. У нас разные понятия о MSK :-)

→ Ответить

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

у нас белорусское MSK...

→ Ответить

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

С блекджеком?

→ Ответить

maslowmw

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

У вас с ареной разные понятия о мск)
а вообще даже не с ареной, а с java 1.6.0_29)

→ Ответить

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

У тебя неправильное. Твое - MSD.

→ Ответить

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

← Rev. 2 →

Хм. Ты меня смутил своим линком. С другой стороны, я там же нашёл, что MSK теперь вообще deprecated - http://www.timeanddate.com/library/abbreviations/timezones/eu/msk.html

Так что не у одного меня неправильное)

→ Ответить

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

← Rev. 2 →

Сдвинули на 8:17 по Москве.

Надеюсь, room assignment останется прежним.

→ Ответить

Dmitry_Egorov

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

← Rev. 2 →

+21

Ну вот почему нельзя заранее с запасом выделить время для распихивания по комнатам?! Уже ведь много раз распределение с трудом укладывалось в отведенное время, и рано или поздно оно должно было не успеть.

→ Ответить

Sultan

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

+27

Каким прекрасным SRMом завершился этот год, похоже ребята на топкодере уже вовсю празднуют.

→ Ответить

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

заманчивое начало)

→ Ответить

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

-9

создаю анонимный фонд засравших раунд! присоединяйтесь!

→ Ответить

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

+1.
Вот бы ещё ничего не упало.

→ Ответить

Sultan

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

Как я обожаю нашего СТАБИЛЬНОГО провайдера byfly. Стабильно падает в конце раунда. Еще и модем huawei(оправдал марку). Хорошо бы еще первая и вторая зашла.

→ Ответить

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

хорошо, что есть чему падать.... я вот КАЧЕСТВЕННО :( засрал...

→ Ответить

caustique

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

В тебе никто и не сомневался

→ Ответить

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

почему?

→ Ответить

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

молчал бы, у самого -25, у меня хоть очки положительны

→ Ответить

sdryapko

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

У меня byfly редко тупит...тупит скорее wi-fi в ихнем модеме.

→ Ответить

agul

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

я засрал даже первую задачу(

→ Ответить

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

← Rev. 2 →

Я присоединяюсь, фонд перестает быть анонимным.

Первый раз в жизни написал вторую, зато прогнал, как и многие, в первой, и еще -25 словил.
~~А вторая может запросто упасть, локально 1.3 сек работает~~ не упала, фейл не эпичный

→ Ответить

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

← Rev. 3 →

Вот это мясо. Я по B в своём духе написал самое сложное, что только может прийти в голову. Динамика за 2^(n / 2) * n³ с пятью оптимайзами тащит :-)
В результате угрохал время контеста куда-то в задни^W чёрную дыру.

→ Ответить

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

Как ты там по-человечески хранил 2⁵⁰?

→ Ответить

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

Таки подозреваю, что имелось в виду 2^n / 2, нэ?

→ Ответить

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

2^n / 2· n³ - это вполне нормальное решение, разве нет? Я писал квадрат, но по моим оценкам куб без оптимизаций прекрасно должен заходить.

→ Ответить

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

Да, действительно n / 2. Прошу прощения.

→ Ответить

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

Ну как сказать...
40 * 20 * 20 * 2^20 * (лонг лонги повелевае!1) = полтора миллиарда операций с лонг лонгами. Я это очень долго и со скрипом впихивал.

→ Ответить

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

Бр, куб без оптимизаций - это ж дофигищи миллиардов?

→ Ответить

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

Может, я что-то очевидное просто за оптимизации не считаю. Ту же проверку на количество единичек в маске я поставил автоматом, а не на этапе пропихивания. Поэтому и думал, что мой куб пройдет.

→ Ответить

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

Вань, ты демон. У меня квадрат не работал никак. Хотя и не прооптимизированный.

→ Ответить

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

Хм. Мне кажется, что я вогнал аж куб. Скажите кто макстесты?

→ Ответить

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

Мне было все равно для решения. Я брал случайный на 40.

→ Ответить

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

У меня везде работает не более чем за 0.6 sec.
У меня критичный макстест - когда нулей и единиц по 20 и они разбросаны по строке.

→ Ответить

maksay

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

Точно на тесте из всех о нормально проходит? Однако.. У меня решение за 2^N * N - перебор битмасок и запоминание в сеты хешей несовпадающих кусков строки - и на макстесте это было 0.4.

→ Ответить

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

Точно проходит. За O(n³) :-)
У меня есть отсечение, которое проверяет, что очередная маска по количеству нулей и единиц подходит исходной строке. А на таком тесте единственная подходящая маска - это в которой все нули.

→ Ответить

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

Я запустил на двух неслучайных макстестах и одном случайном. Максимальное время - 1.5. Может, и свалится, не знаю, хотя от теста там вроде бы мало что зависит.

→ Ответить

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

Прошел.

→ Ответить

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

Мой куб тоже. А первая - упала :-( В результате я последний из ненулевых в комнате со второй задачей.

→ Ответить

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

Во-первых, не 50 а 40. Во-вторых - я опечатался, конечно n/2 в показателе.

→ Ответить

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

2⁴⁰ количество элементов 40

→ Ответить

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

Товарищи красные, а правильно ли такое решение 500?

Возьмем первые n/2 символов, далее для каждой маски:
Найдем начала строчек a и b, которые войдут в x и y.
Пусть для определенности a длиннее b. Тогда если a[1..blen] == b[1..blen], обновим в мапе, сколько раз встречается строчка a[blen+1..alen].

Потом проделаем почти такую же операцию для вторых n/2 символов и второй мапы. Только там надо кое-что реверсить.

Далее пройдемся по всем строкам из первой мапы и попробуем найти их во второй. Если получилось, прибавим к ответу m1[s]*m2[s].

Еще, конечно, строки можно делать числами, а мапы - массивами (последнее я не успел). Получается за O(n * 2^(n/2))

→ Ответить

cmd

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

← Rev. 2 →

Я так примерно делал.

Со строками локально работало порядка 8 секунд на 'o' x 40, переделал на маски - в арене работало 1.5 секунды.

→ Ответить

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

← Rev. 2 →

И там не просто посчитать сколько раз такая строка была, а надо еще вроде сохранять какая именно строка была длинее и потом sum( m1[<num, s>] * m2[<1 - num, s>]. И отдельно учесть пустые строки.

Да, это я учел. У меня локально работает 1.3 сек, и почему-то кажется, что мой Core 2 Duo E6600 четырехлетней давности побыстрее их компов

UPD: Зашло. Жаль, с 250 протупил

→ Ответить

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

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

→ Ответить

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

← Rev. 4 →

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

1. Нам надо найти набор x_i, y_i такой что

a) $\text{[math]}$

b) $\text{[math]}$

c) $\text{[math]}$

d) $\text{[math]}$ максимальна.

2. Ответ не превосходит 2000.

3. При ответе больше 40 можно делать бинпоиск, так как второе условие выполнено автоматически

4. Перебрали ответ до 40 и бинпоиск дальше.

5. При фиксированном ответе какая-то очевидная динамика нужна.

UPD: Судя по всему это лажа. Буду рад если кто-то объяснит где.

UPD2: А нет не лажа - просто ТЛ.

→ Ответить

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

← Rev. 2 →

+19

не понял пункт b, честно говоря

UPD: у меня не прошла 1000, поэтому разбора от меня не будет.

→ Ответить

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

Пункт b обеспечивает слово distinct в условии на цвета.

→ Ответить

Gassa

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

Видимо, основное ограничение — P1, P2 >= 50.

Но я прочитал его только в последнюю минуту и послал какую-то жесть, которая меня удивит, если пройдёт систесты.

Идея решения у меня такая: смотрим на цвета по очереди и для каждого решаем, сколько раз отнять от него P1 и сколько раз отнять P2. Считаем динамикой ответ для состояний (количество просмотренных цветов, сколько у нас свободных P1-ок, сколько у нас свободных P2-ек).

→ Ответить

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

← Rev. 2 →

Я делал динамику f(i, mx, opened) -- максимальное количество раз, которое мы можем отнять P2, если мы отняли P1 ровно opened раз, максимальная сумма количества отниманий P1 и P2 для одной коробки равна mx, и всего мы обработали i коробок.

Легко видеть, что если f(n, mx, opened) ≥ opened, а также mx ≤ opened, то ответ opened * (P1 + P2) возможен, иначе -- нет. Параметр mx нам нужен для того, чтобы мы не попытались отнять P1 и прибавить P2 к одной коробке за одно действие. Осталось заметить, что mx ≤ 40, причем если opened > 40, то нам уже не важно, чему равен mx. Значит, мы mx можем форсированно ставить 0 при opened > 40.

Судя по резам на форуме, это проходит.

→ Ответить

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

Кто как вторую решал?

→ Ответить

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

Переберем все маски размера 2^n / 2. Динамика по длине маски и длине исходной строки.

$\text{[math]}$

→ Ответить

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

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

→ Ответить

shevchen

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

← Rev. 2 →

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

2 задачи, 2 ресабмита, 2 неудачных челленджа.

Update: у Гены без двух последних оптимизаций проходит.

→ Ответить

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

Ну про "проходит" пока с уверенностью сказать нельзя, хотя мало кто в этом сомневается, я думаю :)

→ Ответить

shevchen

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

Я его пробовал на макстесте ломать)

→ Ответить

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

Наивный человек...

→ Ответить

JKeeJ1e30

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

Если тот, кто пробует ломать Петю, в следующей жизни будет индусом, то кем будет тот, кто пробует ломать Гену?

→ Ответить

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

+19

Может быть JKeeJ1e30'ом??

→ Ответить

JKeeJ1e30

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

Не надо, если бы я ломал Гену в прошлой жизни, я бы знал.

→ Ответить

Jokser

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

Надо еще отсечение сделать, чтобы кол-во x и o в маске совпадало. Тогда получается не 2^n/2. А в худшем случае $\text{[math]}$

→ Ответить

iroro

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

← Rev. 3 →

я делала даже C(18, 9) — первый и последний фиксированы, отсечение по нулям в слое динамики и по кол-ву, как у Вас. На макстесте как-то быстро работало, надеюсь по wa не свалится — не особо проверяла свой код

upd: ня, прошло

→ Ответить

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

← Rev. 2 →

Можно всунуть пересчитывание динамики в перебор маски так чтобы было 2ⁿ· n а не на n². Работает 1,2 стабильно на 40.

→ Ответить

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

← Rev. 2 →

+24

один я решал meet-in-the-middle?

Разбиваем строку на две, в каждой части перебираем за 2²⁰ что отойдет в первую последовательность, что во вторую. Сохраняем состояния (len1, len2, mask), что означает, что в первая последовательность уже длиной len1, вторая длиной len2, а хвост длиной |len1 - len2| представимо маской mask. Перед тем, как сохранить это состояние нужно проверить, что у последовательностей равный префикс длиной min(len1, len2).

Во второй половине делаем то же самое, только проверяем на равенство суффикс, и из сохраненных префиксов ищем количество подходящих.

Асимптотика 20 * 2²⁰ - очень быстро.

Годится?

→ Ответить

cmd

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

Тоже так же решал, только изначально хранил не маску, а строки и это работало долго, когда на маски переписал стало норм.

→ Ответить

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

делал все со строками, сравнивал, удалял, брал подстроки - работало локально 2.5 сек, я не рискнул заслать, пришлось переписывать на побыстрее.

теперь локально работает 0.7 примерно

→ Ответить

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

Очень похоже на то, что выше описал dalex.

→ Ответить

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

наверно, я не читал

→ Ответить

I_love_Nastya

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

И я так делал, на макстесте ~0.2c работает.

→ Ответить

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

← Rev. 2 →

Я делал тоже meet-in-the-middle. Достаточно заметить, что если в левой половине у нас маски (A, B) для синих и красных, а во второй (X, Y), то должно выполняться:

A· 2^{n / 2 - numberOfBlue} + X = B· 2^{n / 2 - numberOfRed} + Y, что эквивалентно

A· 2^{n / 2 - numberOfBlue} - B· 2^{n / 2 - numberOfRed} = Y - X.

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

→ Ответить

VArtem

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

Вроде делал абсолютно также, но не зашло. Баг в реализации, или, может, есть какие-то тонкие моменты в таком решении?

→ Ответить

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

А, да, точно. Я еще в маски разностей добавлял информацию о разности длин красных и синих посдедовательностей. Т.е. просто брал эту разность, умножал на 2 в большой степени и ксорил с тем что вышло. Потому что может выйти что длины последовательностей не совпадут.

→ Ответить

VArtem

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

← Rev. 3 →

У меня был N/2+1 массив масок, в, к примеру, left[i] хранятся разности, у которых ровно i элементов принадлежат красной поcледовательности. Сливаю массивы left[i] и right[n/2 - i] для всех i. Вроде должно работать.

UPD: Разобрался. Глупая ошибка в реализации - сравнивал Long между собой оператором ==, а не .equals(), как следует.

UPD2: При том, что интересно, сэмплы проходили прекрасно, ибо для маленьких значений Long все объекты закэшированы, и прекрасно сравниваются через ==. Обидно.

→ Ответить

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

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

→ Ответить

Edvard

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

Колян я точно также делал. Написал где-то на 300. Потом решил потестить в арене увидел что у меня не укладывается в памяти 81 метр вместо 64. Сделал 2 ресубмита в итоге печальный результат. А работало у меня очень быстро я очень нахаченно сразу написал

→ Ответить

Anarivu

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

как можно решить С Div2 не перебором с отсечением по времени?

→ Ответить

vilcheuski

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

← Rev. 2 →

Я просто шагал с шагом 0.01 и считал максимальное количество для текущего времени.

→ Ответить

kolya37

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

Скорее всего тернарным поиском по времени =)

→ Ответить

qwerty787788

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

Переберем все возможные времена, при которых расстояние между некоторыми двумя москитами равно 2R. Место взрыва - средина между ними. Также учтем время T = 0. Вроде бы должно пройти.

→ Ответить

qwerty787788

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

зачем минусовать правильное решение? (исправил глупую ошибку в реализации зашло в дорешивании)

→ Ответить

SkyHawk

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

← Rev. 3 →

Я решал так:

Пусть [l,r] - отрезок, который накроет бомба. Попробуем рассмотреть каждую из точек в качестве левой границы. Теперь пробежимся по всем остальным точкам и определим момент времени, когда эта точка войдёт в этот отрезок и выйдет из него. Время входа и выхода толкаем в вектор, сохраняя флаг того, вход это или выход, после чего его сортируем. Идём по вектору и пользуемся принципом стека: когда встречаем момент времени, в который точка входит в отрезок, - увеличиваем счетчик, а когда выходит - уменьшаем. Тут требуется определённая эпсилон-кунг-фу, я не придумал как её избежать. максимум из всех значений счетчика и будет ответом. асимптотика - O(n²*logN)

UPD. Упало. Эпсилон-магия мне неподвластна =(

UPD2. Тупая бага с целочисленным делением. стыдно. Но в целом решение верно.

→ Ответить

steiner

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

← Rev. 2 →

> Тут требуется определённая эпсилон-кунг-фу, я не придумал как её избежать.

Избежать очень просто: хранить вместо double два int'а - числитель и знаменатель.

Кроме того, кажется, что можно просто из левых концов всех отрезков повычитать эпсилон.

→ Ответить

SkyHawk

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

Действительно, спасибо!

→ Ответить

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

Записываем моменты времени, когда 2 москита стоят в одной точке.
Так как все скорости разные, считались такие точки очень просто.
Добавляем момент времени 0, и для каждого момента считаем сколько максимально москитов находятся на отрезке длиной 2R.

→ Ответить

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

В точности такое же решение у меня не прошло один из финальных тестов... Там видимо нужно было шаманство с эпсилонами?

→ Ответить

qwerty787788

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

и это решение прошло систесты? - оно же не правильное, или я чего-то не понимаю...

→ Ответить

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

Ну не знаю.

Сам не ожидал.

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

Прошло все тесты.

Можете посмотреть код тут: http://pastebin.com/9RYSsr25

→ Ответить

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

Ну, интуитивно кажется вроде бы, что идея решения как раз верная.

P.S. Епсилон таки присутствует. Абсолютно такой же код без него получает Failed System Tests. Ну когда же я научусь в правильные места эти эпсилоны засовывать... =(

→ Ответить

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

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

→ Ответить

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

А ты проверял в момент времени 0?

→ Ответить

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

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

→ Ответить

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

У очень многих уже видел такой вердикт:

Test Arguments

Expected Results

Success

{-70, 79, 0, -12}, {90, -99, 0, 18}, 1	4	FAILED - Result: 3

→ Ответить

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

a < b   ->   a < b-eps
a <= b   ->   a < b+eps
a == b   ->   abs(a-b) < eps
a >= b   ->   a+eps > b
a > b   ->   a-eps > b

Главное - считаем, что числа равны, если abs(a-b)<eps. Если есть сомнения, надо на бумажке нарисовать, станет все ясно.

→ Ответить

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

хм, спасибо. Сейчас вроде стало понятнее откуда берутся эпсилоны в сравнениях и с каким знаком их нужно ставить. Надеюсь, этот SRM послужит мне уроком =)

→ Ответить

nerd

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

когда систесты закончатся?

→ Ответить

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

Мне интереснее - когда они начнутся?

→ Ответить

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

← Rev. 2 →

вопрос в том, когда они начнутся...

UPD: опередили...

→ Ответить

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

← Rev. 2 →

Когда систесты начнутся?

upd: Ого, видишь, этот вопрос всех куда больше интересует!

→ Ответить

nerd

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

В арену только у меня не логинится?

→ Ответить

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

нет

→ Ответить

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

No active contests - атлична

→ Ответить

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

Что? SRM 528? Да не было такого, о чем вы...

→ Ответить

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

Было сообщение, что арена глючит и результаты пока тут: http://apps.topcoder.com/forums/?module=Thread&threadID=731935

→ Ответить

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

-7

после Нового года протестируют... января так 11

→ Ответить

SyFy

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

А каким образом сдают 250p задачу на 250 поинтов? И вообще любую другую на полное кол-во баллов?

Читы вроде чтения задачи с одного акка?

→ Ответить

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

да

→ Ответить

SyFy

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

Админы на это как-то реагируют или пофигу?

→ Ответить

Jokser

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

Конечно. Читеров всегда вырезают.

→ Ответить

Tranvick

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

Да. Либо чужой код. С такими после контеста быстро разбираются, они ни на что не влияют.

→ Ответить