dalex's blog

By dalex, 10 days ago, In Russian,

Всем привет.

Можете ли вы представить, что монитор (тот, который положение участников контеста, а не который надо разбивать после этого контеста) может быть вреден? На самом деле такое встречается нечасто, но в этом посте мы разберем два таких примера, а также попробуем предложить возможное решение этой проблемы. По идее, для MikeMirzayanov не должно быть проблемой реализовать эту фичу.

Итак, первый пример, 2015 год, четвертьфинал Южного региона в Саратове. Пруфы тут будут такие себе, так как контест куда-то исчез с CF. Вот тут этот контест был, когда я его писал: https://codeforces.com/contest/589 (можете глянуть 14-ую страницу моих посылок, там еще задачи были пошаффлены), вот анонс: https://codeforces.com/blog/entry/20989, а сейчас ссылки на задачи ведут в тренировку с id 102042, закрытую от всех. Непорядок! Тем не менее, постараюсь рассказать, что там было.

Официальные стендинги: http://neerc.ifmo.ru/archive/2015/southern/standings.html Мы видим на первом месте с 11 задачами команду Нижнего Новгорода, на голову сильнее остальных (так оно и было на самом деле). Но давайте себя поставим на место одной из команд, решивших 7 задач. Вопрос: на часах 3:00, два часа до конца. Какую задачу решать восьмой по счету?

Мы видим, что все команды, пытавшиеся сдать 8-ую задачу, пробовали сдать задачу I. Именно задачу I сдала восьмой по счету команда Нижнего Новгорода. Между тем, когда этот контест проводился на Codeforces через пару дней после четвертьфинала, почти все команды из фиолетовых-желтых участников решили 8+ задач, а восьмой они сдали задачу, которая в официальном мониторе обозначена как G. Кроме того, команды, решившие 9 задач, примерно поровну сдавали I и K из официального монитора (к примеру, мы тогда сдали 9 задач, и девятой сдали именно K). Пруфов, как я уже написал, не будет, так как контест куда-то удалили.

Ошибка всех команд с онсайта состояла в том, что они пытались следовать за командой, в составе которой были vepifanov и KAN. Для этих ребят сложность 8-10 задач была примерно одинаковая: примерно very easy. Но для более слабых участников это вовсе не так! Им не стоило копировать порядок задач, стоило подумать своей головой, а не смотреть в монитор. И тогда бы они обнаружили и то, что G халява, и то, что K не очень то уж и сложнее I.

В случае с четвертьфиналом Южного региона 2015 правда о сложности задач хотя бы вскрылась на зеркале, но вот второй пример меня полностью поразил. Это случилось совсем недавно, когда мы выложили контест, проводившийся в этом году в Самаре: https://codeforces.com/gym/102215, анонс: https://codeforces.com/blog/entry/67178 Результаты как онсайта, как зеркала, так и того, что в нем происходило потом, в виртуальных участиях, абсолютно неадекватны. Не в том плане, что слабые обгоняют сильных, а в плане порядка решения задач. Постараюсь не особо спойлерить.

В принципе, что на онсайте, что в зеркале происходило одного и то же. Итак, начинается контест, и желтые участники начинают решать задачи по порядку. Читают первую — сдают за 10-15 минут. Читают вторую — она еще легче, сдают за 5-10 минут. Читают третью — тоже легкая, тоже сдают. Читают четвертую — ну тут конечно кода побольше, но тоже легкая, сдают уже за 20 минут. И так далее.

А между тем зеленые видят монитор и недоумевают, а чего это контест какой сложный. Почему вторая по сложности задача какая сложная, на нее полчаса нужно! А на третью еще полчаса, а на четвертую целый час! Ответ прост: не нужно следовать за теми, кто намного сильнее тебя. Для желтых почти все задачи в этом контесте легкие, желтые решают их буквально с прочтения. Как минимум три задачи, сложность которых я оцениваю как very easy, остаются почти неоткрытыми до третьего/четвертого часа, где их обнаруживают желтые после того, как они решили намного более сложные задачи. А на онсайте одну из этих very easy задач вообще first-accept-нул участник, решивший ТОЛЬКО эту задачу.

Я думаю, если написать этот контест, сначала прочитав все задачи, а потом вообще не смотря в монитор, результат будет лучше, чем если бы вы использовали монитор по назначению. И точно не будет (цитата) туплю, чтобы мне на четвёртом часу таблица предложила [решить задачу уровня Div2B]. Если вы слабо-желтый и ниже, можете попробовать, а потом взглянуть на таблицу и, мягко говоря, удивиться.

Ну а теперь feature request. Нужно добавить два параметра в монитор — верхнюю и нижнюю границу рейтинга участников, показываемых в мониторе и внизу монитора (там, где говорят, сколько человек какую задачу решило). В принципе, можно только верхнюю. Например, я бы поставил себе верхнюю границу 2300 или 2400 и мне бы это отлично подошло — мне неважно, сколько там решил условный турист, это для меня не показатель. Турист может решить за 5 минут то, что я не решу за 5 часов. Намного более важно, какие задачи решают люди, равные и чуть более сильные по скиллу (ну а более слабые точно не помешают). Сделаем результаты более адекватными!

Read more »

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

By dalex, 2 months ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +170
  • Vote: I do not like it

By dalex, history, 4 months ago, In English,

Hi,

I was allowed to upload two contests from Petrozavodsk camps, Yandex Cups 2018 and 2019, into Codeforces Gyms:

These contests are mostly authored by Zlobober and ifsmirnov, with the help of some other people. Yandex Cup 2018 has more easier problems and less hard problems.

The 2018 one is also known as Grand Prix of Khamovniki (discussion on CF), the 2019 one was never published before.

Enjoy!

Read more »

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

By dalex, history, 4 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By dalex, 9 months ago, In English,

Hello!
I want to solve different contests to learn a new language (Kotlin), but I have a busy shedule (and cannot write regular contests in suitable time), so the only way for me is to train using virtual contests.
There is a great variety of contests on Codeforces (thanks to Mike!) and consequently it is not easy to decide which contests to solve.
I love random, but I have a better idea. Let's make the list of not anime-themed contests! But I need your help (in comments) to find them all...

Read more »

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

By dalex, 16 months ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

By dalex, 17 months ago, In English,

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.

Read more »

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

By dalex, 20 months ago, translation, In English,

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.

Read more »

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

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

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?

Read more »

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

By dalex, 2 years ago, translation, In English,

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,

Read more »

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

By dalex, 2 years ago, In Russian,

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

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

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

Read more »

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

By dalex, 2 years ago, In Russian,

Всем привет.

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

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

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

Read more »

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

By dalex, 3 years ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +147
  • Vote: I do not like it

By dalex, 3 years ago, translation, In English,

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,

Read more »

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

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

Всем привет.

Мне сегодня скинули вот такую ссылку: 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.

Read more »

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

By dalex, 4 years ago, In Russian,

Всем нравятся тренировки без мониторов? А даже если и с мониторами, то с кривыми логами сабмитов, автоматически сгенерированными 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: На момент написания я ничего другого не умел. Переписывать заново лень.

Read more »

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

By dalex, 4 years ago, translation, In English,

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:

Read more »

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

By dalex, history, 4 years ago, In English,

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:

Read more »

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

By dalex, 4 years ago, translation, In English,

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.

Read more »

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

By dalex, 4 years ago, translation, In English,

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.

Read more »

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

By dalex, 5 years ago, translation, In English,

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.

Read more »

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

By dalex, 5 years ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +104
  • Vote: I do not like it

By dalex, 5 years ago, In Russian,

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

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

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

Read more »

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

By dalex, 6 years ago, translation, In English,

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: dpmask 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 dp2m - 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 m2·2m passed — we should have been set TL to 1 second or even to 0.75 seconds). So if you solved it in m2·2m, you may assume that you're just lucky and your correct verdict is Time Limit Exceeded.

Why it can be solved in m·2m? 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{li} ≤ L, R ≤ min{ri}, and L ≤ vi ≤ 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 li ≤ L ≤ vi and vi ≤ R ≤ ri. 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 vi remain only one building that has speed equal to vi and minimal ci. Also throw away all buildings whose speed is less than the speed of the fastest building which has ci = 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 vi, and each of these line segments is active on a certain segment [xli, xri] of the axis x.

For example, at the beginning the graph is just the line y = v1x, where v1 is the speed of building that can be bought for 0 units of money. Let the next building's price is c2. Find the minimal point x02 where value of our function is greater or equal to y = f(x02) ≥ c2 and buy this building at the moment x02. Then we should make the line y = y02 + v2x where y02 = f(x02) - c2 is the amount of money remaining after the purchase. Now we have two lines. Till some moment the first line is better (not till x02, maybe later), but as v2 > v1 there exists a moment of time (it's ceil(x12) where x12 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.

Read more »

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

By dalex, 6 years ago, translation, In English,

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.

Read more »

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