Всем привет!

Надеюсь у вас уже праздничное настроение?

Чуть позже я опубликую статистику за год и расскажу про наши достижения за год, а пока речь пойдет о чемпионатах и соревнованиях, которые мы сделали с партнерами в 2015-м году. Сюда не вошли какие-то мероприятия, которые мы делали совсем далеко от площадки Codeforces (например, Russian AI Cup).

Этот год запомнился большим количеством интересных соревнований, которые мы сделали не сами по себе, а вместе с партнерами. Особенно приятно, что все компании, кто хотел пополнить ряды своих сотрудников — все они нашли себе достойных кандидатов среди наших участников. А еще кто-то говорит, что олимпиады не нужны — врут! Вот список мероприятий:

Традиционно проект SnarkNews проводит голосование "Итоги года".

Цель голосования — отметить лидеров спортивного программирования прошедшего года — как участников, так и тренеров, а также наиболее удачные проекты и наиболее удачные публикации в прессе.

В настоящий момент проходит первый этап — выдвижение номинантов. Первый этап проходит до 23:00 30 декабря. Желающие опубликовать своё предложение по номинантам (и подискутировать по этому поводу) могут сделать это в комментариях к данному сообщению.

В этом году голосование проходит на базе системы Яндекс.Контест. Соответственно, предложить номинантов может любой, кто имеет логин в этой системе. При входе в систему описаны правила; для перехода к конкретным номинациям и выдвижению номинантов перейдите в раздел "Задачи"; справа появится список номинаций. По каждой номинации принимается не более двух вариантов; каждый вариант задаётся в отдельной строке в соответствии с правилами номинации (которые находятся на том же экране, что и форма отправки).

Ссылка на вход в систему для выдвижения номинантов.

Кроме того, Простой Новогодний Контест и Новогодний Блиц-Контест в этом году также пройдут на базе системы Яндекс.Контест; по сравнению с прошлым годом особых изменений в правилах не ожидается.

Открыта регистрация на оба контеста:

Простой Новогодний Контест — начнётся 30 декабря в 0:00, завершится 10 января в 23:50. Состоит из задач, предлагавшихся на различных командных соревнованиях по программированию, но так и не решённых в основное время.

Новогодний Блиц-Контест начнётся 31 декабря в 16:00, завершится 1 января в 8:00. Контест пройдёт по правилам Multiple Language Round (то есть за каждую задачу, успешно сданную на языке программирования, на котором участник ещё не сдал ни одной задачи, начисляется бонус -100 минут от штрафного времени) и по правилам Новогоднего Блиц-контеста (отличие от системы ACM в том, что время отсчитывается не от начала, а от 0:00 1 января по времени сервера, то есть и успешная сдача в 23:55, и успешная сдача в 0:05 дают штрафное время 5 минут).

Привет, Codeforces!

27 декабря 2015 года в 14:05 MSK (время московское) состоится очередной раунд Codeforces #337 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!!!

В этот раз задачи для вас готовили я и Эдвард Давтян (Edvard).

Хотелось бы сказать большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD Раунд переносится на 10 минут. Разбалловка 500-1000-1500-2500-2500

UPD2 Соревнование завершено! Всем спасибо! Разбор

Всем привет!

Раньше на Codeforces всюду показывалось локальное время сервера, и все программисты мира точно знали, чему соответствует в их часовом поясе 19:35 по Москве. Теперь же вам будет намного сложнее ошибиться во времени и пропустить раунд, так как вы будете видеть время в вашем часовом поясе.

Вот, к примеру, что видит простой лондонский программист в ожидании Codeforces Round #337 (Div. 2):

Задача оказалась не самой простой, так как многие части сайта усиленно кэшируются, и манипуляции со временем пришлось сделать непосредственно в браузере с помощью JavaScript.

Спасибо за внимание, удачи всем на следующем раунде!

Привет, Codeforces!

25 декабря 2015 года в 18:00 MSK состоится четвертый учебный раунд Educational Codeforces Round 4 для участников из первого и второго дивизионов. С прошлого учебного раунда в этот раз прошло всего ничего. Несмотря на то, что проведение раунда мы спланировали ещё в понедельник, мы почему-то забыли включить его в расписание, поэтому в расписании раунд только появился. Таким образом, это уже четвертый и последний в этом году учебный раунд.

<Эти два абзаца может быть никогда не изменятся>

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

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

</Эти два абзаца может быть никогда не изменятся>

Подготовкой задач в этот раз занимался только я (Эдвард Давтян). Пока благодарю, только MikeMirzayanov мы вместе придумывали задачи. Через некоторое время здесь появится благодарность тестеру. Также заранее благодарю Машу Белову Delinur, которая вычитает английские тексты условий, когда они появятся :-)

На этом раунде вам по традиции будет предложено шесть задач. Думаю задачи в этот раз будут немного проще, чем обычно. Это связано с тем, что исходный комплект задач оказался чересчур сложным, поэтому мы убрали самую сложную задачу (она скорее всего будет самой сложной на следующем раунде) и добавили очень простую задачу. Надеюсь комплект задач вам понравится и вы решите все задачи!

Поздравляю всех с наступающим новым годом!!!

Good luck and have fun!

UPD 1: Первая фаза соревнования закончена, ломайте решения соперников!

UPD 2: Опубликован полный разбор задач.

Background

One of the regionals in India was scheduled to be held at Hindustan University at Chennai on December 17 — 18, 2015. Unfortunately Chennai was stuck by a natural disaster. The entire south India received heavy rainfall and hence there was a lot of flooding at many places including Chennai around that time. Atleast 347 people died in the state of Tamil Nadu (where Chennai is located). The damage due to the floods overall in south India is estimated to be atleast USD 3 Billion. It is the costliest flood in 2015.

Ofcourse, due to this the Chennai regionals was postponed. I think everyone here will agree that this was an unexpected, unprecedent situation and hence it was entirely understandable that the regionals was postponed.

The Blog post

Dr. C J Hwang is the ICPC Asia director. In response to the above postponement he posted a blog article on his blog. You can read it here. Please read it as this post deals with that announcement.

Quote from the blog: "In the 20 years of ACM-ICPC Asia history, we never had the case of contest postponement."

Comment: That is just luck. It is great luck that there never was any problem during any of the Asia regionals during the past 20 years.

Quote from the blog: "Several years ago, Vietnam contest had a flood and I was there. I walked over the deep water.I was wet with pants and shoes. Vietnam committee did not request any postponement."

Comment: Wet pants and shoes, seriously? This seems like a minor water logging not a major, destructive flood.

Quote from the blog: "To avoid any future abuse of asking postponement to cover the un-readiness and the irresponsibility of hosting the contest ..."

Comment: Abuse? What exactly does Dr. Hwang want the organizers to do? How can you conduct a coding contest when there is water 2 storey high? How is this un readiness or irresponsibility? The flights/train/bus service were all stopped so how would the contestants reach the venue? What if something happened to them? There were no proper supply of food/water/electricity during the floods. As someone who has experienced a real flood, I am extremely offended by this statement.

Quote from the blog: "..., I am proposing to insert a few new lines into 2015 Asia rules. These new lines are same as I had approved for Asia Chennai. We have no time for negotiation/discussion and the complexity of calculating Asia site scores prevent us from any other solutions."

Comment: Why no time for negotiation or discussion? Calculating the slots is indeed complicated, but it does not take that much time either. This reason is here just so he can rush the decision before any discussion takes place. This should not be how decisions are taken at ICPC.

You can read the actual rule in the blog itself. Rules are generally passed by a vote. Here is the result of the voting for this rule:

Quote from the blog: "Voting Result: Casting Yes vote – 11 (Including 3 from WC sub-region)

Casting No vote – 1 (Including 1 from WC sub-region)

Implicit Yes vote – 40"

Comment: See that last line? The Implicit Yes vote? It means those who did not vote were automatically considered as "Yes". Yeah, that is how decisions are taken for such an important rule.

Concluding Remark

I have nothing against the rule. But everything against the manner in which it was decided. Also, the remarks about the flood situation reeks of arrogance and a total lack of empathy for the disastrous situation at Chennai. It is really sad that decisions are taken like this at such a prestigious contest like ICPC.

Добрый день.

Теперь для поиска по постам вам вовсе не обязательно уходить в Google, а можно это делать прямо на Codeforces. Мы поддержали поиск по текстам постов на базе Apache Lucene. В индексе содержатся все открытые публичные посты, которых уже более 15000 штук.

Временно поиск по тегам теперь недоступен (но и по тегам заиндексируем), но вместо него вы обнаружите возможность найти посты и даже отсортировать выдачу по нужному критерию. Кстати, язык запросов к поисковику — это все возможности Lucene, так что можете найти полное описание и писать неочевидные запросы.

Можно ввести несколько слов — все они попадут в требования к поиску (что-то из требований может быть опущено движком, если документов, удовлетворяющих всему запросу нет). Кроме того, осуществляется поиск по словоформам и, если повезет, по синонимам. Поддерживается поиск по названию, автору и специальный синтаксис запросов.

Вот примеры запросов:

• 305 — ищет все посты, содержащие 305, найдет посты про Раунд 305
• andrew stankevich contests — можно писать сразу много слов, будут искаться все
• user:mikemirzayanov title:сазанка — ищет все посты в названии со словом "сазанка" авторства MikeMirzayanov
• "vk cup" — можно использовать кавычку, чтобы искать точные совпадения
• title:educational — искать в названии

По поводу индексирования комментариев, исходных текстов решений и тестов условий есть ощущение, что это может оказаться бесполезным. Слишком сложно будет найти что-то релевантное (а может и нет). Как вы думаете, стоит делать?

Greetings! CodeForces Round #336 welcomes both divisions this Wednesday, December 23, 2015 at 16:35:00 UTC. The round is authored by me, Amor727, Chilli, and GlebsHP. We hope you'll like the problems. Scoring and score distribution: Not Dynamic; Div1: 500 — 1250 — 1500 — 2000 — 3000; Div2: 500 — 1000 — 1500 — 2250 — 2500

Much thanks to Amor727 and Chilli for writing and editing problems, GlebsHP for organizing the competition and for his very helpful attitude, Delinur for translations, winger for testing, Marina Kruglikova for statement fixes, and MikeMirzayanov for his amazing CF and Polygon platforms.

During this contest you will be assisting Genos from the series One Punch Man. His master Saitama will also make some appearances. We wish everyone good luck and high rating in assisting the two. From the contest crew and the two fellows below, happy holidays!

Congratulations to the winners:

Division 1:

1. matthew99

2. tourist

3. ACRush

4. jqdai0815

Division 2:

1. Hansuzu

2. ajjack999888

3. platypus179

4. Petru

5. Mihaell

Editorial of round: /blog/entry/22256

It's always a hassle to define our 2D Geometry library during a contest. Is there a way to make our computational geometry lives easier in any way? Fortunately for us, there is, at least in C++, using complex numbers.

Complex numbers are of the form a + bi, where a is the real part and b imaginary. Thus, we can let a be the x-coordinate and b be the y-coordinate. Whelp, complex numbers can be represented as 2D vectors! Therefore, we can use complex numbers to define a point instead of defining the class ourselves. You can look at std::complex reference here.

Defining our point class

We can define our point class by typing typedef complex<double> point; at the start of our program. To access our x- and y-coordinates, we can macro the real() and imag() functions by using #define. Of course, don't forget to #include <complex> before anything.

#include <iostream>
#include <complex>
using namespace std;

// define x, y as real(), imag()
typedef complex<double> point;
#define x real()
#define y imag()

// sample program
int main() {
	point a = 2;
	point b(3, 7);
	cout << a << ' ' << b << endl; // (2, 0) (3, 7)
	cout << a + b << endl;         // (5, 7)
}

Oh goodie! We can use std:cout for debugging! We can also add points as vectors without having to define operator+. Nifty. And apparently, we can overall add points, subtract points, do scalar multiplication without defining any operator. Very nifty indeed.

Example

point a(3, 2), b(2, -7);

// vector addition and subtraction
cout << a + b << endl;   // (5,-5)
cout << a - b << endl;   // (1,9)

// scalar multiplication
cout << 3.0 * a << endl; // (9,6)
cout << a / 5.0 << endl; // (0.6,0.4)

Functions using std::complex

What else can we do with complex numbers? Well, there's a lot that is really easy to code.

1. Vector addition: a + b

2. Scalar multiplication: r * a

3. Dot product: (conj(a) * b).x

4. Cross product: (conj(a) * b).y
   
   notice: conj(a) * b = (ax*bx + ay*by) + i (ax*by — ay*bx)

5. Squared distance: norm(a - b)

6. Euclidean distance: abs(a - b)

7. Angle of elevation: arg(b - a)

8. Slope of line (a, b): tan(arg(b - a))

9. Polar to cartesian: polar(r, theta)

10. Cartesian to polar: point(abs(p), arg(p))

11. Rotation about the origin: a * polar(1.0, theta)

12. Rotation about pivot p: (a-p) * polar(1.0, theta) + p
    
    UPD: added more useful functions

13. Angle ABC: abs(remainder(arg(a-b) - arg(c-b), 2.0 * M_PI))
    
    remainder normalizes the angle to be between [-PI, PI]. Thus, we can get the positive non-reflex angle by taking its abs value.

14. Project p onto vector v: v * dot(p, v) / norm(v);

15. Project p onto line (a, b): a + (b - a) * dot(p - a, b - a) / norm(b - a)

16. Reflect p across line (a, b): a + conj((p - a) / (b - a)) * (b - a)

17. Intersection of line (a, b) and (p, q):

point intersection(point a, point b, point p, point q) {
  double c1 = cross(p - a, b - a), c2 = cross(q - a, b - a);
  return (c1 * q - c2 * p) / (c1 - c2); // undefined if parallel
}

Drawbacks

Using std::complex is very advantageous, but it has one disadvantage: you can't use std::cin or scanf. Also, if we macro x and y, we can't use them as variables. But that's rather minor, don't you think?

EDIT: Credits to Zlobober for pointing out that std::complex has issues with integral data types. The library will work for simple arithmetic like vector addition and such, but not for polar or abs. It will compile but there will be some errors in correctness! The tip then is to rely on the library only if you're using floating point data all throughout.

Привет, Codeforces!

19 декабря 2015 года в 18:00 MSK состоится третий учебный раунд Educational Codeforces Round 3 для участников из первого и второго дивизионов. С прошлого учебного раунда прошло немало времени. В основном это связано с тем, что 6 декабря в Санкт-Петербурге состоялся NEERC и многие из вас (в том числе и я) в нём участвовали. Думаю дальше учебные раунды станут более частыми и регулярными.

<Эти два абзаца не менялись с прошлого раза>

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

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

</Эти два абзаца не менялись с прошлого раза>

Подготовкой задач в этот раз занимался не только я (Эдвард Давтян). Во-первых, большое спасибо Алексею Дергунову dalex, который поделился своей задачей, которую он раньше хотел дать на раунд, а она оказалась немного подбояненной. Во-вторых, хочу поблагодарить Александра Фролова fcspartakm RW, Виталия Кудасова kuviman АЁ и Артура Свечникова ikar за помощь в подготовке задач. Придумывать задачи нам помогал MikeMirzayanov. Также большое спасибо Маше Беловой Delinur, которая вычитывала мой RussianEnglish.

На сегодняшнем раунде вам будет предложено шесть задач. Надеюсь они вам понравятся.

Good luck and have fun!

UPD1: Первая часть соревнования завершена, надеюсь всем понравились задачи. Теперь можете ломать соперников :-)

UPD2: Разбор готов.

UPD3: Раунд закончился. Решения протестированы на дополненном наборе тестов. Результаты окончательные.

UPD4: 6725 rows affected :-)