GlebsHP's blog

By GlebsHP, history, 7 months ago, In English,

Problem A. Long-Term Mail Storage.

The probelm asked to simply simulate the process. One can keep yet unread mails in any data structure (array, deque, set, whatever) and iterate through time. For any moment of time x we first check whether there is a new incoming letter and add it to the structure if that is the case. Now, check if the ``feeling guilty'' condition is satisfied. If so, compute k and remove k oldest letter from the structure. Doing all this in the most straightforward way would result in O(nT) complexity.

Excercise: solve the problem in O(n) time.

Problem B. Lassies Versus Machine.

First of all, note that if Dusya and Lusia split n in x and n - x they would get exactly the same set of banknotes as a change as if they split in x + 5000 and n - x - 5000. That means, we only have to check all possibilities to split from a to min(a + 5000, n - a). For each possibility we compute the change in O(1) time. If some girl wants to pay y the change will be (5000k - ymod 500, where .

Excercise: prove that it's enough to check only values from a to min(a + 499, n - a).

Problem C. Effecient Management Returns.

There are many different approaches for this problem and almost all solutions one can imagine will work as the size of the answer will never exceed (excersise: prove). This editorial contains only one possible linear time solution.

Proceed vertices one by one. After we have processed first i - 1 vertices (v1, v2, ..., vi - 1) we would like to keep a way to dirstibute them among ki teams T1, T2, ..., Tki that will satisfy all the requirements. When we add a new node vi we should find any component Tj, such that there is no node and . Assuming this can be done in time by simply making an array of boolean marks and traversing the list of all neighbours. If there is no such Tj, we consider ki + 1 = ki + 1, i.e. we create a new set for this vertex. However, we actually do not need this time to set up the boolean array, as we can use only one array and mark it with a number of iteration instead of a simple \emph{true}. Thus, we set marks in O(deg(vi)) time and then simply consider all sets one by one till we find first valid. Obviously, we will skip no more then deg(vi) sets till we find first possible match, thus the running time will be O(deg(vi)) and the total running time is O(n + m).

Problem D. The Sting.

First of all we would like to slightly change how we treat a bet. Define ci = ai + bi. Now, if we accept the i-th bet we immediately take bi and then pay back ci in case this bet plays. Define as A some subset of bets, , i.e. the total profit we get from subset A. Define as L(A) the total amount we will have to pay in case the game result will be "team looses", i.e. . Similarly we introduce D(A) and W(A). Now, the profit of Ostap if he accepts subset A is S(A) - max(L(A), D(A), W(A)).

In this form it's not clear how to solve the problem as we simultaneously want to maximize S(A) from the one hand, but minimize maximum from the other hand. If we fix the value max(L(A), D(A), W(A)) = k the problem will be, what is the maximum possible sum of bi if we pick some subset of "loose" ("draw", "win") bets with the sum of ci not exceeding k. Such values can be computed for each outcome independetly using knapsack dynamic programming. The complexity of such solution is O(nL), where .

Problem E. Random Value of Mode.

To start with consider O(n2) dynamic programming solution. Let dpleft(i, j) be the optimum expected value if Gleb has visited all shops on segment from i to j inclusive and is now standing near the shop i. In the same way dpright(i, j) as the optimum expected value if segment from i to j was visited and Gleb stands near shop j.

We are not going to consider all the formulas there, but here is how we compute dpleft(i, j), picking the minimum of two possibilities go left or go right:

dpleft(i, j) = min(1 + ti - 1 + pi - 1·|i - 1 - x| + dpleft(i - 1, j)·(1 - pi - 1)

,

(j + 1 - i) + tj + 1 + pj + 1·|j + 1 - x| + dpright(i, j + 1)·(1 - p{j + 1}))

To move forward we should have a guess that if there are no pi = 0 we are going to visit many shops with a really small probability. Indeed, the smallest possible positive probability is one percent, that is 0.01 which is pretty large. The probability to visit k shops with pi > 0 and not find a proper coat is 0.99k, that for k = 5000 is about 1.5·10 - 22. Assuming ti ≤ 1000 and n ≤ 300 000 the time required to visit the whole mall is not greater than 109, thus for k = 5000 it will affect the answer by less than 10 - 12. Actually, assuming we only need relative error k = 3000 will be sufficient.

Now, we find no more than k shops with pi > 0 and i < x and no more than k shops with pi > 0 and i > x. Compress shops with pi = 0 between them and compute quaratic dynamic programming. The overall running time will be O(n + k2).

Problem F. Measure Twice, Divide Once.

We need to assign each vertex a single positive integer xv~--- the number of the process iteration when this vertex will be deleted. For the reason that will be clear soon we will consider xv = 0 to stand for the last iteration, i.e. the greater value of x correspond to the earlier iterations of the process. One can prove that an assignment of positive integers xv is correct if and only if for any two vertices u and v such that xu = xv the maximum value of xw for all w on the path in the tree from u to v is greater than xu. That is necessary and sufficient condition for any two vertices removed during one iteration to be in different components.

Pick any node as a root of the tree. Denote as C(v) the set of direct children of v and as S(v)~--- the subtree of node v. Now, after we set values of x in a subtree v we only care about different values of xu, that are not "closed", i.e. there is no value greater between the corresponding node and the root of a subtree (node v). Denote as d(v, mask) boolean value whether it's possible to set values of x in a subtree of node v to have values mask unclosed. Because of centroid decomposition we know there is no need to use values of x greater than , thus there are no more than different values of mask, i.e. O(n). d(v, mask) can be recomputed if we know d(u, mask) for all in O(n3) time. Indeed, if one child ui uses mask mi we know:-

  1. We have to set xv greater than any i that occurs in more than one mask.
  2. We can set xv to any i that doesn't occur in any mi.
  3. If we set xv = i, all j < i are set to 0 in m.

Now, one can notices that according to the following process if mask m1 is a submask of m2 it is always better lexicographically smaller than mask m2 it always affects the result in a better way. Now, we claim that if for some subtree v we consider the minimum possible m, such that d(v, m) is true, for each m1 > m there exists m2 submask of m1 such that d(v, m2) is true. Indeed, consider the first (highest) bit i where m and m1 differ. Because m1 is greater than m it will have 1 at this position, while m will have 0. If there is no 1 in m anymore it is itself a submask of m1, otherwise, this means xv < i. We can set xv = i and obtain a submask of m1.

The above means we should only care about obtaining a lexicographically smallest mask for each subtree S(v). To do this we use the above rules to merge the results in all . This can be easily done in or in O(n) if one uses a lot of bitwise operations.

Read more »

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

By GlebsHP, history, 7 months ago, translation, In English,

Hello everybody!

Tomorrow, at 10:00 Moscow time will be held Round 1 of Yandex.Algorithm competition, authored by me. I would like to thank Zlobober for all the job he does to make this competition interesting, MikeMirzayanov for the great polygon that ease the preparation process a lot, and everyone, who tested the round and made useful comments. Of course, we did our best to make the problem diverse by topics and difficulty.

See you in the competition dashboard!

UPD Thanks to everyone who participated, hope each of you found at least one interesting problem. We apologize for the situation with problem F, we have googled for all the problems and asked all testers whether they have seen such problems or not, but that didn't helped. The editorial has been published.

Read more »

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

By GlebsHP, history, 8 months ago, In English,

I've already expressed everything in this comment, however, I've decided to additionally create this post to raise the attention to what I consider to be a very serious and frustrating issue.

Read more »

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

By GlebsHP, history, 10 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By GlebsHP, history, 10 months ago, translation, In English,

Hello everybody!

Tomorrow round will be held using problemset of Moscow programming competition for school students of grades from 6 to 9. Do not be tricked by the age range of the participants, Moscow jury always tries its best to select interesting problems of various topics. Problems were developed by feldsherov, ch_egor, halin.george, ipavlov and GlebsHP.

Hope to see you in the standings!

P.S. Scoring distribution is standard.

UPD Congratulations to the winners!

  1. Mr.Stream

  2. mamka

  3. funtik

  4. HE_MATEMATIK

  5. XLightDog

UPD2 Problem analysis is here.

Read more »

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

By GlebsHP, history, 11 months ago, In Russian,

Всем привет!

Если вдруг вы очень хотели написать короткий тур заочного этапа, и расстраивались, что он доступен только для официальных участников с определённым количеством баллов, то спешим вас порадовать. Жюри приняло решение провести внеконкурсную трансляцию для всех желающих. Ссылка на вход в соревнование. Контест можно стартовать до 23:59:59 23 января (понедельник).

Read more »

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

By GlebsHP, history, 11 months ago, translation, In English,

Dear community!

It was a fantastic year, with great pleasure I took a role of Codeforces Coordinator. This year I learned a lot, communicated with wonderful people and realized how valuable this work is for thousands of people. I would like to thank you all for these great moments! I strongly believe that there are many cool rounds and interesting problems ahead as I'm passing this duty to Nikolay KAN Kalinin!

Please, watch my New Year's speech (Russian language, English subtitles):

P.S. Special thanks go to Maxim zlobober Akhmedov and Oleg shhdup Mingalev who helped me prepare this video.

Read more »

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

By GlebsHP, history, 17 months ago, In English,

Finally, the analysis is here! Feel free to ask in comments for any unclear part.

Problems ideas and development:

Cards: MikeMirzayanov, fcspartakm

Cells Not Under Attack: GlebsHP, fcspartakm

They Are Everywhere: MikeMirzayanov, fcspartakm

As Fast As Possible: GlebsHP, fcspartakm

Connecting Universities: GlebsHP, fcspartakm, dans

Break Up: GlebsHP, MikeMirzayanov, kuviman

Huffman Coding on Segment: GlebsHP, Endagorion

Cool Slogans: GlebsHP

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By GlebsHP, history, 17 months ago, translation, In English,

Hello everybody!

Today the second regular rated round based on problems of VK Cup 2016 Final Round will take place. Of course, we have created some more easy problems to fulfill the requirements of different skill levels and make the contest interesting for everyone.

The commentators of the previous announcement pointed out that I forgot to thank MikeMirzayanov for making Codeforces and Polygon so awesome. I was wrong, Mike, that's really cool :)

Scoring distribution will be published right before the start of the contest. We wish you good luck and beautiful solutions!

UPD1. Scoring for div2: 500-750-1000-1500-2000-2500. Scoring for div1: 500-1000-1500-2250-3000.

UPD2. The contest is over, congratulations to winners!

Div1:

  1. ainta

  2. W4yneb0t

  3. Petr

  4. muratt

  5. kcm1700

  6. Vercingetorix

  7. Tinsane

  8. Reyna

  9. aid

  10. zemen

Div2:

  1. MinamiKotori

  2. Ancient_mage

  3. WhatTheFua

  4. Yanba

  5. macieck9

  6. OMRailgun

  7. radoslav11

  8. zhsh

  9. skywalkert

  10. abgnwl

UPD3. I sincerely apologize for the delay with problem analysis. I was out of town for a vacation. Here it is.

Read more »

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

By GlebsHP, history, 17 months ago, In English,

New problems will be added as soon as the analysis is ready.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By GlebsHP, history, 17 months ago, In English,

Dear friends!

We are glad to invite you to take part in Codeforces Round #363, featuring some problems of the VK Cup 2016 Final Round that took place in Saint Petersburg at the beginning of July. The second part of the problemset will be used to conduct Codeforces Round #364. Of course, we made some new problems to complete the set to fulfill the requirements of the regular round and it now contains problems of the appropriate difficulty for participants of any color.

We will obey the good old tradition to publish the scoring distribution right before the start of the competition.

We wish you good luck and an interesting contest!

UPD1. Scoring distribution will be standard in both divisions 500-1000-1500-2000-2500-3000 (yes, there will be six problems featured in both div1 and div2).

UPD2. Problems were prepared for you by MikeMirzayanov, Errichto, fcspartakm, qwerty787788 and Stonefeang.

UPD3. System testing is over, congratulations to winners!

Div. 1:

  1. Petr
  2. Egor
  3. TooDifficuIt
  4. semiexp
  5. gs12117
  6. vercingetorix
  7. ilyakor
  8. Marcin_smu
  9. gullesnuffs
  10. izrak

Div. 2:

  1. Out_of_Cage
  2. lajiniunai
  3. tweety
  4. UNoNotingJonSno
  5. _Madiyar
  6. zoomswk
  7. dogewizard420blazeit
  8. FlappyBird
  9. IHaveInt
  10. AmSen

UPD4. Analysis is almost here

Read more »

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

By GlebsHP, history, 21 month(s) ago, In Russian,

20 марта в 15:00 начнётся второй квалификационный раунд чемпионата VK Cup 2016!

Правила этого раунда будут совпадать с правилами Квалификации 1. К участию приглашаются команды, не участвовавшие в первой квалификации или набравшие в ней менее 4800 баллов. Те, кто успешно справился с первой квалификацией, могут принять участие вне конкурса, при этом их результаты никак не будут влиять на проход остальных команд. Разумеется, от команд, участвующих вне конкурса, также требуется соблюдение всех правил Чемпионата.

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

Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Квалификационный раунд, как и все предстоящие раунды, требует отдельной регистрации, она будет открыта на протяжении всего раунда.

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

В Раунд 1 пройдут все команды, которые наберут положительное количество баллов, не меньше количества баллов у команды на 500-м месте.

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

Категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них до окончания раунда. Запрещено обсуждать задачи с кем-либо, кроме вашего сокомандника. Будьте честны, пусть в Раунд 1 пройдут сильнейшие!

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

Read more »

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

By GlebsHP, history, 21 month(s) ago, In Russian,

Это был бы самый обычный разбор, если бы не новая фича — спойлеры. Заценить как это круто и удобно можно уже прямо в этом посте, к каждой задаче под спойлером прикладывается код решения. Скажем спасибо kuviman :)

Текст разбора: MikeMirzayanov, fcspartakm и GlebsHP.

637A - Voting for Photos

Автор идеи: MikeMirzayanov. Разработка: fcspartakm.

Для решения данной задачи достаточно было проитерироваться по поставленным лайкам в хронологическом порядке и в отдельном массиве поддерживать количество лайков, которые уже были поставлены фотографиям (например, в cnt[i] будет храниться количество лайков, поставленных i-й фотографии). Для нахождения ответа достаточно на каждой итерации обновлять имеющийся максимум лайков текущим значением cnt[i], и если cnt[i] > maxCnt обновлять ответ, где maxCnt — это текущее максимальное количество лайков.

Асимптотика такого решения — O(n), где n — количество поставленных лайков.

Пример решения

637B - Chat Order

Автор идеи: GlebsHP. Разработка: fcspartakm.

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

Асимптотика такого решения — O(n·log(n)), где n — количество сообщений, отправленных Поликарпом.

Пример решения

637C - Promocodes with Mistakes

Автор идеи: GlebsHP. Разработка: GlebsHP.

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

Для каждого промокода можно построить множество последовательностей отличающихся от него не более чем в k позициях, то есть шар радиуса k в данной метрике. Так, для промокода 123456 подойдут последовательности ?23456, 1?3456, 12?456, 123?56, 1234?6 и 12345? (вопросик заменяется на любую цифру). Очевидно, что некоторое k подходит, если никакие два шара радиуса k не пересекаются. Этого уже достаточно для решения задачи, просто честно перебрать значения k и проверить наличие пересечения шаров. Единственная тонкость — процесс необходимо остановить как только найдётся любая последовательность принадлежащая двум шарам.

Благодаря условию n ≤ 1000 задачу можно было решить и гораздо проще. Заметим, что два шара радиуса k пересекаются если расстояние между их центрами не превосходит k. Таким образом достаточно найти пару прокодов с минимальным расстоянием между ними и выбрать максимальное подходящее k. Не забываем про случай n = 1.

Пример решения

637D - Running with Obstacles

Автор идеи: MikeMirzayanov. Разработка: fcspartakm.

В самом начале отсортируем все координаты препятствий по возрастанию. Затем воспользуемся следующим фактом: если спортсмен может преодолеть препятствие номер x и успевает разбежаться перед прыжком до препятствия номер x + 1 (то есть s ≤ a[x + 1] - a[x] - 2, где s — длина разбега перед прыжком), ему выгодно разбежаться и начать новый прыжок в точке a[x + 1] - 1.

Таким образом, для решения задачи достаточно проитерироваться по препятствиям слева направо. Пусть спортсмен преодолеть препятствие с номером i. Тогда нужно найти первое такое препятствие с номером j (правее i), что спортсмен успеет разбежаться для прыжка после препятствия j - 1 и до препятствия j. В таком случае спортсмену необходимо выполнить прыжок из точки a[i + 1] - 1 в точку a[j - 1] + 1. Если расстояние между этими точками больше чем d, значит спортсмен не сможет добраться до финиша. В противном случае нужно выполнить такой прыжок и продолжить работу программы. После преодоления всех препятствий нужно проверить нужно ли спортсмену бежать до финишной точки, или он уже находится в ней.

Асимптотика такого решения — , где n — количество препятствий.

Пример решения

Read more »

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

By GlebsHP, history, 22 months ago, In English,

Hello, community!

Tomorrow Codeforces Round #342 is going to take place. It will share the problemset with Moscow Olympiads in Informatics for students of grades from 6 to 9. Though, grades from 6 to 9 in Russia usually match the ages from 12 to 15, I guarantee that everyone (even Div. 1 participants) will find some interesting problems to solve. Problems were selected for you by the Moscow jury team: Zlobober, _meshanya_, romanandreev, Helena Andreeva and me; and prepared by members of our scientific committee: wilwell, sender, iskhakovt, thefacetakt and feldsherov.

Scoring distribution will be quite unusual: 750-750-1000-2000-3000.

UPD System testing is over. Here are the top 10:

  1. _XuMuk_
  2. pandamonium
  3. latisel
  4. zetamoo
  5. yukariko
  6. I_Love_Ximera
  7. KittyLover
  8. shdut
  9. harry.zhao
  10. luke0201

Congratulation! Also, problems seemed to be too tough, we should have probably made Div. 1 round. Anyway, thanks for participating, I hope you enjoyed it and learned something new!

Thanks to romanandreev for nice analysis.

Read more »

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

By GlebsHP, 2 years ago, In Russian,

Добрый день, дорогие пользователи Codeforces!

2 ноября начался заочный этап X Открытой олимпиады школьников по программированию. В контест добавлен первый пакет из пяти задач, остальные задачи будут добавлены позднее. Те из вас, кто знает что такое Открытая олимпиада (она же "заочка") и её правила, могут не читать дальше и сразу переходить на сайт олимпиады :) Первый пакет задач подготовили для вас: Zlobober, romanandreev, snarknews и GlebsHP.

Те, кто раньше в данной олимпиаде не участвовал, могут так же пойти на сайт и прочитать полную информацию там, а в этом посте будут обозначены лишь основные моменты. Олимпиада состоит из двух этапов: заочного и очного. Заочный этап проходит со 2 ноября по 18 января, и традиционно состоит из 10-15 задач различной сложности, тематики и формата. Мы подбираем задачи таким образом, чтобы они были интересны как совсем новичкам, так и "зубрам" олимпиадной информатики. Лучшие n участников (n приблизительно равно 400) будут приглашены на очный этап олимпиады.

Очный этап пройдёт в Москве, ориентировочные даты проведения — 7-8 марта. Площадка проведения — учебный центр нашего генерального спонсора 1С на м. Тимирязевская. Также, благодаря нашему спонсору, участникам оплачивается проживание в гостинице на время проведения олимпиады. Очный этап состоит из двух туров, уровень участников немного превосходит уровень Всероссийской олимпиады по информатике за счёт приезда сильных школьников из ближнего зарубежья. Возможно это прозвучит слишком пафосно, но на наш вкус качество задач олимпиады в последние годы превосходит Всероссийскую олимпиаду и сравнимо с IOI. Олимпиада имеет первый уровень и даёт соответствующие льготы при поступлении.

Призеры заочного этапа олимпиады никаких льгот не имеют — поступить, не выходя из дома, всё-таки не получится.

Для тех, кто не является школьником и хочет просто порешать задачи, доступно внеконкурсное участие.

Жюри олимпиады призывает всех участников действовать честно, не обсуждать друг с другом решения задач и не делиться написанным кодом. Особенно хотим отметить, что любое обсуждение задач запрещено, в частности, и в комментариях на Codeforces (в том числе, и к этому посту). Все интересующие вас вопросы по задачам вы можете и должны задавать через тестирующую систему. К сожалению, каждый год некоторые участники заочного этапа не допускаются к участию в очном этапе из-за выявления случаев списывания с их участием.

Любые оставшиеся вопросы смело задавайте в комментариях.

UPD: в контест добавлены четыре новые задачи: F, G, H и I. Для вас их подготовили: thefacetakt, Sender, haku и masterOK.

UPD2: в контест добавлены последние три задачи: J, K и L. За подготовку задач мы благодарим: romanandreev, vaness и shhdup.

UPD3: на сайте олимпиады доступны предварительные результаты и архив олимпиады. Рады сообщить, что Zlobober подготовил для вас разбор задач заочного этапа.

Read more »

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

By GlebsHP, history, 2 years ago, translation, In English,

I like the idea of Endagorion to supplement the problems analysis with small challenges, somehow related to the problem preparation, it's generalization, or more effective solution. Following this, some problems in this analysis are also complemented with this sort of tasks.

Div. 2A (Wizards' Duel)

Idea of the problem: Roman Gusarev, development: timgaripov.

Let's start with determining the position of the first collision. Two impulses converge with a speed p + q, so the first collision will occur after seconds. The coordinate of this collision is given by the formula .

Note, that the distance one impulse passes while returning to it's caster is equal to the distance it has passed from the caster to the first collision. That means impulses will reach their casters simultaneously, and the situation will be identic to the beginning of the duel. Hence, the second collision (third, fourth, etc) will occur at exactly the same place as the first one.

Code example: 13836780.

Div. 2B (Rebranding)

Idea of the problem: glebushka98, development: thefacetakt.

Trivial solution will just emulate the work of all designers, every time considering all characters of the string one by one and replacing all xi with yi and vice versa. This will work in O(n·m) and get TL.

First one should note that same characters always end as a same characters, meaning the position of the letter doesn't affect the result in any way. One should only remember the mapping for all distinct characters. Let p(i, c) be the mapping of c after i designers already finished their job. Now:

  • p(0, c) = c
  • If p(i - 1, c) = xi, then p(i, c) = yi
  • Same, if p(i - 1, c) = yi, then p(i, c) = xi

This solution complexity is O(|Σ|·m + n) and is enough to pass all the tests.

Challenge: improve the complexity to O(Σ + n + m).

Code examples: 13837577 implements O(|Σ|·m + n) and 13839154 stands for O(|Σ| + n + m).

Div. 2C\Div. 1A (Median Smoothing)

Problem idea and development: Sender.

We will call the element of a sequence stable, if it doesn't change after applying the algorithm of median smoothing for any number of times. Both ends are stable by the definition of the median smoothing. Also, it is easy to notice, that two equal consecutive elements are both stable.

Now we should take a look at how do stable elements affect their neighbors. Suppose ai - 1 = ai, meaning i - 1 and i are stable. Additionaly assume, that ai + 1 is not a stable element, hence ai + 1 ≠ ai and ai + 1 ≠ ai + 2. Keeping in mind that only 0 and 1 values are possible, we conclude that ai = ai + 2 and applying a median smoothing algorithm to this sequence will result in ai = ai + 1. That means, if there is a stable element in position i, both i + 1 and i - 1 are guaranteed to be stable after one application of median smoothing. Now we can conclude, that all sequences will turn to stable at some point.

Note, that if there are two stable elements i and j with no other stable elements located between them, the sequence of elements between them is alternating, i.e. ak = (ai + k - i)mod2, where . One can check, that stable elements may occur only at the ends of the alternating sequence, meaning the sequence will remain alternating until it will be killed by effect spreading from ending stable elements.

The solution is: calculate max(min(|i - sj|)), where sj are the initial stable elements. Time complexity is O(n).

Challenge 1: hack the solution that just applies median smoothing until something changes.

Challenge 2: think of how to speed up the algorithm from challenge 1 using bitmasks (still gets TL).

Code examples: 13838940 and 13838480.

Div. 2D\Div. 1B (Chip 'n Dale Rescue Rangers)

Problem idea and development: StopKran.

If the velocity of the dirigible relative to the air is given by the vector (ax, ay), while the velocity of the wind is (bx, by), the resulting velocity of the dirigible relative to the plane is (ax + bx, ay + by).

The main idea here is that the answer function is monotonous. If the dirigible is able to reach to target in seconds, then it can do so in seconds, for any x ≥ 0. That is an obvious consequence from the fact the maximum self speed of the dirigible is strictly greater then the speed of the wind at any moment of time.

For any monotonous function we can use binary search. Now we only need to check, if for some given value it's possible for the dirigible to reach the target in seconds. Let's separate the movement of the air and the movement of the dirigible in the air. The movement cause by the air is:

  • (xn, yn) = , if ;
  • (xn, yn) = , for .

The only thing we need to check now is that the distance between the point (xn, yn) and the target coordinates (x2, y2) can be covered moving with the speed vmax in seconds assuming there is no wind.

Time complexity is , where C stands for the maximum coordinate, аnd ε — desired accuracy.

Challenge 1: think of the solution in case it's not guaranteed that the dirigible is faster than the wind.

Challenge 2: can you come up with O(1) solution?

Code examples: 13838659 and 13842505.

Div. 2E\Div. 1C (Three States)

Problem idea and development: haku.

Affirmation. Suppose we are given an undirected unweighted connected graph and three distinct chosen vertices u, v, w of this graph. We state that at least one minimum connecting network for these three vertices has the following form: some vertex c is chosen and the resulting network is obtained as a union of shortest paths from c to each of the chosen vertices.

Proof. One of the optimal subgraphs connecting these three vertices is always a tree. Really, we can take any connecting subgraph and while there are cycles remaining in it, take any cycle and throw away any edge of this cycle. Moreover, only vertices u, v and w are allowed to be leaves of this tree, as we can delete from the network any other leaves and the network will still be connected. If the tree has no more than three leaves, it has no more than one vertex with the degree greater than 2. This vertex is c from the statement above. Any path from c to the leaves may obviously be replaced with the shortest path. Special case is than there is no node with the degree greater than 2, meaning one of u, v or w lies on the shortest path connecting two other vertices.

The solution is: find the shortest path from each of the chosen vertices to all other vertices, and then try every vertex of the graph as c. Time complexity is O(|V| + |E|).

To apply this solution to the given problem we should first build a graph, where cells of the table stand for the vertices and two vertices are connected by an edge, if the corresponding cells were neighboring. Now we should merge all vertices of a single state in one in order to obtain a task described in the beginning. Time complexity is a linear function of the size of the table .

Code examples: 13843265 — the solution described above that uses 0-1 bfs instead of merging, 13840329 — another approach that tries to different cases.

Div. 1D (Top Secret Task)

Problem idea and development: glebushka98.

If , than the sum of k minimums is obviously an answer.

Let i1 < i2 <  ...  < ik be the indices of the elements that will form the answer. Note, that the relative order of the chosen subset will remain the same, as there is no reason to swap two elements that will both be included in the answer. The minimum number of operations required to place this k elements at the beginning is equal to .

T ≤ S  ≤  . .

Calculate the dynamic programming d[i][j][p] &mdash minimum possible sum, if we chose j elements among first i with the total indices sum no greater than p. In order to optimize the memory consumption we will keep in memory only two latest layers of the dp.

Time complexity is O(n4), with O(n3) memory consumption.

Code examples: 13845513 and 13845571.

Div. 1E (Birthday)

Problem idea: _meshanya_, development: romanandreev.

The given problem actually consists of two separate problems: build the directed graph of substring relation and find the maximum independent set in it. Note, that if the string s2 is a substring of some string s1, while string s3 is a substring of the string s2, then s3 is a substring of s1. That means the graph of substring relation defines a partially ordered set.

To build the graph one can use Aho-Corasick algorithm. Usage of this structure allow to build all essential arc of the graph in time O(L), where L stands for the total length of all strings in the input. We will call the arc essential, if there is no w, such that and . One of the ways to do so is:

  • Build Aho-Corasick using all strings in the input;
  • For every node of the Aho-Corasick structure find and remember the nearest terminal node in the suffix-link path;
  • Once again traverse all strings through Aho-Corasick. Every time new symbol is added, add an arc from the node corresponding to the current string (in the graph we build, not Aho-Corasick) to the node of the graph corresponding to the nearest terminal in the suffix-link path;
  • The previous step will build all essential arcs plus some other arcs, but they do not affect the next step in any way;
  • Find the transitive closure of the graph.

To solve the second part of the problem one should use the Dilworth theorem. The way to restore the answer subset comes from the constructive proof of the theorem.

Time complexity is O(L + n3) to build the graph plus O(n3) to find the maximum antichain. The overall complexity is O(L + n3).

Congratulation to ikatanic — — the only participant to solve this problem during the contest. View his code 13851141 for further clarifications.

Challenge: solve the problem with the same asymptotic, if we are to find the subset with the maximum total length of all strings in it.

Read more »

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

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

Hello, dear participants of Codeforces community!

Starting from Codeforces Round #327 I'll be the new coordinator and will manage preparation process for all regular Codeforces rounds and other contests held on this platform. I'll do my best to increase the quality of contests we offer you, though Zlobober already raised this bar high. Let's cheer him once again, for all the great job he had done!

Tomorrow round will be held using the problems of Moscow team olympiad for high-school students. Do not be tricked by the word "school" — there will be a gold medalist of IOI 2015 participating and some candidates to this year Russian IOI team, meaning the level of the problems will be appropriate. I am sure everyone will find an interesting problem to enjoy.

The problemset was prepared by the team of Moscow authors (list is incomplete): Zlobober, romanandreev, _meshanya_, wilwell, glebushka98, timgaripov, thefacetakt, haku, Lhic, Timus, Sender, sankear, iskhakovt, andrewgark, masterOK, StopKran, AleX leaded by your humble servant GlebsHP and the chairman of the jury Helen Andreeva.

Special thanks to Delinur for translation and stella_marine for correction.

Five problems will be offered in both divisions and the scoring distribution will be announced later (good traditions should live).

UPD. Round time. Please note that Russia is not changing the timezone this night, while about 100 countries do so. Be sure to check when round starts in your timezone!

UPD2. Please note, that the distribution motivates you to read all the problems! Div1.: 750-1000-1250-1750-2500 Div2.: 500-1000-1750-2000-2250

UPD3. The results and the editorial will be published later, after the closing ceremony of the official competition.

UPD4. The system testing is over, results are now final. Feel free to upsolve and read other contestants code. Congratulations to Div. 1 top-5:

  1. Endagorion
  2. izrak
  3. sdya
  4. RAD
  5. -XRay-

UPD5. Problem analysis is now available.

Read more »

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

By GlebsHP, history, 3 years ago, In English,

Good evening Codeforces, let me briefly describe solutions for all problems of today's morning yandex algorithm round. Thanks everyone who participated, I apologize for making problems a bit too tough and viscous for a 100 minutes contest. Anyway, I hope everyone found something interesting.

I would like to thank lperovskaya for organising this competition and managing Yandex.contest, snarknews and sergeifedorov for their help with the problemset, endagorion, PavelKunyavskiy, AleX, glebushka98, gustokashin, map and boris for testing. Special thanks to gassa and my girlfriend Marina Kruglikova for fixing mistakes and disambiguations in English and Russian statements.

Let's get it started.

Problem A. Odysseus Sails Home.

There is no tricky idea behind this problem: one just needs to check if the vector (xf - xs, yf - ys) can be represented as a convex combination of vectors (xi, yi). One of the easiest approaches for the general case is to try all pairs of wind vectors and check if the target vector lies inside the cone they form. However, the devil is in the details. One shouldn't forget to:

  • Check if it's possible to get to Ithaca using only one wind direction;

  • Special if for case (xf, yf) = (xs, ys);

  • Ignore wind vectors (xi, yi) = (0, 0);

  • Avoid usage of doubles — everything fits in long long.

Time complexity: O(n2). O(n) solution also exists.

Problem B. Chariot Racing.

For the fixed value t = const we can easily calculate the intersection of all segments (chariots) as max(0, min(bi + vi * t) - max(ai + vi * t)). The problem was to find maximum for t ≥ 0.

Both min(bi + vi * t) and max(ai + vi * t) are convex functions. min(bi + vi * t) is concave upward, because it's derivative only decreases, as faster chariots overtake slower one. Similar max(ai + vi * t) is convex down. This means function min(bi + vi * t) - max(ai + vi * t) is concave upward, and this, in turn is sufficient condition for applying ternary search.

Ternary search is enough to solve the problem, but the solution which does binary search on derivative is faster and more stable. We need to find the maximum t such that the chariot i with minimum bi + vi * t goes faster then the chariot j with maximum aj + vj * t.

The only special case (for some solutions only) was n = 1.

Time complexity: O(n·logMaxC).

Problem C. Equality and Roads.

First check if the graph is connected. If no, print <<\t{NO}>> for all queries.

For connected graph count the number of connected components if only 0-edges are allowed (denote it as a) and the number of connected components if only 1-edges are allowed (denote it as b). Then, for the given x it's possible to construct the desired span if and only if condition b - 1 ≤ x ≤ n - a holds.

Lets proof the above statement. It's pretty obvious that this condition is necessary, but the sufficiensy isn't that clear. In my opinion, the easiest way is to present the algorithm. It consists of five steps:

  1. Create DSU, add all 1-edges.

  2. Add all 0-edges, remember which of them caused joins. There will be b - 1 such edges.

  3. Clear the DSU, add all 0-edges remembered on step 2.

  4. Add 0-edges until there are exactly x of them in the current span.

  5. Add 1-edges until the graphs becomes connected. That will always happen because of the step 1 and 2.

Time complexity: O(n).

Problem D. Sequences of Triangles.

Thanks to snarknews — the author and developer of this problem.

Let f(x) be the longest sequence that ends on the triangle with the hypotenuse of length x. If we generate all Pithagorean triples with a, b, c ≤ L the dynamic programming approach will be the one that is easy to implement here.

Exhaustive description of the generation process and Euclid's formula could be found here, I would like to skip copying it to analysis.

Problem E. Strong Squad.

Thanks to sergeifedorov — the author of this problem.

Perimeter p is equal to 2·(h + w), where h is the number of rows and w is the number of columns in the resulting rectangle. Build a bipartite graph on rows and columns where there is an edge connecting row x to column y if and only if soldier(x, y) = 0. What we should find now is the maximum independent set, such that in both set of rows and set of columns there is a least one vertex chosen (we are not allowed to choose rectangles 0 × m or n × 0).

The [well-known fact](https://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_(graph_theory)) (yes, just say that the fact is well-known if you don't want to proove it) is that the size of the maximum independent subset in bipartite graph is equal to |V| + |U| - ν(G), where ν(G) stands for the maximum matching. To meet the condition that there should be at least one vertex chosen in both parts we should:

  1. Try all the available pairs;

  2. Exclude vertices already connected to chosen pair;

  3. Find maximum matching.

Time complexity: O((nm)2·min(n, m)) or O(n5) for the worst case n = m. Is reduced to O(n4.5) by using Dinic's algorithm.

About Time Limit: though for n = m = 100 the number of operations will be about C·1010, C seems to be pretty small. We can show that comes from the fact that the worst case is then only half of the cells is filled with zeroes. Also at least comes from the Kuhn's algorithm itself. The actual timing for the most straightforward Kuhn was about 2.5 from 5 seconds TL. Any optimisations sped it up to less than 1 second.

Problem F. Lexicographically Smallest String.

We want to pick up two indices and revert corresponding substring to make the resulting string as small as possible. To start with let's reduce a degree of freedom from 2 to 1.

Statement 1. If we represent string S as S = c + S' and character c is not greater than any character in S', than Answer(S) = c + Answer(S'). Otherwise, the answer always reverts some prefix.

Proof. Assume Answer(S) < c + Answer(S'), that means we should revert some prefix of S, i.e. some substring (1, i). If we revert substring (2, i), the length of the prefix that consists of only c will increase, and the result will become lexicographically smaller. Assumption is incorrect. If c is greater than some character os S' it's obvious we should revert some prefix that ends at position with the smallest possible character.

Now we need to solve the following task: revert some prefix of the string S to make it as small as possible. First, we need to take a look at string Sr and it's suffixes. We will call two suffixes strongly comparable if none of them is a prefix of another. Similary, we will say that one suffix is strongly lesser or strongly greater than another, if they are strongly comparable and the corresponding inequality holds for classiс comparison.

Statement 2. If S = A + B = C + D and Ar is strictly lesser than Cr than Ar + B is stricly lesser than Cr + D. Proof: obvious.

From statement 2 it follows that we should only consider suffixes of Sr that are greater than any other suffix they are strictly comparable to. From definition of strict comparison it comes out all the remaining suffixes are prefixes of the longest one remaining. We can try to revert them all and choose the best, but this may be too slow.

From the string theory and prefix-function algorithm we know, that if the longest suffix of the string S' that is equal to it's prefix has length l than S' = w + w + ... + w + w', where w' is prefix of w and w has length n - l.

Statement 3. If we present the longest suffix S' that is not majorated by any other suffix in the above form, than the set of other not majorated suffixes will be equal to the set of suffixes of S' that have the form w + w + ... + w + w'.

Proof. If the string w is not prime, than there exists some suffix of S' of length more than n - |w| that is not striclty lesser than S', but this contradicts to the way we found w. That means the string w is prime and only suffixes of form w + w + ... + w + w' are not strictly comparable to S'.

Statement 4. If |A| = |B| then A + A + C < A + C + B < C + B + B or A + A + C > A + C + B > C + B + B or A + A + C = A + C + B = C + B + B for any string C.

Proof. Compare strings A + C and C + B. The result of this comparison will determine the case, as we could always change A + C to C + B or vice versa.

Applying the statement 4 to the case where C = w', A = w, B = wr we conclude that we should only try to revert the longest and the shorest prefix of S such that corresponding suffixes of Sr are not strongly greater than any other suffix of Sr.

To find those suffixes of Sr one should perform Duval's algorithm to find Lindon decomposition of the string Sr. We are interested in the last prime string in the decomposition and the last pre-prime string in algorithm's workflow (or the last prime for the string S + #, where # is some character striclty smaller than any other character in S as was mentioned in comments by Al.Cash.

Time complexity: O(|S|).

Read more »

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

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

Доброго времени суток, уважаемые пользователи Codeforces!

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

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

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

Призеры отборочного этапа олимпиады никаких льгот не имеют — поступить не выходя из дома всё-таки не получится.

Более подробную информацию об олимпиаде вы можете найти по приведённой выше ссылке. Любые оставшиеся вопросы смело задавайте в комментариях.

P.S. Тех, кто будет в комментариях обсуждать решения задач, ждёт справедливое возмездие и отрицательная карма!

UPD: добавлены две новые задачи, больше задачи добавляться не будут.

UPD2: Почти наверное традиционного продления олимпиады не будет. Планируется пригласить порядка 400 участников. Обратите внимание, сейчас для попадания в топ-400 требуется набрать совсем немного баллов. Жюри рекомендует прочитать все задачи — почти в каждой имеются простые группы с немалым количеством баллов.

Read more »

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

By GlebsHP, 4 years ago, In English,

In the clarification during just finished 222 round it has been announced that this round is going to be rated for both divisions, however, div1 coders are able only to register for "out of competition" participation. Is it a mistake or the concept has changed?

It'll be a little unfair to make the last round of the old year div2-only :)

Read more »

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

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

Hello everybody!

Today's round will be held by SergeiFedorov and me. We have done our best to make it diverse (different task complexity and themes) and rated (we know it's important). Your questions, wishes and constructive criticism (destructive we already can do :-)) leave in comments.

The contestants will plunge into the cold February of Nvodske and will be to help one's friends to survive the cold. Just imagine all responsibility!)

On this occasion I would like to thank all Codeforces team for the great job, they are doing, Artem Rakhov (RAD) for his help in task preparations, Maria Belova (Delinur) for problems translation, my mom, my dad, our soundman and Tuscany winemakers, for us didn't fall ill while preparing this round.

Distribution will be something like:

div. 1: 500-500-1000-1500-3000 (yeah, it really costs 3000)

div. 2: 500-1000-1500-1500-3000

Good luck & have fun!

Read more »

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

By GlebsHP, 8 years ago, In Russian,
Mike, как вы относитесь к идее создать на codeforces базу со всеми известными пользователям алгоритмами?
Конечно, такие базы уже существуют, но они все обладают разными недостатками, здесь же можно было бы соорудить базу, в которую каждый может добавлять новые алгоритмы, давать советы по использованию уже имеющихся, делать какие-то поправки и замечания, давать свои коды и подсказывать задачи на эти алгоритмы.
Уверен, что пользователям есть чем поделиться!

Read more »

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