Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

witua's blog

By witua, 9 years ago, translation, ,

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

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

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)).

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.

• +17

 9 years ago, # |   0 OK,here it is. :)
 9 years ago, # |   0 What is T in the last sentence of Div1-D analysis?"Complexity – O(T * |N})"
•  9 years ago, # ^ |   0 Number of test cases.
 9 years ago, # |   +3 Problem E div1 "For each A[i] is log(C[i]) things (cost of this thing is size of subset that create it)"may u explain "size of subset" more clearly?
•  9 years ago, # ^ | ← Rev. 2 →   0 Look, if we have C[i] components of A[i] vertex, cost of each of this C[i] things (in standart knapsack algo)  is 1 (we need one new edge). In this case we decompose each C[i] in 1 + 2 + 4 + ... 2^k and costs are now 1, 2, 4 ... , respectively.
•  9 years ago, # ^ |   +3 Thanks! Now I got it!
 9 years ago, # |   0 Are there any O(N*W) solution in http://codeforces.com/contest/95/status/E , Can you show me where it is ?
 8 years ago, # |   0 Please could you explain how you minimize the number of regions selected (so that connected roads are minimized) in Lucky Country?What is the knapsack formulation that you use?
 » 4 weeks ago, # |   0 how to write recursion function for B please guide