Hello everyone,

At March 11 there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, March 18, at 11:00 MSK.

Third time in a row it is a personal contest. So we ask everyone to participate solo. The contest is the most interesting for blue and violet coders.

And as usual,

Qualification Round has ended, but no blog on Codeforces yet. What happened to my Codeforces?

Main page: https://hashcode.withgoogle.com/

Judge system: https://hashcodejudge.withgoogle.com/

Our points: 10 / 176877 / 15824126 / 11808094 / 21465945, total score 49275052, 55th place.

How did you solve all the subtasks? I'm most interested in C and D.

Some weeks ago I read a Quora answer by I_love_Tanya_Romanova (link). The 4th paragraph attracted me, here is it's short content:

There are jokes about these typical problem statements: “Little Rohit got an array as a birthday present”. I’m also not getting why these trashy statements should be writtten instead of formal model of the task. It is awesome to have fictional statement when it makes sense, or when it comes from real life; it is at least funny to have stuff like problems I mentioned above. And I know that some of the platforms I mentioned are requiring problems with fictional statements and say that formal models are bad. Well, OK, “Parents asked little Chandan to perform following operations…”. May I go to some other site and solve normal problems, please? That’s a matter of taste — but for me this kind of statements is something that makes strong negative impression, and I think I’m not the only one.

I also don't like statements where characters were added just because there were no characters originally. You read such statement and think: "Why do they added this Alice with her birthday present? It has nothing to do with the problem".

I think there must be some rules that authors should use when they write a problem statement:

1. If the problem comes from real life or from some situation that may appear in real life / fiction book / computer game — use the original statement. Those who will solve this problem will be clearly understand what's going on.
2. If the problem originally had the formal statement (e.g. you have an array and you have to answer some queries, you have an array and you have to find a subarray with maximal xor / and / or, and so on): use formal statement.
3. Never introduce a setting if the problem originally had formal statement.

I've just met a comment with a link to a problem statement. There was such text in the statement:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help her find all possible reconstructions of Anatoly’s code.

Don't you see something weird here? I think it should be:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help him find all possible reconstructions of Anatoly’s code.

or:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help them find all possible reconstructions of Anatoly’s code.

I know that people either use the gender that is more common for a person, e.g. he for drivers and she for nurses, or just use they (my English teacher said they is correct). I've wandered across Wikipedia (here is one of the links: https://en.wikipedia.org/wiki/English_personal_pronouns#Use_of_he.2C_she_and_it), but haven't found anything about preferrable usage of female pronouns.

However, I've read really a lot of English statements, and everywhere the female pronouns are used! For children and professors, for drivers and miners, for rabbits and foxes, for everything and everyone. Why?

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:

• 2012, V Samara Regional Intercollegiate Programming Contest
• 2012, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2014, VII Samara Regional Intercollegiate Programming Contest
• 2014, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2015, 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, Samara SAU ACM ICPC Quarterfinal Qualification Contest

The list of our previous contests:

• 2012, V Samara Regional Intercollegiate Programming Contest
• 2012, Samara SAU ACM ICPC Quarterfinal Qualification Contest
• 2013, VI Samara Regional Intercollegiate Programming Contest
• 2013, 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 не повторять ошибок питерцев и провести хорошее мероприятие.