Problems A(div2), B(div2)

Problem C(div2), A(div1)

Problem D(div2), B(div1)

There were a lot of different solutions but I will tell you the author solution. Let's precalculate [i, n]. It can be done with the time equal to O(n) moving from the right to the left. Define [i, n] as Min_i. Obviously, that Min_i <  = Min_i + 1. Now for every position i using binary search let's find j (j > i), that Min_j < a_i and Min_j + 1 >  = a{i}. For such j there are no walruses who have age younger then walrus i. It's obviously because Min_j is the minimum on [j, n]. If there is no such j then print  - 1 else print j - i - 1.

Problem E(div2), C(div1)

We will count the number of ski bases including the base consisted of empty subset of edges (before printing just subtract one). In the beginning the number of bases is equal to 1. If we connect vertexes in the same connected components then the result should be multiplied by 2 else do nothing. You should use DJS data structure to know information about connected components where vertexes are and to unite them.

Why is it correct?
To prove it we will use the matrix of incidence I, rows in it will be edges and columns will be vertexes. Let's define xor of two rows. Xor of two rows a и b will be row c such that c_i = a_i xor b_i. Notice if  xor of some subset of rows is equal to a zero row then this subset form the ski base. It's correct because, the degree of contiguity of every vertex is even, so we can form an Euler cycle in every connected component. The answer is  2(m - rank(I)). 

Why it is correct? Let's write the number of edge from the right of each row which suit this row. While finding the matrix rank using gauss method with xor operation, we will xor the subsets from the right of the strings. In the end the subsets of edges written from the right of the zero rows will form the basis of the linear space. Thats why we can take any subset of vectors from basis and make up a new ski base. The number of these subsets is equal to 2^k = 2(m - rank(I)), where k is the number of zero rows.

The last thing we should notice that the adding row is liner depended if and only if there is exist a way between the vertexes a and b (a and b are the ends of the adding edge).

Задача D(div1)

Let's find all cycles in substitution:
1 2 3 4 5 ...
a₁ a₂ a₃ a₄ a₅ ...
For example, in sequence a = {2, 1, 4, 5, 3} exist two cycles with length 2 and 3 on positions 1 2 and 3 4 5 respectively. If the length of the cycle is more than 5, then we can take 5 consecutive elements and make a new order in such way that 4 elements will take their places where they should be in sorted array. In common: if we take p elements in a cycle of length more than p, the we can make a new order in such way that p - 1 elements  will take their places where they should be in sorted array. If the cycle length is p we can sort all the elements taking p elements from it. Next in the analysis I will define length of a cycle as a real length of a cycle - 1 (now I can say that if we take p consecutive elements then p - 1 will take the right places).
We also can take some elements in one and some elements in other cycles. We can make up division numbers from 2 to 5 into a sum to see how we can use them: 5, 4, 3, 2, 2 + 3, 2 + 2. We can take, for example, three elements in one cycle and two in other, their sizes were reduced by 2 and 1.
The task now is to get all cycle lengths equal to zero. Let's to suppose that an optimal solution have four operations which decrease the same cycle length by one. We will work with operations of 5 elements and which are not process the same cycle except one, because it's more stronger condition.
Such operation can be shown as a table where rows are operations, columns are cycles and cells of table are the values on which cycles will be reduced.
a    b   c    d    e
1    2
1        2
1              2
1                   2 
Replace operations this way:
a    b    c    d    e
4
      2   1
           1    2
                       2
The number of operations was not increased, but now we can see that if there is an optimal solution where one cycle reduced by one four times then there is an optimal solution where no cycles reduced by one four times. Look at some other replacements:
a    b    c
2    1
2          1
Replace by:
a    b    c
4
      1    1

and

a    b    c    d
2    1
1         2
1               2
Replace by:
a    b    c    d
4
      1   2
                 2
Now we can see that there is an optimal solution where no operation reducing one cycle in ways:1 + 1 + 1 + 1, 2 + 2, 1 + 1 + 2. That's why we can reduce any cycle by 4 while it's size is  >  = 4. Let's use zhe same method to prove that cycles of size 3 reduced by 3 in some optimal solution.

a    b    c  
2    1
1          2
Replace by:
a    b    c    d
3
      1    2

and

a    b    c    d
1    2
1         2
1               2
Replace by:
a    b    c    d
3
      2   1
           1    2

Now we have cycles only with size 1 or 2. Let's brute the number of operations to process like {2, 2} -  > {0, 1} (one cycle will be reduced from 2 to 1 and the other will be reduced from 2 to 0). Fix some such number and make these operations. Now we should process the maximum available operations like {2, 1} -  > {0, 0}. After it we will have no cycles or some cycles of size 1 or  some cycles of size 2. In the second case  we should do the maximum of available operations like {1, 1} -  > {0, 0} and if one cycle lasts we should do {1} -  > {0}. In the third case we should to do operations like {2} -  > {0}. Using such way we can find the optimal set of operations. We shouldn't divide cycle into a parts because it makes the number of operation bigger or the same. Stress test shows the uniting cycles will not improve the answer.  

Problem E(div1)

We are given the array where the value in each cell is described by the formula depends on T val_i = a_i + b_i * T (in geometry mean it is a line equation). Lt's divide the array in blocks of size d ~ sqrt(n): [0;d), [d, d * 2), [d * 2, d * 3), ..., [d * k, n). Now let's precalculate for each block time moments when the leader of the block changes. So as we have line equation we can perform an intersection of half planes. On Oy axis values of the cells are marked and the time moments marked on Ox axis. we are interested on x coordinate of points of intersections  and number of leader after time x. So now we know time moment of leader changing for every block. For each block it takes O(d * log(d)) time. The number of blocks (k) is about n / d ~ n / sqrt(n) ~ sqrt(n) so all the process will take O(n * log(n)) time.

Let's sort all queries by increasing t_i. Now we should to perform queries one by one. Brute all blocks which lay into the query interval. For each such block we will keep up the leader for current time. For this let's process all the time moment of leader changing until t_i inclusively and relax leader on the current block. The time moments which ware processed should be erased, they are not keep any useful information ,because all queries sorted by t_i.  Let's process all cells which were not covered by the processed blocks but covered by the query and relax the leader for the query.

The number of erasing time moments of leader changing is not mere then n and every query need O(sqrt(n)) time to calculate answer without erasing time moments. So the complexity of algorithm is O(n * log(n) + m * sqrt(n)). 

Interval tree also can be used to solve this problem. Such solution has complexity O(n * log(n)), but O(n * log(n)) memory.

Hello everyone.

Today I am an author of the contest. This round is for both divisions. There will be five problems in each division. This is my second round on the Codeforces. The actors in this contest will be walruses again =)

I want to thank Codeforces and Alias for helping me to prepare the round.

Good luck!

UPD1:

Points for problems in div1: 500-1000-1500-2500-2500

Points for problems in div2: 500-1000-1500-2000-2500

Analysis 

Problem A.

Let's define a half-filled square of size k as an empty square of size k after adding a cookie of the biggest posible size.

Problem B.

It's obviously, that sentences should be added into the SMS greedily. Really, if we put the sentence into the new message, when it's possible to add into previous, the number of messages may be increased. The only thing you should pay attention is correct processing whitespaces between the sentences.

Problem C.

Will be added soon.

Let's learn how to solve more easy problem: it's need to count a number of lucky tickets with 1 ≤ a ≤ x and 1 ≤ b ≤ y. Rewrite sentence a * b = rev(a) * rev(b) as a / rev(a) = rev(b) / b. Brute all a and count a number of irreducible fractions a / rev(a) using, for example, map from STL. Now for every b you should count the number of fractions a / rev(a) equal to rev(b) / b and add to answer.

Come back to our problem. 

If the number of lucky tickets with 1 ≤ a ≤ max_x and 1 ≤ b ≤ max_y less than w, it should be printed  - 1. If the solution exist, let's use the method of two pointers. 

We need to keep up the quantity of lucky tickets with 1 ≤ a ≤ x and 1 ≤ b ≤ y for some state (x, y) an change it to (x,y+1), (x+1,y), (x,y-1), (x-1,y). That's why we create two structures of type map (named m1 and m2). Let's learn how to change state from (x,y) to (x,y+1), (x+1,y), (x,y-1), (x-1,y). If we want to increase  (decrase) the value of x, we should add (subtract) m2[x/rev(x)] to (from) the number of lucky tickets and increase (decrease) m1[x/rev(x)] by one. In the case of changing y you should do the similar actions.

Let's set the state (x, y), where x = max_x, y = 1 and count the quantity of lucky tickets for it. We will be increase y, while the number of lucky tickets is less than w. Obviously, that it will be the least y for x, such as it will be enough lucky tickets in the range. Relax the answer. You had to decrease x by one and do the same actions while x is greater than one.

The anser have the least value of x * y because we relaxed it with the optimal state for every x.

So, the x was equael to every value between 1 and max_x not more than once. The similar is correct for y because it was only increasing. The time need for change the value in map is O(log(map_size)), that's why the algorithm lave an asymptotic form as O(max_x * log(max_y) + max_y * log(max_x)).

Problem D.

Notice, that any point from the triangle based on first three points will be into the area bounded with the convex hull in the future. Let choose one of these points ad set it as the origin. All points of convex hull will keep in structure like map in C++, where the key is the angle of vector from the origin to a point. No two points from the hull will have the same angle.

How to answer the second-type queries? For the point from the query (A) let's find the closest point clockwise (B) and the closest point anticlockwise (C). If the vectors AB and AC make up a clockwise rotation, then point A doesn't lay into the convex or on it's bounds. 

How to answer the first-type queries? If the point from the query (C) lays into the convex hull, then do nothing else let's find two closest points clockwise relative to point C (the closest will be named A, tho other will be named B). If rotation from the vector AB to the vector AC is a counterclockwise rotation then processing points laying clockwise relative to point C in ended, else you have to delete point A from the structure and repeat the same actions. The similar actions you should apply to points anticlockwise relative to point C.

All points will be added and deleted in the structure not more than once. These operations need O(log(h)) time, where h is a number of point in convex hull. Total  asymptotic form is O(q * log(h)).

Problem E.

Notice next facts. If we have the fixed state of some regional centers then for every city will be assigned the nearest regional center. The regional center of some city will be assigned for all cities between this city and it's regional center. It means that tree should be divided into some subtrees. Also define d[0] = 0.

Let's solve the problem using "crossed" Dynamic Programming.

First function of DP. D1(T, g, x, s) will be responsible for forming the subtree with the regional center g. T is somme subtree of tree from the input defined with edge uv. regional center g must be situated in T. Let's consider that g is assigned to v. The aim will be considered in choosing edges which will bound our subtree. Picture:

Green and red edges connect cities which g was assigned. Purple edge bounds the set of such cities. Notice, that vertexes laying on the red pass cannot be bounding, because g is assigned to v. 

Let xs edge be bounding, then for subtree T' (vertexes of it's subtree are into the circle) call the secnod funtion of DP D2(T').

The second function of DP will brute every point of subtree T' as a regional center and call D1.

D1 have O(n³) states, because the number of subtrees T is O(n), number of options to choose g is the same and pair (x;s) makes up an edge, number of edges is 2*n-2. The second function of DP has O(v) states and transition need O(v) iterations. Thats why solution need O(n³) memory and have asymptotic form O(n³).

Today you will visit the Walrusland and help the common citizens and government to solve their problems.

Good luck for everybody, let the best man win!

Winner is Petr. Congratulations!

Analysis

Last time I began to notice that there are more and more sites which give contests regularly. That's why some contests have the same time.

For example, there will be 3 contests at Saturday:

• School Team Contest #3 (Winter Computer School 201011) at 14:00
• ITMO training at 16:30
• TopCoder 487th Single Round Match at 20:00

I have some questions:

Was this situation before or it have a place to be not so long time?

Which contests do you prefer? Which of them do you solve regularly, from time to time or don't solve at all?