Analysis Codeforces Beta Round #63 (Div. 2)

Problem A.

In this task all you had to do was to make sure that the sum of all Σxi is 0, the sum of all Σyi is 0 and that the sum of all Σzi - 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.