Привет, 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 :-)

Добрый вечер!

Я рад вам сообщить, что в эти выходные пройдет шестнадцатая ВКОШП. В этом году олимпиада будет проходить на пяти площадках: в Санкт-Петербурге в здании Университета ИТМО, Барнауле, Алматы, Ташкенте и Тбилиси. Для участников завтрашний день начнется с регистрации, открытия и продолжится пробным туром.

Основной тур соревнования начнется в 10:00 в воскресенье 13 декабря.

Следите за текстовой трансляцией в твиттере NEERCNews от budalnik, qwerty787788 и subscriber.

Подписывайтесь на наше сообщество в ВКонтакте, там будет много интересной информации.

Смотрите видеотрансляцию от команды ICPCLive, которую будет вести Aksenov239. Во время трансляции к нам в студию придут много интересных людей.

Официальный хештег соревнований: #ВКОШП.

Также завтра состоится зеркало основного тура ВКОШП на платформе Яндекс.Контест. Ссылка появится позже, следите за обновлениями.

UPD: Ссылка на зеркало, начало зеркала в 11:00 по московскому времени.

Текущие результаты соревнования

Удачи участникам соревнования!
Пресс-служба NEERC

With many regionals around the world finished, I think it is time to start collecting teams that are going to World Final this year. Please help me adding information to the tables :)

Europe

Asia

Latin America

Africa & the Middle East

North America

South Pacific

Всем привет!

В среду 9 декабря в 19 MSK будет CF Round #335 (div 1 + div 2) по задачам, сделанным мной и dalex. Идёмте его играть!

Благодарим GlebsHP за помощь в подготовке задач, Delinur за перевод и MikeMirzayanov за сам Codeforces.

Систему подсчета баллов и их распределение вы узнаете вместе с началом раунда. Все равно эта информация не несет особого смысла, пока контест не начался.

Всем полных решений и успешных взломов!

UPD. Поздравляем победителей Div. 2:

weiszago

Invisble

nezametdinov

И Div. 1:

jqdai0815

Um_nik

Egor

Разбор: blog/entry/22019.

Всех хочется поздравить с началом зимы.

В эти выходные в стенах Университета ИТМО в Санкт-Петербурге, а также в Барнауле, Ташкенте и Тбилиси пройдет двадцатый юбилейный полуфинал чемпионата мира по программированию ACM ICPC в Северо-восточном европейском регионе (NEERC).

На этом полуфинале 268 команд поборются за шанс выступить на чемпионате мира ACM ICPC 2016, который пройдет в мае в Таиланде. Напомним, что от каждого вуза на финал чемпионата мира может попасть не более одной команды: это значит, что для некоторых команд главными конкурентами являются команды из того же университета.

На площадке в ИТМО участвует 102 команды, а завтра пройдет открытие и пробный тур продолжительностью 4 часа.

Подписывайтесь на страницу VK, твиттере и аккаунт в Instagram. Там можно будет найти фотографии и интересную информацию. Также у нас появился канал в Telegram, в котором мы хотим вести текстовую трансляцию NEERC 2015.

Если вы не участвуете в полуфинале, вы можете попробовать свои силы на задачах двадцатого NEERC в зеркале, которое пройдет 6 декабря в 11:00 по московскому времени, регистрируйтесь по ссылке.

Участвуйте в конкурсе прогнозов от snarknews, подробная информация по ссылке.

Результаты можно будет найти по ссылке.

Официальный хештег соревнований: #NEERC.

Удачи всем участникам!
Пресс-служба NEERC

UPD: Если вы знаете еще команды, у которых в сумме хотя бы 7000 рейтинга на Codeforces, пишите в комментариях, я проверил только знакомые мне команды, кого-то мог и упустить.

UPD2: Видеотрансляция