Thanks everybody for participating. Tasks follow in the order of the original contest (the mirror order is given in the brackets).

562A - Logistical Questions

(in mirror: 566C - Logistical Questions)

Let's think about formal statement of the problem. We are given a tricky definition of a distance on the tre: ρ(a, b) = dist(a, b)^1.5. Each vertex has its weight w_i. We need to choose a place x for a competition such that the sum of distances from all vertices of the tree with their weights is minimum possible: f(x) = w₁ρ(1, x) + w₂ρ(x, 2) + ... + w_nρ(x, n).

Let's understand how function f(x) works. Allow yourself to put point x not only in vertices of the tree, but also in any point inside each edge by naturally expanding the distance definition (for example, the middle of the edge of length 4 km is located 2 km from both ends of this edge).

Fact 1. For any path in the tree the function ρ(i, x) is convex. Actually, the function dist(i, x) plot on each path [a, b] looks like the plot of a function abs(x): it first decreases linearly to the minimum: the closes to i point on a segment [a, b], and then increases linearly. Taking a composition with a convex increasing function t^1.5, as we can see, we get the convex function on any path in the tree. Here by function on the path we understand usual function of a real variable x that is identified with its location on path x: dist(a, x). So, each of the summands in the definition of f(x) is convex on any path in the tree, so f(x) is also convex on any path in the tree.

Let's call convex functions on any path in the tree convex on tree. Let's formulate few facts about convex functions on trees.

Fact 2. A convex function on tree can't have two different local minimums. Indeed, otherwise the path between those minimums contradicts the property of being convex on any path in the tree.

So, any convex function f(x) on the tree has the only local minimum that coincides with its global minimum.

Fact 3. From each vertex v there exists no more than one edge in which direction the function f decreases. Indeed, otherwise the path connecting two edges of function decrease would contradict the definition of a convex function in a point v.

Let's call such edge that function decreases along this edge to be a gradient of function f in point x. By using facts 2 and 3 we see that in each vertex there is either a uniquely defined gradient or the vertex is a global minimum.

Suppose we are able to efficiently find a gradient direction by using some algorithm for a given vertex v. If our tree was a bamboo then the task would be a usual convex function minimization that is efficiently solved by a binary search, i. e. dichotomy. We need some equivalent of a dichotomy for a tree. What is it?

Let's use centroid decmoposition! Indeed, let's take a tree center (i. e. such vertex that sizes of all its subtrees are no larger than n / 2). By using fact 3 we may consider the gradient of f in the center of the tree. First of all, there may be no gradient in this point meaning that we already found an optimum. Otherwise we know that global minimum is located in a subtree in direction of gradient, so all remaining subtrees and the center can be excluded from our consideration. So, by running one gradient calculation we reduced the number of vertices in a considered part of a tree twice.

So, in runs of gradient calculation we almost solved the problem. Let's understand where exactly the answer is located. Note that the global optimum will most probably be located inside some edge. It is easy to see that the optimum vertex will be one of the vertices incident to that edge, or more specifically, one of the last two considered vertices by our algorithms. Which exactly can be determined by calculating the exact answer for them and choosing the most optimal among them.

Now let's calculate the gradient direction in a vertex v. Fix a subtree u_i of a vertex v. Consider a derivative of all summands from that subtree when we move into that subtree. Denote this derivative as der_i. Then, as we can see, the derivative of f(x) while moving from x = v in direction of subtree u_i is  - der₁ - der₂ - ... - der_i - 1 + der_i - der_i + 1 - ... - der_k where k is a degree of vertex v. So, by running one DFS from vertex v we may calculate all values der_i, and so we may find a gradient direction by applying the formula above and considering a direction with negative derivative.

Finally, we got a solution in .

562B - Clique in the Divisibility Graph

(in mirror: 566F - Clique in the Divisibility Graph)

Order numbers in the sought clique in ascending order. Note that set X = {x₁, ..., x_k} is a clique iff for (1 ≤ i ≤ k - 1). So, it's easy to formulate a dynamic programming problem: D[x] is equal to the length of a longest suitable increasing subsequence ending in a number x. The calculation formula: for all x in set A.

If DP is written in "forward" direction then it's easy to estimate the complexity of a solution. In the worst case we'll process transitions.

562C - Restoring Map

(in mirror: 566E - Restoring Map)

Let's call a neighborhood of a vertex — the set consisting of it and all vertices near to it. So, we know the set of all neighborhoods of all vertices in some arbitrary order, and also each neighborhood is shuffled in an arbitrary order.

Let's call the tree vertex to be internal if it is not a tree leaf. Similarly, let's call a tree edge to be internal if it connects two internal vertices. An nice observation is that if two neighborhoods intersect exactly by two elements a and b then a and b have to be connected with an edge, in particular the edge (a, b) is internal. Conversely, any internal edge (a, b) may be represented as an intersection of some two neighborhoods С and D of some two vertices c and d such that there is a path c – a – b – d in the tree. In such manner we may find all internal edges by considering pairwise intersections of all neighborhoods. This can be done in about n³ / 2 operations naively, or in 32 times faster, by using bitsets technique.

Note that knowing all internal edges we may determine all internal vertices except the only case of a star graph (i. e. the graph consisting of a vertex with several other vertices attached to it). The case of a star should be considered separately.

Now we know the set of all leaves, all internal vertices and a tree structure on all internal vertices. The only thing that remained is to determine for each leaf, to what internal vertex is should be attached. This can be done in following manner. Consider a leaf l. Consider all neighborhoods containing it. Consider a minimal neighborhood among them; it can be shown that it is exactly the neighborhood L corresponding to a leaf l itself. Consider all internal vertices in L. There can be no less than two of them.

If there are three of them or more then we can uniquely determine to which of them l should be attached — it should be such vertex from them that has a degree inside L larger than 1. If there are exactly two internal vertices in L (let's say, a and b), then determining the attach point for l is a bit harder.

Statement: l should be attached to that vertex among a, b, that has an internal degree exactly 1. Indeed, if l was attached to a vertex with internal degree larger than 1, we would have considered this case before.

If both of vertices a and b have internal degree — 1 then our graph looks like a dumbbell (an edge (a, b) and all remaining vertices attached either to a or to b). Such case should also be considered separately.

The solution for two special cases remains for a reader as an easy exercise.

562D - Restructuring Company

(in mirror: 566D - Restructuring Company)

This problem allows a lot of solution with different time asymptotic. Let's describe a solution in .

Let's first consider a problem with only a queries of second and third type. It can be solved in a following manner. Consider a line consisting of all employees from 1 to n. An observation: any department looks like a contiguous segment of workers. Let's keep those segments in any logarithmic data structure like a balanced binary search tree (std::set or TreeSet). When merging departments from x to y, just extract all segments that are in the range [x, y] and merge them. For answering a query of the third type just check if employees x and y belong to the same segment. In such manner we get a solution of an easier problem in per query.

When adding the queries of a first type we in fact allow some segments to correspond to the same department. Let's add a DSU for handling equivalence classes of segments. Now the query of the first type is just using merge inside DSU for departments which x and y belong to. Also for queries of the second type it's important not to forget to call merge from all extracted segments.

So we get a solution in time.

562E - Max and Min

(in mirror: 566G - Max and Min)

Consider a following geometrical interpretation. Both Max and Min have a set of vectors from the first plane quadrant and a point (x, y). During his turn Max may add any of his vectors to a point (x, y), and Min — may subtract any of his vectors. Min wants point (x, y) to be strictly in the third quadrant, Max tries to prevent his from doing it. Denote Max vectors as Mx_i and Min vectors as Mn_j.

Consider a following obvious sufficient condition for Max to win. Consider some non-negative direction in a plane, i. e. such vector (a, b) that a, b ≥ 0 and at least one of numbers a, b is not a zero. Then if among Max vectors there is such vector Mx_i, that it's not shorter than any of Min vectors Mn_j along the direction (a, b) then Max can surely win. Here by the length of vector v along a direction (a, b) we mean a scalar product of vector v and vector (a, b).

Indeed, let Max always use that vector Mx_i. Then during the turns of Max and Min point (x, y) is shifted by a vector Mx_i - Mn_j for some j, so its overall shift along the vector (a, b) is equal to ((Mx_i - Mn_j), (a, b)) = (Mx_i, (a, b)) - (Mn_j, (a, b)) ≥ 0. By observing that initially the scalar produt ((x, y), (a, b)) = ax + by > 0 we see that at any moment ax + by will be strictly positive. This means that Min won't be able at any moment to make x and y both be negative (since it would mean that ax + by < 0).

Now let's formulate some kind of converse statement. Suppose Max vector Mx_i lies strictly inside the triangle formed by Min vectors Mn_j and Mn_k. In particular, vector Mx_i endpoint can't lie on a segment [Mn_j, Mn_k], but it may be collinear one of vectors Mn_j and Mn_k.

Note that since Mx_i lies strictly inside the triangle formed by vectors Mn_j and Mn_k it can be extended to a vector Mx'_i, whose endpoint lies on a segment [Mn_j, Mn_k]. By using linear dependence of Mx'_i and Mn_j, Mn_k we have that Mx'_i = (p / r)Mn_j + (q / r)Mn_k, where p + q = r and p, q, r — integer non-negative numbers. This is equivalent to a formula rMx'_i = pMn_j + qMn_k. This means that if per each r turns of Max in Mx_i we will respond with p turns of Min in Mn_j and q turns of Min in Mn_k, then the total shift will be equal to  - pMn_j - qMn_k + rMx_i =  - rMx'_i + rMx_i =  - r(Mx'_i - Mx_i), that is the vector with strictly negative components. So, we are able to block that Max turn, i. e. it does not give any advantage to Max.

The natural wish is to create a convex hull of all Min turns and to consider all Max turns in respect to it. If Max turn lies inside the convex hull of Min turns, then by using the previous fact this turn is meaningless to Max. Otherwise, there are two possibilities.

First, this turn may intersect the hull but go out of it somewhere; in this case this Max turn is no shorter than all Min turns in some non-negative direction (more specifically, in its own direction), so Max wins.

On the other hand, Max vector lies to aside from the Min turns convex hull. Let's suppose the vector Mx_i lies to the left of the Min turns. This case requires a special analysis. Consider the topmost of the Min vectors Mn_j. If Mx_i is no lower than Mx_j, then by using the first fact Max is able to win by using only this vector. Otherwise the difference Mn_i - Mx_j is a vector with strictly negative components, by using which we are able to block that Max vector.

So, the full version of a criteria for Min being a winner looks like the following. Consider a convex hull of Min turns and expand it to the left of the topmost point and to the bottom of the rightmost point. If all Max turns lie strictly inside the formed figure then Min wins, otherwise Max wins.

562F - Matching Names

(в трансляции: 566A - Matching Names)

Form a trie from all names and pseudonyms. Mark with red all vertices corresponding to names, and with blue all vertices corresponding to the pseudonyms (a single vertex may be marked several times, possibly with different colors). Note that if we match a name a and a pseudonym b, then the quality of such match is lcp(a, b) = 1 / 2(2 * lcp(a, b)) = 1 / 2(|a| + |b| - (|a| - lcp(a, b)) - (|b| - lcp(a, b))), that is equal to a constant 1 / 2(|a| + |b|), with subtracted half of a length of a path between a and b over the trie. So, what we need is to connect all red vertices with blue vertices with paths of a minimum possible total length.

This can be done with a following greedy procedure: if we have a vertex v with x red vertices and y blue vertices in its subtree then we must match min(x, y) red vertices of its subtree to min(x, y) blue vertices of its subtree and leave the remaining max(x, y) - min(x, y) ref or blue vertices to the level higher. The correctness of such algorithm may be easily shown by the next idea. Give each edge of each path a direction from a red vertex to a blue. If some edge recieves two different directions after this procedure, we may cross-change two paths through it so that their total length is reduced by two.

So, we get a solution in O(sumlen) where sumlen is a total length of all names and pseudonyms.

562G - Replicating Processes

(в трансляции: 566B - Replicating Processes)

==== UNTRANSLATED SECTION, PLEASE WAIT A FEW MINUTES... ====

Kitten to take your attention :)

This problem may be solved by simulating the replication process. Let's keep a list of all replications that may be applied by the current step. Apply an arbitrary replication, after that update a list by adding/removing all suitable or now unsuitable replications touching all affected on current step servers. The list of replications may be kept in a "double-linked list" data structure, that allows to add and remove elements to/from the set and to extract an arbitrary element of the set in O(1).

The proof of correctness of such algorithm is not hard and is left as an exercies (maybe it will appear here later).

We got a solution in O(n) operation (though, the constant hidden by O-notation is pretty large; the input size is already 12n numbers and the solution itself hides a constant 36 or higher).

The registrations before 00:00 have been deleted, because the form didn't support teams. Please, register again if your registration has been affected.

VK Cup 2015 Final Round has ended two days ago. It's very likely that you've seen our previous posts. The last event to happen is online mirror of the final round. It will be held on Thursday, July 30th, at 19:00 Moscow time. Individual contestants as well as teams consisting of two people may participate in this round. Round duration is three hours, problems will be shuffled in comparison with to the original order. Both division participants may take part, but we want to warn 2nd division contestants that problemset may be hard for them. This round is a rated Codeforces round.

Finally, we want to thank all people that made this Championship. Following VK developers, Codeforces team members and the other people suggested their help to us while creating and preparing problems: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Kurpilyansky, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. We want to thank the people that helped us very much by testing our rounds and giving great advices: winger и AlexFetisov. Also we want to say thank you to all VK members that helped us to run the onsite Finals: burunduk3, Burunduk2, KOTEHOK and many others. Thank to all of them!

Good luck and have fun on our Online Mirror!

UPD: Note that during the round the team is allowed to use only one computer. This means that you may code/use console/succeed in solving problems in any other manner by using only one computer at time. The only thing that is allowed from two computers is reading the statements.

UPD2: Since this is a team contest, specially for your convenience we publish the encryped zip-archive with pdf-statements of problems: vkcup2015-mirror-statements.zip. When round starts, we'll publish a password for it.

UPD3: The round will use the dynamic scoring with 250 points step.

UPD4: Due to technical reasons the round starts at 19:20 Moscow time.

UPD5: Password for statements archive: vkcup4ever. Good luck!

UPD6: Online mirror has ended! Congratulations to winners:

1. rng_58
2. Zenith: I_love_Hoang_Yen, ngfam_kongu
3. OrOrZZZ!: zld3794955, KFDong
4. Petr team: Petr, ilyakor
5. jcvb_matthew99: matthew99, jcvb

Also, my personal respects for a team "Petr team: Petr, ilyakor" for only solution for a problem Е in this mirror, user rng_58 and a team "Excited: YuukaKazami, jqdai0815" for two correct solutions for problem С.

Congratulations to a user rng_58 that showed that a single contestant can compete with teams consisting of two people!

Rating will be updated shortly.

UPD7: Editorial!

VK Cup 2015 завершен! Это было что-то невероятное — частая смена лидеров, тяжелый ход контеста фаворита, посылки топовых команд на последних секундах!

Сегодня же вечером в торжественной обстановке в зале "Толстой" отеля Кортъярд Марриотт были подведены результаты.

• 1 место: команда из ИТМО в составе Геннадия «tourist» Короткевича и Нияза «niyaznigmatul» Нигматуллина — Чемпионы VK Cup 2015 и приз в 1048576 рублей,
• 2 место: команда из ИТМО в составе Адама «subscriber» Бардашевича и Бориса «qwerty787788» Минаева — приз в 524288 рублей,
• 3 место: команда из ИТМО в составе Ивана «Belonogov» Белоногова и Ильи «izban» Збаня — приз в 262144 рублей,
• 4 место: команда из Нижегородского ГУ в составе: Владислав «vepifanov» Епифанов (ННГУ) и Николай «KAN» Калинин
• 5 место: команда из Уральского ФУ в составе Ильи «KuchumovIlya» Кучумова и Олега «Merkurev» Меркурьева
• 6 место: команда из Московского ГУ в составе: Василия «SirShokoladina» Мокина и Глеба «GlebsHP» Евстропова
• 7 место: команда из Уральского ФУ в составе Алексея «Um_nik» Данилюка и Никиты «sivukhin» Сивухина
• 8 место: команда из МФТИ в составе Михаила «Endagorion» Тихомирова и Александра «map» Машрабова

Команды с 4-го по 8-е места завоевали призы в размере 131072 рублей! Все участники финала получили ценный подарок и сертификат финалиста.

Вот несколько фотографий с закрытия соревнования.

VK Cup 2015 - Finals состоится уже сегодня! Мы желаем удачи всем участникам, а болельщикам — насладится интересным соревнованием.

Лучшие 20 команд по результатам серии отборов собрались в Санкт-Петербурге, чтобы встретиться в финале и побороться за титул Чемпиона и солидный призовой фонд:

• 1 место — 1048576 рублей,
• 2 местo — 524288 рублей,
• 3 местo — 262144 рубля,
• 4-8 места — 131072 рубля.

Болеть за команды можно будет по ссылке http://codeforces.net/spectator/contest/562/standings, которая будет доступна после старта соревнования.

Удачи! Желаем только положительных эмоций. На старт! Внимание! ...

Hi everybody!

Yesterday, on July 24th, we started VK Cup 2015 Finals! During the day all participants of the competition successfully went to the St. Petersburg, those who got here earlier enjoyed a great trip over the roofs of this beautiful city. And now we are waiting for a practice round that will happen in a few hours, giving participants an option to test their contest environment and do their best while solving several usual (and not only usual) problems. After the lunch, contestants will compete in the first round of the Finals that is called CodeGame Coding, where they have to write the strategy for a battle wizard.

During today and tomorrow not all of the Codeforces features will be available. On this weekend you may take a rest from writing contests and enjoy the results of the one of the biggest competitions of 2015.

The results of the practice round will be available for spectators by this link. Stay tuned!

This Sunday, May 3-rd, 19:00 Moscow Time there will be Round 3 of VK Cup 2015 Championship!

As in Round 2, there will also be an online mirror that is rated round available only for Div1-contestants. There will be 6 task in random order and a smooth dynamic scoring system.

Round was brought to you by Codeforces team, VK team and yeputons. As usual, we want to thank winger and AlexFetisov for a great testing help.

Top-50 participants of online mirror will get a nice VK Cup T-Shirt!

Good luck and have fun!

UPD1 The round is over! Congratulations to all contestants in top-50, you will get a nice VK Cup 2015 Championship T-Shirt soon! There will be an editorial soon, stay tuned...

UPD2 Finally, the editorial is ready!

April 18, 18:00 (UTC) the second Wild-card round of VK Cup 2015 will take place.

Participants are invited to achieve progress in solving an unusual problem. VK Cup teams which were advanced to the Round 2 (and didn't advance to the Round 3) will take part in VK Cup 2015 - Wild Card Round 2 officially. In addition, this round will be open to the public for unofficial participation for everybody. Registration will be open for the whole round duration.

The round will be one week long. After the end latest submission (with positive score) of each participant will be judged on system tests.

Good luck!

UPD.: System testing is done. Final tests are available by link: http://assets.codeforces.com/files/vkcup-2015-wildcard-2-tests.2.zip

You can appeal on tests and their answers until April, 28th, 23:59:59. After that we will finalize the results. After finalizing all found bugs will not affect the final standings.

This Friday, April 17th, 19:00 there will be Round 2 of VK Cup 2015! For all unofficial participants there will be an online mirror that is a usual rated div1-round. Any div1 contestant that does not participate in official Round 2 is able to compete in this mirror.

Round consists of 6 problems that are shuffled randomly. There will be a smooth dynamic scoring system.

Round is brought to you by Codeforces team, VK team and user Errichto, that offered his important help as a part of his donation for "Codeforces 5 years campaign". Significant testing effort was made by user winger.

Good luck and have fun!

UPD: Thanks everybody for participating! Editorial has just appeared. See you on Wild-card Round 2 and mirror of Round 3!

This round features Picat, a language somewhat similar to Prolog. We tried to make most of our problems convenient to solve using declarative approach.

The traditional A+B program (A and B are space-separated) looks as follows:

main =>
  A = read_int(),
  B = read_int(),
  C = A + B,
  println(C).

The main source of information about language is http://picat-lang.org/ The contest uses version 0.9.

В субботу, 21-го марта, в 17:00 будет дан старт Раунду 1 чемпионата по программированию VK Cup 2015! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.

В этом раунде могут принять все те команды, которые прошли квалификацию. Напомним, что из первой квалификации допущены все те команды, что набрали не менее 1500 баллов. Таких оказалось 789. Вторую квалификацию прошли 504 команды, все те, что набрали не менее 1850 баллов. Таким образом, принять участие в Раунде 1 могут 1293 команды!

Участников ждет соренование по правилам классических раундов Codeforces с некоторыми адаптациями:

• задачи будут исключительно на русском языке (в отличие от интернет-трансляции, где будут и на английском);
• в Раунде 1 будут участвовать команды по 1 или 2 человека, разрешается любая коммуникация внутри команды, но какое-либо общение с другими лицами по прежнему, конечно, запрещено;
• каждая команда может использовать один или более компьютеров по своему усмотрению (напомним, что в Финале команде будет дана возможность использовать только один компьютер);
• для членов команды рейтинг будет пересчитан одинаково, исходя из рейтинга команды (учитываются зарегистрированные на раунд члены команды), о подсчете рейтинга команды можно почитать здесь.

Участников ждет обновленная динамическая стоимость задач (смотрите пост), теперь более плавная, с шагом в 250 баллов.

Отметим, что сразу после окончания Раунда 1 будет проведена интернет-трансляция, поэтому просим участников воздержаться до ее окончания от публичных обсуждений, распространения информации о задачах, идеях и даже ходе соренования.

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

Желаем удачи и интересной борьбы!

UPD.: Раунд закончен, спасибо за проявленный интерес. Раунд получился динамичным, жюри с интересом следили за ходом соревнования. Поздравляем победителей и напоминаем, что лучшие 400 команд (т.е. те, кто набрал не менее 796 баллов) получают приглашение в Раунд 2. Остальным еще рано расстраиваться, ведь через неделю вас ждет Вайлд-кард 1, по результатам которого будут разыграны еще 50 приглашений в Раунд 2.

523A - Rotate, Flip and Zoom

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

for i = [0...2*a-1] begin
  for j = [0...2*b-1] begin
    print(a[i / 2][j / 2])
  end
  вывести перевод строки
end

Пример решения: 10286345.

523B - Mean Requests

Подсчет приближенного среднего подробно описан в условии задачи (даже приведен псевдокод). В самом деле при его подсчете надо было просто следовать описанным правилам подсчета.

Для подсчета среднего на отрезках длины T достаточно знать значение суммы элементов на отрезках длины T (для получения среднего надо просто значение суммы делить на T). Если это делать наивным способом, подсчитывая сумму каждый раз в цикле заново, то получается неэффективный медленный алгоритм. В самом деле, при T = n / 2 и наборе из m = n запросов n / 2 + 1, n / 2 + 2, ..., n такой алгоритм суммарно выполнит около n² / 4 действий. Для заданного максимального значения n эта величина будет слишком большой для вычисления в 4 секунды.

Для ускорения подсчета суммы на отрезках длины T можно либо поддерживать эту сумму, тогда при перемещении старта такого отрезка с индекса i на индекс i + 1 сумма изменяется следующим образом: sum:  = sum - a[i] + a[i + T]. Таким образом, пересчет суммы от предыдущего положения старта отрезка до нового будет работать за одну формулу (ограниченное сверху некоторой константой количество действий).

Второй вариант как быстро находить суммы на отрезках состоит в подсчете вспомогательного массива частичных сумм. Пусть b[i] — сумма первых i элементов массива a. Тогда сумма элементов массива a на отрезке от l до r равна b[r + 1] - b[l] (если массив a 0-индексирован). Подсчет массива b можно осуществить за один проход слева направо по формуле b[i] = b[i - 1] + a[i - 1].

Пример решения: 10291184.

523C - Name Quest

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

Посчитаем две позиции:

• такую минимальную позицию l, что подстрока t[1..l] хорошая, тогда очевидно, что любой разрез за позицией l будет таким, что левая часть "хорошая",
• такую максимальную позицию r, что подстрока t[r..|t|] хорошая, тогда очевидно, что любой разрез перед позицией r будет таким, что правая часть "хорошая".

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

j := 1
for i := 1 to |t|
    if j <= |s| && s[j] == t[i]
        j = j + 1
        if j = |s| + 1
            l := i

Для того, чтобы после разреза обе части содержали s необходимо и достаточно, чтобы разрез проходил между l и r. Таким образом, ответ равен r - l или 0, если l или r не нашлось или r < l.

523D - Statistics of Recompressing Videos

Для эффективной реализации алгоритма моделирования процесса необходимо хранить в какой-то структуре h отсортированные моменты освобождения каждого из серверов. Сначала h состоит k единиц.

Будем обрабатывать ролики последовательно в хронологическом порядке. Для того, чтобы начать обрабатывать очередной i-й надо дождаться освобождения какого-либо сервера. Пусть ролик приходит в момент s_i и имеет длительность t_i.

Очевидно, что можно ждать освобождения до первого из моментов из h (так как первый — минимальный). Возможно, что дожидаться в явном виде и не надо, так как сервер уже освобождается к моменту s_i, в любом случае можно считать, что ролик надо отправить на первый из серверов, который освободиться. Пусть минимальный элемент из h равен h₀, тогда ролик начнется обрабатываться в момент max(h₀, s_i), а закончит к моменту max(h₀, s_i) + t_i. Для поддержания структуры h надо исключить из нее h₀ и добавить max(h₀, s_i) + t_i. Таким образом, в h по прежнему будут все моменты освобождения серверов.

Для того, чтобы решения быстро работали, h надо хранить в подходящей структуре данных. Это может быть очередь с приоритетами (тогда минимум будет в голове), либо в упорядоченном множестве. Так как в h могут быть равные элементы, то эта структура либо должна работать с одинаковыми элементами (как очередь с приоритетами или мультимножество по типу std::multiset в C++) или надо в структуре хранить пары (момент освобождения, номер сервера).

Кроме того в качестве h можно использовать классическую бинарную кучу или упорядоченный ассоциативный массив (TreeMap в Java).

Такое решение будет работать за .

Пример решения: 10290987. В этом решении в очереди с приоритетами q моменты хранятся со знаком минус, чтобы сортировка по-умолчанию ставящая максимум вперед, ставила вперед минимум.

14 марта в 18:00 начнется второй квалификационный раунд чемпионата VK Cup 2015!

Правила этого раунда будут совпадать с Квалификацией 1. К участию приглашаются те команды, кто не участвовал в Квалификации 1 или набрал менее 1500 баллов в ней.

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

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

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

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

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

Результаты раунда не будут влиять на рейтинг. Уже прошедшие в Раунд 1 команды, могут участвовать в Квалификации 2 вне конкурса. Они никак не влияют на отбор участников в Раунд 1, они могут участвовать только just for fun. Внеконкурсное участие тоже требует соблюдение всех правил, в случае нарушения команда может быть дисквалифицирована с Чемпионата.

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

522A - Reposts

Для решения этой задачи надо было проитерироваться по записям о репостах и поддерживать для каждого пользователя длину цепочки, которая заканчивается в нем. Здесь удобно воспользоваться ассоциативным массивом из строки (имени пользователя) в целое число (длину цепочки). Например, для С++ такой структурой данных будет просто map<string,int>. Назовем такую структуру chainLengths, тогда при обработки строки вида <<a reposted b>> надо просто выполнить присвоение chainLengths[a] = chainLengths[b] + 1. В качестве ответа надо вывести максимальное из значений chainLengths, что можно подсчитывать на лету.

Пара тонкостей: в начале надо занести chainLengths["polycarp"] = 1;, а всюду при работе со строками приводить их к нижнему регистру (или верхнему), чтобы сделать сравнение строк нечувствительным к регистру букв.

Пример такого решения: 10209456.

522B - Photo to Remember

В этой задаче для каждого i фактически надо было найти:

• W_i, равное сумме всех заданных w_j без w_i,
• и H_i, равное максимуму всех h_j без h_i.

Для подсчета первой величины достаточно найти сумму s всех значений w_j, тогда W_i = s - w_i.

Для подсчета второй величины достаточно заметить, что либо искомое значение есть просто максимум по h, либо (если h_i совпало с максимумом) это второй максимум (т.е. предпоследний элемент при сортировке по неубыванию). Второй максимум, как и максимум ищется за один проход по массиву.

В таком случае, для нахождения как W_i, так и H_i требуется O(1) действий, то есть O(n) суммарно на всё решение.

Пример решения: 10193758.

522C - Chicken or Fish?

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

Пусть массив b — это массив максимальных возможных количеств порций каждого из блюда на момент старта обслуживания Поликарпа. То есть просто массив b надо заинициализировать массивом a, а каждый раз, когда t_i отлично от 0, то делать b[t_i] = b[t_i] - 1 (уменьшать количество порций блюда). Кроме того, пусть unknown — это количество пассажиров, про которых неизвестно какие точно блюда им достались (то есть для них t_i = 0). Пусть величина unknownBeforeUpset — это такое же количество, но до первого недовольного.

Таким образом, есть два основных случая:

• недовольных пассажиров нет вообще, тогда блюдо i могло закончится тогда и только тогда, когда b[i] ≤ unknown (жадно отдаем это блюдо всем пассажирам, для кого их точное блюдо неизвестно),
• недовольный пассажир есть, этот случай разберем подробнее.

Каким блюдом мог быть недоволен первый из таких пассажиров? Очевидно из списка кандидатов надо выкинуть все такие блюда, которые упоминаются не раньше него (значит, что они закончится до него не могли). Из оставшегося набора блюд достаточно перебрать все блюда и проверить могли ли они закончиться до этого пассажира. То есть блюдо i могло быть тем блюдом, что привело в недовольство первого недовольного, если одновременно верно:

• это блюдо i не упоминается на этом пассажире или позже,
• это блюдо i такое, что b[i] ≤ unknownBeforeUpset.

Для всех таких блюд, очевидно, в ответе должно стоять Y (они могли закончится к Поликарпу). Кроме того, из всех таких блюд наибольшую степень свободы дает блюдо с наименьшим расходом (количеством порций b[i]). Выберем именно такое блюдо и в остаток пассажиров с неизвестным блюдом restUnknown = unknown - b[minFirstFinished] попробуем поместить все вхождения каждого из других блюд. То есть блюдо j могло закончится до Поликарпа тогда и только тогда, если для него b[j] ≤ restUnknown (то есть закончилось то блюдо, что расстроило первого из недовольных, а следом — j-е).

Такое решение работает за O(m + k).

Пример решения: 10212686.

522D - Closest Equals

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

Пройдем слева направо по массиву и составим новый массив b, записав в b[j] расстояние до ближайшего слева парного j-му элементу значения, то есть a[j - b[j]] = a[j]. Если такового нет, то запишем в ячейку бесконечность.

Эти значения соответствуют расстояниям между парными элементами и записаны они в позициях правых элементов в этих парах.

При рассмотрении запроса на отрезке [l, r] нам не нужны вообще такие пары, что начинаются левее l, а минимум надо искать среди пар, что заканчиваются не правее r.

Отсортируем все запросы по l слева направо. Тогда при прохождении по запросам можно поддерживать, что для запроса [l, r] в массиве b установлены бесконечности для всех пар, в которых левый элемент левее l. Для этого просто предподсчитаем для каждого элемента ближайший справа парный next[i] (то есть верно, что b[next[i]] = next[i] - i), и при покидании ячейки i будем записывать в b[next[i]] значение бесконечность.

В таком случае, для ответа на запрос [l, r] надо просто найти минимум на префиксе до индекса r включительно по массиву b. Это можно делать быстро разными способами (дерево отрезков, дерево Фенвика).

Асимптотическая временная сложность такого решения составляет .

Пример решения: 10192075.

Всем привет!

7 марта в 18:00 начнется первый квалификационный раунд чемпионата VK Cup 2015!

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

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

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

Чтобы пройти в Раунд 1, вам надо принять участие хотя бы в одной из квалификаций. Из каждой квалификации в Раунд 1 проходят все команды с положительным числом баллов, которые набрали не меньше баллов, чем команда на 500-ом месте.

Пользуясь случаем поздравляем всех девушек-участниц с праздником. Спасибо вам за весну!

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

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

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

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

Мы рады сообщить вам, что в этом году компания ВКонтакте совместно с площадкой Codeforces проведет обновленный VK Cup. Во многих IT-компаниях, в том числе и ВКонтакте, широко применяется практика парного программирования. VK Cup 2015 предлагает участникам попробовать именно такой формат, допуская к участию команды до двух человек. За призы и звание победителя приглашается побороться русскоязычным молодым специалистам, студентам, школьникам и просто любителям алгоритмов и программирования.

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

• 1 место — 1048576 рублей
• 2 местo — 524288 рублей
• 3 местo — 262144 рубля
• 4-8 места — 131072 рубля

Hi Codeforces!

The VK company (vk.com), the largest social network in Europe and the most popular site in Russia and Ukraine, announces the competition for russian-speaking programmers VK Cup 2015.

As you can see, the reborn VK Cup is focused on Russian-speaking programming lovers. Indeed, the whole VK developer team speaks Russian, most social network users communicate in Russian and the head office of the company is located in St. Petersburg. Those are the reasons we decided to concentrate on the competition for russian-speaking participants — most of the social network code is written by medal winners and ACM-ICPC finals champions. We believe that when we support the enthusiasm of young people towards solving problems and studying algorithms, that we make the world better and invest for the future of our company.

That is not the only innovation of the championship: unlike many other championships conducted by companies, VK Cup 2015 will have two-man teams competing with each other, the participants’ age ranges from 14 to 23 years.

Though we focus on the Russian-speaking participants, we are happy to share our problems and rounds with the participants from the whole world. For that reason, all problems of the championship will be translated into English and will be available to solve after the official championship rounds are over. Besides, in some rounds the participants from around the world can take part unofficially, side by side with the official championship contestants. We will be happy to give out 50 brand T-shirts of the Championship to the best out of competition unofficial participants of Round 3. We will be happy to see interest towards the problems of our championship!

VK Team