Напоминаю, что этой ночью в 1-00 MSK состоится второй раунд Facebook hackercup.
Напоминаю, что этой ночью в 1-00 MSK состоится второй раунд Facebook hackercup.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
3 часа продлится
Удачи вам!
%s + "А я спать."
Не трави душу))
А кому-то еще в Петрозаводске завтра контест писать...
Ой как мы сочувствуем:) Вариант пропустить Facebook HC рассматривался?
Туда вроде ради контестов и ездят:) Ловите два)
Ой, спасибо! Чуть не забыл!
Можно ли будет где-нибудь наблюдать за таблицей результатов?
UPD. Скорее всего тут.
Наверное, тут.
Добавьте эту ссылку в тему: https://www.facebook.com/hackercup/problems.php?round=154897681286317
Их нельзя прочитать, если не прошел :(
Меня несколько смущают последние 4 ответа 0/1 в последней. Может кто-нибудь потестить на моем инпате если не сложно?
upd: нашел косяк, не умею решать..., хотя если все же кто-то выложит ответ — буду благодарен
md5: c8d468eb0d7c0d762071e74b92c8e2ef
Спасибо, печалька..
Твой инпут прерывается на 17 тесте...
перезалил. `
Как решать Sequence Slicing ?
Элементы растут в среднем на 1. Зафиксируем начало отрезка и будем идти вправо, считая элементы которые еще не встречались, где-то через 100000 элементов новые будут встречаться периодически, то есть если среди N позиций 1-ая 4-ая и 9-ая была новой, то в следующих N на этих позициях тоже будут стоять новые числа. Кроме того если сдвинуть начало отрезка на N в любую сторону, то "новые" элементы тоже сдвинутся. Получается, что достаточно перебрать начало отрезка от 0 до N - 1, посчитать где должен быть его конец x, он на промежутке
Unable to parse markup [type=CF_TEX]
тоже смещается вправо, и посчитав сумму арифметической прогрессии R - R1, R - (R1 + N), ... мы учтём все отрезки, начало которых делится на 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]. Тогда мы можем посчитать число валидных отрезков. начинающихся от этого элемента. Посчитаем общее число валидных и выведем ответ.
upd: нет. видимо n^2 log n. ОК. Чтобы это написать оставалось пару строк, дебажил какую-то фигню)
n ^ 2 log n log k вроде бы как. Ведь мы перебираем старт, для него дихотомией решаем задачи за ассимптотику n log n.
Ну да, логи более менее не страшны. мне просто казалось третья степень вылазит.
да неоткуда ей взяться.
По идее можно еще решать, если распараллелить и мощный комп, то может успеть нормально зайти и скользящее окно, поддерживать последний добавленный, первый добавленный и общий набор элементов.
Да, сейчас допер уже, что не откуда. просто считал что проверка по n модулям, каждая за o(n) итого n^2, а потом понял, что там каждое число как раз 1 раз используется и o(n) в сумме.
Объясните кто-нибудь и первые две тогда
В первой оказывается можно не убирать рёбра между неважными городами. Остальные убираем чтобы было дерево, поэтому ответ вычисляется из кол-ва рёбер, кол-ва вершин, кол-ва компонент связности, и тому же самому но только по неважным городам.
То есть ответ можно найти так: n-k+h, где k-кол-во компонент связности, h — кол-во рёбер, у которойх оба конца — неважные города?
А не.. тупанул. Я решал двумя обходами... видимо именно как у вас написано.
полная формула: (M - (N - S)) - (M1 - (N1 - S1)) где S это кол-во компонент связности, а 1 это то же самое, но только по неважным городам. Первое слагаемое в формуле — это сколько надо удалить рёбер чтобы получилось дерево, второе — сколько рёбер всё-таки не надо удалять.
Подскажите, пожалуйста, как искать компоненты связности в графе? Пробовал Тарджана Тарджана, однако на первом примере в описании проблемы, выдавал только одну компоненту :(
Тарьян это поиск компонент сильной связности, актуально только для ориентированных графов. А в неориентированном они легко ищутся простыми обходами в глубину или ширину: бежим по всем вершинам и если вершина еще не посещена, то запускаем из нее обход помечая компоненту.
UPD: Кстати, в первом примере на самом деле одна компонента, так что Тарьян прав =)
Ок, теперь ясно. Однако, к алгоритму Тарьяна я пришел только затем, чтобы найти циклы в графе. Никак не могу найти внятного объяснения как же всё-таки циклы находить. Не знаете, где можно почитать?
Циклов в графе бывает слишком дофига чтобы их все находить. По этому обычно стараются как-то обойтись без этого. Ну, а если очень надо, то каким-нибудь перебором находятся, но здесь явно не этот случай.
Можно и с помощью СРМ, по очереди добавляем все ребра, и потом смотрим число корней.
Хорошо бы знать, что такое СРМ.
СНМ, прошу прощения.Система непересекающихся множеств.
В первой можно и дфсить из каждой хорошей вершины, и если мы нашли какое-то ребро, ведущее в нее, то удалим его.
Во второй, рассмотрим такое бинарное дерево, терминальные вершины — это вершины, которые пока не боссы и не подчиненные (компоненты размера 1). При появлении связи (u, v) найдем каким компонентам принадлежат вершины u, v — пусть это c1, c2, тогда найдем в дереве узлы, соответсвующие с1 и с2, создадим новую вершину, которая будет иметь два сына — узел для c1, для c2, т.е. теперь новая вершина соотвествует компоненте c1+c2. После это построения можно сделать динамику F(i,j) — минимальная высота дерева с корнем в i с учетом того что кол-во сыновей (характеристика, которая ограничивается D) должно быть <= i.
Я в первой использовал систему непересекающихся множеств... Сначала объединял все множества рёбрами, на концах которых нет важных городов, потом добавлял оставшиеся дороги. Когда добавлял очередную дорогу, хотя бы на одном конце которой есть важный город, считал количество попыток объединений множеств с "самим собой"
Немного другое решение второй. Будем по очереди объединять компании и для каждой хранить список людей, которые могут быть директорами. Для каждого из таких кандидатов в директора храним минимальный уровень который при нем достигается и количество непосредственных подчиненных (тут оно не зависит от способов объединения). Соответсвенно, при сливании компаний эти значения легко пересчитываются. Чтобы понимать кто в какой комании я, недолго думая, сделал СНМ. Трудоемкость такого решения оценить, правда, сложновато, но, вроде как, это что-то около О(ND). По крайней мере даже на питоне работает весьма шустро, да и пишется быстро.
Резы появились, круто быть 99, учитывая что до разморозки был 166)
Поздравляю :) Сам тоже доволен, как слон, до разморозки был 161 :)
Что-то я как-то... Проснулся даже
У кого первая прошла, дайте пожалуйста ответы.. а то никак не могу понять, где у меня ошибка..
Инпут где взять? Или свой?
P.S. И да, там теперь можно скачать решение чьё угодно, можно взять любое подходящее и прогнать на своих тестах
Ой... что-то я туплю... своё то решение оттуда взял :) Спасибо!
Круто, лег спать за 2 часа до конца раунда и занял 41 место:) А еще всю ночь кошмары снились про то, что первая задача упала