Gerald's blog

By Gerald, 4 years ago, In English,

Hey, folks!

I am not a fan of sport-programming t-shirts, but surely know that some of you would like to have one. If you wanna get a t-shirt, just add yourself in Google Form. After a couple of days I will pick a person randomly from the list, and contact him/her for contacts.

Also, I didn't decide how to calculate a random seed fair enough. So, feel free to propose something :)

Cheers!

Edit 1: Guys, please, don't mess around with the doc. Now you cannot edit the doc, please, add a comment with your handle.

Edit 2: Ok, you forced me to delete Google Doc, and spend more time, thanks :) Please, add you handle again in Google Form. Pay attention, you can only add your handle once. Make sure you wrote it correctly. Also to prevent cheating, I will chose among people who participated in at least 2 competitions.

Edit 3: Seems that everybody who wanted to participate in this put nickname in form. So, we can start the lottery.

I was super lazy, so I decided not to do anything complicated. I wrote python script:

#!/usr/bin/python                                                                                                                                                              
import random

filename = "input.txt"
times = 20

with open(filename) as f:
  lines = f.readlines()
  random.seed(314159265)
  for i in xrange(times):
    index = random.randint(0, len(lines) - 1)
    name = lines[index]
    print index, name[:len(name)-1]

Firstly, I picked 20 nicknames:

  • 202 TooSchoolForCool
  • 179 Hdz_78
  • 202 TooSchoolForCool
  • 259 LouisCK
  • 18 serghov
  • 324 krismaz
  • 290 dutzul
  • 188 Swift
  • 86 Elk-cloner
  • 233 TahaMahmoud
  • 251 bnick
  • 179 Hdz_78
  • 168 muratt
  • 107 heaton
  • 6 zeulb
  • 53 Prestige
  • 157 bayram
  • 242 Mohammad_Mohsin_COU
  • 120 sampriti
  • 199 gridnevvvit

Interesting that Mohammad_Mohsin_COU wrote his nickname in a wrong way, but I fixed it :)

Then I ran the same program with another filename and times=1. And the winner is: muratt. Congratulations to him!

Read more »

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

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

Good evening!

The final contest of Coder-Strike 2014 will be started tomorrow at 16:00 MSK. The problems (as in previous Coder-Strike 2014 rounds) are prepared by: Gerald, HolkinPV, Igor_Kudryashov.

And we have good news for you. There are two rated online rounds related to the contest: one round for the first division participants and the other for the second division participants. Of course, we've added simple problems in the second division contest (and also deleted hard problems).

The registration for the contest will start at 4:00 MSK, as usual registration ends 5 minutes before the contest start. The first division participants should register on "Coder-Strike 2014 — Finals (online edition, Div. 1)", the second division participants should register on "Coder-Strike 2014 — Finals (online edition, Div. 2)".

Hope the problems will be nice for you, we are really tried our best to prepare them.

Good luck!

UPD. Due to the holding the onsite competition of Coder-Strike 2014, we have to restrict access to the site after the contest. Approximately, the site will be unavailable for 15-30 minutes after the end of the contest.

The editorial is now available.

Read more »

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

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

Good day!

Coder-Strike 2014: Round 2 will start tomorrow at Russian morning. If you want to participate, please register for the contest on the page.

In much the same way as the first round, all users can take part in the competition. But this round will be usual rated round only for the second division participants. The first division participants can take part too, but for them the round will be unrated. Please, do not get upset, the next Coder-Strike round (finals) will be rated round for the first division participants.

If you have any additional questions, please, ask at comments.

Good luck, and see you on the contest!

UPD 1. Sorry for delay, the score distribution is standard.

UPD 2. The contest is over, congratulations to the winners, hope you like the problems!

Read more »

Announcement of Coder-Strike 2014 - Round 2
Announcement of Coder-Strike 2014 - Round 2
 
 
 
 
  • Vote: I like it
  • +81
  • Vote: I do not like it

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

Good Day!

Coder-Strike 2014: Round 1 will start very soon. If you want to participate, please register for the contest on page. The round was prepared by me, HolkinPV and Igor_Kudryashov. And we tried our best to make it really awesome.

The round will be usual rated round for the second division participants. The first division participants can take part too, but for them the round will be unrated.

If you have any additional questions, please, ask at comments.

Hope you enjoy the problems! Good luck!

UPD 1. Score distribution will be standard: 500-1000-1500-2000-2500.

UPD 2. The competition was delayed by 10 minutes. :]

UPD 3. Because of unusual room assignment Div.1 and Div.2 participants will be in the same rooms this round.

UPD 4. The contest has ended, hope you like the problems. Rating for Div.2 participants will be updated a bit later.

Read more »

Announcement of Coder-Strike 2014 - Round 1
Announcement of Coder-Strike 2014 - Round 1
 
 
 
 
  • Vote: I like it
  • +61
  • Vote: I do not like it

By Gerald, 6 years ago, In Russian,

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

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

Еще одна новость состоит в том, что, так как количество школьников, проявивших интерес к соревнованию, оказалось меньше ожидаемого, сетка соревнования была пересмотрена. В раунд 2 пройдут лучшие 50 официальных участников раунда 1. Квота на финал не изменилась: 25 лучших официальных участников раунда 2 пройдут на финал. Кроме того, каждый официальный участник раунда 1, решивший хотя бы одну задачу в нем, получит памятную футболку чемпионата Coder-Strike 2014.

Все те, кто не являются школьниками из Москвы или Московской области, и те, кто не прошел квалификацию, могут поучаствовать в раунде 1 неофициально. Раунд будет рейтинговым для всех неофициальных участников раунда 1 из Div. 2, а также для всех официальных участников раунда 1. Рейтинг будет считаться отдельно для официальных участников и неофициальных участников. Неофициальные участники из Div. 1 также могут насладиться задачами раунда :], для них раунд будет нерейтинговым.

Удачи на предстоящем раунде!

Read more »

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

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

411A - Password Check

In the first problem you should correctly implement what was written in statement. It could be done like this:

string s;
cin >> s;
bool upper = false, lower = false, digit = false;
for(int i= 0; i < s.size(); ++i){
    if(isupper(s[i]))
        upper = true;
    if(islower(s[i]))
        lower = true;
    if(isdigit(s[i]))
        digit = true;
}
puts((upper && lower && digit && s.size() >= 5) ? "Correct" : "Too weak");

411B - Multi-core Processor

In this problem you should read the statement carefully, consider some principal cases and implement them in your program. The author's solution is:

  1. We will store array$blockedCell[]$ (value in cell i equals 1 if this cell is blocked, 0 otherwise), blockedCore[]$ (value in cell i equals 0, if this core is not blocked and the number cycle when this core is blocked otherwise).
  2. Consider all cycles from the first to the last. Consider the cycle number k.
  3. Consider all processors and calc what cells will blocked on the cycle k. Set values one to corresponding cells of array blockedCell[]
  4. Then for each core i if conditions blockedCore[i] = 0 and blockedCell[x[i][k]] = 1 meet then core i is blocked on cycle k. Set blockedCore[i] = k.

411C - Kicker

To solve this problem you should use logic (mathematic logic) :] Logic says:

  1. If for some arrangement of the first team there is no arrangement to have even a draw then the first team is guaranteed to win.
  2. If for any arrangement of the first team there is some arrangement for the second team when the second team wins then the second team is guaranteed to win.
  3. Otherwise nobody is guaranteed to win. The answer is Draw.

This logic should be implemented in your program. I could be done considering each arrangement of every team.

Read more »

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

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

Good day!

Codeforces will hold competition Coder-Strike 2014 for Moscow school children. Qualification Round of the competition will start soon. The round will be unrated for all participants.

As usually, anyone can enjoy the problems! If you aren't a Moscow school child you can take part in the round unofficially.

Hope you will enjoy our problems, good luck!

Read more »

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

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

Testing Round #7 will start tomorrow on 28th of June 2013 at 00:00. Our goal is to test the platform after recent improvements. Recently, there have been many improvements / innovations. In particular, a large part of Codeforces was moved to another server.

I invite you to take part. It will be Div.2 + unofficials from Div.1. It will contain three obsolescent problems. But I think it will be interesting for many of you. I ask not to compete those who have been on a winter school in Kharkov this year — perhaps, you can know the problems. The problems contain very weak pretests to force more hacks. Of course, the round will not affect the rating.

Thanks to all who take part!

Upd. Round has finished successfully, great thanks to all participants!

Read more »

Announcement of Testing Round #7
Announcement of Testing Round #7
 
 
 
 
  • Vote: I like it
  • +57
  • Vote: I do not like it

By Gerald, 7 years ago, translation, In English,

Good Day!

The next Codeforces round will start soon. It will be held by usual Codeforces round rules.

The author of today's round is Mykhailo Granik (Fcdkbear), he is listening the lecture at the Winter Kharkiv Programming School now. Great thank him for this contest!

The score distribution will be standart: 500-1000-1500-2000-2500.

Good luck to all!

Read more »

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

By Gerald, 7 years ago, translation, In English,

Good day!

For technical reasons, we've decided to move the start time of the online version of the round. Online version will be held as separate competition CROC-MBTU 2012, Final Round (Online version, Div. 2). Please register for this competition.

This round will be usual rating round for the Div. 2 participants.

UPD. The online version of the round will come soon. Let me remind you that this contest will hold by usual Codeforces rules. The score distribution is 500-1000-1500-1500-2000.

Enjoy contest!

Read more »

Announcement of CROC-MBTU 2012, Final Round
Announcement of CROC-MBTU 2012, Final Round
 
 
 
 
  • Vote: I like it
  • +59
  • Vote: I do not like it

By Gerald, 7 years ago, In Russian,

245A - Системный администратор

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

    int[] accepted = new int[2];
    int[] lost = new int[2];
    for (int i = 0; i < n; i++) {
        int z = nextInt() - 1;
        accepted[z] += nextInt();
        lost[z] += nextInt();
    }

    for (int i = 0; i < lost.length; i++) {
        if (accepted[i] >= lost[i]) {
            out.println("LIVE");
        } else {
            out.println("DEAD");
        }
    }     

245B - Интернет-адрес

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

    String s = nextToken();
    if (s.startsWith("http")) {
        out.print("http://");
        s = s.substring(4);
    } else {
        out.print("ftp://");
        s = s.substring(3);
    }

    out.print(s.substring(0, s.lastIndexOf("ru")));
    out.print(".ru");
    s = s.substring(s.lastIndexOf("ru") + 2);
    if (s.length() != 0) {
        out.print("/");
        out.println(s);
    }

245C - Игра с монетами

У этой задачи было несколько решений, видимо, самое простое для осознание использует идею динамического программирования. Динамическое программирование dp[i][up], сколько нужно ходов, чтобы опустошить сундук номер i и все зависящие от него сундуки, при условии, что в нем сейчас находится max(0, ai - up) монет.

Чтобы посчитать dp[i][up] переберем сколько раз мы возьмем монету из этого сундука. Пусть мы возьмем из него p, тогда должно выполняться max(0, ai - up - p) = 0. Перебрав p переходим к подзадачам dp[2·i][p], dp[2·i + 1][p].

После подсчета всех состояний, ответ на задачу будет содержаться в dp[1][0].

Сколько операций выполнит подсчет такого динамического программирования. Очевидно, что p не имеет смысла брать более 1000. Тогда всего состояний в таком dp будет n·1000. Умножить на количество переходов, получается 100·1000·1000 = 108, операций в худшем случае.

245D - Восстановление таблицы

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

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j){
            cin >> b[i][j];
            if(i == j)
                continue;

            a[i] |= b[i][j];
        }

245E - Происшествие в клубе

В задаче нужно было применить жадные соображения следующего характера. Если есть человек, который вышел и которого видел Поликарп, то если кто-то заходит в клуб, можно считать, что заходит этот человек. Аналогочно для выходящих. Лаконичный код решения:

    int in = 0, out = 0;
    for(int i = 0; i < n; ++i){
        if(s[i] == '+'){
            in++;
            out = max(out - 1, 0);
        }
        if(s[i] == '-'){
            out++;
            in = max(in - 1, 0);
        }
    }
    cout << in + out << endl;

245F - Анализ потока логов

В этой задаче нужно было аккуратно распарзить входные данные. Перевести все даты в секунды. А затем, одним проходом по отсортированному массиву чисел, сделать ровно то, что написано в условии. Важно заметить, что размер входных данных был достаточно большим, поэтому читать эти данные нужно было достаточно быстро.

245G - Возможные друзья

В этой задаче планировалось решение за O(m2) с маленькой константой. Для начала предложим, что заданный во входных данных граф отношений связный, тогда количество вершин в нем n ≤ m + 1. Будем хранить такой граф в виде матрицы смежности a и ввиде списка смежных вершин для всех вершин. Теперь переберем вершину, которая будет общим другом предполагамых друзей. Далее переберем пару вершин, из списка смежных ей вершин, проверим, что они не соединены ребром, и сделаем инкремент в некоторую другую матрицу в ячейку b[u][v]. Эта матрица будет хранить количество, общих друзей между u, v, если u и v не соединены ребром.

После того, как мы построили матрицу b можно легко посчитать возможных друзей.

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

245H - Запросы на количество палиндромов

Решение задачи динамическое программирование. dp[i][j] — количество палиндромов в подстроке s[i...j], isp[i][j] — является ли палиндромом подстрока s[i...j]. Переходы dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + isp[i][j], isp[i][j] = 1, если isp[i + 1][j - 1] = 1, и s[i] = s[j]. Иначе isp[i][j] = 0.

Read more »

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

By Gerald, 7 years ago, translation, In English,

Good day!

Elimination round of the CROC Collegiate Programming Competition for the MSTU Bauman students is going to be here soon. The official championship participants will take part in the competition, all others will be out of the competition in the table of results.

The contest is held by the well-known rules ACM-ICPC. Competition duration is 2:00 hours. Supported programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, and D.

This Round will be the rated for the Div-2 participants, regardless of whether one is the competition championship party or not. For Div-1 participants this round is unrated.

Please note that the official participants of the competition are not need to register for this competition they will be registered automatically (with advance registration at website).

Good luck to everyone!

UPD. Competition is completed, thank you very much for your participation! I hope that the problems with the queue is not much to spoil your impression of the contest. The results of elimination round for official participants will be announced tomorrow. Rating will be update soon.

Read more »

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

By Gerald, 7 years ago, translation, In English,

Good day, Codeforces!

Please note that there have been significant changes in the schedule of competition! Competition Codeforces Round #148 rescheduled for Sunday, also added new competition Bayan 2012/13 Elimination Round.

The latter is an elimination for the BAYAN 2012/13, as it is sure to be a rated round for participants from Div1. The issue of rating for participants from Div2 currently being addressed. Do not pass by, registration starts now!

Please note that the competition Bayan 2012/13 Elimination Round will held by the ACM ICPC rules, and the statements of this competition will be available in English only.

Gain your strength before the upcoming competition! Good luck to all!

Read more »

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

By Gerald, 7 years ago, translation, In English,

Good day, Codeforces!

I can't wait to give you a good news that a new competition for div1 participants is appeared in the list of events. This competition is a broadcast of the Saratov Team Olympiad on Programming and therefore will be held by the ACM-ICPC rules. Especially for div1 participants, we complicate this school competition a bit, so that everyone was interested to solve the problems.

This Competition is individual, it will be rated for both divisions.

Please note that the start time of the competition is different from the usual. Also note the unusual length of the competition.

See you at Codeforces Round #145! I hope that everyone will find the time to participate in the competition.

UPD. The competition finished, the editorial will come soon.

Read more »

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

By Gerald, 7 years ago, In Russian,

Итак, начнём разбор.

219A - k-Строка

Давайте для каждой буквы l посчитаем, сколько раз она встретилась в строке --- массив c[l]. Подсчет осуществляется примерно так: c[s[i]]++. Если количество вхождений какой-то буквы не кратно k, то мы уже сразу понимаем, что составить нужную нам строку невозможно. Теперь построим строку p: добавим в неё букв 'a', букв 'b', и так далее. Выведем полученную строку k раз.

219B - Только сегодня! Супер цена 999 бурлей!

Переберем количество девяток на конце числа от 1 до 18. Пусть эта величина равна k. В таком случае максимальное число не превосходящее заданное p можно получить так:

  • сотрем последние k цифр числа x:  = p / 10k
  • добавим справа k девяток y:  = x·10k + 10k - 1
  • если значение y больше p, то уменьшим число x (то, что идет до k девяток) на 1 и к результату допишем k девяток y:  = (x - 1)·10k + 10k - 1

Если получившееся y >  = p - d, то обновим ответ значением k.

219C - Цветная полоска

Разберём 2 два случая:

  1. k равно 2. Тогда нам подходят только две строки — чередующиеся буквы 'A' и 'B'. Выбираем из них тот, который требует меньшего числа перекрасок.
  2. k больше 2. Возьмем самый левый блок из одинаковых букв. Пусть его длина равна k, тогда надо не менее k / 2 перекрашиваний, чтобы избавиться от соседних одинаковых клеток в этом блоке. Если k нечетно, то можно каждую вторую клетку в блоке перекрасить в любой из цветов, отличных от цвета блока. Если k четно, то можно делать тоже самое, но аккуратнее выбрать цвет: он должен отличаться не только от цвета блока, но и от цвета следующей клетки за блоком. Это всегда возможно сделать, так как количество цветов больше 2.

219D - Выбор столицы Древляндии

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

В задаче были достаточно большие ограничения, поэтому нельзя было просто посчитать все эти значения n обходами в глубину. Авторское решение запускает только два обхода в глубину. Первым обходом в глубину посчитаем ответ для города номер 1. Заметим, что если посчитан ответ для вершины x, то ответ для вершины y, которая соединена с x, можно посчитать за O(1). А именно, ans(y) = ans(x) - direction(x, y) + (1 - direction(x, y)), где direction(x, y) — равно 1, если ребро (x, y) ориентировано не так как во входных данных, и равно 0, иначе.

Пользуясь описанным фактом, можно посчитать все значения ans(v) одним обходом, зная ans(1).

Итоговая ассимптотика решения O(n).

219E - Стоянка

Будем поддерживать две структуры: множество отрезков свободных парковочных мест, в котором отрезки отсортированы по их началу, и множество отрезков свободных парковочных мест отсортированных по размеру. Такие структуры должны поддерживать операцию быстрого поиска первого больше либо равного элемента, удаление элемента и его вставку, нахождениe максимума и следующего по величине элемента.

В языке C++, авторское решение использовало set <pair<int,int>> и map <int, set<int>>. Set отрезков и Map из длины отрезка в набор отрезков с заданной длиной. Операция поиска больше либо равного элемента в этих структурах называется lower_bound.

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

Чтобы удалить автомобилиста со стоянки нужно добавить новый отрезок свободных парковочных мест длины один в структуру. Предварительно нужно удалить смежные с этим отрезком отрезки в структуре. Соединить их с нашим отрезком и добавить один большой отрезок в структуру.

Отдельные случаи возникает при рассмотрении крайних отрезков.

Итоговая сложность решения O(m log n)

Read more »

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

By Gerald, 7 years ago, translation, In English,

Good Morning, Codeforces!

Analyzing the task C (Div1), E (div2) I came to the conclusion that the author's solution is wrong, so I bring to you all a huge apology.

However it turned out all pretests were correct and there are only a few number of incorrect hacks (only 3). After discussing the situation with MikeMirzayanov we made ​​this decision:

  • Problem E almost do not effect on contest results for Div2 participants (there are only a few number of submits and no hacks), so the contest will be rated for Div2 participants.

  • The contest will be rated for Div1 participants, only if this problem have right and fast solution. I wasted all todays night (or morning) finding this solution. Therefore I propose to solve this problem by the community (if it's possible). If during the day, i.e. 24 hours after publishing this post, one cannot find solution, Div1 competition will be considered unrated.

Once again I bring you my apologies for this mistake. I hope that we will be able to master this problem together. Feel free to write all your ideas in this post, even some wrong idea may hint at the right solution. We would be very grateful to everyone who will take part in solving of that problem.

Note that this problem appeared in problemset. All tests are correct and you may try to solve it.

UPD: 24 hours have passed. Unfortunately, no one has written the correct solution, or close to it. Div1 round is declared unrated. Many thanks to all those who put their efforts and tried to solve this problem.

Best regards, Gerald Agapov.

Read more »

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

By Gerald, 7 years ago, In Russian,

Добрый день, Codeforces!

Меня интересует, умеет ли кто-нибудь считать такую сумму  . Или такую сумму (они друг через друга выражаются)  (деление целочисленное).

Буду очень признателен любым методам подсчета быстрее чем линия (или около-линия).

Read more »

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

By Gerald, 7 years ago, translation, In English,

Good Day, Codeforces!

Remember, that at 17:15 the final of the Open Moscow Programming Championship By CROC will start.

As usual anyone wishing to participate in this round can compete in it out of competition. But as this competition is quite complex, it will be rated only for participants from Div.1.

Note that this competition is closely connected with onsite competition in Moscow. So the starting time can be shifted. Watch closely for changes in the schedule.

Read more »

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

By Gerald, 8 years ago, translation, In English,

Good day, Codeforces!

Today at 19:00 the Round 1 of the Open Moscow Programming Championship By CROC will start.

This is usual two-hour Codeforces round with hacks and decreasing values of problems. Everybody, who passed Qualification Round and registered for today’s round, has advanced to Round 1. The remain participants are allowed to participate in this Round out of competition. Round will be rated for everyone as usual. Contestants who gain a score equal to the 300-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

You will find a few problems, roughly ordered by the increasing complexity. Score distribution is standard (500-1000-1500-2000-2500). During the Round the problems are judged only on pretests and system testing will take place after the end of the Round. The pretests do not cover all possible cases of input data, test your programs carefully!

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements and so on. Be honest and let the best men make it into Round 2. When the Round is over, you can discuss the problems and solutions.

It seems that this Round could be a bit hard for Div2 participants. Don’t forget that rating will be calculated only for participants, who make at least one submit.

In today’s round preparation take part: Ripatti, havaliza, HamedSaleh, RAD, Gerald, MikeMirzayanov, Delinur. A huge thank you to all of them for their work!

Good round to everybody!

Read more »

Announcement of Croc Champ 2012 - Round 1
Announcement of Croc Champ 2012 - Round 1
 
 
 
 
  • Vote: I like it
  • +181
  • Vote: I do not like it

By Gerald, 8 years ago, translation, In English,

152A - Marks

In this problem you should do exactly what is written in the statement. Here is rough code of solution:

for (int i = 0; i < n; ++i){   
    bool wasBest = false;
    for(int j = 0; j < m; ++j){
        bool isBest = true;
        for(int k = 0; k < n; ++k)
            if(a[k][j] > a[i][j])
                isBest = false;
        if(isBest)        
            wasBest = true;
    }
    if(wasBest)
        ans++;
}      

152B - Steps

Let's find a formula for the position (x, y) and vector (dx, dy), how many steps to stop the boy can do. You should use "almost" binary search, for example, see the code written by RAD.

for (long long cof = 1100000000; cof; cof /= 2)
    while (onField(xc + cof * dx, yc + cof * dy)) {
        xc = xc + cof * dx;
        yc = yc + cof * dy;
        ans += cof;
    }      

152C - Pocket Book

In this task, it was necessary to understand that in position 1 Vasya can get any name of a special form. More exactly, it's the name of form s = s1 s2 s3 s4 ... sm, where s1 — the first letter of any of the names, s2 — the second letter of any of the names, ... smm-th letter of any of the names. Then the answer to the problem is the product of cnti (1 ≤ i ≤ m), where cnti is a number of different letters in the names placed in position i.

152D - Frames

It was necessary to understand if there are two borders or not.

Let's distinguish those x — and y-coordinates, in which there are at least 3 consecutive symbols '#', becouse the length of each border is no less then 3. It is clear that the coordinates of the corners of borders should be chosen only from those selected x and y. In general, the various selected x no more then 4 and various selected y no more then 4.

Except that case when the height or width of the first border is 3, and length of the second side of this border is more than 3, and one side of the second border fills a part of the inside first at least.

For example:

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

The first border:

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

The second border:

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

There are 7 different y-coordinates in the example.

Carefully processed these cases separately, it is quite simple. (Let's choose 4 y-coordinates: minimum, maximum, second minimum and second maximum).

Otherwise, if the amount selected x — and y-coordinates no more then 4, then let's choose opposite corners of the first and second borders and verify that the selected borders — the correct borders and there are no other characters '#'. Checking is carried out at O(n + m) or O(1) (using partial sums).

152E - Garden

The solution of this problem is based on dynamic programming. dp[mask][v] — the value of the minimum correct concrete cover, if we consider as important elements only elements of the mask mask, and there are additionally covered the vertex v = (i, j) of the field.

There are two types of transfers.

First of all we can, as if to cut coverage on the vertex v. Then you need to go through subpattern of vertex submask, which will go to the left coverage and make an optimizing transfer. Update dp[mask][v] with the value dp[submask][v] + dp[mask ^ submask][v] - cost(v).

Second, perhaps in the vertex v in the optimal coverage mask mask, which covers the vertex v, you can not make the cut separating the set of vertices. In this case, this vertex forms something a kind of <>. And there a vertex u exists, on which we can make the cut, with the whole shortest path from a vertex u to v belongs to the optimal coverage. Let's precalculate the shortest paths between all pairs of cells. Now to make this transition, we should count the value of dynamics dp[mask][v] for all vertices v only on the basis of the first transition. Now you can make the second transition. For all u, dp[mask][v], update the value of dp[mask][u] + dist(v, u) - cost(u).

Let's process separately state in which exactly one bit in the mask, and the vertex which corresponding to this bit is equal to v. In this case the answer is equal to cost(v), of course.

Thus, each solution is obtained for the O(min(3k·n·m, 2k·(n·m)2)).

Read more »

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

By Gerald, 8 years ago, translation, In English,

Good day, friends!

Today another Codeforces round for Div2 participants will be. As the last Div2 only round, this round has been prepared by a team of three people: NALPPolichka and Gerald. Traditionally, we express our gratitude for their help to Artem Rakhov (RAD) Maria Belova(Delinurand Mike Mirzayanov (MikeMirzayanov).

Score distribution: 500-1000-1500-2000-2500

Good luck and have fun of solving problems! :)

UPD: Problem analysis

Read more »

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

By Gerald, 8 years ago, translation, In English,
It was enough for solving this problem to calculate for each letter: ac - amount of occurrences of letter c in first and second strings in input, bc - amount of occurrences of letter c in third string in input. If the answer is "YES" else "NO". 

Let's bust the "level" 0 ≤ i ≤ 106, in which assumedly the stone could hit. Let’s find the minimal number of square on this level. Then we can understand, how many squares there are on this level: one or two. Then we check with one or two ifs (if on this level two squares) if the stone is in corresponding square or not. If the stone is inside then output the answer. If we didn't find any square, where the stone is, output "-1".  

Let's sort the pairs (namei, ai) by ascending of ai. If there is an index i: 0 ≤ i < n that ai > i, then answer is "-1". Otherwise the answer exists. We will iterate through the array of sorted pairs from left to right with supporting of vector of results res. Let on the current iteration ai = n - i, then we must transfer the current man in the position ai. It can be done in C++ with one line: res.insert(res.begin() + a[i], man); 

Let's generate the weighted directed graph of all ramps. The graphs' vertexes are the important points on the line Ox, there are points: 0, L, xi - pi, xi + di. The graphs' edges are the possible ramp jumps: transfer from point xi - pi to point xi + di or transfer from vertex in neighboring vertexes (neighboring means that we get the next and previous important points on the line). The weights of these edges are correspondingly pi + ti and xv + 1 - xv, xv - xv - 1. We must note that in the transfers we can't get in the negative part of Ox, and we must delete this transfers.

Then we must find and output the shortest path in this graph from vertex 0 to L. This can be done, for example, with Dijkstra's algorithm for the sparse graphs. 


In this problem we must find the minimum spanning tree, in which the half of edges are marked with letter 'S'.

There are  n - 1 edges in this tree, because of it if n is even then the answer is "-1".

Let's delete from the given graph all S-edges. And there are cnt components in obtained graph. For making this graph be connected we must add cnt - 1 edges or more, that's why if cnt - 1 > (n - 1) / 2 the answer is "-1". Then we find cnt - 1 S-edges, that we must add to the graph, so that it become connected. If cnt - 1 < (n - 1) / 2 then we will try to add in this set of edges another S-edges, so that the S-edges don't make circle. We must do all of this analogically to Kruskal's algorithm of finding a minimum spanning tree. If we could get a set of S-edges of (n - 1) / 2 elements, that there are exactly cnt - 1 edges and no S-circles, then the answer exists, Then we must add to this set (n - 1) / 2 M-edges, that forms with our set of edges the minimum spanning tree, it must be done analogically with Kruskal's algorithm.

Read more »

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

By Gerald, 8 years ago, translation, In English,
Consider three cases.
  • s = f, ans = t.
  • s < f, we must find the smallest non-negative k such, that t ≤ (s - 1) + 2(m - 1)k. ans = s - 1 + 2(m - 1)k + (f - s).
  • s > f, similarly, we must find the smallest non-negative k such, that t ≤ 2(m - 1) - (s - 1) + 2(m - 1)k. ans = 2(m - 1) - (s - 1) + 2(m - 1)k + (s - f).
We can find k in any reasonable manner, for example, by using formulas of integer division.

Suppose, that the first player made a move x ≤ a, then consider the remainder rem = x· 109%mod. Obviously, if (mod - rem)%mod ≤ b, then the second player can win. Thus, we must iterate through all relevant values of x (we don't need iterate through more than mod values) and check whether the second player to win. If there exist a losing move for second player, then won the first, else second. Since we iterate through all relevant moves of the first player, then we can easily determine his winning move (if such move exist).

Approval. If the tournament has at least one cycle, then there exist a cycle of length three.

A constructive proof. Find any cycle in the tournament by using any standard algorithm, such as depth-first search. If there is no cycle, then output -1, else choose any three consecutive vertices of the cycle v1 v2 v3 (Av1, v2 = Av2, v3 = 1). Since given graph is a tournament, then there is an edge (v3, v1), or there is an edge (v1, v3). The first of these two cases, we find immediately the cycle of length three of the vertices v1 v2 v3,  the second, we can reduce the length of the loop (erase vertex v2). 

We can reduce the length of the cycle until we find a cycle of length three.

Imagine a recursion tree our transformation F. This tree is binary. We write on the edges leading into the left subtree, zero, and on the edges, leading to the right, one. Now consider the path of some number a (hereafter, we assume that we substracted one from all numbers in the array over which we make the conversion). This path start in the root of the tree and end in some leaf, and numbers written on the edges of the path is exactly bit representation of a in order from least significant bit to the most significant bit.

Construct the recursive function which solve our problem, similar to how we carry out a query to the segment tree. Here is the prototype of this function.

solve(idx, tl, tr, l, r, u, v)

This function returns the answer to the query (l, r, u, v), if we consider only subtree with positions [tl, tr], while on the path from the root to the subtree is written bit representation of idx. If l ≤ tl ≤ tr ≤ r, then we calculate answer by formulae, else we divide our segment of positions and return sum of answers from left and right part.

As described above, the answer to the whole subtree is a formula. Here you need to use the fact that all the numbers in the subtree have the form k· 2depth + idx, where depth - depth of subtree. We must find k such, that u ≤ k· 2depth + idx ≤ v and then calculate the sum of  appropriate numbers.   

Asymptotics of this solution O(m· log(n)· (formulae - for - whole - subtree)). We can calculate formulae for whole subtree in O(logn).

In this problem, suggested a solution using heavy light decomposition. Graph, given in problem statement, is a cycle, on which are suspended trees. For each tree construct the data structure (heavy light + segment tree), which can perform change on the path from some vertex to any parent, and to maintain the amount of ones. The same structure we use for the cycle. 

Suppose, that we have no cycle, i.e. there is just a bunch of trees (forest). Then the amount of switched-on edges uniquely determines the number of connected components (each switched-on edge decrease the amount of components by one). 

Suppose, that we have only the cycle. Then, similarly, the amount of switched-on edges uniquely determines the number of connected components.

We will maintain the amount of switched-on edges in the cycle and in the all trees. So, the answer to the problem Compscicle + Compstrees - CntCicle, where Compscicle - the amount of connected components in cycle, Compstrees - the amount of connected components in all trees, CntCicle - the amount of vertexes in cycle.


Read more »

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

By Gerald, 8 years ago, translation, In English,

Hello everybody! My name is Gerald Agapov. I study at Saratov State University. Today I present you the set of, I hope interesting, problems. Good luck to all!

And also a warm thanks RAD,  MikeMirzayanov and the entire Codeforces team for the great system and this opportunity! (с) dolphinigle

UPD. 

The match has ended. Thank you for paticipating!

Top 5 Coders:
5. kelvin

Read more »

Announcement of Codeforces Beta Round #88
Announcement of Codeforces Beta Round #88
 
 
 
 
  • Vote: I like it
  • +208
  • Vote: I do not like it

By Gerald, 9 years ago, In Russian,
Недавно я узнал, что есть способ перемножить два 64 битных числа по модулю третьего 64 битного числа без применения длинной арифметики. Вроде как такое перемножение можно сделать используя long double в 2 строчки кода. Прилично погуглив, я не обнаружил ничего путного на эту тему, хотя польза от такой операции весьма большая (например не прибегать к длинной арифметике в тесте миллера рабина на простоту большого 64 битного числа). Может кто-то знает как это можно сделать?  Заранее благодарен за помощь.

Read more »

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