Круто, лег спать за 2 часа до конца раунда и занял 41 место:) А еще всю ночь кошмары снились про то, что первая задача упала

Ой… что-то я туплю… своё то решение оттуда взял :) Спасибо!

Инпут где взять? Или свой?

P.S. И да, там теперь можно скачать решение чьё угодно, можно взять любое подходящее и прогнать на своих тестах

Я в первой использовал систему непересекающихся множеств… Сначала объединял все множества рёбрами, на концах которых нет важных городов, потом добавлял оставшиеся дороги. Когда добавлял очередную дорогу, хотя бы на одном конце которой есть важный город, считал количество попыток объединений множеств с “самим собой”

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

Поздравляю :) Сам тоже доволен, как слон, до разморозки был 161 :)

Что-то я как-то… Проснулся даже

Резы появились, круто быть 99, учитывая что до разморозки был 166)

перезалил. `

Твой инпут прерывается на 17 тесте…

Да, сейчас допер уже, что не откуда. просто считал что проверка по n модулям, каждая за o(n) итого n^2, а потом понял, что там каждое число как раз 1 раз используется и o(n) в сумме.

да неоткуда ей взяться.

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

полная формула: (M - (N - S)) - (M₁ - (N₁ - S₁)) где S это кол-во компонент связности, а 1 это то же самое, но только по неважным городам. Первое слагаемое в формуле — это сколько надо удалить рёбер чтобы получилось дерево, второе — сколько рёбер всё-таки не надо удалять.

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

А не.. тупанул. Я решал двумя обходами… видимо именно как у вас написано.

Во второй, рассмотрим такое бинарное дерево, терминальные вершины — это вершины, которые пока не боссы и не подчиненные (компоненты размера 1). При появлении связи (u, v) найдем каким компонентам принадлежат вершины u, v — пусть это c1, c2, тогда найдем в дереве узлы, соответсвующие с1 и с2, создадим новую вершину, которая будет иметь два сына — узел для c1, для c2, т.е. теперь новая вершина соотвествует компоненте c1+c2. После это построения можно сделать динамику F(i,j) — минимальная высота дерева с корнем в i с учетом того что кол-во сыновей (характеристика, которая ограничивается D) должно быть <= i.

То есть ответ можно найти так: n-k+h, где k-кол-во компонент связности, h — кол-во рёбер, у которойх оба конца — неважные города?

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

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

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

upd: нет. видимо n^2 log n. ОК. Чтобы это написать оставалось пару строк, дебажил какую-то фигню)

Объясните кто-нибудь и первые две тогда

Не успел докодить. решение такое. Пусть мы знаем отрезок [a, b]. Тогда посчитаем в нем количество различных чисел. Для начала разобьем этот отрезок на N подпоследовотельностей, возможно, некоторые будут пустые, такие что в каждой из них у нас индексы элементов сравнимы по модулю N. Получили N таких подпоследовательностей. В каждой из них мы можем легко найти первый и последний элемент. Теперь давайте пробежимся по каждой из таких последовательнстей. Мы можем узнать остаток от деления на N первого элемента в каждой из них ( а каждая такая последовательность — это арифметическая прогрессия с разностью N). Тогда, если мы запомним для каждого rem какие последовательности были, то есть первый член и последний, то мы тогда получим что у нас для каждого rem есть набор отрезков ( вида rem + xN, rem + yN, где x, y — нам уже известны). Тогда посчитаем их длину их пересечения. Это будет число различных чисел для данного остатка. Проитерировав по всем остаткам, получим общее число различных числе для отрезка [a,b]. Теперь давайте решать исходную задачу. Перебираем индекс a = 0, … , N — 1 Дихотомией перебираем индекс b. пусть мы нашли, что нам подходит [a, b]. Тогда понятно, что и [a, b + delta] подходит, а также будет подходить отрезок [a + N, b + N]. Тогда мы можем посчитать число валидных отрезков. начинающихся от этого элемента. Посчитаем общее число валидных и выведем ответ.

Элементы растут в среднем на 1. Зафиксируем начало отрезка и будем идти вправо, считая элементы которые еще не встречались, где-то через 100000 элементов новые будут встречаться периодически, то есть если среди N позиций 1-ая 4-ая и 9-ая была новой, то в следующих N на этих позициях тоже будут стоять новые числа. Кроме того если сдвинуть начало отрезка на N в любую сторону, то “новые” элементы тоже сдвинутся. Получается, что достаточно перебрать начало отрезка от 0 до N - 1, посчитать где должен быть его конец x, он на промежутке Unable to parse markup [type=CF_TEX] тоже смещается вправо, и посчитав сумму арифметической прогрессии R - R₁, R - (R₁ + N), … мы учтём все отрезки, начало которых делится на N с определённым остатком.

Спасибо, печалька..

md5: c8d468eb0d7c0d762071e74b92c8e2ef

Как решать Sequence Slicing ?

Меня несколько смущают последние 4 ответа 0/1 в последней. Может кто-нибудь потестить на моем инпате если не сложно?

upd: нашел косяк, не умею решать…, хотя если все же кто-то выложит ответ — буду благодарен

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

Зачем же такое говорить? Может, в этом обсуждении бы случайно решили проблему Кука :)

Их нельзя прочитать, если не прошел :(

Не подскажете, а разбор будет? уже вижу..

Добавьте эту ссылку в тему: https://www.facebook.com/hackercup/problems.php?round=154897681286317

Туда вроде ради контестов и ездят:) Ловите два)

Наверное, тут.

Можно ли будет где-нибудь наблюдать за таблицей результатов?

UPD. Скорее всего тут.

Ой как мы сочувствуем:) Вариант пропустить Facebook HC рассматривался?

Воронежская область

Ой, спасибо! Чуть не забыл!

А кому-то еще в Петрозаводске завтра контест писать…

Не трави душу))

%s + “А я спать.”

Удачи вам!

3 часа продлится

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

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

I think every thing is ok now,

I also have the same problem using Java.

I have the same problem on Python)

no , um using java

Поток минимальной стоимости в графе с отрицательными ценами и циклами строится беллманом фордом. Если есть просто цикл даже не связанный с истоком и стоком (граф несвязный), то мы должны будем пустить по этому циклу поток, чтобы уменьшить стоимость. Отсюда мы видим, найти путь минимальной стоимости в этом графе, и найти единичный поток минимальной стоимости это разные задачи. Вторая решается эффективно беллманом фордом, первая не имеет быстрого решения, иначе мы могли бы решать задачу Коммивояжера как я описал.

Are you using Python on this problems?

Как мне видится, если в построенном таким образом графе найти поток минимальной стоимости, то это решит задачу. Но можно ли его быстро найти? Я совсем не силен в потоках, но первая проблема, которая мне бросается в глаза – наличие в графе с ценами циклов отрицательного веса. Как в этом случае быстро находить поток? Мне кажется, что при этом мы вернемся к тому, с чего начинали.

Это один из вариантов, есть вариант опенкапа http://opencup.ru/index.cgi?data=macros/results&menu=index&head=index&ncup=oca&class=oca&region=main

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

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

А, понятно в чем ошибка. Суть в том, что макс поток ищет и нулевые потоки, т.е. если в сети существует отрицательный цикл, то МинКостФлоу пустит по нему поток кругом, не добавив при этом величины к потоку от s к t. Это мешает нам сделать рёбра между раздвоенными вершинами отрицательными. И стоит пересмотреть предложенное мною решение исходной задачи, возможно оно также ошибочно.

+1. Если решить эту задачу за полином, то перебором стартовой вершины за O(n) можно не просто проверить граф на гамильтоновость, но и найти гамильтонов путь если он существует.

Смотрите еще внимательнее. Команда ДонНТУ в один из дней была в Высшей лиге,а в остальные в юниорской, поэтому она имеет два результата.

Думаю, что как и MikeMirzayanov. Минусовать то за что?

да, ты прав

чё-то я гоню, ибо мне кажется я решил задачу коммивояжера с подачи MikeMirzayanov: назначим на на рёбра i * 2 -> i * 2 + 1 стоимость -1e30, на остальные рёбра w, будем в самом начале перебирать ребро (x, y), которым путешествие завершится, и исключать его из графа, исток в x * 2, из y * 2 + 1 в сток. Покажите где ошибка?

Уточняющий вопрос для проверки понимания. Разве ребро из истока не должно идти в start * 2? Мне кажется, что если оно идет в start * 2 + 1, то появляется возможность пройти через start второй раз, что не соответствует постановке задачи.

Разве это не эквивалентно проверке графа на гамильтоновость, что NP-полная задача?

конечно неочевидно, ибо я привел решение.
Upd: я ошибся

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

А хотя, это не важно. Я нашёл решение и для взвешенного графа. Раздвоим каждую вершину i на две (i * 2, i * 2 + 1), , если было ребро i -> j, стоимостью w, добавим в граф ребро (i * 2 + 1, j * 2, -w). Ребра (i * 2, i * 2 + 1) имеют пропускную способность 1 и стоимость 0, из истока ребро в start * 2 + 1, из i * 2 + 1 рёбра в сток. Найдём поток минимальной стоимости.

Да. Обновил условие.

Безусловно, она не решается за полином, если граф взвешенный

Граф невзвешенный? т.е. цена всех рёбер еденица, да?

ok, я нашел в правилах, там линукс

Контрпример. Граф c ребрами: 1 2 1 3 3 2

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

Ошибочка вышла, прошу прощения, бред написал.

No. You must use epsilon to compare doubles. x >= y -> (x > y || fabs(x - y) < 1e-9).

лично я пишу реализацию снизу, так как кода там намного меньше. Но к реализации сверху очень просто прикручиваются операции на отрезках, что при реализации снизу сделать ОЧЕНЬ сложно:)

Эм… Ну вот, написал подробный ответ, и всё сбросилось. Очень хорошо…

Тогда в двух словах:

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

Что касается Украины — об этом можно спросить у человека из Украины. Но, вроде, никаких “аспектов” ни у Украинцев, ни у Белорусов, ни у граждан Узбекистана не возникало.

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

UPD: О, удалось запостить хоть что-то с n-ой попытки…

Эм… Ну вот, написал подробный ответ, и всё сбросилось. Очень хорошо…

Тогда в двух словах:

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

Что касается Украины — об этом можно спросить у человека из Украины. Но, вроде, никаких “аспектов” ни у Украинцев, ни у Белорусов, ни у граждан Узбекистана не возникало.

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

Добрый день.

Подводный камень (может для кого-то весьма существенный) — тут грузят так, что о чём-то кроме учёбы думать не приходится. Это я за большинство говорю, вообще находятся уникумы…

По мнению человека с последнего курса (т.е. это я не своё мнение воспроизвожу), система образования построена так, что в самом начале даётся мощная математическая подготовка, что бы вся группа вышла на нормальный уровень (в это время не особо сладко приходится тем, кто с математикой не особо дружил в своём предыдущем ВУЗе — хотя это всё, вроде, не смертельно…), а потом любое программирование и сопутствующие технологии просто на ура ложатся на такую математическую базу.

Что касается Украины — можно об этом спросить у человека который тоже из Украины… Хотя, вроде ни у кого из не граждан России никаких “аспектов” не возникало.

Hi,

In http://codeforces.com/submissions/arpit_s

1st solution from top 1144453 gives correct answer — here i am accumulating total distance and calculating time from that.

4rth solution from top 1144243 gives Wrong answer — here i am accumulating total time and calculating distance from that. It gave WA where my answer differed from actual solution by 1. If precision issue is there, then it should be in both cases, isn’t it ?

Да, я это заметил. Но мне понадобилось несколько секунд, чтобы посмотреть тест и её разрешить.

Thanks.

-1) после виртуальной тренировки пропадают посылки.

Исправлено

Ну почему же, здравая и обоснованная критика ещё никому не вредила. Другое дело, что не стоит, пожалуй, настолько перегибать палку.

Однако заметьте, что в данном случае формализация получается неоднозначная — в этом и вся проблема, не более.

http://codeforces.ru/blog/entry/1256 здесь описывается нерекурсивный метод

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

Рекурсивно:

       [0,4]
   [0,2]    [3,4]
 [0,1] [2]  [3][4]
[0] [1]

и нерекур.

           [0,4]
    {0,3,4}     [1,2]
  [3,4]  [0]   [1] [2]
 [3] [4]

ну надо дерево на 10 элементов — заведи дерево на 16 элементов, а юзать будешь только элементы с 0 по 9 -ый (включительно). памяти отожрёшь под 32 вершины. Но это не страшно, по сравнению с возможностью багов, а такая реализация довольно простая, я уже как-то закидывал сюда код, ищи по фразе RMQ, RSQ

все нормально будет) это получается не совсем дерево отрезков, но это работает

Прошу внимательно посмотреть на строчку 15 и поискать эту команду в победителях Юниорской лиги каждого дня.

Не совсем понял, что происходит, если длинна отрезка — не степень двойки.

Если корень дерева — 1, а для каждой вершины v дети это v*2 и v*2+1, для массива с 1 индексацией места i-того элемента будет i+n-1

        1
       2  3
      4 5 6 7
      1 2 3 4

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

А как в нерекурсивном случае определять, в каких местах массива у нас находятся листья? Или структура реализации дерева в этом случае принципиально иная?

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

Спасибо за up =)

Нуууу… наверное это педантичность =)

Немного не в тему, но вообще говоря, есть два вида реализации построения дерева отрезков — рекурсивный и нерекурсивный. Рекурсивный предполагает движение от корня к листьям, нерекурсивный — от листьев к корню.