Спустя три месяца ̶т̶у̶п̶о̶ ̶о̶т̶д̶ы̶х̶а̶н̶и̶я̶ подготовки к важным экзаменам, я всё-таки решил поделиться своими впечатлениями про IV этап UOI 2019. В этом году олимпиада проходила в г. Одесса с 25 по 29 марта.

Жили мы (барабанная дробь) в школе-интернат. Условия проживания были лучше, чем в прошлом году. Кровати не на решётке, нормальные.

Ну, почти:

это не шоколад

В комнатах от 3 до 7 человек. Вроде неплохо.

На фото слева направо stanislav.bezkorovainyi, Jajceslav, MaxZubec.

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

Питание отличное. Каждый раз давали что-то подобное:

кто-то очень странно ест хлеб

Организация мне лично не понравилась. Перед первым туром сказали, что пустят в кабинет за примерно 30 минут до начала контеста. В итоге, пустили за 5 минут. На втором туре смотрящие очень долго спорили между собой в какую сторону и на сколько сдвигать места.

Между турами была прикольная автобусно-пешеходная экскурсия по городу.

Третий диплом получил носки, ручку, блокнот. Второй — флешка, блокнот, ручка. Первым дипломам выдавали то же, что и вторым плюс какие-то наушники.

Привет, Codeforces!

Codeforces Round #553 (Div. 2) состоится в Apr/18/2019 18:35 (Moscow time). Раунд будет рейтинговым для участников из второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут участвовать в раунде вне конкурса.

Большое спасибо arsijo и KAN за координацию раунда, тестировщикам: Markellonchik (отдельное спасибо за помощь в подготовке одной из задач), mohammedehab2002, Jeel_Vaishnav, а также 300iq за идею и подготовку одной из задач, Aleks5d и isaf27 за её тестирование, и конечно же MikeMirzayanov за системы Codeforces и Polygon.

В этом раунде вы будете помогать жителям Королевства Кремляндии. Настоятельно рекомендую прочитать условия ВСЕХ задач (ну и конечно же попытаться решить их).

Удачи!

UPD: Разбалловка раунда: 500-750-1250-1750-2250-2750.

UPD: Разбор

UPD: Спасибо за ваше участие в этом раунде! Поздравляем победителей!

Div. 2

1. square1001
2. hitonanode
3. jaguar1996
4. Mofk_wont_2k8
5. sansen

The first round of UOI 2019 is starting tomorrow. If I do not get to the top 10, then I will dye my hair white.

upd: I got top 25 :/

UPD: https://www.instagram.com/orapandrey/ in stories (in "memy" topic)

Problem C:

https://www.geeksforgeeks.org/largest-power-k-n-factorial-k-may-not-prime/.

https://acmp.ru/index.asp?main=task&id_task=200

https://www.quora.com/How-do-I-find-the-number-of-trailing-zeroes-of-N-factorial-in-Base-B

Or it faster to solve by yourself than find the solution on the internet?

После раунда я увидел несколько интересных ссылок в комментариях.

Задача С: https://www.quora.com/What-is-the-radius-of-the-circle-surrounding-a-circle-if-all-the-surrounding-circles-are-equal — ну тут без комментариев :/

Задача F: Из условия поймем, что нам нужно найти "подмножество с максимальным XOR`ом" на отрезке с L по R. Эту подзадачу очень легко загуглить (https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/)

Такая же задача: https://blog.csdn.net/ShadyPi/article/details/79939990

Можно увидеть много успешных посылок с этой же идеей :|

Problem E: https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/ — такая же идея с тем, что-бы ориентировать ребра в порядке топологической сортировки.

Спасибо Rinne and M_H_H_7 за ссылки в комментариях (https://codeforces.net/blog/entry/64495?#comment-484476, https://codeforces.net/blog/entry/64495?#comment-484418).

Hello Codeforces.

Did anybody from outside the USA get a T-shirt from Codefights? How exactly do they notify about its sending?

Всем привет.

Возникла необходимость сгенерировать множество размера ~15000 и числами до 300000 в котором все суммы двух различных чисел различны.

Множество {1, 2, 3, 4} — плохое, потому что 2 + 3 = 5 и 1 + 4 = 5.

Множество {1, 2, 3} — хорошее.

Никто не знает как быстро генерировать хорошее множество и возможно ли это вообще?

Вот и закончился IV этап UOI 2018. В этом году он проходил в г. Николаев 2-6 апреля.

Жили мы в школе-интернат №7. Условия ужасные. Кровати плохие — решетка не жесткая. Когда ложишься сильно проваливаешься, из-за чего на туре немного болела спина (по крайней мере у меня). Со мной в комнате жило ещё 9 человек. Розеток первое время не было (потом протянули удлинители). Зато была одна тумбочка :)

Жили как сельдь в консервной банке:

Питание, честно говоря, не очень. Порции маленькие и невкусные :c

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

Между турами был день отдыха, нас повели в зоопарк. В обед была уборка, поэтому нам не удалось увидеть большинство животных.

На закрытии решили не выдавать серые дипломы (их просто отдали тренерам). Вторым выдали ноунейм сборку поэзий с наготой. Первым — наушники и толстую книгу про историю Николаевской области.

Оптимизация декартова дерева по памяти, о которой знают не все.

Фишка в процедуре erase() (находит вершину с заданным ключем и удаляет ее). На e-maxx.ru есть код:

void erase (pitem & t, int key) {
	if (t->key == key)
		merge (t, t->l, t->r);
	else
		erase (key < t->key ? t->l : t->r, key);
}

Добавим капельку магии:

void erase (pitem & t, int key) {
	if (t->key == key){
                pitem to_del = t;
		merge (t, t->l, t->r);
                delete to_del;
        }
	else
		erase (key < t->key ? t->l : t->r, key);
}

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

UPD: добавлено в https://cp-algorithms.com/data_structures/treap.html

Дано три числа N, M, K (ограничений, пока нет)

Надо найти количество способов выбрать на матрице N, M одну связную область размером K.

Меня интересует, решается ли эта задача полным перебором или есть какое-то оптимальное решение?

upd: нашел кое-что интересное OEIS

1. Можно ли как-нибудь выбирать несколько тегов?
2. Можно ли как-нибудь исключать ненужные теги?