Fcdkbear's blog

By Fcdkbear, history, 4 years ago, , Hi everybody,

As you've probably already guessed, I am looking for teammates for Deadline 24. I have no experience in participating in such kind of contests, but I've taken part in algorithmic competitions since 2009. I speak Ukrainian, Russian and English. We may communicate via Skype/Hangouts/etc during the qualification round.

So if you are interested — do not hesitate to PM me. By Fcdkbear, history, 4 years ago, , Hi everybody,

It's been exactly a year since MemSQL Start[c]UP 2.0 — Round 2, but I still have not received my T-shirt. Am I the only one with this problem? By Fcdkbear, 5 years ago, translation, , The dates of algorithmic track of TopCoder Open 2015 are finally announced! A lot of changes were introduced in the rules:

1) There is no specific registration needed for the TCO15 Algorithm Competition.

2) The rule of receiving the automatic berth was changed a little bit

3) Regional onsite events were introduced. They will coincide with Algorithm Round 2. There will be four stages of Round 2 this year.

5) There will be only 12 finalists this year. The rules of onsite finals were also changed. Thanks to ffao and cgy4ever for noticing that

TopCoder Open usually is a very cool competition, so don't miss it!

GL&HF! By Fcdkbear, 5 years ago, , Let's discuss problems here.

Here is very-very short explanation of my solutions.

Die Hard 3

Use dfs/bfs on a graph, where vertice is represented by a pair of integers, each of which denotes the amount of water in a jug.

Chocolate in Box

This problem requires very basic knowledge about game theory and nim game. It is also important to notice, that we can do exactly 0 or 1 optimal moves in one heap.

String Function Calculation

Let's build suffix array and calculate LCP array. Now we can calculate maximum of occurrences of a substring with some fixed length using some sets/multisets

Savita And Friends

Have no idea how to solve this problem. I tried ternary search, but obviously it won't give the correct answer. I'll be very grateful if someone posts his solution to this problem

The crazy helix

One can use treap to answer all the queries. However, i used treap to answer the queries of type 1 and 2. For the third type of query I used sqrt-decomposition on the queries. By Fcdkbear, 6 years ago, , Всем привет.

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

И так, контест официально начался в пятницу. На регистрации участников, кроме, собственно говоря, организаторов олимпиады, ожидали также стенды Яндекс, Facebook и SysIQ (это более-менее известная в Украине фирма, офис которой есть в Виннице). Отдельное спасибо Яндексу, который порадовал прикольными сувенирами с надписью «Яндекс. Наш лось» и, соответственно, рисунками лося :)

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

Вдохновившись бодрым примером команды Samara SAU Teddy Bears, мы решили выиграть пробный тур. Задачки на пробном были стандартные для SEERC. Более того, кодить их можно было до старта контеста. Несмотря на то, что в 4-ой задаче я сделал две ошибки (одну в понимании условия, вторую – в коде), мы все сдали с плюса и выиграли пробный тур :)

На вечер были запланированы технические семинары от Яндекса и Facebook. Michael в презентации от Яндекса рассказал о том, как они зарабатывают на рекламе, а Остап Коркуна из Facebook рассказал про новую фейсбуковскую фичу — Facebook Graph Search. Было довольно-таки интересно, к тому же рассказы на отвлеченные темы помогли убрать волнение накануне контеста.

А на следующий день был контест. Комплект задач разыгрывался на воскресном этапе Открытого Кубка, поэтому, полагаю, все знакомы с условиями. Я расскажу, как это проблемсет решала моя команда (VNTU [wRabbits]) На старте Outside дал мне задачу I, сказав, что это простая динамику по DAG-у. В процессе написания я осознал, что не все так просто и отдал компьютер Igel_SK, который сел писать задачу G. Сабмит – ВА. Я читаю задачу J и решаю проверить сабмитом очевидную гипотезу. Аксепт! Вот и наш первый шарик за решенную задачу. Igel_SK находит баги в G, исправляет их и приносит нашей команде второй ОК. Хух, уже чуть лучше. Возвращаемся к задаче I. Внезапно, я слышу возглас озарения от OutSide, который говорит, что к тупому решению по ней надо докрутить битсет и все будет хорошо. И действительно, на 1:22 мы получаем третий ОК. Смотрим на монитор – сдают задачу C. С алгоритмической точки зрения она совсем простая, нужно только научиться считывать из бинарного файла. Через некоторое время Igel_SK научился это делать, я дописал алгоритмическую часть и мы сдали задачу. С этого момента начинается наш затуп длиной 2 часа и 14 минут за который мы не сдали ничего. Сналача Igel_SK придумал как решать А максимальным потоком минимальной стоимости. Пишем, отсылаем, тайм лимит эксидед. Меняем Беллмана-Форда на Левита (вдруг авторы не знают контртеста) – все еще TL. Igel_SK добавляет какую-то эвристику – программа начинает летать на макстесте, но WA. В это время я и OutSide думаем про задачу B. Придумываем, как ее решить. Я пишу решение – WA. Да что ж такое. Печатаю код, ищу баги. Igel_SK пишет жадность на А и сам же придумывает к ней контртест. Я перечитываю условие по В – да нет, все я правильно в нем понял. В конце-концов я понимаю, что допустил идейный баг, исправляю – АС. Igel_SK пишет еще одну жадность на А. Сабмит. АС! Я начал было радоваться, но мои сокомандники говорят, что у многих команд до заморозки было 7, у нас же пока что 6. Мы начинаем засылать всякий бред по задаче H, пытаясь найти закономерность и с 5-ой попытки таки верно угадываем ее. Ну что же, у нас тоже 7. В лучшем случае мы на 7-м месте. До конца контеста 38 минут. Мы начинаем писать задачу Е, хотя особой уверенности в решении нет. Мы дошли до диофантового уравнения, Igel_SK сказал, что корни должны быть взаимнопростыми, однако верное решение мы так и не придумали. Контест закончился.

Разморозка показала, что победила команда Sobolev Team, сдав победную 9-ую задачу за 2 минуты до конца. На втором месте BZFlags, на третьем – Phantom Menace. Мы же закончили 7-ыми (6-ыми по украинскому сайту). Награждались все команды, решившие 7 и более задач, а топ 6 команд, писавших в Виннице получили медальки и кубки – они стали призерами параллельно проходившего открытого чемпионата Украины. Также какие-то призы получили иностранные команды – просто за то, что они иностранные :)

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

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

Ссылка на результаты

Ссылки на фотографии на сайте ВНТУ с его кривой фотогалереей: 1 2

UPD Мы в финале! By Fcdkbear, 6 years ago, , Здравствуйте.

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

Авторы задач — Outside, Igel_SK, Sammax и я.

Внимание! Тренировка делалась с учетом того, что ее будут писать люди, уровень которых сопоставим с уровнем второго дивизиона. Участники первого дивизиона вряд ли найдут там что-то интересное.

По возникшим вопросам просьба отписываться здесь в комментах или мне в личку. By Fcdkbear, 7 years ago, translation, , A. Lunch Rush

Let’s look at all restraunts, where Rabbits can have their lunch. Let’s calculate the answer for all restraunts and choose the maximulm value among of them. We need to use formula descrbed in problem statement to calculate the answer for some particular restraunt. Time complexity of this solution is O(N).

C++ code

Java code

B. Little Girl and Game

Let’s calculate the number of letters with odd number of occurrences in s. Let this value be equal to k.

If k = 0, then first player can win immediately: he can easily build palindrome, placing equal letters in different sides of resulting string (he always can do it, because total number of all letters is even).

If k = 1 then first player can win immediately again; at first he builds palindrome from letters with even number of occurrences in s; after that he inserts the rest of the letters in the middle of built in previous step string.

Let’s proof very useful statement. If k > 1 our problem has the following solution: if k is even, than second player is winner; otherwise, first player is winner.

Let k = 2. At the beginning of the game first player can make move of two types.

Using move of first type first player can decrease k to 1 by erasing one appearance of letter with odd number of occurrences. But this move leads him to defeat, because after this move second player can build palindrome.

Using move of second type first player can increase k to 3 by erasing one appearance of letter with even number of occurrences. In this case second player can make similar move — he will erase the same letter. Since the number of moves of this type is finite, sooner or later first player will have to make a move of first type. After this move he loses immediately.

So, if k = 2, than second player is a winner.

Let k = 3. First player can decrease k to 2 by erasing the letter with odd number of occurrences. If second player will try to increase k to 3 again by erasing the similar letter, first player can decrease k to 2 again (he erases the same letter again). It’s easy to see that the last move in this sequence of moves will be the move of first player. So, first player always can change the game in such a way that k = 2. This position is losing position for second player and winning position for first player.

Now we can easily proof our statement for any k using mathematical induction.

So, we have quite easy solution with time complexity О(|S|).

C++ code

Java code

C. Little Girl and Maximum Sum

Lets calculate for each cell of the initial array the number of queries that cover this cell. It’s claimed, that we should associate the cell with bigger value to the cell with bigger value in initial array. More formally: suppose b is an array, in i - th cell of which is written the number of queries that cover i - th cell. Suppose а is an initial array. Let’s sort those arrays. It’s claimed, that the answer in this case can be calculated with following formula: Let’s proof this statements. We will take a look at some indexes i < j, and at elements, corresponding to shis indexes a[i], a[j] , b[i], b[j] (a[i] ≤ a[j], b[i] ≤ b[j]). Those elements add to the answer the following value: a[ib[i] + a[jb[j]. Let’s swap a[i] and a[j]. Now those elements elements add to the answer the following value a[ib[j] + a[jb[i]. Let’s take a look at the following difference:

a[ib[j] + a[jb[i] - a[ib[i] - a[jb[j] = b[j]·(a[i] - a[j]) + b[i]·(a[j] - a[i]) = (b[j] - b[i])·(a[i] - a[j]) ≤ 0.

So, swapping of two elements leads us to nonincreasing of the total result. This means, that our arrangement is optimal.

Now we need to calculate array b fast enough.

For this purpose one can use different data structures, which support segment modifications (segment tree, Cartesian tree and so on). But there exists much easier method.

Let’s create some array d. When we have query li, ri, we should increase value d[li] by 1 and decrease value d[ri + 1] by 1. In such a tricky way we increase all elements in segment [li;ri] by 1 After processing all of the queries we need to make a loop, which visit every element of array d. In this loop we can easily calculate all elements of array b.

Now we are ready to get the final answer. The complexity of author’s solution is O(NlogN + Q)

C++ code

Java code

D. Little Girl and Maximum XOR

To be honest, I am surprised that problem D had so many accepted solution during the contest. The author’s solution uses dynamic programming. In this editorial I’ll explain this solution.

First of all we should convert L and R to the binary numeral system. Now we can solve our problem with dynamic programming, using the following state d[p][fl1][fr1][fl2][fr2], where p is current position in binary representation of our numbers a and b (this parameter is in range from 0 to number of bits in R), fl (0 or 1) is a variable, which shows if current value of а is strictly greater than L, fr1 (от 0 до 1) is a variable, which shows if current value of а is strictly less then R, fl2, fr2 are variables, which show the similar things for b.

Let’s use recursion with memorization for our solution.

Let’s define the base of recursion. If we have looked through all the bits, we should return 0.

Let’s define a recursive transition. We need to know, which bits we can place into binary representation of number а in p-th position. We can place 0 if the following condition is true: p-th bit of L is equal to 0, or p-th bit of L is equal to 1 and variable fl1 shows that current value of a is strictly greater then L. Similarly, we can place 1 if the following condition is true: p-th bit of R is equal to 1, or p-th bit of R is equal to 0 and variable fr1 shows that current value of a is strictly less then R. Similarly, we can obtain, which bits we can place into binary representation of number b in p-th position.

Let’s iterate through all possible bits’ values and check the result of xor operation. If it is equal to 1, we should add to the answer corresponding power of 2. We also need carefully recalculate values of variables fl1, fr1, fl2, fr2. We should choose maximum answer from all valid options.

Initial state for our recursion is (P,0,0,0,0), where P is number of bits in R.

I hope, my code will clarify all the obscure points.

I also want to say, that this approach is in some sense universal and can be applied to many similar problems, like this one

The complexity of algorithm is O(logR)

C++ code

Java code

In Russian thread I saw another really nice solution, so I decided to include this solution to the editorial.

First of all, if L = R, than the answer is 0.

Now let’s consider case with L ≠ R. Let Ri be the i-th bit of R, Li be the i-th bit of L. Let’s define p as largest number such as Rp ≠ Lp (we use 0-based indexation). Let’s take a look at all numbers in range [L;R]. It’s easy to see, that bits, that are higher than bit with index p are equal for all this numbers. Thus, those bits can not affect our answer, because their xor will always equal to 0.

Let’s build numbers a and b in the following way:

1) a: bits which are higher than bit with index p are equal to the corresponding bits of L, p-th bit is equal to 0, the rest of bits are equal to 1.

1) b: bits which are higher than bit with index p are equal to the corresponding bits of L, p-th bit is equal to 1, the rest of bits are equal to 0.

It’s easy to see, that a and b both lie in range [L;R]. It’s also easy to see, that xor of this numbers sets all bits, that are not higher than bit with index p to 1. So, our answer is maximum possible and is equal to 2p + 1 - 1

The complexity of algorithm is O(logR)

We can iterate through value of p using binary search. We can achieve time complexity O(log(logR)) in this way, but it wasn’t required during the contest.

E. Little Girl and Problem on Trees

One can see, that our tree is a set of chains, each of which starts in the root.

First of all we need to decompose our tree in chains using, for example, depth first search. For each vertex we should find out it’s depth and number of chain, which contain this vertex. For each chain we’ll use some data structure, which can fast enough change it’s elements and fast enough answer to the range sum query. For example, we canuse Binary Indexed Tree (BIT). We also need to create one BIT for root. This BIT is global: it’s information is actual for all the chains

Let’s remember problem С. In that problem we used array d for processing all the queries. We need to know values of elements of array b in that problem after processing all the queries. In this problem queries are online. That’s why we need to use BIT; it allows to change element and answer range sum query in O(logN) time.

Let’s learn, how to process queries, which require modification and queries, which require finding the element, using BIT.

BIT can make two types of operations:

add(x, y) — add value y to element with index x

find(x) – finds sum in range from 1 to x

Let’s consider, that we need to add value val to all elements in range from l to r . Than we should just make operations add(l, val) and add(r + 1,  - val).

Let’s consider, that we have query which require printing the value of element with index v. Then we should just make operation find(v).

Now let’s go back to the initial problem.

During the processing query of type 0 we should check, if it affects the root. If query affects the root, we should carefully process this query in our chain and make necessary changes in root’s BIT. Otherwise we just process query in our chain.

During the processing query of type 1 we should just find corresponding sums in root’s BIT and in BIT for our chain. We should print the sum of this values.

Time complexity of this solution is O(N + QlogN)

C++ code

Java code Tutorial of Codeforces Round #169 (Div. 2) Tutorial of Codeforces Round #169 (Div. 2) 169,
By Fcdkbear, 7 years ago, , Предлагаю здесь обсудить задачи раунда. Интересует, как решалась задача А. snws,
By Fcdkbear, 7 years ago, translation, , Hy to all!

I need help. I want to find server with contests and judging system, which allows to hold personal trainings. Contest duration should be from 2 to 3 hours, and difficulty of the tasks should be comparable with CodeForces Div1 rounds. I am interested in complete problemsets. Do you know servers like described one? Any help will be appreciated. By Fcdkbear, 8 years ago, , Здравствуйте!

У меня два вопроса:

1) Кто-нибудь в Украине уже получил футболки Google Code Jam 2011?

2) Куда можно написать по поводу того, что футболка долго не приходит?

Заранее спасибо.

UPD. Только что пришло письмо из техподдержки. "We are working on distributing the shirts within Ukraine. We should have them out shortly." Так что ждем, надеемся и верим :) By Fcdkbear, 10 years ago, , На далеком-далеком острове жили два типа людей: голубоглазые и черноглазые. Стоит заметить, что все они были идеально умные. Также жители острова не могли передавать кому-либо какую-то информацию(то есть они были немые, не умели общаться на языке жестов и т.д.)  Существовало у туземцев такое правило: если житель острова узнает цвет своих глаз, он идет к высокому обрыву, прыгает оттуда и разбивается насмерть. Сброситься со скалы туземец может каждый день ровно в 17-00. Для того, чтобы узнать свой цвет глаз, туземец не может смотреть в воду, зеркало и т.д.

Всё у жителей острова было хорошо до тех пор, пока к ним не приехал иностранец. Он пожил на острове несколько месяцев. И вот, настало время ему уезжать. Иностранец сел в лодку, и перед тем, как отправиться в далекий путь, сказал лишь одну фразу:"Как здорово, что я увидел человека, такого же голубоглазого, как я". Лодка иностранца тут же покинула пределы острова. Опишите, что произошло на острове после отъезда иностранца.

З.Ы. Правильное решение задачи я пока-что не придумал.

З.З.Ы Огромное спасибо пользователю SkidanovAlex за корректировку условия и детальный разбор задачи. By Fcdkbear, 10 years ago, , Всем доброго времени суток!

Так как это моя первая запись в блоге, прежде всего хочется поблагодарить создателей Codeforces за отменную работу!

А теперь, собственно говоря, по теме. Контесты USACO писал в на этих выходных впервые. Так вот, меня немного удивила финальная таблица турнира(http://ace.delos.com/MAR10results). Как видим, таблица всех дивизионов поделена на две части. Обе части начинаются с наивысших результатов и заканчиваются наинизшими. То есть, после самого плохого результата первой части резко следует самый хороший результат второй части. Подскажите пожалуйста, чем это вызвано?  И еще: что означает в таблице таинственная колонка GRAD? 