Всем добрый день!
В связи с неожиданными изменениями в расписании Кубка я остаюсь без команды, так как Дима Матов (Nerevar) на выходные меня покидает. Поэтому было бы очень здорово объединиться с кем-нибудь еще, у кого в команде не хватает человека.
Моя цель — пройти на онсайт. Поэтому главное условие — преемственность нашей сборной с Saratov SU Retired либо с вашей командой (если у нее высокий результат в настоящий момент) и мое участие в онсайте, если пройдем. Еще крайне желательно, чтобы вы могли взять меня на все три этапа (6, 7 и 9 мая). Расписание есть на сайте www.opencup.ru.
Ваше географическое положение особой роли не играет. Надеюсь, в связи со сложными обстоятельствами разрешат участвовать дистанционно.
Если есть деловые предложения — пишите в личку, а вот троллить, наоборот, лучше где-нибудь в другом месте.
Удивительно, что все как-то подзабыли, что сегодня, 23 февраля, в России праздник — День защитника Отечества. Поздравляю с этим замечательным праздником представителей сильной половины человечества от лица другой половины, менее многочисленной на Codeforces. Дорогие мужчины, вы у нас самые умные, обаятельные, изобретательные и веселые. Счастья, здоровья, успехов, великих свершений, удачи на контестах и побед на всех фронтах!
The plates must touch the edge of the table, so their centers must lie on the circle with radius R - r (see the figure).
In case the plates have the largest radius possible for the given table, their centers are situated in the vertices of the regular polygon (n-gon) inscribed in this circle. The problem is to find the length of the side of the inscribed regular n-gon and to compare it with 2r. The formula for the length of the side is a = 2(R - r)sin (π / n), it can be easily deduced. For that you should consider the right triangle (the green one in the figure).
In implementation, be careful with a case when the equality r = (R - r)sin(π / n) (*) holds. Because of the computational error the right-hand side can get larger than the left-hand one. This can result in answer "NO" instead of "YES". Comparison in such cases should be performed with a small ε:
a + ε < b instead of a < b ,
a < b + ε instead of a ≤ b.
A constant ε should be chosen in such a way, that it is smaller than any possible difference between precise values of a and b, if they are distinct. In particular, for computations by the formula (*), taking into account the constraints of the problem, this difference may be approximately 7· 10 - 7. So ε = 10 - 7 is sufficient, but ε = 10 - 6 is not.
Once again, I focus your attention on the fact that the choice of ε depends on specific formulas used for computations and comparisons. Different solutions can be accepted or not with the same ε.
This problem was just a problem on implementation. Note that a number of a send card is uniquely determined by a number of a friend and a set of cards Alexander already has at the moment. Consider the sample form the statement.
| 1 | 2 | 3 | 4 | |
| {1} | - | 1 | 1 | 1 |
| {1, 2} | 2 | 1 | 1 | 1 |
| {3, 1, 2} | 3 | 3 | 1 | 3 |
| {3, 1, 2, 4} | 3 | 3 | 1 | 3 |
The first column of the table contains sets of cards that Alexander gets after having received a next card each time. Numbers in the sets are written in order of Alexander's preferences. Each i-th of the next four columns contains numbers of cards that the i-th friend will get from the corresponding sets. Our goal is to choose for each friend the most preferred card in his column.
Note that to determine by the current Alexander's set and the number of the friend a number of a card received by this friend, it is not necessary to know the whole Alexander's set. The two most preferable cards are sufficient. So for each time moment find the two most preferable cards for Alexander. Using them, determine which of them will be send to each friend (find the numbers in the columns). Then choose the element with the maximum priority in each column. We get the O(n2) solution.
Solution 1. Suppose that the answer is k. If there are more than k equal among the given numbers, it's clear that we can't use them all (we can't use equal snowballs in the same snowman). So we leave k snowballs of them, and discard the rest. Then, sort the radii in the non-decreasing order. After that every two snowballs with numbers i and k + i are different. Make snowmen of snowballs with numbers (1, k + 1, 2k + 1), (2, k + 2, 2k + 2), (3, k + 3, 2k + 3) and so on. If the total number of snowballs is not less than 3k, we always manage to make k snowmen. Now we can for the fixed k answer to the question, if k snowmen can be made, so k can be chosen by binary search.
Solution 2. Count quantities of snowballs of each size, choose greedily the three largest quantities, take a snowball from each of them, make snowman and continue the process, while it's possible. Why is it correct? Let k be the answer for the problem. If there are quantities larger than k, we will count them as k, because other snowballs in them will not be used in any way. We prove the correctness of the algorithm using
Proposition: if every quantity is ≤ k and the total quantity of snowballs is ≥ 3k, then it's possible to perform a step of the algorithm.
Proposition is valid because by Pigeonhole principle there are no less than three non-zero quantities. If there are 3 (or more) quantities equal k, then k steps of the algorithm can be performed. If there is one or two such quantities, by the first step we certainly decrease them and come to a similar situation with k - 1. If there are no quantities equal k, after the first step we obtain quantities ≤ k - 1, and their total sum is ≥ 3(k - 1). Thus, we always can perform k steps and get the answer k.
From the point of view of implementation, in the second solution it is easy to calculate quantities for each size of snowballs (using sorting and scaling). Use set to work with these quantities. The time for the both solutions is 
.
.Solution 1 (greedy). Optimal order to solve problems is an increasing (non-decreasing) order by their difficulties. Problems solved before the New Year must be submitted at 0:00, ones solved after the New Year must be submitted just after finishing their solutions.
Let us prove the optimality of this solution by the descent method. General scheme of reasoning is the following. Suppose you have the optimal order which is not the increasing order by problems' dificulties. Show that it is possible to come (to descend) from it to another variant, that is not less optimal. As a result you come to the sorted variant by such steps.
So suppose that there is a pair of problems in the optimal solution such that their difficulties are going in decreasing order. Then there are consecutive problems with this property. Suppose they both are solved before the New Year. Then the swap of them doesn't influence the penalty (it doesn't decrease). If the both problems are solved after the New Year, then their contribution to the total penalty is (T + ai) + (T + ai + aj), where T is a time of the beginning of solution for the first problem, ai is a time for the solution for the first problem, aj < ai is a time for the solution for the second problem. After the swap of these problems we get the penalty (T + aj) + (T + aj + ai), that is less than (T + ai) + (T + ai + aj). It remains to consider cases when one of the consecutive problems that are in the "wrong" order "intersects the New Year". These cases can be treated similarly.
In case when Gennady hasn't time to solve all problems, you should choose the maximal possible number of the easiest problems. Indeed, it doesn't make sense to solve a more difficult problem instead of an easy one: change of a larger ai to a smaller one doesn't spoil an answer. Rigorous proof can be obtained by the same descent method.
Solution 2 (dynamic). First of all, as in the previous solution, choose the maximal number of the easiest problems that Gennady has time to solve. Discard the remaining tasks. Try every problem as one being solved in the moment of the New Year (0:00). Remaining problems (except it) must be divided into two sets. One is for solving before the New Year, and another is for solving after the New Year. Problems in the second set must be solved in increasing order of their difficulties (it is a well-known fact for everybody participating in contests by ACM rules). In the first set an order of solving is immaterial. Sort the given numbers in increasing order, and count the dynamics d[i][j][k] that is the smallest possible penalty, if there are the first i problems solved, j from them are solved after the New Year, and the last problem after the New Year was solved at the moment k. Note that the triple (i, j, k) uniquely determines the number of problems solved before the New Year and the total time needed for their solutions. After calculating the dynamics, recollect the problem being solved exactly at 0:00 (it was not taken into account in the dynamics). Try moments of time before the New Year when its solutions starts, and count remaining problems using the dynamics we already has.
First, let us solve the subtask for one layer. It consists in finding the number of ways to compose a garland of lengths s with lamps of exactly k colors such that no two consecutive lamps have the same color. Variants different only by an order of colors are considered to be the same (we always can multiply by k! if we need). The solution of the subtasks is required only for k ≤ s ≤ 5000, so can be done by O(s2)-dynamics:
a[s][k] = a[s-1][k-1] + a[s-1][k] * (k -1).
They would be Stirling numbers of the second kind, if there was not a restriction about different colors of consecutive lamps.
Then, calculate the dynamics d[i][j] that is a number of ways to compose a garland for the first i layers according to the rules, such that the i-th layer contains exactly j different colors. There will be about L positions (the total length of the garland), because every layer can't contain more colors than its length: j ≤ li (!). All d[i][j] can be calculated in O(L) operations, because sets of colors with different cardinalities are always different (!!). Indeed, put d[i][j] = Amj * a[l[i]][j] * (sum of all d[i-1][k]), and then subtract variants with equal sets on the i-th and (i-1)-th layers. Coefficients Amj = m(m - 1)... (m - j + 1) can be pre-calculated because they are required only for j ≤ 5000.
Thus, the author's solutions works in O(L + s2) (L ≤ 107, s ≤ 5000), and it doesn't use division (only addition and multiplication modulo p).
Start with the check of a candidate symmetry center (xc, yc). Consider all points symmetrical to (xi, yi) with this center. They are of form (2xc - xi, 2yc - yi). It is necessary to check that they all except may be k of them are in the set {(xi, yi)}. It can be done in by binary search (if the set was previously sorted). But there is more effective way of check in O(n). Note that if initially the points (xi, yi) were sorted, say, by x-coordinate in increasing order and in case of equal x by y, then the points of the form (2xc - xi, 2yc - yi) will be sorted in the reverse order. The order doesn't depend on the center (xc, yc). So we can check the points (2xc - xi, 2yc - yi) in the order of sorting moving a pointer in the sorted array (xi, yi).
by binary search (if the set was previously sorted). But there is more effective way of check in O(n). Note that if initially the points (xi, yi) were sorted, say, by x-coordinate in increasing order and in case of equal x by y, then the points of the form (2xc - xi, 2yc - yi) will be sorted in the reverse order. The order doesn't depend on the center (xc, yc). So we can check the points (2xc - xi, 2yc - yi) in the order of sorting moving a pointer in the sorted array (xi, yi).It follows from the previous reasoning, that if a set has a symmetry center, then the first point (in the order of sorting) forms a pair with n'th, the second one with (n-1)-th and so on. Since up to k points have not a pair, try the first (k+1) points from the beginning and (k+1) from the end of the array. For every pair of these points find the midpoint and check it in O(n). Asymptotics of the solution is O(nk2).
In conclusion, a couple of words about the difficulty order in the problemset must be said. Difficulty of a problem is subjective. Especially if we need to compare a problem with idea and nearly without implementation and implementation without idea. As a result, different participants form different preference lists (russian). I can't deny that the order chosen during preparation of the contest appeared to be inadequate with the number of solutions for the problems, and it surely can be not liked by someone personally. Nevertheless, I want to say a couple of words in its support. Namely, about principles we have used to choose it.
Score for a problem is, first of all, its "price". Ability to solve problems with idea, IMHO, must have higher price then ability to solve implementation problems. Because everybody can learn to solve implementation with level like problem B. But idea with sorting in problm D, as I saw, was not invented by several strong and experienced participants. About the order of the problems, I can say that nobody makes you to solve them exactly in this order. It is not bad, if you fast get an idea for C or D, solve them before B, and get more scores. Many contestants acted this way. Moreover, the current standing is available that can help you to choose right problems to solve.
Hello everybody!
I hope you have finished New Year celebrations, or you are ready to make a small break to take part in the anniversary Codeforces Round #100. Round will have place January 4 at 15:00 (UTC). There will be a common contest for participants of the both divisions with the same set of 6 problems. The top 100 participants of the contest receive prize t-shirts.
Score distribution: 500-1000-1500-2000-2500-3000
As you may have guessed, the author of the problems is me. Invaluable help in preparation (and a bit in inventing) of problems was provided by Artem Rakhov (RAD) and in translation of the problem statements into English by Maria Belova (Delinur).
Under the influence of my festive mood, the problem statements turned out to be about different characters celebrating New Year. All characters and events are fictional, please take any resemblance as completely coincidental :)
The contest is over. Codeforces team and I personally want to thank all who take part in the greatest round in Codeforces history! Much to our surprise, the 100th place was shared by two contestants: pooya_ and Timur_Sitdikov. Of course, they both will receive prize t-shirts as all others who took higher places. Prizewinners will receive special emails.
Congratulations to the winners:
1. Egor
3. tourist
4. Petr
5. RAVEman
6. e-maxx
7. hos.lyric
8. dzhulgakov
9. Coder
10. SergeyRogulenko
Manthan прошел на Codeforces где-то в середине марта, побив очередной рекорд по количеству регистраций. Мне по счастливой случайности удалось занять на этом контесте 15-е (последнее призовое) место. Только о моем подарке стоимостью 1000 рупий (по словам Димы Матова, это 600 рублей, не проверяла) ничего не было слышно. Я уже была готова обидеться на организаторов и почти забыла про это соревнование, как вдруг мне приходит письмо. Цитирую только самое интересное.
Congratulations for securing 15th rank in manthan of CodeFest 2011 and winning Gift Vouchers worth INR 1000 from our gifts partner, Naaptol. Please find the details of the GVs as below (along with the terms and conditions):
Дальше приводятся номера ваучеров и прочая секретная информация. Далее:
- The Gift Voucher (GV) can be redeemed on orders placed at website www.naaptol.com/hot
- Only one order per GV No. (As printed overleaf) can be placed. No two GVs can be clubbed together for an order
- This GV is valid till 31st May 2011
- GV is not redeemable/ refundable for CASH and cannot be returned for a cash refund under any circumstances
- If this GV No. is non functional on account of any technical reason, your sole remedy and the sole liability of Naaptol shall be reissue/ replacement of the particular GV NO
- Naaptol is not responsible for the lost or stolen GV and no representation in this regard will be accepted in any form or nature
- This Voucher can be redeemed only by online payment mode. (No cash on Delivery orders will be accepted)
- Customer Care - 9223516148
Вообще использовать подарочные карты в качестве призов - неплохая идея. Только вот приведенный сайт ничего конкретного не сообщает мне о доставке товара, а при выборе конкретного товара предлагает мне указать адрес в Индии :) Еще даже чуть-чуть обидно, что ваучеров два по 500 и их нельзя объединять :(
Извините, что так многословно, просто подобные призы создают определенное настроение :) Интересно,
1. может быть, я чего-то не понимаю и у меня все-таки есть возможность использовать эти деньги в России?
2. на codechef награждать таким образом - обычная практика?
3. что вы думаете по поводу адекватности таких призов на международном соревновании?
В любом случае я благодарна организаторам Manthan, что не забыли :)
Три последних "общих" контеста: Codeforces Beta Round #58, Codeforces Beta Round #60 и Manthan 2011, выявили ряд моментов в правилах Codeforces-раундов и вообще принципах их подготовки, которые вызвали разгоряченные споры и недовольство некоторых участников. Самый наболевший вопрос - взломы и их оценивание, я затрагивать не буду. Он обсуждается, например, здесь.
Хочу выдвинуть такие предложения.
1. После того, как решение участника прошло претесты, нужно открывать их для этого участника.
Какую роль вообще играют претесты? Согласно правилам, "тот факт, что решение прошло претесты говорит только о том, что оно вполне разумно". "Вполне разумно" - понятие расплывчатое, поэтому подбор претестов очень субъективен. Обобщая опыт участия в контестах, могу сказать только то, что в претестах обычно нет максимальных тестов. А вот крайние случаи могут быть представлены в большей или меньшей степени. Цель претестов - с одной стороны, не пустить взламывать тех, кто не может написать хоть какого-то разумного решения по задаче, с другой стороны, оставить некоторый простор для взломов.
Я считаю, что претесты все-таки должны охватывать значительную часть случаев и не пропускать совсем "паленые" решения, как вышло в этом случае. Но они все равно будут пропускать решения с серьезными багами. Даже если автор не хочет этого намеренно, он может не учесть в претестах какого-то распространенного заблуждения участников. Когда я собиралась готовить свой контест, я спросила у Артема Рахова, сколько всего претестов по задаче. Когда я узнала, что их 5-7 (включая примеры из условия!), это сильно изменило мою тактику на контестах: я стала более тщательно тестировать свои решения. Когда нужно гарантированно сдать задачу с первой попытки (например, на школьных олимпиадах), нужно тестировать хотя бы на 10-15 тестах. Причем скорее на 15, если задача сложнее a+b.
Вот и встает вопрос: если решение прошло претесты, нуждается ли оно в дополнительном тестировании? На какие случаи? Открытие претестов даст участнику возможность решить для себя этот вопрос сразу же по ходу соревнования и не обижаться ни на кого потом за слабые претесты.
2. Выставлять баллы по задачам не обязательно 500-1000-1500-2000-2500, а в соответствии с их реальной сложностью.
Потому что бывает, что задачи A и B, или D и E примерно одинаковые по сложности. Тогда имеет смысл дать за них 750-750 или 2250-2250. Правда, эта идея немного близка к Топкодеру :)
3. При определении сложности задачи учитывать не только сложность алгоритма, но и количество частных случаев в ней.
Эту проблему особенно ярко показал последний контест (Manthan). Задачи D и E (особенно D) опирались на более или менее стандартные алгоритмы и их решение вызвало у многих участников меньше проблем, чем B и C. Тем более, когда идет активный "взломный" процесс, для "взламываемых" и исправляющих свои решения задача все дешевеет и дешевеет. В итоге задачу сдает маленькое количество людей и те, кто сдает, получают совсем небольшие баллы, хотя им пришлось преодолеть значительные трудности. За такие задачи, на мой взгляд, надо давать побольше баллов. Что касается порядка, то ничего страшного, если эти задачи будут A или B - это будет говорить о том, что они не требуют знания чего-то совсем сложного и доступны для начинающих участников. А большая стоимость задачи будет говорить о том, что задача, возможно, содержит подводные камни.
Problem A
Fist, consider the case when all the numbers are non-zero. You can take a*c*e grams of sand, turn them into b*c*e grams of lead, and them turn into b*d*e grams of gold, and them turn into b*d*f grams of sand. If b*d*f > a*c*e, you can infinitely increase the amount of sand and consequently the amount of gold. Otherwise, if b*d*f <= a*c*e, it is impossible to get infinitely large amount of gold. The same is true when the fraction (a*c*e)/(b*d*f) has zero numerator only or zero denuminator only. Otherwise there is 0/0, and you have to check cases specially.
I explain, why I make this problem to be problem A.
1. Solution of the problem requires very little knowledge of programming (only "if"), so it was feasible for all participants.
2. Tricky cases really exist, but I hoped that "stronger competitors will ... help newcomers to catch all bugs by their hacks". And so it happened.
Maybe I was wrong: this problem is too complex for A.
A large number of hacks for this problem is a quite foreseen circumstance. I haven't include the special class of tests into the pretests intendently, to make hacking more interesting. In fairness I should note that Artem Rakhov was against this idea. Beause of this task the problem surfaced that Gassa writes about here in Russian: pretests cover some incomplete set of cases and it is not clear in advance what the event "solution passed pretests" means. I think it should be discussed, and strong principles of pretests development should be stated.
Problem B
I'm glad to invite everybody to take part in the current round.
Today the problems' author is me. I with Artem Rakhov, Maria Belova and Dmitry Matov have tried to do everything possible to make problems more reliable.
I hope that the problems will be interesing for you, the contest will be dinamical, and stronger competitors will cope with the problems quickly to help newcomers to catch all bugs by their hacks :)
Good luck!
P.S. The phrase "stronger competitors will cope with the problems quickly" in no way means that all the problems will be easy. Don't forget to read statements and to test your solutions!
UPD. The contest is over. Congratulations to the winner - Kenny_HORROR!
UPD2. Tutorial is added. In spite of the record number of participants the system has been working stable during the round. Thanks to Codeforces team! Also thanks to everyone who took part in the round.
Problems A and B have no difficult ideas, so let's start from C.
Problem C
Put β = α / 10. Then the given numbers are a1 = [β], a2 = [2β], a3 = [3β], ... an = [nβ], and you have to count [(n + 1)β] ([x] is the integral part). The given equalities are equivalent to the system of inequalities: an ≤ nβ < an + 1,
. Choose maximum among left-hand sides and minimum among right-hand sides and obtain an inequality in the form A ≤ n < B. Now compare integral parts of the numbers A / (n + 1) and B / (n + 1). If B is divisible by (n + 1), subtract 1 from the right-hand side, because of the strict inequality in the right-hand side.
Problem D
Create vertors vi, and put positions of ones to the first vector v1, positions of 2s - to v2, positions of 3s to v3, etc. The vectors can be filled for one pass of the given sequence. The number of permutations is the number of ones, or the size of the first vector. Mentally put the first 1 to the first permutation, the second 1 to the second permutation, and so on. Now turn to 2. If the number of 2s is greater than the number of 1s, there is no solution. Otherwise put the first 2 to the first permutation, the second 2 to the second permutation, and so on. It is possible for some last permutations to remain without 2. Then do the same for 3s (there should be less 3s than 2s), and so on. Obtain the O(n) solution.
Put β = α / 10. Then the given numbers are a1 = [β], a2 = [2β], a3 = [3β], ... an = [nβ], and you have to count [(n + 1)β] ([x] is the integral part). The given equalities are equivalent to the system of inequalities: an ≤ nβ < an + 1,
. Choose maximum among left-hand sides and minimum among right-hand sides and obtain an inequality in the form A ≤ n < B. Now compare integral parts of the numbers A / (n + 1) and B / (n + 1). If B is divisible by (n + 1), subtract 1 from the right-hand side, because of the strict inequality in the right-hand side.Problem D
Create vertors vi, and put positions of ones to the first vector v1, positions of 2s - to v2, positions of 3s to v3, etc. The vectors can be filled for one pass of the given sequence. The number of permutations is the number of ones, or the size of the first vector. Mentally put the first 1 to the first permutation, the second 1 to the second permutation, and so on. Now turn to 2. If the number of 2s is greater than the number of 1s, there is no solution. Otherwise put the first 2 to the first permutation, the second 2 to the second permutation, and so on. It is possible for some last permutations to remain without 2. Then do the same for 3s (there should be less 3s than 2s), and so on. Obtain the O(n) solution.
Problem E
I tell two solutions. The first solution examines three possible cases separately. Build a graph which have pairs (h, t) as vertices, where h and t are dragon's current amounts of heads and tails. Edges are determined by possible Ivan's blows. Firstly, determine by bfs if it is possible to get from the start vertex to (0, 0) and the number of required steps in case if it is possible. Then check if the draw is possible, i.e. if the graph has cycles. Otherwise the graph is acyclic, and by dynamics on the acyclic graph you can find the longest path to a dragon-win position.
I tell two solutions. The first solution examines three possible cases separately. Build a graph which have pairs (h, t) as vertices, where h and t are dragon's current amounts of heads and tails. Edges are determined by possible Ivan's blows. Firstly, determine by bfs if it is possible to get from the start vertex to (0, 0) and the number of required steps in case if it is possible. Then check if the draw is possible, i.e. if the graph has cycles. Otherwise the graph is acyclic, and by dynamics on the acyclic graph you can find the longest path to a dragon-win position.
The second solution is to implement the standard algorithm often used for games on cyclic graphs. In fact the described process is a game on a cyclic graph with Gorynych moves determined uniquely. Start from vertices for that the answer is known, i.e. (0, 0) and h + t >= R, and go by reversed edges marking other vertices as winning or losing. Unmarked vertices will be draw-positions.
Problem F
For each of n days you have to solve the so-called "continuous knapsack problem". The solution is greedy: sort the firms by prices of produced snow and take snow starting from small prices until you get the required volume. Solutions with sorting for each n work too long. The author's solution takes O(nm) time, and it is based on ideas of QuickSort. Choose a random element r in the segment. The same way as in QuickSort, reoreder the rest elements so that elements smaller than r preceed r, and elements greater than r follow r. Calculate the total volume of snow with prices less than r. If it is enough for us - solve the problem on the left subsegment, otherwise - buy all the left subsegment and go to the right subsegment recursively.
For each of n days you have to solve the so-called "continuous knapsack problem". The solution is greedy: sort the firms by prices of produced snow and take snow starting from small prices until you get the required volume. Solutions with sorting for each n work too long. The author's solution takes O(nm) time, and it is based on ideas of QuickSort. Choose a random element r in the segment. The same way as in QuickSort, reoreder the rest elements so that elements smaller than r preceed r, and elements greater than r follow r. Calculate the total volume of snow with prices less than r. If it is enough for us - solve the problem on the left subsegment, otherwise - buy all the left subsegment and go to the right subsegment recursively.
Note an unpleasant feature of this problem. On the one hand, an answer can be rather large. On the other hand, the large precision is required. So you should calculate an integral part and a fractional part of the answer separately.
Problem G
The given graph is connected and has one cycle. First solve the problem for a tree. Choose any vertex as a root, and for each subtree calculate the following characteristics by standard dynamics:
1) number of vertices in it;
The given graph is connected and has one cycle. First solve the problem for a tree. Choose any vertex as a root, and for each subtree calculate the following characteristics by standard dynamics:
1) number of vertices in it;
2) sum of disnances from its root to all vertices in the subtree.
You will get the answer of the root. To find the answer for other vertices, make tree traversal again. Consider a move from a vertiex u to its descendant v. To get to v from vertices of its subtree one have to use the same path as to u but without the last edge. On the contrary, for the other vertices path will be lengthened for the length of the edge (u, v). Thus, d[v] = d[u] - L(u, v) * c[v] + L(u, v) * (n - c[v]), where c[v] is the number of vertices in the subtree with v as a root.
Now consider a graph with one cycle that may have trees attached. Consider the vertices in the cycle as roots of the trees. Calculate the answer inside each tree. The total answer for each vertex is the sum of:
1) the sum of all distances inside its subtree;
2) the sum for all other trees distances from their roots to all vertices in the tree (because to get from a vertex to some vertex in another tree one has to pass its root);
3) distance form the vertex to the root of its tree multiplied by the total number of vertices in other trees;
4) the sum of <legth of the shortest path in cycle from the root to the root of tree t> * <number of vertices in the tree t>.
The most difficult part is calculation of the summand 4. Go through the cycle by two pointers: one to the current vertex, another to the vertex that separetes vertices from that one has to go left or to go right to the current vertex. Moving the pointers one can obtain partial sums for the summand 4 in a total linear time.
The most difficult part is calculation of the summand 4. Go through the cycle by two pointers: one to the current vertex, another to the vertex that separetes vertices from that one has to go left or to go right to the current vertex. Moving the pointers one can obtain partial sums for the summand 4 in a total linear time.
Problem H
Imagine that you have exactly m black-and-white tiles. Then you can solve the problem as follows. Go by cells from top to bottom, from left to right. First put a black tiles, then put c black-and-white tiles, then - b white tiles. As a result you get a border of black-and-white tiles that separates black from white. The black-and-white tiles can be rotated such a way that makes the tiling correct. For example, n = m = 4, a = b = 6, c = 4.
In the general case replace c - m black-and-white tiles (for example) by white ones, and build the tiling. Then replace back white tiles to black-and-white ones starting form the lower-right corner. For example, n = m = 4, a = 6, b = 3, c = 7.
The solution of the problem always exists.
Imagine that you have exactly m black-and-white tiles. Then you can solve the problem as follows. Go by cells from top to bottom, from left to right. First put a black tiles, then put c black-and-white tiles, then - b white tiles. As a result you get a border of black-and-white tiles that separates black from white. The black-and-white tiles can be rotated such a way that makes the tiling correct. For example, n = m = 4, a = b = 6, c = 4.
######## ######## #####/\# ####/..\ \##/.... .\/..... ........ ........
######## ######## #####/\# ####/..\ \##/.... .\/..... .../\../ ../##\/#
The solution of the problem always exists.
Good day!
I invite everyone to take part in the last contest of the series of WCS olympiads for school students which is one of the regular Codeforces rounds at the same time. The start of the contest is on the 12th of December, at 11:00 MSK.
The competition rules are ACM-ICPC rules, the duration of the contest is 3 hours.
Like the previous school individual olympiads, the contest will be rated for all participants (both for school students and others). Rating will be calculated according to the merged result table.
The authors of the problems are me and Dmitry Matov again. Thanks to Gerald Agapov and Artem Rakhov for their help in preparing the problems and to Maria Belova for translating the problem statements.
Good luck everyone!
UPD. The contest is over. The results are available. The winner of School Personal Contest is scottai1, the winner of Codeforces Beta Round is ilyakor. Congratulations to the winners!
The author's problem analysis is posted. Now problems G and H are added to the tutorial, too.
Thanks to everyone who participated in WCS series for school students, officially and unofficially!
Problem A
The solution of the problem based on modeling of the decribed process. It is important to perform a pass throw the beginning correctly. You can take the current number modulo n (and add 1), or you can subtract n every time the current number increases n.
Problem C
First of all, count the number of hamsters in the sequence. Let it is h. Try positions where the sequence of hamsters will start, and for each position count the number of tigers in the segment of length h starting from the fixed position. These tigers should be swapped with hamsters in a number of swaps equal to the number of tigers not in proper places. Choose minimum among all starting posotions.
Problem F
First, note that all the described operations are invertible: opening/closing doors, moving from one room to another and exchanging keys. So we may perform such operations from the initial arrangement to get some arrangment A, and then perform some operations from the final arrangement to get the same arrangement A, in this case the answer is "YES". Let apply the following strategy to both arrangements: while there is a person who can go to some room and open some door, perform this action. As a result from each arrangement we obtain subsets of connected rooms (we call them connected parts of the house), corresponding subsets of people and corresponding subset of keys in each connected part of the house. If these resulting subsets coincide for the initial and the final arrangement, then the answer is "YES", otherwise the answer is "NO". Indeed, if they coincide, it is obvious that we can get from the initial arrangement to the resulting arrangement, and then - to the final arrangement. Otherwise it is impossible, because there exist some keys that cannot be applied to the corresponding doors, because they are in another connected part of the house, or there exist people, who have no way to get to rooms in another connected part of the house.
Second, a few words about implementation. One of possible ways is to have two boolean matrices:
1) saying for each person if he/she could get to each room and
2) saying for each key the same,
and then recursively implement operations:
1) if a person can get to a room, try to get to neirbouring rooms,
2) the same for keys, but also trying to open a door to the neirbouring room,
3) if the door opens, people and keys in the incident rooms are assigned to another room.
So we try each pair person-room, person-door, key-door, key-room for O(1) times, and the total asymptotics is O(nk + km + m2 + nm).
Problem G
Note that the lengths of the sides can be 
, 
, 
, 
, and so on, i.e. the roots of integers, that can be represented as a2 + b2. Generate a proper quantity of such numbers. Denote them 
, 
, ... In some cases we can take first n such numbers as lengths of sides, but in some cases we surely cannot. It depends on the parity. If the sum r1 + r2 + ... + rn is odd, it is impossible. Indeed, we can
, , , , and so on, i.e. the roots of integers, that can be represented as a2 + b2. Generate a proper quantity of such numbers. Denote them , , ... In some cases we can take first n such numbers as lengths of sides, but in some cases we surely cannot. It depends on the parity. If the sum r1 + r2 + ... + rn is odd, it is impossible. Indeed, we canrepresent each side by vector (xi, yi), xi2 + yi2 = ri (xi and yi may be negative). If ri is even, then xi + yi is even too. If ri is odd, then xi + yi is odd. If we form a polygon with vectors of the sides (xi, yi), then x1 + x2 + ... + xn = 0 and y1 + y2 + ... + yn = 0, so the total sum x1 + ... + xn + y1 + ... + yn must be even! But if r1 + ... + rn is odd, it is odd too, so to build a polygon is impossible.
Let us take r1, ..., rn if their sum is even, and otherwise take r1, ..., rn + 1 and throw away one of them to make the sum even (in my solution I throw away the greatest such number). For each ri choose non-negative xi and yi, xi2 + yi2 = ri. In general case there are 8 possible orientations of a vector: (xi, yi), ( - xi, yi), (xi, - yi), ( - xi, - yi), (yi, xi), ( - yi, xi), (yi, - xi), ( - yi, - xi). The current subtask is to find such orientation for each vector that their sum is zero. It can be done by the greedy algorithm. Let's take the vectors from the longest ones. We will calculate current vector sum that is initially (0, 0), and it will be updated by each new taken vector. At each step choose such orientation that the current vector with that orientation minimizes the current sum (by its length) being added to it. Then, when the vectors are oriented, sort them by polar angle and apply them consequently to get a convex polygon. The described algorithm finds a required polygon for all possible tests.
Problem A
One of possible ways of solving the problem is to compare every leave with all taken before. If it matches one of them, than do not take it. Since the order of leaves is immaterial, you can just sort all the leaves (for example, as pairs of strings) and delete unique leaves.
Problem B
The problem is to find a number of triples (x, y, z), such that 0 <= x <= a, 0 <= y <= b, 0 <= z <= c and 0.5 * x + y + 2 * z = n. Trying all triples gets TL, but you can try all possible values of x and y, satisfying 0 <= x <= a, 0 <= y <= b. When x and y are fixed, z can be determined uniquely. So we get O(a*b) solution.
Problem C
The easiest solution is to process all the days from 1 to n, and check for each day, that it is covered by exactly one segment [ai, bi]. If you find a day which is covered by less or more than one segment, output this day.
Good day to everybody!
I am glad to invite you to participate in the next round of the series of winter programming school olympiads, that will be held on the 6th of November at 14:00 MSK.
The contest is official for school teams, and unofficial and not rated for everyone else. Remember, that if you have a school team, you must register all the participants for the series, if you haven't done it yet.
The duration of the contest will be 5 hours, and the rules are standard ACM ICPC.
The problems were prepared by me, Dmitry Matov, Polina Bondarenko, Mikhail Mirzayanov, and also by Maria Belova, who translate them to English. We all hope that the contest will be interesting for you to participate.
Good luck!
UPD. Statements in PDF: russian version and english version. The statements will be available when the contest starts.
The contest is over. The winner is Gennady Korotkevich who solved 9 problems for less than 3 hours. Results are available.
Tutorial:
Problem A
To get the maximal possible result you have just to sort summands in non-decreasing order by coefficients (counting coefficients with preceeding signs + and -). You should not pay attention to 'a++' or '++a'! The question is: why is it true?
First, consider an expression with only 'a++'. Then our assertion is obvious: it is better to multiply 'a' by small coefficients when it has small value, and by large coefficients, when it becomes larger. The same also takes place in case of negative coefficients or a-value. Of course, it is not a rigorous proof. I hope you will think on it if you haven't get it yet.
Second, consider the expression k * a + + + k * + + a, where k is some coefficient equal for both summands. Let initial value of 'a' equals to a0. Calculating the value of the expression both ways, we obtain: k * a0 + k * (a0 + 2) = k * (a0 + 1) + k * (a0 + 1). So in this case the order is immaterial.
Third, let us have the expression k * a + + + l * + + a, where k and l are two distinct coefficients. This expression can have two different values: k * a0 + l * (a0 + 2) and k * (a0 + 1) + l * (a0 + 1). The first value is greater than the second one if and only if k < l. We can deal with the expression k*++a+l*a++ analogously.
Thus if we have two succesive summands with the same coefficient, we may swap or not to swap them. If we have two succesive summands with distinct coefficients, we must put the summand with a smaller coeficient first. Applying these considerations while it is necessary, we get a sequence of summands sorted by coefficients.
Good day to everybody!
Welcome to School Team Contest #1 that will be held on the 24th of October at 11:00 MSK. The contest will be official for school teams as a part of the series of winter programming school olympiads (http://codeforces.ru/blog/entry/753), and it will be informal (and not rated!) contest for everyone else.
To compete officially, each participant of a school team must at first register personally, then you must create a team of registered participants, and when registration to the contest opens, you must register your team there too.
I hope that the problems will be interesting for school students with different level of programming skills, and not only for school students! Pay attention to some differences from usual Codeforces contests. First, the duration of the contest is 5 hours, and there will be standard ACM rules. Second, problems will not be sorted in increasing order by their complexity, they will be shuffled. So your first problem for you is to find an easy problem :)
The authors of the problems are Mikhail Mirzayanov and me. Thanks to Gerald Agapov, Polina Bondarenko and Artem Rakhov, who helped me to prepare the round. Also thanks to Maria Belova for translating problem statements into English. We all are from Saratov State University.
Good luck!
UPD: After the contest start, it will be available PDF-versions of the statements:
UPD: The contest is over. The results are available. The winner in both official and non-official standings is Gennady Korotkevich, who has solved all the problems. Congratulations to the winner! The problem analysis is available.
The problem is to divide edges of a graph into two groups forming two paths in the graph. Clearly, each path is contained in one connected component. So if the given graph has more than two connected components, the problem has no solution. The same we can say if the graph has more than four vertices of an odd degree. Indeed, each vertex in a path (even if the path contains some vertices more than once) have an even degree, exept the first vertex and the last vertex. So the union of two paths can contain no more than four odd vertices.
Now consider the cases:
1. One connected component, no vertices of an odd degree. So we have an euler cycle, which can be divided into two paths.
2. One connected component, two odd vertices. The same with an euler path instead of euler cycle. There is a tricky case of a graph with only one edge, which cannot be divided into two nonempty paths.
3. One connected component, four odd vertices. The most interesting case. Connect two vertices of an odd degree by a dummy edge. You will get a graph with an euler path. Find the euler path and delete the dummy edge - you will get two paths.
4. Two connetced components, each having zero or two odd vertices. Two euler paths/cycles.
5. Two connected components, four odd vertices in one and no odd vertices in another. No solution.
In the problem we have a game on an acyclic graph. Positions in the game (vertices of the graph) are pairs (n, m), where n and m are distances from the current position of the piece to the bottom and to the rights borders of the board. For every position (n, m) there are at most three moves: (n - 1, m), (n, m - 1), (n - k, m - k). The graph is acyclic, because at each move the sum n+m strictly decreases.
If the numbers n, m and k do not exeed, say, 1000, the problem is solved by easy dynamics on the acyclic graph, standard for such games. Let d(n, m) = 1, if the position (n, m) is winning, and d(n, m) = 0, if the position (n, m) is losing. The value of d(n, m) is calculated using the following considerations. If there exists a move from the current position to a losing one, then the current position is winning, otherwise it is losing.
But conditions of the problem do not allow us to solve it by the standard dynamics. The solution is to implement the dynamics for small values of n and m and to find a pattern! For example, build the matrix of values d(n, m) for k = 2:
If the numbers n, m and k do not exeed, say, 1000, the problem is solved by easy dynamics on the acyclic graph, standard for such games. Let d(n, m) = 1, if the position (n, m) is winning, and d(n, m) = 0, if the position (n, m) is losing. The value of d(n, m) is calculated using the following considerations. If there exists a move from the current position to a losing one, then the current position is winning, otherwise it is losing.
But conditions of the problem do not allow us to solve it by the standard dynamics. The solution is to implement the dynamics for small values of n and m and to find a pattern! For example, build the matrix of values d(n, m) for k = 2:
01010101010101
10101010101010
01111111111111
10110101010101
01101010101010
10110111111111
01101101010101
10110110101010
01101101............
In author's solution the fractal is built by a recursive function. Let ''a'' be a square nk × nk result matrix. Write the recursive function fractal(x, y, k) filling a square part of the matrix with an upper left corner in (x, y) and a length of the side nk, drawing the fractal of depth k. In case k = 0 put ''.'' at the current position. Otherwise you have to divide the part of the matrix into n2 square parts with size nk - 1 × nk - 1, and fill them according to the model. If the corresponding symbol in the model is ''*'', fill the square with symbols ''*'', otherwise execute fractal(x1, y1, k-1) for (x1, y1) being the coordinates of the upper left corner of the new square.
kdalex offers a solution (http://codeforces.ru/blog/entry/764), which is easier in implementation. Consider all positions (x, y). If for some c = nd, 0 ≤ d < k the square ((x/c)%n, (y/c)%n) of the model is black then (x, y) must be black, otherwise it is white. It is easy to check that if the square ((x/c)%n, (y/c)%n) is black for d = k - 1 , then we have that the current position (x, y) is in the black square after the first step of the algorithm. If ((x/c)%n, (y/c)%n) is black for d = k - 2, it happens after the second step, etc.