Попробуйте "Да".

Где указывать? В регистрационной форме указывается только email?

Да, собираемся, в данный момент и работаем над этой проблемой

Проблемы с тестированием решены. Все посылки, висевшие в очереди, в данный момент протестированы.

Есть подозрение, что WA7 — это если разрешить проходить через города (и останавливаться в них). По крайней мере, когда я это разрешил — я получил WA7.

Более интересный вопрос — что такое WA11. Я перепроверил свой код 57 раз и представить не могу, в чём может быть проблема...

Задача 9. Хэш-функция.
В задаче ответ есть всегда единственный.
Надо нарисовать эти сложения и XOR на бумажке в столбик и заметить это.
Рассмотрим самый простой пример.
Знаем c, знаем с = a ^ (a<<16), найдем a.
Обозначим b = (a<<16).
Младшие 16 бит a равны младшим 16 битам с. Установим эти биты в a. b = a << 16. И тогда a = с — b.
Аналогично для других сдвигов, только там эти операции надо повторять несколько раз.

Хеш-функция — вглядываемся в то, что там происходит и получаем такую функцию обращения: #rx8VI4

Можно заметить, что x+(x<<16) = x*(2^16 + 1), то есть можно домножить на обратный к 2^16+1 по модулю 2^32 (он существует, потому что число взаимно просто с модулем). Для xor выше написали.

Скажем, что x_i > x_j или x_i ≥ x_j — это ребро из i в j. Числам тоже сделаем мнимые вершины. Далее сконденсируем полученный граф. Если в какой-то КСС есть два разных числа или есть  > , а не только  ≥ , то ответ не получить. Иначе пытаемся поставить его по топологической сортировке компонент сильной связности как динамика по ориентированному ациклическому графу (возможно, не получится, тогда тоже NO).

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

1) Почему вы запилили свою систему проверки, если не умеете? Остальные обладают фатальным недостатком? Или, может быть, ответственные за Я.Контест и snark вам отказали в помощи?

2) Почему задачи такие мерзкие и простые? Нет, серьезно, лучше не включать такие задачи, как 12, в контест, чем включать.

3) За каким чертом я обязан себе ставить MinGW или вижак и проверять, компилируется ли все, что я отсылаю, на них, если вы даже в положении не написали о компиляторах? Лол, да в каждом компиляторе свои заморочки.

4) Что еще за бредятина с минусами за 1 тест? Или у вас с long double все нормально во всех компиляторах?

5) Очень круто продлевать тур на 15 минут, если по факту это абсолютно ничего не дало тем, у кого были проблемы с тестирующей системой? Почему не продлили на столько, сколько у вас ничего не работало? Ну 15 минут у нас задача стояла в очереди, а потом еще 25, после чего не скомпилировалась (см пункт 3), очень нам продление помогло.

6) Далее неправда, зачеркнуть не получилось. Почему у вас тур пересекается со сборами в физтехе? Как много команд из топ 25 поедут к вам посреди сборов? Лично мы не поедем посреди сборов. Или это такой неофициальный фильтр, что ждете на онсайте вы только свои команды?

Можно считать дейкстру 10 раз на графе с 1600 вершинами и 1600² рёбрами

У меня на джаве сразу зашло: 20 дейкстр на графе 1600² рёбер. Главное — писать за n² + m, а не за .

У нас 19й не заходил из-за мелкого бага с циклами

Нам в кларах указали "MinGW неправильно работает с выводом long double. "

Нужно учитывать, что кратчайший путь — не всегда отрезок и две дуги параболы. В тесте 23 кратчайший путь — по отрезку (не вертикальному).

Мы у Олега попросили тест:

input:
0.973033
-1.171615 0.382832 0.124928
4.294446 0.985231 0.439197

output:
1.003649438

Там картинка выглядит так:

Ответ — AB, а отрезок касательной CD. Мы правильно поняли, что ответ — идти не по отрезку касательной, а что надо его загнать в полосу, но чутка неправильно это делали.

Привет. Задача — боянище тысячелетней давности.
Надо определить, верно ли неравенство 1/a + 1/b + 1/c < 1.

http://ideone.com/xeIW1P

Там же long long хватает. Нужно просто сравнить с 1 или c , теперь всё целочисленное, считаем дробь и сравниваем стандартно.

Почему бы не сделать честно и не прочитать ТОЧНО с помощью строк и перевести в i64 *10^5.

Привет :) Автором задачи "Ставки" был я, хотя, как уже написали выше, она оказалась баяном :(

По решению: с математической точки зрения задача простая и формула выводится несложно. А вот с точки зрения программирования у команд возникли две проблемы при работе с вещественными числами:

1. Поскольку деление даблов даёт погрешность, а нас определять ответ просят точно, то считать здесь надо в целых числах (например, сами числа домножить на 10⁵, а в неравенство домножить на wdl), либо использовать что-нибудь точнее double (например, в той же джаве есть BigDecimal).

2. Вещественные числа представляются таким образом, что даже числа с небольшим количеством знаков до и после точки будут храниться с погрешностью (выше есть один из самых простых примеров: 0.29), поэтому читать и преобразовывать к int'y их надо аккуратно.

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

Бинпоиск тут в общем-то, лишний. Просто надо вести кусочно-линейную функцию из стартовой точки с максимальной S*sigma как можно дальше, а потом делать отсечку в точке с заданной длиной проволоки. Бинпоиск фактически все это и делает.

http://olimpic.nsu.ru/widesiberia/2015/info

Основной страницей олимпиады можно считать http://olimpic.nsu.ru/widesiberia/2015/news и все те ссылки, откуда с этой страницы можно уйти. Или интересует какой-то конкретный вопрос, на который нет ответа в положении?

Потом дорешка откроется. Там же.

Открыл дорешивание в олимпиаде "Тренировки".

Немного о том, как в него попасть. Допустим, вы уже зашли в nsuts. Кликаете на название олимпиады "XVI Открытая Всесибирская олимпиада по программированию имени И В Поттосина" в правом верхнем углу, дальше выбираете олимпиаду "Тренировки". Если её нет в списке, регистрируйтесь на неё (ссылка ниже списка олимпиад). Дальше выбираете тур "Интернет-тур XVI Всесибирской олимпиады: дорешивание", и можно сдавать.

Конечно, можно также сдавать в дорешивание OpenCup-а.

f[i][s][fl] — максимальное количество различных цветов, после того как посмотрели первые i, набрали сумму s, fl == 0, если раньше такой цвет не брали, и fl == 1, если брали.

Сортируешь цветы по типу. Пишешь обычный рюкзак, но кроме dp[w] хранишь еще и last[w] — последний используемый тип для набора цветков на сумму w.

Построим граф в явном виде. Теперь на запрос АB отвечаем так: пытаемся пройти от A к корню, если на пути есть B, значит, что B сильнее А, аналогично идем от B к корню и пытаемся найти А, тогда А будет сильнее. Если ничего не получилось, выводим "Unknown".

Результаты 1 номинации

У нас O(n²m²). Можно прикрутить быстрое умножение многочленов, наверное, но вряд ли это хоть сколько-то улучшит время работы.

а зачем, итак проходит за 210ms

Может тогда стоит ещё и решение в пост добавить, а то как-то не информативно :)

Сожмем компоненты СС. Так же как в транзитивном замыкании за O(nm / 64), только храним не битсет со всеми вершинами, а только с 64. Запускаем n / 64 раза.

P.S. Конечно же, ответа либо нет, либо это граф из уже заданных отношений первого типа.

Вот, что сдали команды из СПбГу

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

Конденсация + N^2 / 32. В память все не влезало, поэтому нужно было по слоям считать битмаски.

Видимо число 32 в эпиграфе было не просто так :)

А расскажите, кто-нибудь умеет объяснять, почему эта задача не проще, чем reachability problem? Или, наоборот, приводить решение за время лучше O(VE / 32 + Q)? У меня было очень стойкое ощущение, что можно как-то воспользоваться спецификой, что нам не нужны точные ответы на каждый запрос, а надо только узнать, есть ли хотя бы одна из данных достижимостей, но довести ни до чего не удалось.

UPD Видимо, я их не так понял.

Скорее всего, несколько раз считается одно и то же выражение. Например, выражение 1 + 1 + 1 является корректным, но если неаккуратно написать динамику, то оно посчитается два раза (когда "внешним" является первый плюс и когда "внешним" является второй плюс).

11 — добавляем обратные дуги из ввода вместо прямых. Если добавилась дуга из черной в белую, то запускаемся дфсом из черной и красим рекурсивно все встретившиеся на пути белые. Таким образом, каждая белая вершина покрасится только один раз -> O(N).

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

У нас FFT получает TL 1 :)

Нужно объединить отрезки (получится снова набор отрезков, но теперь они не пересекаются). Пара отрезок + переход даёт +1 какому-то отрезку сдвигов. Нужно на этот отрезок прибавить +1, а потом найти лучшую точку. Прибавлять на отрезок можно в оффлайне префиксными суммами.

Зачем fft? :) Для начала избавимся от пересекающихся и касающихся отрезков, объединив их. Представим себе, что мы взяли и все перекрёстки унесли куда-то далеко влево и начинаем перемещать их направо. Как только одна точка попадает в отрезок, тогда к счётчику +1, как только выходит — -1. Соберём все такие события, отсортируем (можно подсчётом), пройдёмся, найдём максимум. Ну и не забудем, что иногда хорошо не двигать вообще ничего.

Об FFT мы подумали только в пятницу =)

На самом деле, ограничения были не в пользу FFT. Если увеличить N и M, а также уменьшить L, то получилась бы задача на FFT. Но увы =)