Hello everyone!
I’ve just added two contests from Summer Petrozavodsk Training Camp to the Gym section.
The first contest was prepared by the students of Taras Shevchenko National University of Kyiv: Vladislav Simonenko, Roman Rizvanov and me (Iaroslav Tverdokhlib). The second contest was prepared by the students of Taras Shevchenko National University of Kyiv and V.N. Karazin Kharkiv National University: Andrii Korotkov (KNU), Stepan Palamarchuk (KNU), Vladislav Simonenko (KNU), Dmytro Soboliev (KhNU), Evgen Soboliev (KhNU) and me (Iaroslav Tverdokhlib — KNU).
I hope you’ll like the contests. Good luck and have fun!
Here is the editorial of Codeforces Beta Round #97. If you have any questions or suggestions --- feel free to post them in the comments.
136A - Presents (A Div 2)
In this problem one had to read a permutation and output the inverse permutation to it. It can be found with the following algorithm. When reading the i-th number, which is equal to a one can store i into the a-th element of the resulting array. The only thing left is to output this array.
The complexity is O(N).
Hello everyone!
Codeforces Beta Round #97 will take place on Friday, December 9th at 19:00 MSK. This will be my second classical Codeforces round and I hope it won't be the last one :)
I'd like to thank maksay, Shtrix, it4.kp, RAD and Delinur for their help in preparing contest, testing problems and translating them into English.
Good luck!
UPD: Due to technical reasons the round start time is shifted 5 minutes forward.
UPD 2: Due to the large number of participants and large number of tests the testing will finish not soon.
UPD 3: The testing is over. Thanks for participation! I apologize for a very long testing process.
The winners:
UPD 4: The editorial is released.
Завтра (01.05.2011) состоится личный этап кубка Векуа. На snarknews.info сказано, что он будет проходить по системе TCM/Time. Может кто-то знает, это то же самое что и TCM/SE или же что-то новое?
UPD: правила есть на сайте кубка Векуа.
The editorial is now completed.
Problem A: Gift (Roman Iedemskyi)
Suppose that the pair (A, B) is an optimal solution, where A is the number of gold coins in a gift and B is a number of silver coins. It is easy to see that there exist two (probably equal) indexes i and j such that gi = A and sj = B. It is true, because in the other case we could decrease either A or B without changing connectivity of the graph.
Let R(A, B) be the graph in which for all i the following statement holds: 
.
.Let T(A) be the weighted graph in which for all edges gi ≤ A. For each edge i we will assign a weight equal to si. Let's find a spanning tree of this graph, which has the property that its maximal edge is minimal possible. It can be shown that for the fixed A the minimal value of B for which graph R(A, B) is still connected is equal to the weight of the maximal edge in this spanning tree.
Claim. Minimal spanning tree of a graph has the property that its maximal edge is minimal possible among all spanning trees.
Proof. Let L be the minimal spanning tree of a graph. Suppose there exists a spanning tree P in which all edges have smaller weight than the weight of the maximal edge of L. We can then remove the maximal edge from L and add some edge from P to it which will connect the graph back. After that L will have strictly smaller weight, which is impossible because it is a minimal spanning tree.
Let's sort all edges of the graph in ascending order of gi. Then the edges of graph T(A) for the fixed i will be all edges with indexes j ≤ i.
Suppose that for some value of i we have already found minimal spanning tree in every connected component of the graph T(gi). Let's add an edge with index i + 1 into it. If it connects two different components, then after this operation they will be merged into one big component and it is obviously that the spanning tree we have in it is the minimal spanning tree. If i + 1-th edge connects two vertices from the same connected component, then it will create exactly one cycle in the graph. We can find the maximal edge in this cycle and remove it from the graph. It can be proven that the remaining tree will be the minimal spanning tree of this connected component.
We can perform the search of the maximal edge in a cycle as well as the insertion and removal of the edges in O(N). The total complexity is O(NM + MlogM).
Problem B: Mice (Roman Rizvanov)
It is easy to see that the number of closest pieces of cheese for each mouse is not greater than 2.
Let's find the closest pieces of cheese for each mouse to the left and to the right from it. From two directions we will choose the one which gives us shorter way to cheese or both of them if their lengths are equal. If on the chosen way between the mouse and the cheese stands another mouse, then we should exclude this way from consideration, because another mouse will get to the cheese faster. Now all the directions lead to cheese and for each piece of cheese there is at most one mouse which can potentially eat it from each direction.
We will process mice from left to right. If the current mouse can move left and the cheese to the left of it is not chosen by any other mouse or it is chosen by a mouse with the same distance to it, then the current mouse can move to the left and eat this piece of cheese without interfering with other mice. This choice will not affect any choices of the next mice, because only one mouse can go to this piece of cheese from the right (see previous paragraph). Thus, this choice can not decrease the answer. In all other cases the current mouse can not increase the answer by moving left, so it should move to the right if it has such opportunity.
The complexity is O(N + M).
This problem can be also solved using dynamic programming.
Problem C: Mutation (Iaroslav Tverdokhlib)
In the editorial we will replace terms "risk", "genome" and "gene" with "cost", "string" and "character", respectively. Let S be the starting string.
Let M be the bitmask of chars which will be removed. Let's iterate over all possible values of M. For the fixed M we need to find a cost of the string, which remained after removal of M and if this cost doesn't exceed T we will increase the answer by 1. Naive implementation of this idea has the complexity O(2KN).
We can not get rid of iterating over all M, so we will try to optimize a part of the algorithm which finds a cost of the remaining string.
Let's take two indexes l and r from the beginning string l < r. Let M' be the bitmask of all characters which are located strictly between them. It is obviously that if 
or 
then l and r can not be neighbours in the remaining string. Hence for the fixed l there are not more than K possible candidates for r, which means that there are O(NK) pairs of such potential neighbours. We will call such pairs "good".
or then l and r can not be neighbours in the remaining string. Hence for the fixed l there are not more than K possible candidates for r, which means that there are O(NK) pairs of such potential neighbours. We will call such pairs "good".We want to find out what form should have the set M that after its removal indexes l and r became adjacent. It is easy to see that the following two conditions should be true:
1. 
2. 
Let's iterate over all good pairs of l and r and for each of them we will find the set M'. For each triple (a, b, P) we will store the sum of costs of neighborhood of all pairs l and r for which Sl = a, Sr = b, M' = P. After that for the fixed M we will iterate over all pairs of characters (a, b) and its subsets P and add all their costs together. Also we need to add the cost of removal of M and the resulting sum will be the cost of the string which will left after removal of M. The complexity of such solution is O(3K * K2 + NK).
We will optimize the previous solution by decreasing a factor near 3K. Let's look at the following (incorrect) algorithm:
We will iterate over all good pairs l and r and for each of them we will find M'. Let's create an array v in which for each mask P we will store the sum of costs of neighborhood of all pairs l and r for which M' = P. For the fixed M we will find a sum of all values from v for all submasks of M, then add the cost of removal of M to it and the resulting sum will be the cost of the remaining string.
This algorithm is incorrect, because some costs of neighborhood are added to the total cost, but in fact the respective l or r are removed. Let's use inclusion-exclusion principle and make the following at the phase of filling array v:
v[M'] + = cost
With such filling of v the algorithm described above is correct and the total complexity becomes O(3K + NK).
This is still not enough for the full solution, but we are almost there. We only need to find a fast way of finding the sum of the values of v for all submasks of all masks M. We will use the following iterative algorithm for this purpose:
Before the first iteration we have an array v in which the starting values are stored. After iteration with number i in v[mask] we will store the sum of all the values from the original array v for all submasks of mask for which the first K - i bits are equal to the respective bits of mask. On iteration with number i for all masks in which the i-th bit is equal to 1 (bits are numbered from 1) we will perform the following: v[mask] + = v[mask\{i}]. It is easy to see that after the K-th iteration of this algorithm we will have the values we were looking for in array v.
The complexity is O(2KK + NK).
Problem D: Plus and XOR (Daniel Neiter)
Let's take a look at some bit in X, which is equal to 1. If the respective bit in Y is equal to 0, then we can swap these two bits, thus reducing X and increasing Y without changing their sum and xor. We can conclude that if some bit in X is equal to 1 then the respective bit in Y is also equal to 1. Thus, Y = X + B. Taking into account that X + Y = X + X + B = A, we can obtain the following formulas for finding X and Y:
X = (A - B) / 2
Y = X + B
One should also notice that if A < B or A and B have different parity, then the answer doesn't exist and we should output -1. If X and (A - X) ≠ X then the answer is also -1.
Problem E: Points (Daniel Neiter)
Let's regroup summands and split the sum of squares of distances we are looking for into two sums:
Now we need to rewrite each of these sums in the following way (it will be shown for the first sum):
This formula allows us to find an answer in one pass through the array. The complexity is O(N).
Problem F: Tourist (Ilya Porublyov)
We can get to the event j from the event i if the following statements are true:
- ti ≤ tj
- |xi - xj| ≤ |ti - tj|· V
We can represent all the events as points on a plane with coordinates (xi, ti). Now we can reformulate the two statements written above in the following way:
From the event i we can get to the event j if the point (xj, tj) lise inside an angle pointed to the top with its vertex in (xi, ti) and its sides form an angle arctg(V) with vertical axis. Let's make coordinate transformation according to which the point with coordinates (xi, ti) will transform into the point (pi, qi), where
pi = - xi + ti * V
qi = xi + ti * V
Now we can get to the event j from the event i if pi ≤ pj и qi ≤ qj. Let's sort all points in ascending order of p. If several points have the same p we will sort them by q. The second subproblem of our problem can be solved by finding a longest increasing subsequence by q in this array. It can be done in O(NlogN).
To solve the first subproblem we can add dummy event with coordinate 0 and time 0 (if it is not present in our set of events yet) and force tourist's start from it.
The total complexity if O(NlogN).
Hello everyone!
I woud like to announce unofficial translation of All-Ukrainian School Olympiad in Informatics, which will take place on Codeforces at Tuesday, 12th of April at 16:00 MSK. Contest will be based on problems from recently finished All-Ukrainian Olympiad in Infomatics - UOI2011. It will go according to the ACM-ICPC rules. Both teams and individuals are eligible for participation. The contest will be unrated.
We kindly request not to discuss problems from this olympiad before its ending and not to participate in this contest if you already know statement or solution of any problem from it.
The authors are: Daniel Neiter, Roman Iedemskyi, Roman Rizvanov, Ilya Porublyov and me (Iaroslav Tverdokhlib).
The PDF problem statements will be available via links:
Я давно собирался написать некоторые свои мысли о системе взломов, которую мы имеем на данный момент, и раунд 60 стал своеобразным толчком к этому.
Что мы имеем на данный момент: взломы можно делать на протяжении всего раунда, каждый успешный взлом приносит 100 очков, каждый неудачный взлом отнимает 50 очков, участники из обоих дивизионов перемешаны и каждый может взламывать каждого в своей комнате.
Мне всегда казалось, что на олимпиадах по программированию вроде Codeforces или Topcoder в первую очередь нужно уметь решать задачи, а уже потом взламывать чужие решения. Кто-то скажет что все заранее знают правила и у всех свои стратегии. Я согласен с этим, но тем не менее не считаю правильным иметь возможность за счет вариации стратегии будучи с 2-мя задчами обойти человека который решил 4, причем не очень медленно.
Для статистики я взял последние 10 раундов для обоих дивизионов и для каждого выписал максимальный процент баллов, набранных за счет взломов от общего количества баллов набранных участником, взятый среди первой пятерки по результатам контеста.
Раунд Максимальный процент Средний процент
Codeforces Beta Round #39 12.1% 4.8%
Codeforces Beta Round #41 10.3% 7.0%
Codeforces Beta Round #47 15.4% 5.2%
Codeforces Beta Round #48 30.8% 15.9%
Codeforces Beta Round #50 10.8% 5.4%
Codeforces Beta Round #51 11.6% 2.8%
Codeforces Beta Round #53 20.8% 10.8%
Codeforces Beta Round #56 12.2% 2.4%
Codeforces Beta Round #58 27.3% 6.5%
Codeforces Beta Round #60 70.5% 53.0%
Итак, в каждом из последних 10 контестов для обоих дивизионов был хотя бы один участник из первой пятерки, набравший более 10% своих баллов на взломах. В 4 из 10 контестов был хотя бы один участник из топ-5, набравший более 20% своих баллов на взломах. В одном контесте был участник, набравший более 70% своих баллов на взломах, причем в среднем на этом контесте первая пятрка набрала более 50% баллов на взломах.
Хоть ситуации подобные последнему раунду - редкость (хотя, в раунде 58 было бы то же самое, не будь там проблемы с условием задачи А), но все же они встречаются. Далее я постараюсь провести анализ ситуации со взломами на последнем раунде.
Итак, победитель раунда реализовал 39 успешных взломов, причем в его комнате другими участниками была сделана всего одна успешная попытка взлома. Теперь возьмем комнату 3. Во взломах в этой комнате принимали участие 4 человека, из них двое сделали более одного успешного взлома, поэтому далее будем учитывать только их. В сумме они реализовали 28 успешных взломов по задаче А, причем в этой комнате было всего 3 решения по этой задаче, которые не прошли финальное тестирование. Учитывая что в комнате победителя было 5 решений задачи А, которые не прошли финальное тестирование, то можно проигнорировать эти 3 решения из комнаты 3. Получаем, что даже если сильнейший участник попадет в комнату 3 и реализует эти 28 взломов с 1 попытки, он максимум сможет получить 2800 очков на взломах против 3800 реально полученных очков из комнаты 7.
Из-за распределения по комнатам очки за взломы могут варьироваться даже на +-1000 и даже сильнейшие участники попав в неудачную комнату не имеют шансов выиграть контест. Рассматривая эту ситуацию с комнатами 3 и 7 я не учитываю то что взламывать могут несколько человек в одной комнате, что тоже сильно снижает суммарные очки по взломам. Например, в комнате 6 два участника примерно в одно и то же время (на 11 и 13 минутах) начали взламывать задачи А, позже к ним присоединился еще один. Каждый из первых двух начавших взламывать реализовал по 12 взломов. Сильнейший участник попав в эту комнату не имеет шансов реализовать все взломы в этой комнате, даже если он очень быстро сдаст и заблокирует А и сразу начнет взламывать чужие решения. Даже если предположить что у него отберут 12 взломов, реализовав все остальные взломы с 1 раза он сможет набрать 2000 очков на взломах, что на 1800 меньше чем у победителя раунда. Опять же, шансов победить в этом раунде у него нет.
Я считаю что текущая система должна быть подвергнута изменениям. Есть 2 способа стабилизировать взломы, причем лучше всего их объединить.
1. Разделить участников из 1 и 2 дивизиона в разные комнаты. В среднем первые 5 участников по турнирной таблице последнего раунда набрали +300 очков на взломах фиолетовых, оранжевых и красных, остальные очки были набраны на серых, зеленых и синих. Разделив дивизионы, красные уже не смогут так беспощадно взламывать серых, тем самым уменьшится суммарное количество очков по взломам.
2. Изменить количество очков за взломы. Я уже не помню кем и где высказывалась мысль о том, что можно насчитывать баллы за взлом в зависимости от разности рейтинга взломщика и взламываемого. Например, если красный взламывает серого, прибавлять 20 баллов, если же серый взламывает красного, прибавлять 100 баллов. Количество баллов за взломы у победителя не будет заоблачным, в то же время вряд ли серые смогут навзламывать много красных и выбиться в топ турнирной таблицы за счет этого, не решив при этому большую часть задач.
Это сугубо мое мнение и оно может отличаться от мнения общественности. Критика и комментарии приветствуются.
Suppose that the top and the bottom borders of the rectangle are fixed, and we are to choose only the left and the right borders. Then we can in O(K) find a list of all the rectangles which are contained in our band, and also a list of all the rectangles having a part in our fixed strip. We can represent it as a sorted collection of segments [l, r], where l and r are x-coordinates of left and right borders of a rectangle.
If multiple segments in the collection have a common point, glue them to make a one long segment, and memorize that now it really represents two segments. Thus, after such a gluing we obtain a collection of segments, and for each segment in the collection we know the number of rectangles covered by it (if there is a rectangle in it not lying in the band completely, we threat this segment as if it contains an infinity number of rectangles). Now we can process all the free segments (located between neirbouring segments in ur collection) and count the number of ways to cover them by a segment including no more than three objects (for this we will memorize only free segments separated from the current one by not more than three objects).
Thus, we already have the O(N^2 K) solution: to try all possible horisontal bands and to compute for each of them in O(K) the number of rectangles covering from 1 to 3 objects. Note that if, for instance, the top border of the band touch no object, then we can move it up or down, and the answer for the band wouldn't change. Hence we can take as a border of a band only those rows, which contain at least one square belonging to an object, and then multiply the obtained result by the distance to the closest "non-empty" strings from above and below.
Thus, we get the solution working O(K^3) and not depending on the field size or the limit on the number of covered objects.
There are regular after-contest competitions on Topcoder named shortest code competitions. Sometimes it is very interesting to see how the code of some easy task can be compressed to weird and unreadable one, but at the same time this code passes all the test cases. I suggest to hold such competitions here.
I will start from task C from Codeforces Beta Round #24. The rules are simple: each next code should be shorter than previous one. The winner is the person whose code is not beaten by anyone else. Length of the code is the number of non-whitespace characthers in it. Of course, the code should be AC on at least one of the allowed compilers. As far as I know, defines are not used on Topcoder shortest code competitions, so I suggest not to use them here either.
There are some special features in different languages, so I suggest to have different standings for different languages, because I doubt that C++ or Pascal can compete with Haskell or Python.
214:
#include <iostream>
__int64 n,k,x,y,a[' '],b[' '],d;
int main()
{
std::cin>>n>>k>>x>>y;
for(k%=2*n;d<n;d++) std::cin>>a[d]>>b[d],d<k?x=2*a[d]-x,y=2*b[d]-y:0;
for (d=0,k-=n;k>0;--k,++d) x=2*a[d]-x,y=2*b[d]-y;
std::cout<<x<<" "<<y;
}
Let me introduce an editorial to Codeforces Beta Round #13. If you have any questions or propositions - feel free to post them in the comments.
Welcome all to Codeforces Beta Round #13, which will be held on Thursday, 6th of May at 18:00 MSK. I am an author of the problems.
I would like to thank Mike Mirzayanov who made this contest possible, Roman Iedemskyi and Andriy Maksay for helping to test authors solutions and Dmitry Matov for the translation of problem statements into English. Hope you will like the problems.
I hope that number 13 would be lucky for you!
UPD: Congratulations to Ivan Metelsky who became the winner, having solved all 5 tasks!
You can view the tasks here.
You can view the results here.
UPD2: I've added an editorial.