431.md (6001B)
1 Source: https://codeforces.com/blog/entry/12369 2 3 ## [431A - Black Square](/contest/431/problem/A "Codeforces Round 247 (Div. 2)") 4 5 To solve this problem, you must only do the process described in statement. 6 7 ``` 8 for i = 1 .. s.size() 9 if (s[i] = '1') ans += a[1]; 10 else ... 11 ``` 12 13 **Complexity**: *O*(*N*) 14 **Solution**: [6676675](/contest/431/submission/6676675 "Submission 6676675 by KaiZeR") 15 16 ## [431B - Shower Line](/contest/431/problem/B "Codeforces Round 247 (Div. 2)") 17 18 In this problem, according to the small limits, we can brute all permutations and choose the best answer of all. The easeast way to do this — use standart C++ function *next_permutation*, or simply write 5 *for*. For each permutation we can simulate the process, which was described in a statement, or notice that first with second student, and second with the third will communicate one time, and third with fourth student, and fourth with fifth — will communicate two times. Another pairs of students will never communicate to each other during they stay in queue. 19 20 **Complexity**: *O*(*n*!) 21 **Solution**: [6676695](/contest/431/submission/6676695 "Submission 6676695 by KaiZeR") 22 23 ## [431C - k-Tree](/contest/431/problem/C "Codeforces Round 247 (Div. 2)") 24 25 This problem can be solved by dinamic programming. 26 Let's `Dp[n][is]` — number of ways with length equals to *n* in k-tree, where if *is* = 1 — there is exists edge with length at least *d*, *is* = 0 — lengths of all edges less then *d*. 27 Initial state `Dp[0][0] = 1`. 28 Transition — iterate all edges which can be first on the way in k-tree, then problem transform to the same, but with less length of the way (because subtree of vertex son is the k-tree). 29 30 `Dp[n][0] = Dp[n-1][0] + ... + Dp[n-min(d-1,n)][0]` `Dp[n][1] = Dp[n-1][1] + ... + Dp[n-min(d-1,n)][1] + (Dp[n-d][0] + Dp[n-d][1]) + ... + (Dp[n-min(n,k)][0] + Dp[n-min(n,k)][1])` 31 32 See solution for more details. 33 34 **Complexity**: *O*(*nk*) 35 Notice that this solution can be easy midify to *O*(*N*) complexity, only precalc partial sums. But it is not neccesary to solve this problem in such way. 36 **Solution**: [6676700](/contest/431/submission/6676700 "Submission 6676700 by KaiZeR") 37 38 ## [431D - Random Task](/contest/431/problem/D "Codeforces Round 247 (Div. 2)") 39 40 We will search *n* by binary search. Such function is monotone, because the amount of numbers with exactly *k* 1-bits on a segment *n* + 2 ... 2·(*n* + 1) more or equal than amount of such numbers on segment *n* + 1 ... 2·*n*. Last statement is correct, because of *n* + 1 and 2·(*n* + 1) have equals number of 1-bits. 41 To find the amount of numbers on segment *L*...*R*, which have exactly *k* 1-bits, it is sufficient to can calculate this number for segment 1...*L*, then the answer will be *F*(1...*R*) - *F*(1..*L* - 1). 42 Let's understand how we can calculate *F*(1...*X*). Iterate number of bit will be the first(from biggest to smallest) which is different in X and numbers, which amount we want to calculate. Let the first difference will be in *i*-th bit(it's possible, if in X this bit equals to 1, because we consider all numbers do not exceed X). Then other smallest bits we can choose in any way, but only amount of 1-bits must equals to *k*. We can do this in *C**i**k* - *cnt* ways, where *cnt* — the number of 1-bits in X, bigger then *i*, and *C**n**k* — binomailany factor. Finally, you should not forget about X (if it, of course, has k one bits). 43 44 ``` 45 long long F( X ) 46 Ans = 0 , cnt = 0; 47 for i = Max_Bit...0 48 if (bit(X,i) == 1) Ans += C[i][K - cnt] , cnt ++; 49 if (Bit_Counts(X) == K) Ans ++; 50 return Ans; 51 ``` 52 53 **Асимптотика**: *O*(*log*2(*Ans*)) 54 **Решение**: [6676713](/contest/431/submission/6676713 "Submission 6676713 by KaiZeR") 55 56 ## [431E - Chemistry Experiment](/contest/431/problem/E "Codeforces Round 247 (Div. 2)") 57 58 First of all let's understand the statement. 59 We have *n* tubes. At the beginning of each of them there are a few amount of mercury is poured. We want be able to perform two types of queries: 60 61 1. Make the amount of mercury in *p*- th tube equals to *x*. 62 2. Given the number *v* — the amount of water that must be optimally pour these tubes. What does it mean optimally? That mean we pour water in some of the tubes in the way, when maximum volume of liquid for all tubes, where we poured water, will be as small, as possible. 63 64 Well, actually now turn to the solution. 65 Use binary search to find an answer, in particular, will sort out the amount of mercury in a tubes(let it equals to *d*), such that in the tubes with smaller volume of the liquid can be poured all *v* liters of water and the maximum liquid level does not exceed *d*. Let the number of tubes, with the amount of mercury less than *d* is equal *t*. 66 67 Now the problem is reduced to learning how to count the total amount of water that we can to pour into each of *t* least tubes, such that the level of the liquid in each of them is equal *d*. 68 69 Let *a*[*i*] — the total amount of mercury in the tubes which exactly have *i* liters mercury and *b*[*i*] — number of tubes which the volume of mercury is equal *i*. Then *t* = *b*[0] + ... + *b*[*d* - 1] and *v*1 = *t* * *d* - (*a*[0] + *a*[1] + ... + *a*[*d* - 1]) — the total maximum amount of the water which can be poured. If *v*1 < *v*, then obviously this space is not enough for pour all the water, otherwise quite enough and so the answer will be no more than *d*. 70 When we found the smallest *d*, we can say that the answer is equal *d* — (*v*1 — *v*) / *t*. 71 72 To quickly find for *a*[0] + *a*[1] + ... + *a*[*d* - 1] and *b*[0] + ... + *b*[*d* - 1], and perform queries of the first type, you can use the Fenwick tree. 73 **Асимптотика**: *O*(*qlog*2(*n*)) 74 **Решение**: [6676668](/contest/431/submission/6676668 "Submission 6676668 by Antoniuk")