Task A. Double Cola
Let's designate characters on the first letter of the name. The queue looks like: SH-L-P-R-G, through 5 cans: SH-SH-L-L-P-P-R-R-G-G, through 10 cans: SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.
The regularity is clear, and the solution is very simple: we will be iterated on p - we will find such minimum p that 5· 2p > n (thus if this number is less or equally we will subtract it from n) then we know that at first 2p Sheldon's stand, then 2p Leonard's and so on. And now we can easily answer who took a can number n (namely there was a person with number n / 2p in sequence SH-L-P-R-G (in 0-indexation).
Task B. Sets
For the solution the following important fact is required to us: we will admit elements v and u are in one set then in any of n· (n - 1) / 2 of sequences from the input data where meets v u necessarily meets. And also if v and u are in different sets there is such sequence in which is v, but isn't present u. Then it is possible to enter the equivalence relation for all elements of all sets - two elements are equivalent, if there is no sequence where one element meets, and another isn't present. Classes of equivalence also are required sets.
It was possible to consider the answer as following algorithm: we will write out for each number the list of numbers of sequences where there is this number, and will unite two numbers if these lists are equal. This algorithm can be realized for O(n2 * log(n)) however the solution for O(n3) passes all tests with time large supply too.
The special case is a test with n = 2. This test was used for a considerable quantity of hacks.
Task C. General Mobilization
At first we will estimate from above the maximum time to which all divisions will reach capital - obviously it is required no more n days for this purpose. Therefore restrictions quite allowed model movements of divisions. The key moment of the solution - we will always consider divisions in priority order. Then in every day we will consider the list of those divisions who hasn't reached yet capital, and we will put in priority order on the necessary train. If the train is already filled, the division remains in a current city, differently we will change its position, and in day when the division will reach capital we will write down the answer. Total: in total days which it is necessary model, no more n, and every day we move no more n divisions. So our solution has asymptotic form no more O(n2).
The solutions using various structures of the data (sets, turns with priorities etc.) work for O(n2· log(n)) and it didn't always keep within in TL.
Task D. Two out of Three
The problem dares the dynamic programming. We will consider a state (i, j) meaning that in the current turn there is a person number i and also all people from j to n inclusive. Any turn achievable of the initial can be presented by corresponding condition. The quantity of conditions is O(n2), the quantity of transitions is only 3, that is O(1). So the total asymptotic form is O(n2).
Task E. Corridor
This problem has some solutions based on the various methods of the search of the area of the association of the figures on a plane. One of such methods is the method of vertical decomposition (more in detail you can esteem in various articles) and also it was possible to notice that among figures there are no three having non-zero crossing and consequently was to learn to find a total area of two figures enough. For this purpose also it was possible to use the various methods, for example, the author's solution is based on algorithm of cutting off of a convex polygon by a semiplane. Authors supposed the solution for O(n2).