Dalgerok's blog

By Dalgerok, history, 2 years ago,

• +176

By Dalgerok, history, 2 years ago, translation,

Hi, Codeforces!

Codeforces Round #553 (Div. 2) will be held on Apr/18/2019 18:35 (Moscow time). 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

• +260

By Dalgerok, history, 2 years ago,

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 :/

• +142

By Dalgerok, history, 2 years ago,

• +37

By Dalgerok, history, 2 years ago,

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/)

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://codeforces.com/blog/entry/64495?#comment-484476, https://codeforces.com/blog/entry/64495?#comment-484418).

• +55

By Dalgerok, history, 3 years ago,

Hello Codeforces.

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

• +21

By Dalgerok, 3 years ago, translation,

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


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.