Hello everyone,

Some days ago there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, 8 April, at 9:30 MSK. Site clist.by says that there are no intersections with something important that day.

Second time in a row it is a personal contest. So we ask everyone to participate solo. It must be very interesting for yellow and lower guys, and, who knows, maybe for reds too. You can start virtual participation at any time.

And as usual,

Я совсем чуть-чуть заинтересованное лицо, но вроде бы стоит поднять немного шума, так как поведение организаторов чемпионата Урала выглядит так, будто им на все плевать.

Собственно, дело в том, что примерно неделю на этой страничке: http://acm.urfu.ru/chu/2017/ была информация, что отбор пройдет на опенкапе 2 апреля, но недавно ее поменяли, и на самом деле он пройдет 26 марта. Никому не кажется, что переносить дату отбора на неделю назад за неделю до начала — это очень подлый и неприемлемый поступок? Видя одну дату, люди начинают планировать свои дела, а спустя некоторое время все планы рушатся. Давайте может на завтра тогда перенесем? Там как раз какой-то контест от сборов МФТИ намечается. Вроде норм, да?

Например, у нас возникло пересечение с нашим ежегодным контестом (2012, 2013, 2014, 2015, 2016). Дата 26 марта довольно долго была свободна, но потом появляется опенкап, а затем на этот опенкап ставят отбор на чемпионат Урала. Если у вас крупное мероприятие — просто анонсируйте его заранее, чтобы организаторы мелких мероприятий могли подогнать даты. На самом деле я не верю, что команда из Самары прошла бы этот отбор, но, кажется, такие коллизии могут возникать где угодно и у кого угодно, и они не ограничиваются олимпиадами по программированию.

Всем привет.

Раунд скоро закончится, примерно через 1 час 30 минут после публикации этого поста. Стартовать вроде бы уже нельзя, если верить расписанию. Ну и конечно же, давайте обсуждать задачи здесь, бла-бла-бла, тому подобное.

Но мне больше интересно вот что: https://www.diffchecker.com/1154oPEl

Попробуйте угадать, какой из вердиктов на задачу X даст решение слева и справа.

Hello,

Another contest from Samara reached Codeforces Gyms. It will be held on Saturday, November 5, at 10:00 MSK. Please don't participate if you know the problems.

And as usual,

Hello everyone,

Some days ago we had an annual programming contest in Samara, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, 17 April, at 11:00 MSK. Site clist.by says that there are no intersections with something important that day.

Previously, it was a team contest, but this year we decided to make it personal. So we ask everyone to participate solo. This is how the results will be the most adequate.

And as usual,

Всем привет.

Мне сегодня скинули вот такую ссылку: https://inclass.kaggle.com/c/dota-2-win-probability-prediction

В этом соревновании надо по первым 5 минутам лога игры определить вероятность победы Radiant (одной из команд). Я бы с удовольствием в этом поучаствовал, но, похоже, что это соревнование закрытое, ибо там выдается вот такое сообщение: This competition is private-entry. You can view but not participate.

Я никогда не был на Kaggle, но здесь наверняка есть люди, знакомые с Kaggle. Можете ли вы рассказать подробнее о подобных закрытых соревнованиях? Можно ли получить на них инвайт? Если да, можно ли участвовать командой и как правильно зарегаться?

UPD. Решение нашлось: надо зайти вот по этой ссылке: https://kaggle.com/join/coursera_ml_dota2_contest. После этого сообщение изменится на This competition is private-entry. You've been invited to participate.

Всем нравятся тренировки без мониторов? А даже если и с мониторами, то с кривыми логами сабмитов, автоматически сгенерированными Codeforces?

Я наконец-то выложил давно написанную утилитку для конвертации лога сабмитов. Называется она Standings Converter. На данный момент поддерживается только чтение из Ejudge-формата и запись в Testsys-формат, потому что это то направление конвертации, что нам приходится использовать каждые полгода, чтобы добавить очередной самарский контест в тренировки Codeforces. Но вы можете добавлять свои Parser-ы и Outputter-ы :)

Q: Я сгенерировал лог Testsys с помощью этой утилиты, как теперь его добавить в тренировку?
A: Назвать этот файл contest.dat, зайти по FTP в папку нужной тренировки, скопировать contest.dat в папку sandbox, а потом нажать в интерфейсе тренировки кнопку Обновить соревнование.

Q: У меня не установлен Maven и я не использую Java!!!11111
A: Пиши свой парсер :) Maven не совсем обязателен, можно просто запускать класс Main.

Q: import org.w3c.dom.*;
A: На момент написания я ничего другого не умел. Переписывать заново лень.

Hi all!

On September 13, a qualification contest for ACM ICPC was held in Samara SAU. We always put our contests to Codeforces Gyms, so this Saturday, November 14, 11.00 MSK everyone will be able to enjoy it.

The contest will be held at Codeforces Gyms, it will be unrated and will last for 5 hours. The problems were prepared by craus and Shlakoblock.

And here is the full list of our previous contests:

• Training 2016.08.06 solo
• 2012-2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013-2014 Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2014, VII Samara Regional Intercollegiate Programming Contest
• 2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest
• VIII Samara Regional Intercollegiate Programming Contest

What's going on here? This contest was held two years ago. Just look at its id: it is 100187. Someone has managed to change its start date (and also to make it invisible for everyone but the author, which is fixed now), but how is it possible? Any permission settings? What if I go and reschedule all the contests in the gym? What if I hide them all? It must be a bug, admins, look into it, please.

P.S. Don't participate if you remember the problems.

UPD. Looks like gym vandals continue their work:

540A - Combination Lock

For every symbol we should determine how to rotate the disk. This can be done either by formula: min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i])) or even by the two for cycles: in both directions.

540B - School Marks

First count the number of marks that are less than y. If there are more than such marks, we can't satisfy the second condition (about the median), and the answer is -1. Otherwise we can get exactly such number of y marks so that the total number of marks greater than or equal to y is at least (maybe it's already satisfied). This is the required action for satisfying the second condition.

Now, in order not to break the first condition, get the remaining marks as lower as possible — all ones — and check the sum of the marks. If it is greater than x, the answer is -1, otherwise the correct answer is found.

540C - Ice Cave

There are three cases here, though some of them can be merged.

1. If the start and finish cells are equal, let's count the intact neighbours of this cell. If there is one, move there and instantly move back — the answer is YES. Otherwise it's NO.
2. If the start and finish cells are neighbours, the solution depends on the type of the destination cell. If it's cracked, the answer is YES — we can just move there and fall down. Otherwise it must have at least one intact neighbour to get the positive answer — we can move to the finish cell, then to this intact neighbour, and then return to the finish cell.
3. In the general case, check if the path from the start cell to the finish cell exists. If it doesn't, the answer is NO. Otherwise check the type of the destination cell. If it's cracked, it must have at least one intact neighbour, and if it's intact, it must have two intact neighbours.

540D - Bad Luck Island (my code: http://pastebin.com/3s6dRK3A)

Let's count the values dp[r][s][p] — the probability of the situation when r rocks, s scissors and p papers are alive. The initial probability is 1, and in order to calculate the others we should perform the transitions.

Imagine we have r rocks, s scissors and p papers. Let's find the probability of the rock killing scissors (the other probabilities are calculated in the same way). The total number of the possible pairs where one species kills the other one is rs + rp + sp, and the number of possible pairs (rock, scissors) is rs. As all meetings are equiprobable, the probability we want to find is . This is the probability with which we go the the state dp[r][s — 1][p], with the number of scissors less by one.

In the end, for example, to get the probability of the event that the rocks are alive, we should sum all values dp[i][0][0] for i from 1 to r (the same goes to the other species).

540E - Infinite Inversions (my code: http://pastebin.com/QFEMRbNP)

At first find the position of each element which is used in swap (using map). Now let's find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let's consider the following test:

2
2 6
4 8

The global sequence will look as follows: [1 6 3 8 5 2 7 4 9 ...], and here is the array of swapped elements: [6 8 2 4].

Let's understand with which numbers the number 8 forms the inversions. The only elements that could do that are the elements between the initial position of the number 8 (where the number 4 is now) and its current position: [5 2 7]. There are two numbers on this segment which didn't take part in swaps: 5 and 7. The number 2 should not be counted as it took part in the swaps and we have already counted it in the first part of the solution.

So we should take the count of numbers between 8's indices in the global sequence (8 - 4 - 1 = 3) and subtract the count of numbers between its indices in the swaps array (4 - 2 - 1 = 1). We'll get the number of inversions formed by the element 8 and the elements which haven't moved at all, it's 2. Counting this value for all elements which have been swapped at least once, we get the second part of the answer. All operations in the second part of the solution can be performed using sorts and binary searches.

Hi all,

I was honored to open the fourth hundred of Codeforces Rounds. Unfornunately, neither I nor my friends couldn't invent any hard problems, so it's only a Div. 2 Round. But we'll definitely prepare a full round in the future! As always, I thank Zlobober for his help in preparing the problems, Delinur for English translations and MikeMirzayanov for the Codeforces itself.

The problems must be pretty easy for Div. 1 guys, so let's start a challenge: reds should solve everything in 30 minutes, yellows — in 1 hour, and violets — in 1 hour and a half. How many people will be able to make a success?

The score distribution will be standard. Wish you accepted solutions and successful hacks!

UPD 1. Congratulations to the winners in Div. 2:

1. PauGra
2. 233333333
3. tgehr

and in Div. 1:

1. niyaznigmatul
2. I_love_Tanya_Romanova
3. dreamoon

UPD 2. This is the editorial: /blog/entry/17643.

Hello guys,

I'm going to tell you about one of the negative aspects of Java on programming contests (actually, not only on contests), or, more precisely, how I have tried to resolve it. As you may know, Java has the disadvantage related to its collections library: the constraints of this language make you use object types even when using primitive types should be enough. Compare ArrayList<Integer> and vector<int>: Java list stores objects of type Integer, which are created every time when you add an element into the list (it's called boxing / unboxing), whereas C++ vector just stores ints. This behaviour slows down Java programs, and many people don't like it.

All this shit comes from the language design: you can't simply write a primitive type inside the angular brackets in Java. Some months ago I was thinking about this problem and came to the solution: why not just write my own collections library, with primitive types? Moreover, I haven't found any library with really all collections in the Internet.

That's how my small project EZ Collections (Github repository) was born. Of course, I haven't written all possible collections for all possible datatypes. Instead of that I have written each collection only once, leaving some hints for Maven plugin to generate everything as needed.

I have to say that this library is designed to use on programming contests or private purposes. It's thread-unsafe, it has some missing validations, it's prohibited to modify the collection during the iteration, it doesn't support serialization and maybe something else. But the problems on the contests can be solved without any troubles.

To use this library, you need:

1. Install Git and download the repository using git clone command (the URL is specified on the main page of the project). Or you can just download it using Download ZIP button.

2. Download Maven (link to the download page), install and configure it (if you don't know anything about it — use Google, but, as far as I remember, it's enough just to set the path to Maven in the system variables).

3. Enter the root directory of the library and execute command mvn clean install. After that two jar files will appear in your local Maven repository, and also in the target folder. One of these jars contains class files, and the other one — source files. Now you can use them in your Java project.

But it's still unclear how to use it on contests. You need Egor's plugin CHelper for IntelliJ IDEA. After it had moved to Github, it became possible to merge the pull request that fixes some problems. The last pre-built version (commit 29dc20b), which includes my pull request, can be downloaded from here and installed in IDEA on your own.

After plugin update you can include the library into your contest project, specifying the path to the jar file with sources. That's all!

This is the example: let's solve the problem 118E - Bertown roads

• use List<Integer>[] for storing the graph: 8293080 — 1060 ms, 39100 KB
• use EzIntList[] for storing the graph: 8293086 — 654 ms, 12148 KB

(this problem has quite large input, the larger it is, the more performance you gain)

One more example: solve the problem Timus 1521

With the TreeList's help the solution takes only a few lines:

int n = in.readInt();
int k = in.readInt();
EzIntList a = new EzIntTreeList(n);
for (int i = 0; i < n; i++) {
    a.add(i);
}
int idx = 0;
for (int i = 0; i < n; i++) {
    idx = (idx + k - 1) % a.size();
    out.print(a.removeAt(idx) + 1);
    out.print(' ');
}

What do we get using EZ Collections? For now, the following data structures are implemented:

• ArrayList
• ArrayDeque (with the possibility to get the element by its index)
• Heap
• Sort (guaranteed NlogN implementation)
• HashSet
• HashMap (I've used open addressing approach. I'm quite sure that it's not hackable)
• TreeSet
• TreeMap
• TreeList (the array that can perform add, set, insert and removeAt operations in logN time)
• Pair classes

Also I have to mention that there is famous Trove library (its repository can be found here) which has the similar idea, maybe some of you use it at work, but the problem is that only ArrayList, HashSet and HashMap are implemented in Trove. It's not enough for programming contests.

Some notes and plans:

• NaN, POSITIVE_INFINITY and other similar stuff is not supported. You know who you are, if you use such things.

• As it's impossible to return null (because EZ Collections store primitive types), method returnedNull() is added in every class where it's necessary. You must call it to perform null-check immediately after calling the method which could have returned null in usual Java Collections. For instance, these code fragments are identical:

    TreeSet<Integer> set = new TreeSet<Integer>();
    Integer lower = set.lower(42);
    if (lower == null) {
        ...
    }

    EzIntTreeSet set = new EzIntTreeSet();
    int lower = set.lower(42);
    if (set.returnedNull()) {
        // don't use the lower variable, it's not guaranteed that it has some certain value
    }

• The current source generation mechanism is ugly and doesn't support some cases that I want to support, so I'm planning to rewrite it. But all collections I wanted to implement in the first version already work.

• boolean is considered to be uncomparable type, so Pairs with booleans don't implement Comparable. It will be fixed after rewriting the source generation.

• Next collections I want to implement are LinkedList (on arrays). But it's only when I rewrite the source generation.

• The next planned thing is to implement maps which have primitive key and object value types, or vice versa. It also should speedup programs a bit.

Please write any suggestions and feedbacks using the private messages on Codeforces.

Version history:

• Feb 21, 2015 — version 0.1.0 is released. It contains the identical content comparing to standard Java collections library.
• Mar 15, 2015 — version 0.1.1 is released. TreeList was added. Also the possibility to specify custom hash functions for HashSet/HashMap was added.

Recently we ran another ACM ICPC quarterfinal qualification contest, whose results influenced the list of teams that will go to Saratov this autumn. The corresponding gym contest on Codeforces will be held on Sunday, Sep 21, 2014, at 11:00 AM.

Link to the contest: 2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest

The list of our previous contests:

• Training 2016.08.06 solo
• 2012-2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013-2014 Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2014, VII Samara Regional Intercollegiate Programming Contest

Добрый вечер. Столкнулся с задачей, никак не могу решить. Выдает Wrong Answer на 2 тесте. Перепроверил код уже тысячу раз, не знаю, где ошибка.

Вкратце условие: надо поддерживать множество чисел и выводить его размер после каждой операции.
В первой строке задано число n (1 ≤ n ≤ 100000) — количество операций. В n следующих строках заданы операция (add или remove) и число (от  - 10⁹ до 10⁹), через пробел. Если операция — add, надо добавить число в множество, если remove — удалить его оттуда.

Код: http://paste.ubuntu.com/7857687/

Link to announcement and discussion.

And here is the problem analysis.

A div 2: 378A - Playing with Dice

Make three counters: for wins of both players and for a draw. Iterate over all six ways how they can throw a dice. For each way determine who wins or there is a draw and increment the corresponding counter.

B div 2: 378B - Semifinals

You can think a bit and understand that you should consider only corner cases: k = 0 and . All other cases will be something between them.

If k = 0, we should choose n biggest elements from two sorted lists, one of the ways is to use two pointers method. And if , we just mark first people in each list.

A div 1 / C div 2: 377A - Maze

Start BFS or DFS from any free cell. As the maze is connected, this search will visit all s free cells. But we can stop the search when it visits s - k free cells. It's obvious that these s - k cells are connected to each other. Remaining k cells can be transformed into the walls.

Solutions which every move transform the cell which has the minimal number of neighbours passed pretests. However, it's wrong. Here is the counter-test:

....
.#..
..##
..##

Top-left cell has no more neighbours than any other cell but we cannot transform it into the wall.

B div 1 / D div 2: 377B - Preparing for the Contest

It's obvious that the time needed to fix all bugs is the monotonic function: if we can do it for some time, we can do it for greater time. So we can use binary search in these problem. We should learn how to check if some time t is enough.

At first sort all bugs by their complexity and all students by their skills. Let's consider the hardest bug. Who can fix it? It can be fixed by student whose skills is not less that this bug's complexity. Push all such students into the priority queue (sorted by students' price) and pop the cheapest student. As we check time t, this student must fix t hardest bugs (he definitely can do it). Save that information and go to the next bug which has not been fixed yet. Again push all students which can fix it to the priority queue and pop the cheapest one. And so on. If at some moment priority queue is empty, time t is not enough. If we spent too much 'money' — it's not enough as well. Otherwise we get the correct schedule.

C div 1 / E div 2: 377C - Captains Mode

There are some observations that do the problem very simple. The first one is that we always should pick the strongest hero. But we cannot say something similar about the bans — in different situations different bans are the best. But the most important observation is that we should consider only m strongest heroes. Indeed, in every game where only strongest heroes are picked, no hero except m strongest can be picked. That's why we don't need to ban them and therefore we don't need to consider them.

So now we have only 20 heroes. It means we can solve the problem using the dynamic programming with bitmasks: dp_mask will be the difference between the teams' strengths when only those heroes are picked or banned whose bits are set to 1 in the mask. At every state we try to pick or ban every available hero and go to the other state. The simpliest way to implement it is the recursion with memoization. The answer will be stored in dp_2^m - 1.

Unfortunately, we couldn't estimate the real complexity of this problem (despite it has the simple solution, this solution is not so easy to think of — standard 1500 points for problem C would be better) and set too big TL (many solutions written in C++ whose complexity is m²·2^m passed — we should have been set TL to 1 second or even to 0.75 seconds). So if you solved it in m²·2^m, you may assume that you're just lucky and your correct verdict is Time Limit Exceeded.

Why it can be solved in m·2^m? There is no point of missing a ban — if we ban the weakest hero, nothing will change since the weakest hero won't be picked.

Also this problem has weak pretests so you could hack solutions without bitmasks with almost any big random test.

D div 1: 377D - Developing Game

Let's note that every answer is characterized with two numbers L and R so that max{l_i} ≤ L, R ≤ min{r_i}, and L ≤ v_i ≤ R. If we know L and R, we can check every person and choose those who satisfies the conditions above.

Let's imagine a plane with the coordinate axes: one of the axes will be L, and the other will be R. If the point (L, R) on this plane is the optimal answer, people included in this answer for sure satisfy the conditions l_i ≤ L ≤ v_i and v_i ≤ R ≤ r_i. These conditions specify the rectangle on the plane. Since we should find the maximum number of people, we should find such point (L, R) that it is inside the maximum number of the specified rectangles.

Now it's the standard problem that can be solved using the scanline through one axis and the segment tree built on the other axis. The hardest part is to reduce the original problem to it.

E div 1: 377E - Cookie Clicker

First of all, throw away the buildings which cannot be used in any optimal answer: for each v_i remain only one building that has speed equal to v_i and minimal c_i. Also throw away all buildings whose speed is less than the speed of the fastest building which has c_i = 0.

It's fairly obvious that at any time we should use the fastest building. And if some building is used in the optimal answer, it should be bought and used immediately when we have enough money (I will use the word 'money' instead of 'cookies').

Let's imagine the plane (x, y) where x axis stands for the time and y axis stands for the money. We will maintain the graph of the function y = f(x) — 'maximal number of money that can be obtained at the time x' and process the buildings one by one, changing the graph. This function is the union of the line segments with the slopes equal to v_i, and each of these line segments is active on a certain segment [x_li, x_ri] of the axis x.

For example, at the beginning the graph is just the line y = v₁x, where v₁ is the speed of building that can be bought for 0 units of money. Let the next building's price is c₂. Find the minimal point x₀₂ where value of our function is greater or equal to y = f(x₀₂) ≥ c₂ and buy this building at the moment x₀₂. Then we should make the line y = y₀₂ + v₂x where y₀₂ = f(x₀₂) - c₂ is the amount of money remaining after the purchase. Now we have two lines. Till some moment the first line is better (not till x₀₂, maybe later), but as v₂ > v₁ there exists a moment of time (it's ceil(x₁₂) where x₁₂ is the x-coordinate of the lines' intersection) when the second line becomes better. Now we know the segments where a particular line is better than the others.

Continue add all buildings to the graph this way. Line segments should be stored in stack, as in all problems with convex hull, and every step remove unnecessary line segments from the stack (these are the lines those position in the stack is after the line which has an intersection with the currently added line). After we process all buildings, we use our graph to find the minimal time when we have S untis of money.

If we also should say which building we must use, we can store for any line segment its 'parent' — the line segment which was active when the current one was bought. With such parent array it's not hard to restore the sequence of buildings in the answer. We removed this part from the problem to make it a bit easier.

Hi all!

Authors of today's round are craus and dalex. We just couldn't miss the round with such a beautiful number, so at 19.30 MSK you will solve problems which were invented by Pavel and prepared by me.

We thank Gerald and Delinur for their help in contest preparation and MikeMirzayanov for creating Codeforces.

Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins.

We wish you accepted solutions and successful hacks!

UPD. Contest is over, congratulations to the winners!

Div. 1:
1. Petr
2. tourist
3. Egor

Div. 2:
1. k3e18
2. cornell2011
3. Daniyar_7

UPD. 2 Problem analysis is published.

As the admins don't want to fix the bug with two different Codeforces sites (1 2), I ask you to paste relative links.

It can be done this way:

• /profile/tourist

• /blog/entry/1

• /contest/1/problem/A

If you click on such link, you won't be logged out. Thanks.

On Satudray, Oct 12, at 12:00 PM another 5-hour contest in Codeforces Gym will be held. It's the second time we prepare qualification contest for Samara SAU teams to determine who deserves to participate in Southern Subregional Contest in Saratov (the previous such contest can be found here).

Maybe you know that team Teddy Bears is no longer able to take part in ACM ICPC. It resulted in renaming and renumbering the teams in the university. You have an unique opportunity to defeat new first team of Samara SAU and show them at what place they can finish in Subregional Contest. Don't miss this chance!

Contest is over. Now you can just solve the problems or take part in the virtual contest.

Many thanks to Xellos who made a tutorial.

Этот текст я пишу в основном для ребят младших курсов своего университета, чтобы они наконец начали участвовать в соревнованиях Topcoder. Так получилось, что на Codeforces это сделать мне наиболее удобно. Может быть, кому-то еще пригодится.

Что вообще такое Topcoder

Topcoder — это как Codeforces, только менее удобный. На самом деле, помимо соревнований по спортивному программированию там проводится еще куча мероприятий, которым аналогов в мире нет, так что многим деваться просто некуда :) А для тех, кто занимается именно спортивным программированием, это просто еще три-четыре неплохих контеста в месяц.

Если кликнуть на сайте на ссылку Events, а далее — Event Calendar, можно увидеть расписание этих контестов. Время там указано какое-то американское, чтобы получить московское, нужно в разное время года прибавлять либо 8 часов, либо 9. Кроме того, можно кликнуть на конкретный SRM (раунды здесь именно так называются — Single Round Match), и там будет ссылка на timeanddate.com, показывающая, во сколько начнется этот раунд.

Точно так же, как на Codeforces, на Topcoder есть рейтинг, есть красные и серые, есть комнаты и взломы, но устроено это немного по-другому. О правилах — в следующем разделе.

Правила Topcoder SRM

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

Раунд состоит из двух частей. Сначала 1 час и 15 минут длится Coding Phase — тут надо решать задачи. Затем следует пятиминутный перерыв, и после него 15 минут идет Challenge Phase — здесь вы можете взламывать решения своих соперников по комнате. В отличие от Codeforces, решение задач и взломы на Topcoder разделены.

В раунде три задачи, обычно они стоят 250, 500 и 1000 баллов, иногда эти числа могут различаться. Изначально все задачи закрыты, но можно открыть некоторые из них и начать решать. Со временем стоимость открытых задач убывает, но нельзя получить за задачу менее 30% от начальной стоимости. Понятно, что пока не решишь одну задачу, невыгодно открывать другие — за них стоимость также начнет убывать. За ресабмит участник получает штраф в 10% от чего-то там, не помню, чего именно. Лучше сразу писать правильно и не ресабмитить.

Успешный взлом дает +50, неудачный дает -25. Затем прогоняются систесты, задачи падают, и участники узнают свои финальные результаты, после чего открывают Codeforces и начинают спрашивать, как решать 500.

Собственно, из правил это все, и дальше пойдет рассказ о конкретной IDE и конкретном языке программирования применительно к Topcoder. Вообще, писать там можно на Basic, C++, C#, Java и Python. Я расскажу про Java и Eclipse.

Arena, или как разработчикам Topcoder удобно кодить

По дефолту контесты пишутся в Арене. Ее можно запустить, протыкав на сайте ссылки Competitions — Algorithm — Single Round Matches — Launch Arena. Это Java-апплет, в котором вы типа должны писать контесты. Но мы не будем этого делать. Большинство людей все-таки используют нормальные среды разработки. Здесь будет рассказано об Eclipse, на странице загрузки подойдет, например, Eclipse Standard, и о плагине EclipseCoder.

Главное меню Арены

Я умолчу о том, что чтобы писать контесты на Java, неплохо бы установить JDK, поэтому этот шаг будет пропущен :) Скачайте Eclipse, распакуйте его и запустите. Теперь пришла пора установить плагин. Нажимаем Help — Install New Software, в строчку впечатываем адрес http://fornwall.net/eclipsecoder/. Понимаем, что можем установить вот такие компоненты (см. картинку). Выбираем Core, Java Support и Problem Archive, принимаем лицензионное соглашение, устанавливаем, перезапускаем Eclipse. Теперь можно писать контесты.

Установка EclipseCoder: выбор компонентов

Добавим вьюшку, из которой можно запускать Арену прямо из Eclipse. Тыкаем Window — Show View — Other, там выбираем EclipseCoder — Problem Statement. У нас появляется еще одна вкладка, на которой есть иконка с логотипом топкодера. Эта кнопка запускает Арену.

Вкладка с кнопкой запуска Арены

Точнее, она смотрит, как версия находится у вас сейчас (необходимые jar-ники качаются в папку ~/.eclipsecoder, где ~ — папка пользователя), обновляет, если нужно, и запускает. Не надо лезть на сайт и искать там ссылку Launch Arena — все делается из IDE.

Обновление Арены из Eclipse при запуске

Посмотрим на настройки EclipseCoder: в Eclipse перейдите по Window — Preferences — EclipseCoder. Здесь, если не боитесь, можно сохранить логин и пароль от своего аккаунта, а в подменю Java можно написать шаблон, который будет у вас появляться автоматически при решении каждой задачи. Довольно несложно догадаться, что означает каждая из этих переменных с долларами.

Шаблон класса

Самое время сказать о задачах. На Topcoder задача представляет собой следующее: вам говорят, как должен называться класс, метод, и какие у него должны быть входные и выходные параметры, а также что он должен делать. Вы должны написать такой класс, в котором есть такой public-метод, с такой же сигнатурой, и чтобы он еще и решал задачу. Topcoder при тестировании будет вызывать ваш метод и смотреть, насколько правильно он отработал на всех тестах и взломах.

Задача Div-2 250: полное прохождение

Давайте теперь для завершения решим какую-нибудь халяву из дорешивания. Процесс решения на контесте и в дорешивании ничем не отличается, так что — запускаем Арену из Eclipse(это важно!), тыкаем там Practice Rooms — SRMs — и я выбрал самый последний раунд: SRM 592 Div 2.

Главное меню SRM 592 в дорешивании

На самом деле по внешнему виду дорешивание не отличается от контеста. Выберем задачу. Нажимаем на Select one и тыкаем 250 — это самая легкая задача.

Окошко с условием задачи

Если бы вы не использовали никаких плагинов, вы бы сейчас кодили в табе Coding Area прямо в этом окошке. Потрясающе удобное времяпровождение. Но мы пойдем наиболее хардкорным путем и откроем Eclipse.

Тем временем в Eclipse

Условие можно читать в Eclipse. Кодить можно в Eclipse. Видим, что нам сгенерировался метод, который нас просили написать, но, к сожалению, return 0; — это неправильное решение и не проходит даже семплы. Слева вы видите результат прогона юнит-тестов: EclipseCoder парсит семплы в условии и создает юнит-тесты, которые можно запустить одним кликом и увидеть, что вернул ваш метод и что он должен был возвращать на самом деле.

Теперь давайте решим задачу. Задача следующая: дан массив чисел pages, надо выбрать из него number чисел так, чтоб сумма была не минимально возможная, но при этом как можно меньше. Еще и все элементы в массиве различны.

Первое, что пришло на ум: выбрать number-1 минимальных чисел, одно пропустить, и выбрать следующее. Давайте попробуем это написать. Пишем, нажимаем Ctrl+F11 (Run). При написании можно писать свои методы и свои вложенные классы, но в этой задаче такое не нужно. Eclipse предложит выбрать, как именно запускать наш проект. Запускаем его как юнит-тесты.

Диалог Run As

Видим, что все тесты зелененькие — значит, мы прошли семплы!

Семплы пройдены!

Давайте добавим какой-нибудь свой тест. Откроем Package Explorer и выберем там класс, название которого оканчивается на Test.

Класс с юнит-тестами

Собственно, тут мы вольны использовать все возможности Junit. Чтобы создать свой тест, надо объявить публичный метод и снабдить его аннотацией @Test. Если при выполнении такого метода не будет никаких исключений, тест будет зелененьким :)

На сгенерированных автоматически тестах есть параметр timeout для аннотации @Test — он поможет вам отловить TL. Если вы хотите подебажить один из тестов — поставьте там timeout = (int)1e9 или вообще удалите этот параметр, поставьте брейкпоинт на внутри тела соответствующего метода-теста и жмите Debug. Либо можно просто выводить что-нибудь в System.out или System.err — топкодер эти выводы игнорирует — ему важно только то, что метод вернул.

Допишем свой собственный тест.

Собственный тест

После запуска выясняется, что он тоже работает правильно! Ну теперь можно сабмитить. Открываем Арену, точнее, то ее окошко, где написано условие задачи, жмем Compile — нам говорят, что все круто. Жмем Test — и запускаем наш код на одном из семплов (в этом режиме код запускается на сервере, я рекомендую в каждой задаче хотя бы один семпл пройти по кнопке Test — ну просто чтоб убедиться, что на сервере все нормально).

Запуск первого семпла на сервере

Видим, что Correct Return Value: Yes. Ну, значит все хорошо. Жмем Sumbit. Так как я писал этот текст одновременно с решением задачи, нам дали 156.76 очков из 250. Это, конечно же, очень мало, и на настоящем контесте за подобные задачи надо получать в районе 240-245 баллов.

У нас приняли сабмит

Систесты, однако, мы не проходили. Это всего лишь сабмит приняли. На настоящем контесте вы по его окончании узнаете, прошла у вас задача или нет, а в Practice Mode можно это проверить. Тыкаем в главном окне Арены Practice Options — Run System Test.

Accepted!

Все, теперь мы умеем решать топкодер. Потренируйтесь немного в Practice Mode, а потом можно приступать к самим SRM.

Раунд кончится в понедельник, 12 августа, в 14-00. Можете считать это небольшой напоминалкой (вход в контест).

Но пост не об этом. Кто вычитывает тексты условий? Уже второй раунд подряд нам предлагают такую ересь from my heart (задача C из Round 1, задача F из Round 2), что ну просто вообще невозможно понять, что от тебя хотят. Может, стоит назначить отдельного человека или даже группу людей, которые будут читать условия и гарантировать, что они понятные?

Вчера, 3 июля, прошел финал ACM ICPC 2013. Этот пост не будет подробно рассказывать о том, как прошел контест нашей команды, этому будет посвящен лишь один абзац. Я поведаю в основном о недостатках и просчетах организаторов финала. Они были, и я надеюсь, что в следующем году этого не повторится.

(осторожно, в этом абзаце вы можете заспойлерить себе некоторые задачи!)
Сначала о контесте: мы заняли 35 место с 5 задачами. Это немного хуже, чем я ожидал (мне казалось, что у нас будет место в районе 25-30). В начале контеста мы сильно растерялись. Я и craus очень долго думали над задачей F — мы сдали ее под занавес первого часа, по пути отсеяв несколько неверных решений и написав то, к которому не получилось придумать контрпример. Затем мы решали задачу D. Не понимая, как ее делать, Hohol распечатал ответы на первые несколько тестов, но ничего не извлек. Потом я вспомнил задачу с тимуса и написал точно такой же перебор — оказалось, что кандидатов на ответ порядка 50 тысяч (конечно, порядочный ACM-щик должен знать, что их мало, но мы такими не являемся), так что работает прекальк. Дальше подоспели решения задач A и H, которые пришлось немного подебажить, так как писать с первого раза мы так и не научились. Затем мы решили задачу C: сабмит в 3:5x был уже правильным, но TL-ным: команда из трех желтых участников не умеет писать maxflow и поэтому копипастит его с Team Reference, где есть лишь алгоритм Диница, да еще и с кучей ArrayList-ов. Заменив все ArrayList-ы на массивы, мы сразу же получили Accepted. Оставалось немногим более получаса, мы решили, что не умеем решать J за это время (задача, надо сказать, очень противная, из тех, что я особенно ненавижу — куча тупейшей бессмысленной реализации), и поэтому попытались решить B, но, как оказалось, надо было решать специфическую системку уравнений за O(1), как когда-то учили на третьем курсе (на самом деле приятная неожиданность — знания, полученные и успешно забытые в универе, оказались нужными в ACM ICPC!).

А теперь о фейлах.

• Мы приехали на поезде в 6 часов утра (примерно в это же время приехали и ИжГТУ). Но в отель нас не заселили, пришлось подождать до 14-00. Разумеется, компания IBM непременно обанкротится, если закажет дополнительные несколько номеров на одни сутки для участников финала чемпионата мира. В то же время craus и I_love_natalia вспоминают, что в 2010 году в Харбине такой фигни не было: тогда их сразу с аэропорта доставили в отель.

• Номера в отеле Англетер по цене OVER 9000 на первый взгляд почти ничем не отличаются от номеров в неплохом санатории, где я отдыхал несколько лет назад, за исключением отсутствия балкона (ну и собственно, самой цены). Но это только на первый взгляд: оказалось, что интернет в Англетере настолько хорош, что видео с Youtube качества выше 240p воспроизводить он не в состоянии. Пламенный привет провайдеру iBAHN.

• Перед открытием состоялось мероприятие IBM TechTrek. Видимо, организаторы считали, что очень комфортно сидеть два часа без перерыва на выставленных в ряд стульчиках. После первого часа количество занятых сидячих мест наполовину опустело — кто гулял, кто вообще вышел на улицу, все пили воду...

• На всех ужинах, проводимых в Манеже, а их было то ли три, то ли четыре — я уже не помню, а заглядывать в расписание лень — был доступен шикарный ассортимент напитков: Coca-Cola, Sprite, Fanta, Nestea и вода. Надо ли говорить, что многие участники вообще не могли пить газированные напитки (к примеру, у меня болело горло, и употребление лимонадов не очень-то способствует состоянию этого самого горла). Поэтому большинство брало себе Nestea, который сразу же после его доставки заканчивался за O(1). Воду пить на такого рода мероприятии тоже не очень круто. Почему нельзя было предоставить банальный чай с горячей водой?

• Во время пробного тура температура в зале была равна 18 градусам. На просьбы сделать потеплее организаторы никак не отреагировали, при том что большая часть участников пришла в одних майках и, я уверен, замерзала. Под конец пробного тура температура поднялась до 22 градусов, что уже приемлемо, но сидеть около 2 часов, ощущая холод вокруг себя, особенно немного приболев, не особенно круто.

• Следующее замечание не является фейлом организаторов — это фейл участников. Почему-то почти все гости из других стран считают, что шведский стол — это именно то мероприятие, где нужно устраивать очередь из ста человек, чтобы взять абсолютно разные блюда. И грустно и смешно.

• Наверное, так принято, но я считаю, что после 5-часового контеста неплохо провести обед. И даже если вы проводите церемонию закрытия, которая заканчивается примерно в 17-30 (а завтрак кончался примерно в 8-00 — разность считайте сами), то после нее надо дать нормально покушать, а не раздавать пакетики с яблоком, пачкой печеньев и минералкой и после этого...

• ... везти в цирк. ЦИРК??? Вы совсем там рехнулись? Какой еще цирк? Пяти сотням взрослых людей интересно смотреть цирковые выступления? Может быть, перед этим хотя бы стоит покушать и отпраздновать победы, не? Лично я половину выступления провел в вестибюле, найдя тот положительный момент, что можно наконец-то позвонить домой и рассказать обо всем, что происходило на финале. Вторую половину выступления я просто гулял по Михайловскому саду. В 19-00 нас таки отвезли в Манеж, где уже были накрыты столы, но на этот раз в холодильниках не было даже Nestea, а когда он появлялся, его мгновенно расхватывали. Это не Celebration Dinner, можно ливать.

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

Наша же команда по причине отыгрывания 5 сезонов завершает свои выступления, оставляя после себя вот этих ребят. Пожелаю им тоже когда-нибудь съездить на финал в качестве участника, может быть, даже в следующем сезоне. И искренне желаю организаторам финала-2014 не повторять ошибок питерцев и провести хорошее мероприятие.

У меня возник вопрос касательно Team Reference Document на финале.

В правилах сказано следующее:

Each contestant may bring a copy of your Team Reference Document.
This document may contain up to 25 pages of reference materials, single-sided, letter or A4 size, with pages numbered in the upper right-hand corner and your university name printed in the upper left-hand corner. Text and illustrations must be readable by a person with correctable eyesight without magnification from a distance of 1/2 meter. It may include hand-written comments and corrections on the fronts of pages only. The document should be in some type of notebook or folder with the name of your institution on the front.

Bring a CD of your Team Reference Document if you are bringing a Team Reference Document.
Label the CD with your university's name. The CD should contain only one file, a PDF of your Team Reference Document, with no active elements.

Соответственно, можно напечатать 25 страниц копипасты и принести ее с собой. Можно записать этот документ на CD, и его скопируют на рабочий компьютер. И вопросы.

• Есть ли PDF-читалка на предоставляемых компьютерах? (да, мы не ставили образ, т.к. Eclipse под виндой точно такой же)

• И что такое with no active elements? Выделяющийся и копирующийся текст — это active element или нет?

Вчера закончилось важнейшее мероприятие в жизни любого ACM-щика из России и стран бывшего СССР, кроме Украины и Молдавии. Сегодня я сижу в торговом центре "Невский" около Московского вокзала и пишу этот пост.

Часть 1: регистрация

30 ноября мы приехали в Санкт-Петербург. Отсидевшись несколько часов на вокзале, попутно иногда согреваясь в кафешках типа "Теремок" (надо сказать, погода была мерзкая, и теплая куртка не особо помогала), мы заселились в хостел (который находился прямо около вокзала), немного отдохнули и поехали в университет.

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

В комнатке для регистрации нас ждали огранизаторы полуфинала, которые отметили, что мы все-таки приехали, сотрудницы Яндекса, которые попросили заполнить их анкетки, сотрудницы Mail.ru, которые дали нам небольшое задание — его надо было отправить по интернету в специальную форму и получить возможность выиграть небольшой приз, и сотрудницы Jetbrains, которые предложили пройти несложный тест по языку Kotlin. Тест мы прошли сразу же. Без маленьких багов не обошлось, но тем не менее они решили дать нам приз. Можно было выбирать из футболки, чайника, кружки и лицензии на один из продуктов Jetbrains. Я подумал, что ворованную IDEA Ultimate IDEA Community Edition я могу и так поставить, поэтому выбрал футболку.

Дальше мы вернулись в гостиницу, решили задания от Mail.ru, немного считерив, воспользовавшись решалкой судоку, решалкой японских кроссвордов и распознавателем QR-кодов, отправили их и дальше весь вечер играли в разнообразные настольные и компьютерные игры.

Часть 2: пробный тур

Наступила зима, а это означало, что пришло 1 декабря и надо ехать на пробный тур. Открытие началось в 11 часов, но из-за неумолимого желания спать, а после пробуждения — еще и покушать, приехали мы примерно в 11-20. Впрочем, это никого не расстроило.

Открытие проходило как всегда: речи замечательных людей здешнего полуфинала переплетались с выступлениями танцевальных коллективов. Не могу не покритиковать ведущих, которые, видимо, никогда не готовятся к произнесению своих речей: в Саратове craus был назван Сёмушкиным, а здесь обижен был сам MikeMirzayanov, фамилию которого почему-то произнесли как "Мирзаян". Ну да ладно, посмеялись и забыли.

Дальше был пробный тур. В качестве пишущего пробный тур был выбран я: по статистике, когда его пишет Hohol, команда сливает контест, а когда я — наоборот. Задачи я решил сдавать в порядке X-Y-Z, т.к. для задачи X требовался стандартный ввод-вывод, а для остальных задач — файловый.

Привыкать к клавиатуре было некогда, поэтому я делал кучу опечаток, но потерял в сумме немного — секунд 30-40 и все-таки сумел получить суммарный штраф 6. К сожалению, с ИТМО-1 бесполезно конкурировать даже на пробном туре: нельзя просто так взять и выиграть пробный тур. Компьютер работал достаточно быстро, PCMS вроде бы тоже не тупил, так что единственное, чем мы остались недовольны — расположением компьютеров в зале. Например, я мог одним движением руки выключить компьютер Saratov SU 2 и Perm SU 1. Не думаю, что их обрадовала такая перспектива, хоть делать мы этого и не собирались.

На встречу с Яндексом и Mail.ru мы не пошли, предпочтя им очередные партии в сет, шахматы, го, покер, прохождение Hitman на максимальной сложности с максимальным рейтингом, прослушивание музыки и прочие бесполезные занятия.

Завтра контест — надо рано лечь спать! Ага, щас. В Петрозаводске лучшие наши контесты были, когда мы играли в покер до двух-трех часов ночи. По странному совпадению в этот день мы легли спать в час ночи — вставать надо было в 7 часов утра. Вроде как идеальная продолжительность сна. Завтра пройдем в финал и окончательно докажем это. Глазки закрывай, баю-бай.

Часть 3: контест

Осторожно: дальше присутствуют спойлеры по задачам!

Итак, наступило 2 декабря, следовательно, надо опять ехать в универ и играть контест. Ну что ж, нам не привыкать, поехали.

В универ приехали за 40 минут до начала. На контест запускали за 15 минут до начала — пришлось подождать в вестибюле. Жюри не гарантировало, что время на компьютерах будет правильное, поэтому я взял у I_love_natalia наручные часы, перевел их на 10.00 и остановил — включу вместе с началом контеста.

3, 2, 1, начали! Hohol берет первую половину комплекта и читает с начала, craus — вторую и читает с конца, я открываю Visual Studio, создаю проект, пишу шаблон. Примерно через 5-6 минут Hohol просится написать задачу A: говорит, изи, решу за 5 минут. Дописываю шаблон — там пара строчек оставалась и отдаю комп, сам читаю с B и дальше. 10:27 — Accepted. Открываем монитор, смотрим: сдают A и G. craus берет G, думает пару минут — идем писать ее.

А переполнения не будет? Что-то я очкую. Пошли на Java напишем. Открываю Eclipse, создаю проект, в это время craus выводит на бумажке формулы. Класс создан, перебиваем решение. Тесты проходит, с TL тоже нормально. Сабмит, WA на примерно 35 тесте. Ctrl+P, Enter, дебаг. Что за фигня? Все вроде работает. Давай посчитаем побольше коэффициентов. Какого черта ответы разные? Ничего не понимаю. Что еще решают? H решают. Hohol идет решать H. Эй, почему тут (k·k)²ⁱ? Надо или (k·k)ⁱ, или (k)²ⁱ! Исправляю, теперь все тесты проходит, даже злобные вроде "64 2". 46:09. Сабмит, Accepted.

Что по H? Ничего? Хреново. Я пошел над ней думать. Комп простаивает. Что еще решили? Во, E решили. craus читает E. Да там же просто жадность! Hohol садится писать. Я в это время придумываю что-то по H: давайте хранить для каждой буквы префиксные суммы по модулю 2, а потом слева направо пересчитывать. Нужно будет что-то вроде ксор-равно на отрезке и сумма на отрезке. craus — а давай в сете хранить все, что слева. В мапе? В мапе. Ммм, 52 * 300000 * логарифм мапы. Не зайдет же. Да ладно, сервак быстрый, если что, на хешмапу переделаем. Ну окей, готов писать.

Hohol дописал E. Сажусь тестить. Вроде все нормально. Сабмит — WA. Что за чушь? Эй, q_i тоже long long! Исправляем. 94:25. Сабмит, Accepted.

Сажусь писать H. Очень быстро дописываю, сабмит, TL. Что? Генерирую макстест, локально 1.8 секунд. Быстрый сервак, говорите? Сабмичу это на уже сданную задачу E — TL. Ну да, быстрый сервак, так мы вам и поверили. Исправляю map на hash_map. Локально 0.8 секунд. Сабмичу на E — Presentation Error. Ну ладно, вроде так успевает. Убираю генератор теста, сабмичу на H. Accepted. Время 118:05. Смотрим монитор. Наша вторая команда отстает от нас на 7 минут штрафа.

Что еще сдают? B сдают, C сдают. craus: мы тут вроде бы запруфили, что ответ равен , но это за квадрат, придумай, как побыстрее. Окей, придумываю. Значит, при фиксированном a_i у нас неравенство . Похоже на уравнение прямой. Давайте нарисуем в плюскости (i, b_i). Похоже, все точки должны лежать по одну сторону от какой-то прямой. Похоже на какую-то касательную к выпуклой оболочке этих точек. Отдаю craus: иди, придумай что-нибудь, вроде все правильно, остались детали.

В это время пишу проверку по задаче B: что, если собрать статистику, сколько какая вещь встречается? Давайте проэмулируем случай 9 и 10 одинаковых вещей, сильно ли они различимы. Хм, совсем не различимы, нельзя так решать. craus: я все вывел, пойдем писать. Ну пойдем. Пишем, тесты проходит. Тестируем, правильно ли написали выпуклую оболочку — все нормально. 179:05. Сабмит — Accepted.

Hohol придумывает решение задачи B: давайте вначале уберем все предметы из рюкзака, а потом положим туда все предметы, не убирая в процессе. Так мы узнаем все веса. Решаем рюкзак, дальше убираем те вещи, которые не нужны в оптимальном ответе. Немного думаю над J, ничего не получается. Начинаю тестить B. Выявляем штук 5 багов. Исправляем, сабмитим. Время 215:38. Accepted.

Что решать: J? Смотрите, еще F сдают. О, да она наверное проще, давайте ее решать, две все равно не успеем. Следующие 20 минут пишем решение, считающее, что поворачивающиеся и неповорачивающиеся элементы змейки чередуются. Блин, да оно семпл не проходит! Нахрена мы это все писали? В семпле они не чередуются! Ладно, тогда вместо динамики пишем просто перебор, наверняка зайдет. Пишем, до конца контеста 10 минут. Семпл прошел. Сабмитим, PE 5. Что, ответ не выводим? Пофиг на штраф, если что, поменяем время на задачу. Ставим assert на то, что не нашли ответ. RE 5. Все-таки не находим. Почему? Непонятно. Contest is over.

Смотрим на замороженный монитор: мы на 9 месте, если убрать лишние команды. Выходим в вестибюль. Говорят, Саратов чуть ли не не проходит. Спрашиваю у Fefer_Ivan: Saratov SU 1, 2, 3 по 5 задач. Ололо, близится сенсация. А, Saratov SU 2 все-таки обогнали JKeeJ1e30? Ну ладно, ололо становится поменьше. Ребята уходят кушать в Subway, я иду в столовку, встречаю там Izhevsk STU. Сколько кто сдал? Ижевск — 7 задач, СПбАУ — 7 задач. Окей, мы теперь 11-ые. Уфа — 6, по штрафу мы лучше. Кто там еще нас может обогнать? University of Latvia — встречаю их в актовом зале, говорят, у них 5. Petrozavodsk SU с 4 задачами сделали три сабмита — спрашиваю Дениса Власова, говорят, ничего не сдали. Странно, Петрозаводск вроде неплохая команда. Подходит yarrr, ему страшно, он не сдал шестую задачу. Смотрим вместе с ним монитор — а ведь их команду мало кто обгоняет. Кто там еще? Altai STU, Moscow SU of Steel and Alloys имеют 5 задач и два вопросика. Ну ладно, мы в худшем случае 13-ые, вроде проход, в том году было 16 команд, а ведь еще и финал в Петербурге.

Разбор задач. Говорим наше решение задачи C, зал дружно смеется. Ну и пихайте дальше ваш бинпоиск с даблами :D Наше решение на самом деле очень небольшое и быстро пишется, сложность только в придумывании. Скоро награждение.

Монитор начинает размораживаться снизу вверх. Наша вторая команда занимает 42 место и получает диплом третьей степени — к сожалению, задачу C они в заморозку не решили. Никогда еще вторая команда СГАУ не была так высоко. Сразу перед ними — две команды Belarusian SUIR, одна из которых — действующий бронзовый призер финала. Сенсации только начинаются.

Дальше команды с 5 задачами. Среди них Moscow IPT The Sun, как мне казалось, самая сильная команда МФТИ (простите, если кому-то казалось не так), команда Новосибирска, почти весь Саратов. Altai STU — оба вопросика превращаются в минусы, тоже 5 задач. Теперь мы точно 11-ые, если удалить лишние команды. Выходим на сцену, получаем благословление от руки Petr.

IITU сдали 8. Молодцы, хорошо сыграли, я рад за эту команду. А по рейтингу на Codeforces такого и не предположишь! SPbSU 4 таки сдают свои 4 задачи в заморозку. Belarusian SU сдают последнюю свою задачу на 299:36 и выходят на второе место! Moscow SU ST сдают последнюю задачу на 299:57 и выходят на второе место! ITMO 1 не сдает задачу K, the hardest problem ever given on NEERC. Контест удался.

Объявляют команды, прошедшие на финал. Мы 11-ые, Ufa SATU 12-ые. Так, команды с 5 задачами все-таки проходят. Алтай, Каунас, МАИ. 16 место достается Saratov SU 2 — предполагаемый гнев MikeMirzayanov должен несколько спасть. 17, 18! 18-ое, как позже выяснилось, предпоследнее место достается Perm SU, которые, по их словам, даже и не надеялись. Скоро становится доступна информация, что квота на самом деле 19, и последними на подножку уходящего финала запрыгнули Novosibirsk SU. Результаты доступны на сайте NEERC, а также у Снарка, где красным цветом выделены прошедшие команды.

Заключение

Мне очень понравился контест. Задачи классные, намного лучше, чем в 2010 и 2011 годах. Почти не требуется знаний каких-то жестких алгоритмов и структур данных, зато подумать надо, и много, этим славится NEERC, и мне кажется, что это хорошо. А решать меньше 7 для команд, которые ставят цель выйти на финал, на этом контесте, вроде бы, позор. Меньше 6 — совсем позор. Квота 12 команд, по мнению некоторых, была бы очень кстати. Но не мне это решать, меня и так все устраивает :)

ACM-карьера продляется до 3 июля. Увидимся на ACM ICPC World Finals 2013!

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

Задание: кооперативный мат в 2 хода. Кому лень читать статью по ссылке — черные начинают первыми, каждая сторона делает по два разрешенных правилами хода, и вторым своим ходом белые объявляют мат. При этом стороны действуют сообща, т.е. черные хотят, чтобы им как можно быстрее поставили мат, и белые это знают.

Вчера я стал почти уверен в том, что быстрейший способ решить эту задачу — написать программу для ее решения. Наверняка тут есть люди, не понаслышке знакомые с шахматами — сможете опровергнуть мое утверждение? :)

Прячьте свои ответы под спойлеры — пишите комментарий и сразу же редактируйте его, чтобы ответ остался в предыдущей правке. Или просто напишите программу и проверьте себя самостоятельно!

Всем привет!

Только что закончился четвертьфинал Южного подрегиона NEERC, и я хотел бы немного рассказать, что происходило сегодня и вообще на этой неделе в Саратове.

Часть 1: читайте инпут, посоны!

Hohol, как обычно, решил выиграть пробный тур. Как это делать, Hohol прекрасно помнил, ведь на его счету два выигранных пробных тура в 2011 году :) На сей раз, как выяснилось на открытии, жюри четвертьфинала решило добавить интерактивную задачу, поэтому на пробном туре нас тоже ждали интерактивные задачи.

Порешили на том, что Hohol садится за клавиатуру и пишет две стандартные задачи саратовского пробного тура, я слежу, как он это делает, а craus решает интерактивку. Посабмитив две первые задачи примерно на 2:10 и 3:30, мы обнаружили, что первая из них получила WA 1 (забыли считать инпут), а вторая — TLE 11 (инпут был слишком большой для cin). Так что мы забили на идею победить в пробном туре, открыли студию и начали спокойно писать две интерактивные задачи.

Сдав эти интерактивные задачи, мы с удивлением и смехом обнаружили себя на первом месте (одна из интерактивок была довольно неплохой сложности и многим не поддавалась). На следующий день нас ждало Code Game Challenge.

Часть 2: не оставляйте known issues, посоны!

Code Game Challenge заключался в следующем: дано игровое поле с двумя большими препятствиями в центре и четыре танка машинки, управляемые программами участников. Машинки должны были ездить по полю, собирать флаги (которые давали очки) и лечиться на своей ремонтной станции. Особенностью этого Code Game Challenge было то, что машинки погибали навсегда — поэтому осторожное объезжание препятствий, стен, других игроков было важной частью стратегии. Еще можно было стрелять друг в друга шинами, правда, кажется, это было не очень эффективно — шины просто отталкивали соперников, но не наносили им урона непосредственно.

Code Game Challenge полностью писал я по указаниям craus, который вечером раздумывал над особенностью стратегии. В итоге наша машинка на тестах против случайных машинок была примерно в серединке. К тому же у нас был баг, проявлявшийся примерно в 1 случае из 15. Я не буду раскрывать всех подробностей Code Game Challenge. Вы можете посмотреть видео, понаблюдать за нашим багом своими глазами и вообще насладиться великолепной атмосферой этого шоу.

Часть 3: не сабмитьте ML 1, посоны!

Контест довольно неплохой, так что советую всем его порешать (на acm.sgu.ru, задачи 542-553 или на Codeforces-тренировках). А если при решении возникнут трудности, специально для вас есть разбор задач с места событий.

Вероятно, вы уже видели финальную таблицу и наше отставание на 5 минут от третьего места. Сейчас я расскажу, как так получилось.

В один из предыдущих дней I_love_natalia толкнул в жюри байку о том, что в мишку встроен голосовой передатчик, а обратная связь прикручена к ноге Hohol. Вроде бы они там сильно посмеялись, но, оказывается, волонтеры поглядывали, чтобы мы не говорили с медведем :D

В начале контеста мы довольно серьезно тормозили. craus прочитал задачу E и мы начали ее писать. Мы ее написали и обнаружили, что задача была решена неправильно: craus пошел думать дальше, а Hohol сел за задачу L.

Задачу L Hohol писал по ощущениям минут 15, один раз полностью переписывая решение заново. После этого я сел писать задачу J, а Hohol за мной наблюдал. Ее мы написали довольно быстро. Посмотрев на монитор, мы увидели один AC по задаче E от нашей второй команды (Slamur, Sinner, Jeg) и несколько AC по задаче F. Читаю задачу F — да это же халява! Пишем сдаем, AC.

После этого craus придумал (видимо, не очень оптимальное — можно было сэкономить на этой задаче минут 20-30) решение по задаче E, требующее дерево отрезков — я пошел ее писать, распечатал, Hohol нашел в ней пару багов, а в это время мы дописали остальное решение. Получив AC, мы посмотрели на монитор — мы были на 4 месте, а на 3 месте расположилась наша вторая команда, очень быстро сдавшая четыре задачи. На первых двух местах были команды из Саратова.

Следующей нашей задачей стала задача G. Hohol и craus придумали основную идею, а я пошел писать. Написав эту задачу (правда, потеряв, по ощущениям, минут 10), мы решили ее посабмитить. Вердикт: Memory limit exceeded on test 1. Ой!

Итак, всем советую:

1. проверять, сколько ваша программа жрет памяти с помощью Task Manager (Ctrl+Shift+Esc) или опции запуска на сервере.

2. или хотя бы правильно считать размеры массивов на калькуляторе, считая, что тип int занимает 4 байта, а не 1.

Через три минуты мы получили AC, но штрафная попытка, к сожалению, уже была получена.

Затем я и craus пошли думать над задачей B, которую к тому времени сдала команда Saratov SU 1, а вскоре Hohol придумал решение задачи H, которую я перед этим неправильно прочитал и посчитал гробом. Hohol сел за комп и вскоре сдал нашу шестую задачу H. Открыв монитор, мы с грустью увидели отставание в 5 минут от третьего места, на котором расположилась команда Saratov SU 4.

В оставшиеся полтора часа мы пытались написать задачу C (по которой у Saratov SU 2 к этому времени было несколько штрафных попыток) и додумать задачу B (потом оказалось, что мы были на правильном пути и немного недопридумали).

Наша вторая команда в это время пыталась сдать задачу G. Оказалось, что они примерно в течение двух часов слали очевидно TL-ящееся решение. Сразу после заморозки Sinner придумал-таки нормальное решение и они сдали пятую задачу. Потом они написали задачу H, получили по ней WA 16, но ошибки до конца контеста так и не нашли. На NEERC, впрочем, наша вторая команда попала, причем за счет быстрых четырех первых задач у них было даже не последнее место среди тех, кто сдал пять задач.

Итак, сегодня у нас было чуть менее, чем 100500 возможностей занять 3 место, но что-то не сложилось :(

Заключение

Собственно, две команды Samara SAU едут на NEERC, где мы со многими из вас встретимся. Пожелаем нам удачи, ибо это последний сезон и последний шанс попасть на финал. Ждем 2 декабря и спасибо за внимание.

P.S. Вроде бы монитор на сайте соревнования не открывается уже открывается: http://contest.sgu.ru/monitor/?id=1
На NEERC прошли команды вплоть до 19 места, из них из Саратова — только три первых говорят, что четыре, так как проведение контеста дает +1 к квоте.

P.P.S. Видео Code Game Challenge выложено на Youtube. Разбор задач выложен на Youtube.