Ufa SATU

TC.
Ripatti
Lepetrandr
coolart8

CF.
Ripatti
Lepetrandr
craybeats

У меня зашла такая байда: генерим около 10^7 рандомных подмножеств из первых 250 чисел и запихиваем полученные суммы в хэш-таблицу. Потом рандомно выбираем подмножества из других 250 чисел, пока не найдем с какой нить суммой, что есть в хэш-таблице.

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

Оно искало ответы чуть больше 5 минут.

Призываются боги

Выпасаются овцы

Триангулируются пирамиды

Сбор ежей

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

Лентяй я короче.

Thank you, fixed

мобов бы

vector< obj > vec;
vec.push_back( obj(123) );
obj * p = &vec[0];

вот так делать нельзя

я больше никогда не буду создавать указатели на объекты внутри векторов

я больше никогда не буду создавать указатели на объекты внутри векторов

я больше никогда не буду создавать указатели на объекты внутри векторов

я больше никогда не буду создавать указатели на объекты внутри векторов

я больше никогда не буду создавать указатели на объекты внутри векторов

да, и оно все равно не прошло, TL7…

я МКМФ писать не умею, взял е-максовский, ВА3. видимо у меня настолько кривые руки, что я не смог готовое прикрутить…

я писал дп на масках

сначала поверим, что оптимальный способ свапанья следуюший:

зафиксим паросочетание и последовательно для каждой вершины сверху (их мы рассматриваем слева направо) двигаем соответствующую вершину снизу слево.

ок, теперь сама dp[mask] — наименьшее количество свопов, где mask — подмножество вершин 2 доли, которые мы потом подвинем до упора влево.

пересчитываем так: для mask находим количество единичек ones и пробуем соединить ребром вершинку номер ones из 1й доли со всеми вершинками, что в маске mask во 2й доле и аккуратно считаем сколько свапов надо (исходя из dp для масок после выкидывания этой пары и, собственно, пары). из всех возможных “соединений” выбираем минимум.

ответ в dp[11..111]

Это еще что… У нас +4 по Н только по той причине, что в цикле нахождения всех делителей числа g я забыл проверить что итератор цикла, собственно, делитель g. Это решение как то 4 раза добиралось до 43 теста, а ошибку нашли только спустя пару часов…

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

я лично решал сортировкой событий за NlogN.

because judge system loves Mike Mirzayanov too)

ну их еще упорядочить надо. события то. хотя, можно их сливанием упорядоченных массивов посортить… тогда будет O(N). но зачем усложнять себе жизнь?

действительно, там же еще время есть. неверно понял условие, прошу прощения.

видимо таки придется сет заменить на дерево отрезков по сжатому времени.

не важно, там бред

теги хорошие

прошло ровно 1000 человек о О

я думаю, что проходной балл будет ровно 4000

О, я покраснел:) В первый раз в новой системе цветов.

upd. кстати да, пересчет рейтингов 1го дива произошел до окончания тестирования 2го дива.

Я проверил точным решением :D Во всяком случае, системные тесты. Вот: 1235773

use hash-table:)

You can see my implementations 1235766 (2970 ms) and 1235773 (1910 ms).

You should sort all numbers inside every list (because lists like {2,3,1} and {1,3,2} should be equal) and use a trie instead of sorting all of lists.

It can be solved using trie that should implemented using hash-table (it is not hashing:) ).

You can find list of friends for every vertex. Now you should sort all of them and insert into trie. In some vertices of the trie you can count a number of lists that end in such vertex.

So, we have exact solution in O(MlogM) time with small constant.

сам решение не писал, ибо опоздал на раунд на 5 минут =_=

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

итого точное решение за O(MlogM) с маленькой константой

upd. что то переходы на новую строку криво обрабатываются…

Не, там просто идет перебор некоторого параметра z чтобы все срослось. При больших n приращения z очень большие и решение тормозит. Но если два z для последовательных n поделить друг на друга, то они сходятся к тем числам, что вбиты в решение. Если перед тем как инкрементить, тупо домножать на них, то ускорение получается такое, что все заходит даже без прекалка.

Короче, магия тут чисто для скорости.

а как нормально решать D?

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

вот оно: http://pastebin.com/aAfaBvED.

ради смеха прошу обратить внимание на строки 107 и 109:D

пишем перебор для маленьких n, гуглим в oeis

ок, значит я не умею писать компараторы.

ну, с ней решение зашло:) set же работал некорректно.

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

Вещество.

У нас были некоторые проблемы с точностью из-за того, что мы складывали точки в set (один из худших случаев — когда все хорды пересекают одну горизонтальную (или вертикальную) и все точки будут отстоять от нее на +- eps и не совсем корректно сортиться). Потом мы стали засовывать точки в самописную хэш-таблицу (не надо сортить) и проблемы исчезли.

ну, еще можно заметить, что ответ всегда самый нижний LCA из этих трех.

	sort(Z+1, Z+n+1);
	cout << 5 << "\n";
	cout << -o_O << " " << o_O << "\n";
	cout << -o_O << " " << -o_O << "\n";
	cout << Z[k].FI << " " << -o_O << "\n";
	cout << Z[k].FI << " " << Z[k].SE << "\n";
	cout << Z[k].FI-1 << " " << o_O << "\n";

правда, это решение не совсем верно (можно подобрать тест когда одна сторона будет иметь длину 0)
но оно как то зашло))