Dalgerok's blog

By Dalgerok, history, 4 weeks ago, In Russian,

10.02.2019 проходил финальный этап Всеукраинской интернет-олимпиады по информатике. Условия на украинском: тык

Помогите, пожалуйста, решить задачу MainPoint, вот её формальное условие:

Даётся N (1 ≤ N ≤ 104) точек с координатами x, y (0 ≤ |x|, |y| ≤ 5000). Необходимо вывести максимальный периметр выпуклого многоугольника (с точностью 3 знака после запятой), который проходит через какие-то точки и обязательно через первую. Многоугольники которые вырождены в линию (например (0, 0) — (1, 1) — (2, 2)) тоже считаются выпуклыми.

Read more »

 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

By Dalgerok, history, 5 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • -41
  • Vote: I do not like it  

By Dalgerok, history, 5 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +37
  • Vote: I do not like it  

By Dalgerok, history, 2 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +55
  • Vote: I do not like it  

By Dalgerok, history, 8 months ago, In English,

Hello Codeforces.

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +21
  • Vote: I do not like it  

By Dalgerok, history, 10 months ago, In Russian,

Всем привет.

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By Dalgerok, history, 11 months ago, In Russian,

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

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

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

image

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

photo_2018_04_07_10_00_59

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +86
  • Vote: I do not like it  

By Dalgerok, 13 months ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • -35
  • Vote: I do not like it  

By Dalgerok, history, 17 months ago, In Russian,

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +33
  • Vote: I do not like it  

By Dalgerok, history, 19 months ago, In Russian,
  1. Можно ли как-нибудь выбирать несколько тегов?
  2. Можно ли как-нибудь исключать ненужные теги?

Read more »

 
 
 
 
  • Vote: I like it  
  • +24
  • Vote: I do not like it