Problem A.

In this task all you had to do was to make sure that the sum of all Σx_{i} is 0, the sum of all Σy_{i} is 0 and that the sum of all Σz_{i} - 0 .

We have not written that condition evidently in order that participants will have a chance to break a solution.

Problem B.

In this problem, in fact, you should find a winner at every section. For each section, you must do a full search of all competitors to find a competitor with a minimum section time, which ran that section. Asymptotic of the solution is O(nm).

Problem C.

In this task, you had to update the collection of artifacts, which belong to Kostya’s friends, after each purchase . You had to set a matrix c[i][j] - number of the j-th basic artifact that is required in order to collect the i-th component artifact. Further, one can make a matrix of composite artifacts, where a[i][j] is number of the j-th basic artifact of the i-th friend and a similar matrix b of composite artifacts, and check whether i-th friend has any a composite artifact of O (MN) after each i-th friend’s purchase. Check whether one component of the artifact assembles for O (N): while checking whether the i-th friend is able to collect the j-th artifact you have to check, if there is such u, that c[j [u]> a[i][u], if so, the j-th artefact will not be collected, if not, then you have to increase the b[i][j] and update the values in a[i]).

So.the asymptotics of the processing of all purchases will be O (NQM). Then, we need to make a list of artifacts for each person, keeping their quantity(a total of O (KN + KM), and sort it (a total of O (QlogQ)).

Problem D.

This game is over, because except for a finite number (2) of reflections about the line y = x,the coordinates are changed to non-negative integer (and at least one coordinate is changed to a positive number).

Algorithm for solving this problem is DFS / BFS (states) where the state is a pair of coordinates, and two logical variables, which denote if the 1 (2) player had reflected a point about the line y = x.

Total number of states is obtained by S <= 4D^2 (pairs of coordinates) * 4 (Boolean variables).

Processing of one state takes O (N) actions (do not forget to try to reflect the point about the line y = x, if the player had not made it earlier in the game). Thereby, we have the overall asymptotic O (ND^2), which works on C + + in less than 200ms.

Problem E

To solve this problem you have to do a "move" subsegment and know :

1. The set B of numbers, meeting once, with the function of extracting the maximum for O (logN)

2.The set of numbers appearing on this subsegments with keeping the number of times,that this number is found on this subsegments, with function of verifying how many times the number in this subsegments for O (logN).

While moving a segment from (a[i] .. a[i + k - 1]) for 1 item left (a[I + 1] .. a[I + k]) you have to:

1) Check whether a[i] with a[I + k]. If yes, then there is no need to modify the set, otherwise proceed to item 2 and 3.

2) Check how many times we have a[i] in the set A: if 2, then add a[i] to B, if 1, then remove it from A and B. Do not forget to reduce the corresponding number of occurrences of a[i] in the current segment 1.

3) Check, how many times we have a[I + k] in the set A: if 0, then add a[i] in the B and A, if 1, then remove it from B. Do not forget to increase the corresponding number of occurrences of a[i] the current interval to 1.

After that, if the set is not empty, we should take peak from it.

So the asymptotics of this process will be O(NlogN).

As such data structures set / map(for those who use C + +) and the Cartesian tree are suitable.

^{2}) then it would have led to TLE?Here is my approach:

Process first K numbers at once. Store frequencies of each number in hash table and maintain a set which contain values which occurred only once. then process rest of the numbers while taking input. reduce frequency of i-K th number, modify the set according to frequency.

Suppose input is:

6 3

1

1

2

6

6

First i will process first 3 numbers. so the set will be {2} and map will be freq[1]=2,freq[2]=1.

When i get 4th number 6,i will reduce freq of 1st number. freq[1] will become 1 from 2. as it has become 1,the set will be {1,2,6}(as i got 6 for the first time).

Then i get 5th number 6,i will reduce freq of 2nd number. freq[1] is now 0. as it went 0 from 1, i need to remove it from set too. so the set becomes{2}(i will remove 6 too as i got it 2 times now).

Every time print the largest number from set. If the set is empty print "nothing". i've used c++ stl <set>.

When I changed "double" to "int" in task E, I've got AC (with double - WA). But I can't find any words in problem statement about representation of numbers in answer. Also I can't find nothing in problem statement to determine if numbers are integers or not...

ATTENTION! THIS CONTEST SHOULD BE UNRATED!

Maybe now you will read my message carefully :) I think that Corny is right. His solution works just after replacing "double" to "int".

Really? Ok, try to output floating-point numbers with 1e-10 precision.

I think result would be the same :)

`b 1`

`c 2`

i-th purchase no more than one opportunity to collect the composite artifact appears. If such an opportunity arose, the hero must take advantage of it."So your solution is wrong. After buyin first 'a' artifact player has oportunity to build artifact 'c' but in your solution he didn't take advantage of it, he waited for the second 'a' to compose 'b'