Hi, Codeforces!

Codeforces Round #553 (Div. 2) will be held on 18.04.2019 18:35 (Московское время). Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in the contest out of competition.

My gratitude to arsijo and KAN for coordinating the round, Markellonchik (special thanks for the help in preparing one of the tasks), mohammedehab2002, Jeel_Vaishnav for testing, and also 300iq for the idea and preparation of one of the tasks, Aleks5d and isaf27 for testing it, and of course MikeMirzayanov for Codeforces and Polygon systems.

In this round you will help the residents of the Kingdom of Kremland. I strongly recommend you to read the statements of ALL tasks (and of course, try to solve them).

Good luck!

UPD: Scoring distribution: 500-750-1250-1750-2250-2750.

UPD: Editorial

UPD: Thank you for your participation in this round! Congratulations to the winners!

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?

After round I saw some interesting links in the comments.

Problem C: https://www.quora.com/What-is-the-radius-of-the-circle-surrounding-a-circle-if-all-the-surrounding-circles-are-equal

Problem F: After understanding that you must find "subset with maximum XOR" on range from L to R, this subtask is becoming very easy to google it (e.g https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/)

Actually the SAME problem: https://blog.csdn.net/ShadyPi/article/details/79939990

You can see many accepted submissions with this idea :|

Problem E: https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/ the same idea to direct edges in order to topological sorting.

Thanks to Rinne and M_H_H_7 for the links in the comments (https://mirror.codeforces.com/blog/entry/64495?#comment-484476, https://mirror.codeforces.com/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?

The trick is in the procedure that finds a vertex with a given key and deletes it. There is a code on the 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);
}

Let's add some magic:

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);
}

Now the vertex is really deleted, thus we save a lot of memory.

UPD: added into https://cp-algorithms.com/data_structures/treap.html