Keeping track of both Codeforces round and online team contest was a doozy, so this is only the best draft of the editorial I have. Missing problems will gradually be added, and existing explanations may improve over time. Hope you enjoyed the problems, and let me know if anything can be explained better!

UPD: okay, all of the problems are out, and most of the bugs are fixed (I hope). By the way, we had a nice discussion with Errichto on his stream about Div. 2 problems, which some of you may find more approachable. Be sure to check it out, as well as other stuff Errichto creates!

(Kudos to Golovanov399 for his neat grid drawing tool)

Hello, Codeforces community!

I'm glad to invite you to Codeforces Round #691 (Div. 1) and Codeforces Round #691 (Div. 2), which will be held on Dec/19/2020 12:35 (Moscow time). The round will be rated for both divisions.

The problems were taken (mostly) from the ByteDance — Moscow Workshops Online Contest, which is happening at the same time. They were prepared by me, AndreySergunin, and amethyst0. We are very thankful to the testers: low_, kalki411, ecnerwala, Tima, IITianUG, thenymphsofdelphi, mohammedehab2002, namanbansal013, Redux for their time and great feedback. Also big thanks to Bytedance instructors chenjb and jqdai0815 for testing and reviewing the Bytedance online contest.

ByteDance is a global technology company operating a range of platforms that allow people across languages, cultures and geographies to create, discover and connect. ByteDance has partnered with Moscow Workshops and Codeforces to organize a top tier and exclusive training camp for the International Collegiate Programming Contest. The upcoming Programming Camp will be held in Beijing from February 20th to 26th, 2021.

ByteDance — Moscow Workshops Online Contest is an opportunity to participate as teams in this camp.

You can find more information about this training camp, including registration and prizes at https://programcamp.bytedance.com/.

Important update: please be informed that the Bytedance online team contest ends 25 minutes after the Codeforces round does. For this reason, we ask you not to discuss the problems publicly during that time, until 3pm MSK. Code and testcases public display will also be disabled during that time. Thank you for your understanding.

Scoring distribution:

Div. 2: 750-1000-1500-2000-2500-3000

Div. 1: 500-1000-1500-2000-2250-3500

Final update: thanks for participating, hope you had fun! Let's hear it for the winners:

Div. 1 (the only contestants to solve 5 problems):

1. tourist
2. Um_nik
3. 142857
4. maroonrk
5. gop2024

Div. 2:

1. spepd — the only Div.2 contestant to solve 5 problems!
2. LebronDurant
3. diuven_fanclub
4. wk_tzc
5. CTP_314

Here's a (now complete) editorial.

Happy winter holidays to all of you, and see you again on the leaderboards!

Heya! I'm going to stream my performance during ICPC Challenge 2020 on my Youtube channel. I'm not great at marathon-style but I'll see what I can do.

I know this is a competition with prizes which you generally can not stream, but ICPC people seem to be okay with this (in fact this wasn't my idea in the first place), so there you go. I still feel a bit weird about this, so I won't try to explain anything I do (help yourself and try to read my code if you want lol). To make it a little less boring, I'm down to talk to everyone in the chat. Drop by and say hello! Unless you want to focus on the competition of course.

Also check out the official Day Zero stream. GL&HF!

Thank you for waiting! I hope you've enjoyed the problems. Let me know what you think in the comments!

UPD: I almost forgot but here are some notes, as well as challenges for all problems. For a lot of them I don't have a solution and would be happy to hear your ideas.

Hi!

On Jun/18/2020 17:45 (Moscow time) we will host Codeforces Global Round 8.

It is the second round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Problems for this round are set by me. Thanks a lot to the coordinator 300iq and testers thenymphsofdelphi, Lewin, Golovanov399, Osama_Alkhodairy, gamegame, dorijanlendvaj, HenriqueBrito, kocko, ruban, Origenes, Ilya-bar, rahulkhairwar. Their feedback was a huge help and affected the problemset greatly.

The round will have eight problems and will last 150 minutes.

Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000 — 3500 — 3000+1500

Good luck, and see you on the scoreboard!

UPD: the round has concluded, congratulations to the winners:

1. ecnerwala
2. tourist
3. Marcin_smu
4. Petr
5. Radewoosh
6. Um_nik
7. maroonrk
8. eatmore
9. snuke
10. KAN

Check current Codeforces Global series standings here (courtesy of aropan).

You can find the editorial here.

Stay tuned for prizes announcement!

How is self-isolation treating you? I recently found this channel with a guy solving Sudoku-like puzzles. Had a lot of fun trying to solve puzzles for myself, and then watching the pro do it ten times faster while explaining everything. That reminded me I didn't upload to my Youtube for a while, and gave a good impression of how things look from the other side.

So here's me solving an old AtCoder Regular Contest for practice. From my experience I can recommend trying to solve problems yourself before watching me do it. Wasn't in particular hurry this time, trying to explain my thoughts as good as I can. Let me know what you think, and enjoy!

UPD: Спасибо за участие! Топ-200 официальных участников отбора приглашены в Финал соревнования.

Поздравляем победителей!

Отбор Технокубка:

1. cookiedoth
2. MaksymOboznyi
3. AlFlen
4. talant
5. DANDROZAVR

Дивизион 1:

1. Benq
2. jqdai0815
3. tourist
4. Um_nik
5. TLE

Дивизион 2:

1. BBumblebee
2. twytch19
3. zhongyuwei
4. kpink
5. 1LLUS0RY

Разбор тут (если не загружается, надо немного подождать).

Разбалловка:

отбор: 500-750+750-1500-2000-2750-3250-3750

второй дивизион: 500-750+750-1500-2000-2750-3250

первый дивизион: 500-1000-1750-2250-2750-3250

Добрый день!

В 26.10.2019 14:05 (Московское время) состоится Отборочный Раунд 2 олимпиады для школьников Технокубок 2020. Раунд будет длиться два часа, участникам будут предложены 7 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация.

Зарегистрироваться на Отборочный Раунд 2 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

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

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

• короткое описание формата
• полное описание формата

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

A few people expressed interest in me answering some questions regarding competitive programming/problemsetting/related stuff. Since I have a bit of free time during these holidays, let's try this. I'll choose a few most interesting questions from comments under this post and try to answer them in a single video.

Ideally a question should not be to broad ("please give us some tips and tricks" is probably too broad) and possible to answer within a few minutes. I probably won't answer a question if it was asked a lot of times here on CF/quora/someplace else. Let's go!

On Oct/04/2018 10:05 (Moscow time), the Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) will start. This is a special round for the Hello Barcelona Programming Bootcamp, in collaboration with Moscow Workshops ICPC. It is rated for all participants, everybody can register on it regardless of a rating.

Hello Barcelona Programming Bootcamp is sponsored by VTB and Indeed Tokyo, with the addition of team sponsors Phaze Ventures, Spark Labs and REMY Robotics.

VTB, the largest international bank based in Eastern Europe, continues to be an official partner of the Hello Programming Bootcamp series, adding further quality to the 3rd edition of the Hello Barcelona Programming Bootcamp by bringing their own participants, as well as by supporting top teams from around the world.

Indeed Tokyo is Japan's branch of the #1 employment website in the world, giving job seekers free access to millions of jobs from thousands of company websites and job boards. As they sponsor for the second year in a row, Indeed continues to offer the best job opportunities to the boot camp participants.

Wish good luck to all the participants!

There will be 8 problems, common for both division. Score distribution: 500 750 1250 1500 1750 2250 2750 3000.

The problems are prepared by me, Arterm and GlebsHP, with assistance from 300iq, ifsmirnov and vintage_Vlad_Makeev. Have fun!

Всем привет! Сегодня, 13 марта в 21:00 MSK пройдет второй отборочный раунд Яндекс.Алгоритм 2018. Перетий в контест можно с сайта Алгоритма.

Задачи подготовлены мной, Михаилом Тихомировым. Я благодарю за помощь с подготовкой задач Глеба GlebsHP Евстропова, а также ifsmirnov, halyavin, kuzmichev_dima, scorpion за тестирование задач.

Всем удачи, увидимся на контесте!

Hi Codeforces!

The Codeforces Round #438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined) is going to be held on 05 Oct at 9:05 (UTC+2)! The round will be rated for everyone.

This round is organised in collaboration with 2nd Hello Barcelona ACM ICPC Bootcamp 2017 and supported by Sberbank, the biggest commercial and investment bank of Central and Eastern Europe, with over 175 years of history.

150 students from 53 universities, including ITMO, University of New South Wales, St. Petersburg State University, MIPT, Ural Federal University, Tomsk State University, Novosibirsk State University, Saratov State University, Samara National Research, Perm State University, and many other top global universities such as USA’s highest placing team, Central Florida University, along with Canada’s University of Waterloo, high-scoring Asian teams from Hangzhou Dianzi and Singapore, and Tokyo University, as well as Stockholm’s KTH, will be competing as individuals for the online round, which includes those of you from Codeforces!

The past week has been full of intense competitions, job interviews with Sberbank, and contest analysis and lectures by Andrey Stankevich (andrewzta), Mike Mirzayanov (MikeMirzayanov), Gleb Evstropov (GlebsHP), Artem Vasilyev (VArtem) and Mikhail Tikhomirov (Endagorion).

The event is completely international, as teams from all parts of the globe compete and practice side-by-side. They say a picture is worth a thousand words, so here is a selection to give you some idea of what’s happening at our boot camp.

And, once again, we can’t wait to see you all compete on the international stage, smoothing the road towards the April World Finals in Beijing.

The round’s creators are Endagorion, ifsmirnov, zemen and Arterm — team MIPT Jinotega, two-time medalist ACM-ICPC World Final (2016-17). The round is combined for both divisions, will contain seven problems and last for three hours.

Good luck!

Scoring: 250-500-1000-1500-2250-2500-3500

UPD: Thanks for participating, glory to the winners!

1. HYPERHYPERHYPERCUBELOVER
2. jqdai0815
3. ainta
4. zigui
5. fateice

We will publish the editorial as soon as the Barcelona Bootcamp activities conclude.

UPD2: the English editorial is here.

A huge breakthrough in approximation algorithms was announced recently as asymmetric travelling salesman problem was shown to allow a constant approximation scheme. See discussion in an article by R.J. Lipton. One of the co-authors was Jakub dj3500 Tarnawski. It always pleases me to see competitive programmers achieving heights beyond CP, in academia and "real-life" problems (recall that OpenAI's bot recently beat human players at 1v1 Dota2, with meret and Psyho in the developers team). Congratulations on an outstanding achievement, Jakub!

A few people have been asking me for tips on practicing. Since explaining this many times is boring, I will be doing a live stream with a small practice routine: virtual round participation and upsolving the problems immediately after (maybe solving something else as well). I'll try to answer your questions as I go, so join in if you're interested.

The stream will start around 16:00MSK on Saturday, September 2nd on my Youtube channel.

UPD: sorry, the stream is going to start at 18:00, not 16:00.

Hello! I've been trying to install moj plugin on a topcoder applet in a new environment. The problem is I'm getting Exception in thread "AWT-EventQueue-2" java.lang.NoSuchMethodError: com.topcoder.client.contestApplet.common.LocalPreferences.removeProperty(Ljava/lang/String;)Ljava/lang/String;... when trying to save preferences of CodeProcessor, at this point:

Pressing the save button doesn't do anything except for raising the exception in the console. Does someone have any information relevant to resolving this issue? Thanks!

Here's my first attempt to participate in a contest while screencasting and commenting in English as it goes, you can watch the video here. Let me know what you think!

UPD: screencast of today's DGCJ round.

На этот раз я решил попробовать писать разбор в спойлерах, как уже делал кое-кто из авторов. Буду рад вашим комментариям о том, стало ли лучше.

Задача A. Сдвиги

Темы: динамическое программирование.

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

Решение: пускай мы можем сдвигать не только вправо, но и влево.

Задача B. Число в подарок

Темы: жадность.

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

Решение: Раз мы максимизируем число, важнее всего понять, насколько большую цифру можно поставить на первое место. Обозначим d первую цифру n.

Задача C. Рекуррентный генератор

Темы: хэширование/строковые алгоритмы.

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

Решение: Для начала поймем, почему последовательность Фибоначчи, определенная в условии, не является 1-рекуррентной.

Задача D. Торговля

Темы: жадность, сортировка, реализация.

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

Решение:

На этом описание решения по большому счету заканчивается.

Задача E. Прогулка по Манхэттену

Темы: математика, кратчайшие пути в графе.

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

Решение:

Задача F. Игра на дереве

Темы: игры, графы, математика.

Общий комментарий: сперва эта задача казалась мне простой, и я ожидал по ней больше правильных решений. Каждая идея по отдельности достаточно несложная, и кода в итоге совсем чуть-чуть. Оказалось, что распутать задачу целиком под силу немногим. Какие у вас впечатления от задачи? =)

Решение:

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

Привет!

Рад объявить, что сегодня, 4 июня в 15:00 MSK состоится третий и последний отборочный раунд соревнования Яндекс.Алгоритм 2017. Ничуть не меньше рад сообщить, что задачи подготовлены мной, Михаилом Тихомировым. Я проработал в Яндексе три года и с теплотой вспоминаю это время в дружелюбной и сплоченной команде. Ура Яндексу!

Этот раунд не смог бы состояться без трудов следующих людей:

• Лидии lperovskaya Перовской и ее команды, обеспечивающих работу системы Яндекс.Контест,

• Максима Zlobober Ахмедова, бывшего сурового координатора Codeforces и нынешнего сурового координатора раундов Яндекс.Алгоритм,

• Михаила MikeMirzayanov Мирзаянова и команды Codeforces, поддерживающих систему подготовки задач Polygon,

• а также всех сотрудников Яндекса, принявших участие в прорешивании раунда (поля этого блога слишком малы, чтобы перечислить их поименно).

Раунд пройдет по стандартной схеме: 6 задач в случайном порядке на 100 минут по системе TCM/Time. По результатам раунда будут присуждены последние очки GP30, влияющие на состав участников финала (текущие результаты можно посмотреть здесь). Даже если вы не участвовали в предыдущих раундах, шансы на участие в финале еще есть!

После окончания раунда появится разбор задач в отдельном посте. Желаем всем участникам удачи и удовольствия от задач!

UPD: начало откладывается на 15 минут по техническим причинам. Приносим наши извинения.

UPD2: раунд закончен! Вот и разбор подъехал (пока на английском).

Yesterday, on April 23 an Open Cup round — Grand Prix of Moscow Workshop was held. In fact, the same contest was held on April 17, the last day of Moscow Pre-Finals ACM ICPC Workshop.

The problems were prepared by the workshop programming committee: Mikhail Tikhomirov (Endagorion) and Gleb Evstropov (GlebsHP), as well as members of MIPT teams Jinotega: Ivan Smirnov (ifsmirnov), Artsem Zhuk (Arterm), Konstantin Semenov (zemen), and Cryptozoology: Alexander Ostanin (Kostroma), Alexander Golovanov (Golovanov399), Nikita Uvarov (-imc-). We hope you enjoyed solving our contest!

The results can be found on the Open Cup page. Our congratulations to teams SPb ITMO University 1 (Belonogov, Zban, Smykalov) and the veteran team SPb Havka-papvsto (Kunyavsky, Kopeliovich) on solving all 11 problems! Please not that since Java issues in Yandex.Contest are not fully resolved yet, the results are not final and Java submissions may be subject to rejudge.

Here is a link to PDF editorial for the problems, prepared by myself and GlebsHP. Please ask your questions and point out the mistakes in the comment section.

Sorry for the wait! We'll be glad to answer your questions in the commens.

I hope you've enjoyed the problems! Please ask your questions and report flaws in the comments.

Problem A

First insight is that two spells are always enough. Why? Let's freeze all leftbound penguins at point 10^- 9 and all rightbound penguins at point 10⁹.

So the only problem is to determine when only one spell is enough. If that holds, there should exist a point which all penguins will cross at some moment. Let's put this point at x + ~--- rightmost point among penguins' coordinates which run to the right. Now all rightbound penguins will cross this point. If there is a leftbound penguin which doesn't cross x +  then its coordinate x -  must be less than x + . But in this case there are two penguins running away from each other~--- clearly one spell will not suffice.

So, the easiest and most effective solution is to find x + ~--- the location of rightmost rightbound penguin, and x - ~--- the location of leftmost leftbound penguin, and check if x -  < x + . If that holds, the answer is 2, otherwise it's 1. This can be easily done in O(n). Other approaches include checking for all pairs of penguins if they run away from each other in O(n²), or more effeciently using sorts in .

Problem B

Let's divide all configurations by leftmost turned-on bulb. Suppose the leftmost turned-in bulb is i-th. If i + k - 1 ≤ n, then the bulbs i + 1, \ldots i + k - 1 can be turned on or off in any combinations, so the number of such configurations is 2^k - 1. If i + k - 1 > n, then the ``free'' bulbs are limited by the end of the line, and the number of configurations is 2^n - i. There is also one combination when all bulbs are off.

These quantities can be summed up in if one uses binary modulo exponentation of 2, or in O(n) if the powers of 2 are precomputed with DP. It can also be shown (by summing the geometric progression which you can try to do yourself) that the answer is always equal to (n - k + 2)2^k - 1, this number can be computed in .

Problem C

Let's come up with a straightforward solution first. We will just simulate the battles and keep the current value of M. How many iterations we will have to make? And more importantly, how can we tell if the answer is  - 1 or we just didn't do enough battles yet?

To answer that, let's keep track of values of M before all battles with the first opponent. If some value of M repeats twice, then the whole process is looped and the answer is  - 1. On the other hand, if M > A (the largest possible value of a_i, that is, 10⁶) we will surely win all battles. So the maximal number of iterations is n(A + 1) (since no value of M ≤ A can repeat twice).

This is still too much for straightforward simulation ( battles). How can we optimize that? Let us find f(M)~--- the number of first lost battle for each value of M at the start that does not exceed A. This can be done in O(A) for all M's at the same time using the fact that f(M) does not decrease. Indeed, suppose we know f(M) and also g(M)~--- our power before battling the last opponent. If the starting power were M + 1, at this point our power would be g(M) + 1. If this is still not enough to win opponent f(M), then f(M + 1) = f(M), g(M + 1) = g(M) + 1. Otherwise, we proceed to following opponents updating f(M + 1) and g(M + 1) accordingly until we lose or win them all. Notice that the total number of increases of f(M) is at exactly n, thus the complexity is O(n).

Using values f(M) we can emulate the battles much more quickly: for given M find the first lost battle, add f(M) to the total number of battles, update M with max(0, g(M) - a_M), proceed until we win everyone or M repeats. This optimization leads to O(n + A) solution.

There is another tempting idea for this problem which turns out to be wrong. If you have trouble with WA3, consider this case:

4 2
0 5 0
6 0 3
7 0 6
8 0 4

Problem D

Let's call a position x \emph{interesting} if color(x) ≠ color(x - 1). If we find two interesting positions x < y so that color(x) = ... = color(y - 1), then the answer is equal y - x.

How can we find a single interesting position? Suppose we have two arbitrary positions a < b and color(a) ≠ color(b). Then we can find an interesting position x with a < x ≤ b using binary search: let . If color(a) ≠ color(c) update a with c, otherwise update b with c. At some point b - a = 1 and we're done. Denote this resulting position as f(a, b).

Okay, how to find two positions of different colors first? Let M be the maximal possible value of L. Consider a segment of length, say, 2M. The colors inside this segment have to be distributed \emph{almost evenly}, so after trying several random cells we will find two different colors with high probability.

There are several possible options what to do after we have obtained two interesting positions x and y. We can use the fact that either the segment x, \ldots, y - 1 is same-colored, or it has at least 1 / 3 of the cells with color! = color(x), so we can try random cells until we find z with color(z) ≠ color(x), and then we can shrink the segment to either x, f(x, z) or f(z, y), y, whichever's shorter. Length of the segment shrinks at least two times after each iteration (in fact, it shrinks even faster).

Another approach is to note that L divides y - x for all interesting positions x and y. Thus we can obtain several interesting positions f(a, b) for random values of a and b, and find G~--- GCD of their differences. Clearly, . It can also be shown that G = L with high probability is the number of positions is, say, at least 50; it is a bit harder to analyze though, but the general idea is that while it's hard to determine the exact distribution of f(a, b), it is \emph{not that bad}, so it is improbable for many values of f(a, b) to be, say, multiples of 2L apart.

I want to describe another, much simpler solution by Chmel_Tolstiy. Let's find the smallest k such that color(2^k) ≠ color(0). It is easy to prove that there is exactly one change color between these two positions, so its position can be found with binary search as before. Do the same way in negative direction and find another closest color change, output the difference. This solution turned out to be most popular among contestants (but less popular among the testers).

Problem E

Let's find out how to check if the answer is at most D and binary search on D.

Let's make an arbitrary vertex the root of the tree. Note that if the subtree of any vertex v contains even number of outposts then no paths can come out of the subtree (since their number must be even, but at most one path can pass through an edge). Similarly, if there is an odd number of outposts then one path must come out of the subtree. Consider all children of v: each of their subtrees will either yield a single path or nothing. We have to match the resulting paths between each other and choose at most one of them to yield to the parent. Naturally, our intention is to make the unmatched path as short as possible while making suring that in each pair of matched paths their total length does not exceed D. We can also note that the answer is never  - 1 since we can always match the paths if we ignore their lengths.

Consider the case when we have to match an even number of paths. Let's say we have an array of even length a₁, \ldots, a_2k, and want to make pairs of its elements such that sum in each pair does not exceed D. It can be shown that the optimal way is to sort the array and then match a₁ + a_2k, a₂ + a_2k - 1, and so on. Indeed, consider that a₁ is not matched with a_2k but with a_x, and a_2k is matched with a_y. Let's rematch them as a₁ + a_2k and a_x + a_y. Since the array is sorted, a₁ + a_2k, a_x + a_y ≤ a_y + a_2k and the maximum sum won't increase after rematching. Drop the elements a₁ and a_2k and proceed until we obtain the matching a₁ + a_2k, a₂ + a_2k - 1, \ldots.

Now we want to match an odd number of paths while minimizing the unmatched path length. This can be done with binary search on unmatched length and checking if the rest of the paths can be matched using previous approach. Another approach is greedy: take the maximal element x, find maximal element y such that x + y ≤ D, erase them both. If there is no such y, then x must be unmatched. Finally, check if there is at most one unmatched element. All these approaches take time for a vertex with d children, but the real time depends hugely on the actual approach (say, using std::set or TreeSet is much slower than sorts and binary searches).

The total complexity is , where A is maximal possible answer value.

Problem F

Consider all possible values of a and b such that . Let's arrange them in a table, roughly like this (second sample, O stands for possible value, . for impossible):

  0 1 2
0 O O .
1 O . .
2 . . .

When can one determine the numbers? Consider the position (0, 1): the person with number 2 knows that the only possible pair is (0, 1), so he can answer it. In general, once there is only one possible value in some row or some column this value is removed on this day since one person can deduce the other number. So, after day 1, the table becomes (X stands for no longer possible value):

  0 1 2
0 O X .
1 X . .
2 . . .

Now position (0, 0) can be solved on day 2 according to our rule. One can see that in the third sample the only solvable positions are (0, 2) and (2, 0).

It is tempting to look for a simple formula, but behaviour of how positions are resolved turns out to be complex (for example, try X = {5, 13, 20}). We should look for a way to simulate the process efficiently.

First, note that there will be at most 2(A + 1) resolved positions, where A is the maximal element of X. Indeed, each resolved position leaves a new empty row or a column. Thus, the process will terminate quite quickly, but the total number of possible initial positions is too large to choose resolved positions straightforwardly.

There are few possible optimization. For one, suppose we have the data structure with following operations: initialize with a set of numbers, remove a single number, once there is a single number in the set, find it. Let's store this kind of structure for each row and column, now the process can be simulated easily. The simplest way to implement this structure is to store a pair (sum of numbers, count of numbers). Moreover, all the structures can be initialized at once in O(A) time using prefix sums and prefix counts.

Another idea: if there are three consecutive numbers x_i, x_i + 1, x_i + 2 with x_i + 2 ≤ x_i + x_i + 1 + 1, then all positions with a + b < x_i will be unsolvable. If we drop all x_j < x_i, the sum of the rest elements of X will be O(A), which allows for a simple simulation.