Div.2 – A Football

In this problem you must find longest substring consisting of equal characters and compare it with 7.

Div.2 – B Lucky Numbers - 2

If the length of input number |N| is odd, then, obviously, resulting number will have length |N|+1 and will be like this: 4444…7777, at first (|N|+1)/2 digits 4, then the same number of 7’s. If the number has even length, then, probably, resulting number will have size |N|, or |N|+2. So, length of the resulting number will have not more than 10 digits. So, we can recursive generate lucky numbers with size <= 10, take the smallest super lucky number which is greater than or equal to N.

Div.1 – A, Div. 2 – C – Hockey

Let B[i] = true, if character in position i is in some substring of W which is in dictionary. For each B[i] = true, do next:

·         If S[i] = letter and letter = ‘a’, then S[i] = ‘b’,

·         If S[i] = letter and letter != ‘a’ then S[i] = ‘a’;

·         If S[i] != letter, then S[i] = letter.

Div.1  - B. – Lucky Number

Read Div.2 – B

Notice, that answer will looks like this: to some position result will be equal with input string (that part must be lucky), next digit well be greater, the rest of digits are not important. That guarantees us that result will be greater than or equal to N. As rightest this position will be as number will be lesser. Some of the positions may not be ok to us. Let chosen position is i. Left part must be lucky. If S[i] < ‘4’, we can assign S[i] = ‘4’, then fill minimally right part. If S[i] < ‘7’, we can assign ‘7’ to it, like in prevision case. Call position i ok, if absolute different between number of ‘4’ and ‘7’ in part from 0 to i, inclusive is not more than n-i-1. If we chose some rightmost position, which is ok, now we must fill right part. How to do it? If we can assign to some position (we will fill them from left to right) ‘4’ and this position is still ok, then we place ‘4’,  else we assign ‘7’. If there is no ok positions at all, resulting number will looks like this: 4444…7777, when number of digits 4 = number of digits 7 = (|N|+2)/2.

Div.1 - C, Div.2 - D – Volleyball

At first in this simple problem you need to find shortest path between all pair of junctions. That can’t be done using O(N^3) algorithms, so you must use Dijkstra algorithm to find this in O(N*N*logN) time. Next part of this problem is to create new matrix, G[i][j] = C[i], if D[i][j] <= R[i], else G[i][j] = INF. Here D[i][j] – length of shortest path between I and j. So, result is shortest path between X and Y using matrix G. That can be done using simple Dijkstra algorithm.

Div.1 – D, Div.2 – E. Horse Races

Traditionally I remain that answer is Result(0..R) – Result(0..L-1).

Let we have array DP[x][y][z] – number of x-digits number if last lucky digit was on position y, bool z (0 or 1) – was the pair of lucky digits with less than or equal distance then K (call it lucky pair)? Now, let S – string which represent number N. Let F(x, y, z) – result for substring of first x digits, y – position of last lucky digit, z – (0 or 1) – was the lucky pair before? Try to assign some digits on position x. If this digit is less than S[i], then add to result for F(x, y, z) DP[n-x-1][yy][zz] (yy – updated position of last lucky digit, zz – updated bool for lucky pairs). If this digit is equal to S[i], add F(x+1, yy, zz). DP can be calculated simply. Let from state (x, y, z) we place some digit d on position x. Then, we can go to state (x+1, yy, zz). Again, yy and zz – updated parameters.

Complexity – O(T * |N}).

Div.1 – E – Lucky Country.

Let A[i] - sorted array of sizes of different connection components, C[i] – number of connection components of size A[i]. Sum for all C[i]*A[i] is equal to N. Size of A will be O(sqrt(N)).

Solution #4 (by RAD)

Coming soon…

Solution #7

Let all C[i] = (2^k)-1, i. e. C[i] = 1 + 2 + 4 + 8 + … + 2^(k-1). Obviously, that if chose some subset of this powers we can get any number from 0 to C[i], inclusive. So, the problem now is next: For each A[i] is log(C[i]) things (cost of this thing is size of subset that create it), each can be used at most once. This is standard “Knapsack” problem (read this). Complexity of this algorithm is O(N * S), when S is the sum for all log(C[i]). If C[i] is not power of 2, then we must find maximal k, which (2^k)-1 <= C[i] and add C[i]-((2^k)-1) to set.

Sorry for my poor English! If you do not understand something – write in comments, please.