KADR's blog

Editorial of Codeforces Round #153
By KADR, 12 years ago, translation, In English

This is a complete English version of the editorial of Codeforces Round #153. If you have any questions or suggestions, feel free to post them in the comments.

252A - Little Xor (A div 2)

Let's iterate over all segments in our array. For each of them we'll find the xor of all its elements. Then we need to output the maximal xor we've seen.

252B - Unsorting Array (B div 2)

If all elements in the array are equal then there's no pair of numbers we are looking for. Now we can assume that there exist at least 2 different numbers in the array. Let's iterate over all pairs of different numbers in the array and for each such pair we'll check if it can be the answer. If some pair indeed can be the answer, we'll output it and terminate the program. Otherwise, there is no pair of numbers we are looking for, so we need to output -1.

It may seem that the complexity of described algorithm is O(N3). Actually it's not true and the real complexity is O(N). One may notice that in every array of length greater than 3 there are at least 3 pairs of different numbers (remember we assumed that there exist at least one pair of different numbers in the array). Note that these 3 pairs lead to 3 different resulting arrays. On the other hand, there are only 2 possible sorted arrays. According to the pigeonhole principle one of these 3 resulting arrays is unsorted.

252C - Points on Line (C div 2)

251A - Points on Line (A div 1)

Let's select the rightmost point of our triplet. In order to do this we can iterate over all points in ascending order of their X-coordinate. At the same time we'll maintain a pointer to the leftmost point which lays on the distance not greater than d from the current rightmost point. We can easily find out the number of points in the segment between two pointers, excluding the rightmost point. Let's call this number k. Then there exist exactly k * (k - 1) / 2 triplets of points with the fixed rightmost point. The only thing left is to sum up these values for all rightmost points.

252D - Playing with Permutations (D div 2)

251B - Playing with Permutations (B div 1)

First, we need to theck whether permutation s is the identity permutation. If it is, then the answer is "NO".

Now we'll describe an algorithm which works in all cases except for one. We'll tell about this case later.

Let's apply our permutation q until either the current permutation becomes equal to s or we make exactly k steps. If the current permutation is equal to s and we've made t steps before this happened, then we need to look at the parity of k - t. If this number is even, then we can select any two consequent permutations in the sequence and apply (k - t) / 2 times the following two permutations in this order: q and inv(q), where inv(q) is the inversed permutation q. Actually, we don't need to build the sequence itself, it's enough to check only the parity of k - t. So, if it is even, then the answer is "YES".

Analogically, we can replace q with inv(q) and repeat described process again. If we still didn't print "YES", then the answer is "NO".

The algorithm we've just described works for all cases except for one: when the permutation q is equal to inv(q) and at the same time s is reachable within one step. In this case the answer is "YES" iff k = 1.

The complexity of described solution is O(N2).

252E - Number Transformation (E div 2)

251C - Number Transformation (C div 1)

Let L be the least common multiple of all numbers from 2 to k, inclusive. Note that if a is divisible by L, then we can't decrease it with applying an operation of the second type. It means that any optimal sequence of transformations will contain all numbers divisible by L which are located between b and a. Let's split our interval from b to a into several intervals between the numbers divisible by L. It may happen that the first and the last intervals will have length less than L. Now we can solve the problem for the first interval, the last interval and for any interval between them. After that we need to multiply the last result by the total number of intervals excluding the first and the last ones. The only thing left is to add up obtained 3 values.

In order to solve the problem for one interval one can simply use bfs.

Be careful in the cases when we have only 1 or 2 intervals.

The complexity of described solution is O(L).

251D - Two Sets (D div 1)

Let X be the xor of all numbers in the input. Also let X1 be the xor of all numbers in the first collection and X2 be the xor of all numbers in the second collection. Note, if the i-th bit in X is equal to 1 then the same bit in numbers X1 and X2 is either equal 0 and 1 or 1 and 0, respectively. Analogically, if the i-th bit in X is equal to 0 then this bit in numbers X1 and X2 is either equal 0 and 0 or 1 and 1, respectively. As we can see, if the i-th bit in X is equal to 1 then it doesn't affect on the sum X1 + X2 in any way. For now, let's forget about the second condition in the statement which asks us to minimize X1 in case of tie.

In order to find the optimal value of X1 + X2 we need to make one more observation. Let's look at the most significant bit of number X which is equal to 0. If there exist such partitions of the initial collection in which this bit is equal to 1 in X1 then the optimal partition should be one of them. To prove this one should remember that the respective bit in number X2 is also equal to 1. Let this bit correspond to 2L. If the bit we are looking at is equal to 1 in both X1 and X2 then the smallest possible value of X1 + X2 is 2L + 1. On the other hand, if both X1 and X2 have zero in this bit, then the maximal possible value of X1 + X2 is 2L + 1 - 2 which is strictly smaller than 2L + 1.

We'll be solving the initial problem with a greedy algorithm. Let's iterate over all bits which are equal to 0 in number X from highest to lowest. We'll try to put 1 to the number X1 in this position and then check if there exists at least one partition which satisfies the current condition together with all conditions we've already set up. If such partition exists, then we can leave our newly added condition and move to lower bits. If there is no such condition, then we need to move to lower bits without adding any new conditions. At the end we'll find the maximal value of X1 + X2.

So, we have a set of conditions and we want to check if there exist at least one partition which satisfies all of them. For each condition for i-th bit we'll create an equation over the field Z2 with n variables, where the coefficient at the j-th variable is equal to the i-th bit of the j-th number. If some variable is equal to one then we take the corresponding number into the first set, otherwise -- into the second one. This system of equations can be solved with Gaussian elimination. Note that we don't need to solve the complete system from scratch every time we add a new equation. It's sufficient to recalculate the matrix from the previous state, which can be done in O(NK). Here K is the number of equations in the system.

Now we need to minimize X1 while keeping the value of X1 + X2 unchanged. It can be done in the similar way as finding the optimal value of X1 + X2. We'll iterate over all bits which are equal to 1 in number X starting from the highest one. For the current bit we'll try to put 0 in the corresponding position of X1. If after adding this condition our system of equations becomes incompatible, then we need to put 1 in this position of X1.

The complexity of this algorithm is O(NL2), where L -- is the length of binary notation of the largest number. For further optimization one can use bitset in Gaussian elimination, although it wasn't necessary for getting AC during the contest.

251E - Tree and Table (E div 1)

If N = 1, then the answer is 2.

If there is a node with degree greater than 3 in the tree, then the answer is 0. That's because every cell of the table has at most 3 neighbors.

If there is no vertex of degree 3 in the tree, then the answer is 2n2 - 2n + 4. This formula can be derieved in natural way during the solution of other parts of the problem. Also, one could write a simple DP to calculate the answer in this case. Anyway, let's prove this formula.

At first, let's solve slightly different problem, which will be also used in the solution of main case of the initial problem. We want to find the number of ways to place a tree in which all nodes have degree smaller than 3 on the table so that one node of degree 1 is attached to the upper-left corner of the table (let it be node number 1). It can be shown that if the table has size 2xK, then the number of placements of the tree is equal to K. The last formula can be proven by mathematical induction. If K = 1 then the above statement is obviously true. Suppose K > 1 and let's assume that the table is oriented horizontally so that we have 2 rows and K columns. If we put a vertex adjacent to the first one to the right from upper-left corner then we have only 1 way to complete the placement of the tree. If we put this vertex to the bottom-left corner, than the next vertex should be put to (2, 2) and the problem is reduced to the same one with K smaller by one. We have a recurrent relation f(K) = f(K - 1) + 1 and we know that f(1) = 1. This means that f(K) = K.

Let's come back to the initial problem of counting the nymber of ways to put a tree without vertices of degree 3 on the table 2xN. Without loss of generality let's assume that the first vertex has degree 1. We'll consider only placements in which the first vertex is laying in the first row and at the end we'll multiply our answer by 2. If the first vertex is laying in the first or the last column then then there are N ways to complete the tree (see the previous paragraph). If the first vertex is laying in the i-th column than there are i - 1 ways of placing our tree in which a vertex adjacent to the first one (let it be vertex 2) is laying to the left of it. Also there are N - i ways in which the second vertex is laying to the right of vertex 1. Adding up these values for all columns and multiplying the answer by 2 we get the final formula: 2n2 - 2n + 4.

Now we have only one case left in which there exists a vertex of degree 3 in our tree. Let's declare this vertex to be a root. If there are several vertices of degree 3, any of them can be chosen to be a root. We'll assume that the root is laying in the first row and at the end we'll multiply our answer by 2. Obviously, the root should be put to a cell with 3 neighbors. Each descendant of the root should be put either to the left, to the right or to the bottom from the cell which contains the root. Let's fix this ordering (to do this we need to iterate over 6 permutations). Also if the "bottom" son of the root has degree greater than 1, then we'll also fix the ordering of its adjacent vertices (there are 2 ways to do this). Now the column which contains the root is fully occupied. The last statement means that regardless of the way we place the rest of vertices, the ones to the right from the root will stay there. The same for all vertices which lay to the left from the root. Moreover, we have the fixed number of vertices to the left from the root, which means that there's at most one way to place the root on our table. Note that if the number of vertices to the left from the root is odd, then we won't be able to complete the placement. In order to find the number of vertices to the left from the root we need to sum up sizes of subtrees of its left descendant and of the left descendant of its bottom son.

So, we have two separate subproblems (for vertices laying to the left from the root and to the right from the root) and for each of them we need to calculate the number of trees to place the rest of our tree in the table. There are only two possible situations:

1) We need to place a subtree with its root in vertex v on the rectangular table in such way that vertex v is laying in the corner (let it be upper-left corner).

2) We need to place subtrees with roots in v1 and v2 on the rectangular table in such way that vertex v1 is laying in the upper-left corner and vertex v2 is laying in bottom-left corner.

Obviously, each of these two problems has non-zero answer only if total size of subtrees is even.

Let's show how to reduce a problem of the second type to a problem of the first type. So, if either v1 or v2 has two descendants, then the answer is 0. If both of them have one descendant, then we can solve the same problem for their children which'll have the same answer. If both v1 and v2 have no children, then the answer is 1. At last, if one of these two vertices has 1 descendant and the other vertice doesn't have any descendants, we have a problem of the first type for this only child of vertices v1 and v2.

The only thing left is to solve a problem of the first type. Let f(v) be the number of ways to place a subtree having vertex v as its root on the rectangular table. The size of this table is determined uniquely by the size of subtree. Let's consider two cases:

a) Vertex v has degree 2.

b) Vertex v has degree 3.

In the case when vertex v has degree 2 and there are no vertices of degree 3 in its subtree, then f(v) = s(x) / 2, where s(v) is the size of subtree with its root in vertex v. We've already proven this formula above. Now let's suppose that there's at least one vertex of size 3 in the subtree with root v. If there are several vertices with degree 3, we'll chose the one that is closer to vertex v. Let it be vertex w. We have 2 possible cases for it:

a.1) Path from vertex v to vertex w will go in such way that the vertex which lays before vertex w in this path is located to the left from vertex w on the table.

а.2) Path from vertex v to vertex w will go in such way that the vertex which lays before vertex w in this path is located to the top from vertex w on the table.

Its easy to show that there's no third option.

In each of two cases a.1) and a.2) we'll fix directions of descendants of number w (one direction is taken by the parent of vertex w, so there are exactly 2 possible directions). In case if descendant of degree greater than 1 is located in the same column with w, we need to fix directions of its descendants, too. After this we have problem of type 1) or 2) to the right of vertex w. To the left from w we have a tree which either can't be put on the table or can be put in exactly 1 way. In order to check this we need to look on the length of path from v to w and the size of subtree of grandson of w, which is located to the right from w (of course, if it exists). Now we need to sup up answers for all possible variants.

So we know how to solve problem of type a), when vertex v has degree w. The only thing left is to solve problem b), when v has degree 3. To do this we need to fix directions of its descendants and after that we'll have either a problem of type 1) or a problem of type 2), which were formulated above.

The complexity of solution is O(N).

Full text and comments »

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

Codeforces Round #153
By KADR, 12 years ago, translation, In English

Hello everyone!

Codeforces Round #153 will take place on Thursday, December 6th at 19:30 MSK. This is my third Codeforces round and I hope there will be more.

I'd like to thank Shtrix, Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I hope you will like the problems.

Good luck and have fun!

UPD: Complete version of English editorial is now available.

Congratulations to the winners!

Division 1:

  1. Egor
  2. tourist
  3. rng_58
  4. kelvin
  5. Burunduk1

Division 2:

  1. inker
  2. WhoTheHellIsMe
  3. memo1288

Full text and comments »

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

Two more contests from Petrozavodsk Training Camp.
By KADR, 13 years ago, translation, In English

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!

Full text and comments »

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

Codeforces Beta Round #97: editorial
By KADR, 13 years ago, translation, In English

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).

Full text and comments »

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

Codeforces Beta Round #97
By KADR, 13 years ago, translation, In English
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.

Full text and comments »

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

All-Ukrainian School Olympiad in Informatics: editorial (A,B,C,D,E,F)
By KADR, 14 years ago, translation, In English
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".

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).

Full text and comments »

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

All-Ukrainian School Olympiad in Informatics
By KADR, 14 years ago, translation, In English
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:

Full text and comments »

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

School Team Contest #1 (Winter Computer School 2010/11): Problem K Tutorial
By KADR, 14 years ago, translation, In English
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.  

Full text and comments »

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

Shortest code competition
By KADR, 14 years ago, translation, In English
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;
}

Full text and comments »

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

Codeforces Beta Round #13 editorial
By KADR, 15 years ago, translation, In English

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.


Full text and comments »

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

Codeforces Beta Round #13
By KADR, 15 years ago, translation, In English
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.

Full text and comments »

Announcement of Codeforces Beta Round 13
  • Vote: I like it
  • +34
  • Vote: I do not like it