Conqueror's blog

By Conqueror, history, 4 months ago, In Russian,

Всем привет из Кыргызстана!

Рад сообщить, что в этом году заключительный этап ИОИП 2018 будет также проводиться в столице Кыргызстана, в г. Бишкек. Спасибо andrewzta! Приглашаем всех участников, особенно соседей из Казахстана и Таджикистана, на свою площадку!

http://neerc.ifmo.ru/school/ioip/contacts.html#bis

В Бишкеке олимпиада пройдет в Кыргызско-Российском Славянском Университете, Естественно-Технический Факультет, пр.Чуй 6, корпус 3.

Добраться до 3-го корпуса университета можно автобусом №38, троллейбусами № 5 и 9, маршрутками 111, 121, 162 до остановки “Кыргызский Камвольно Суконный Комбинат”

Сбор участников в холле университета в 11:30 по местному времени (8:30 по московскому). При себе необходимо иметь паспорт.

Расписание олимпиады в Бишкеке, местное время:

11-30 — сбор в холле университета
12-00 — начало тура
16-00 — конец тура
Контакты для связи – Беляев Артем Александрович: artem_belyaev@mail.ru, +996 (772) 016647

UPD Up.

Read more »

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

By Conqueror, history, 6 months ago, In English,

Dear CF Staff,

Can you, please, consider providing an interface to add a foreign language?

For example, I need that to do problem statements for our Regional & National Olympiads, but, at first, I could not find a way to replace default English "Input file name", "Output file name", etc. names to Kyrgyz ones, so I had to hardcode them into olymp.sty and statements.ftl.

It would be great also if one could make a several-languages statement like this

1. Page 1, Kyrgyz
2. Page 1, Russian
3. Page 2, Kyrgyz
...

or like this

1. Page 1, Kyrgyz
2. Page 2, Kyrgyz
...
N + 1. Page 1, Russian
...

Read more »

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

By Conqueror, history, 6 months ago, translation, In English,

Results, please?

Read more »

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

By Conqueror, history, 6 months ago, In English,

Hi, Chinese part of the Codeforces!

Can you, please, list the main (or the best) Chinese Online Judges and describe for what kind of problems they are known for and other interesting features of them?

Thanks, Azret

Read more »

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

By Conqueror, history, 16 months ago, In English,

Hello CF,

Does anybody know any contests like OpenCup competitions (Grand-Prix of *)? I feel there must at least one of such great regular online competitions with insightful problems like these.

-- Azret, IAmNomad

Read more »

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

By Conqueror, history, 20 months ago, translation, In English,
 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By Conqueror, history, 2 years ago, translation, In English,

Hello.

I am trying to prove that sin (α - β) = sin α * cos β - cos α * sin β but getting something wrong.

OPα = (cos α, sin α)
OPβ = (cos β, sin β)
|OPα × OPβ| = |OPα| * |OPβ| * sin (γ)
|OPα| = |OPβ| = 1
γ = α - β
Hence, |OPα × OPβ| = sin (α - β)
Since, |A × B| = Ax * By - Ay * Bx
|OPα × OPβ| = cos α * sin β - sin α * cos β
Hence, sin (α - β) = cos α * sin β - sin α * cos β

But all formulas in internet say that sin (α - β) = sin α * cos β - cos α * sin β , i.e reverse of what I wrote above. Can someone find my mistake?

P.S Below is the correct proof written in white. You can find my mistake yourself first. ;)
As I understood I made mistake in computing angle. Since angles are + in counter-clockwise direction then
|OPα × OPβ| = ... * sin(360 - γ)
|OPα × OPβ| = |OPα| * |OPβ| * ( - sin (γ))
Hence, |OPα × OPβ| =  - sin (α - β)
And  - sin (α - β) = cos α * sin β - sin α * cos β
Leads to sin (α - β) = sin α * cos β - cos α * sin β

Read more »

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

By Conqueror, history, 2 years ago, translation, In English,

Propose to all to discuss solutions here.

Read more »

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

By Conqueror, history, 2 years ago, translation, In English,

Hello.

Tomorrow at 23:00 UTC will be held GCJ 2016 Qualification Round.
Round will last for 27 hours. Don't forget to register!

Let's discuss problems here after the contest.

Read more »

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

By Conqueror, history, 2 years ago, translation, In English,

Hello.

Reading the article from e-maxx (ALERT! RUSSIAN!). A piece of code ("radix sort of equivalence classes" part):

	for (int i=0; i<n; ++i) {
		pn[i] = p[i] - (1<<h);
		if (pn[i] < 0)  pn[i] += n;
	}
	memset (cnt, 0, classes * sizeof(int));
	for (int i=0; i<n; ++i)
		++cnt[c[pn[i]]];
	for (int i=1; i<classes; ++i)
		cnt[i] += cnt[i-1];
	for (int i=n-1; i>=0; --i)
		p[--cnt[c[pn[i]]]] = pn[i];

Why p[] contains correct order of cyclic shifts of length 2k after?

Read more »

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

By Conqueror, history, 2 years ago, translation, In English,
 
 
 
 
  • Vote: I like it  
  • +34
  • Vote: I do not like it  

By Conqueror, history, 2 years ago, translation, In English,
 
 
 
 
  • Vote: I like it  
  • +71
  • Vote: I do not like it  

By Conqueror, history, 2 years ago, translation, In English,

Hello!

Does anybody know who will host APIO this year? Or when it will be held?

Read more »

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

By Conqueror, history, 2 years ago, In English,

Qualification round just ended. How to solve A, C, D?

UPD Problems — https://www.dropbox.com/s/ywyczn0m0n5q7ts/problems-e-000815.pdf?dl=0

Read more »

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

By Conqueror, history, 3 years ago, In Russian,
 
 
 
 
  • Vote: I like it  
  • +21
  • Vote: I do not like it  

By Conqueror, history, 3 years ago, In Russian,

Раз задачи тренировок теперь не учитываются в Положении архива, то почему бы не учесть их в отдельном Положении в тренировках?

Read more »

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

By Conqueror, history, 3 years ago, In English,

Hello.

Given directed unweighted graph. It consist of N ≤ 105 vertices. There is at most one edge from each vertex. You need to answer for two types of queries (Q ≤ 105):

  1. Delete an edge from vertex V. Unexisting edge won't be deleted.
  2. Find shortest path from U to V.

No ideas. How to solve it?

Read more »

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

By Conqueror, 3 years ago, In Russian,

Здравствуйте.

Тренировал центроидную декомпозицию на 342E — Ксюша и дерево.
Ловлю WA #12. Баг?

Read more »

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

By Conqueror, history, 3 years ago, In Russian,

Здравствуйте.

Сегодня прошёл Кыргызстанский Четвертьфинал ACM-ICPC 2015. Результаты доступны здесь.

Пока что архив недоступен — его закрывали на время соревнования. Скоро будет открыт. Там вы можете зарегистрироваться.

Завтра все желающие могут поучаствовать виртуально. Регистрироваться на него надо, вы будете считаться участником если сделаете >0 сабмитов.

P.S Если будете учавствовать, то рекомендуется заранее не читать задачи.

P.P.S Если не будете, то как решать A? Что-нибудь кроме венгерского алгоритма?

Read more »

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

By Conqueror, history, 3 years ago, translation, In English,

Hi all!

Straightly to the problem — you are given a set of N (1 < N <  = 105) distinct points with integer coordinates on coordinate plane. For each point you need to find number of closest point to it (from set, expect itself). If there are more than one output point with minimum number.  - 104 <  = xi, yi <  = 104

UPD Distance between points (x1, y1) and (x2, y2) is equal to |x1 - x2| + |y1 - y2|. :P

Input
4
0 0
1 1
1 0
0 1

Output
3 3 1 1

Read more »

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

By Conqueror, history, 3 years ago, translation, In English,

Hi all!

How can we add/assign arithmetic/geometric sequence in simple/persistent segment tree?

Tasks:

Read more »

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

By Conqueror, history, 3 years ago, translation, In English,
 
 
 
 
  • Vote: I like it  
  • +18
  • Vote: I do not like it  

By Conqueror, history, 3 years ago, In Russian,

Всем привет!

Сейчас решал задачу и тут понадобилось реализовать копирование декартова дерева, в частности у меня есть дерево T и его нужно скопировать и смержить в конец двух других деревьев. Возможно ли это сделать без обхода всего дерева?

UPD Пишу на указателях.

Read more »

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

By Conqueror, history, 3 years ago, In Russian,

Привет всем!

Недавно нашёл эти классные сборники и решил поделится со всеми.

UPD Обратно не пашут. Новые.

UPD-2 2008-2014: https://www.dropbox.com/sh/bs23ye9u97ck9oi/AAAPcy0zkJUovixoCfPsxHY7a?dl=0

Read more »

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

By Conqueror, history, 3 years ago, In English,

Hello CF!

I think many of you, in particular IOI participants, can not find a good, clear solutions of IOI problems, so I decided to create a blog where we will publish a problem then find solution for it and start to solve next problem (like on AOPS).

Let me begin — IOI 2006 B. Pyramid.

Read more »

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