369.md (5946B)
1 Source: https://codeforces.com/blog/entry/9760 2 3 ### [369A - Valera and Plates](/contest/369/problem/A "Codeforces Round 216 (Div. 2)") 4 5 We will use greedy algorithm. Let's now *i*-th day, and current dish is a dish of first type. Then if we have the bowl, let's use it. Otherwise we will increase the answer. If the current dish is a dish of the second type, we first try to get the plate, and then the bowl. If there are no plates/bowls at all, then we will increase the answer. 6 7 Author's solution: [5306397](/contest/369/submission/5306397 "Submission 5306397 by gridnevvvit") 8 9 ### [369B - Valera and Contest](/contest/369/problem/B "Codeforces Round 216 (Div. 2)") 10 11 In this task you are to determine such array *a*1, *a*2, ..., *a**n*, that following conditions are met: 12 13 1. *r* ≥ *a*1 ≥ *a*2 ≥ ... ≥ *a**n* ≥ *l*; 14 2. ; 15 3. ; 16 17 It's clear to understand, that value *s**k* should be distributed evenly between the first *k* elements. For example, you can use following algorithm: 18 19 ``` 20 remainder = (s_k mod k); 21 for(int i = 0; i < k; i++) 22 { 23 a_i = s_k / k + (remainder > 0); 24 remainder = remainder - 1; 25 } 26 ``` 27 28 If *k* ≠ *n*, you should use same algorithm with other elements, but there are to distribute value *s**all* - *s**k*. 29 30 Some participants forgot about test, where *k* = *n*. They received RE11. 31 32 Author's solution: [5306414](/contest/369/submission/5306414 "Submission 5306414 by gridnevvvit") 33 34 ### [369C - Valera and Elections](/contest/369/problem/C "Codeforces Round 216 (Div. 2)") 35 36 Consider all the roads that we need to repair. Mark the ends of *u*, *v* white. After that, we will consider a simple dynamic programming *d*[*v*] (*v* is the vertex) on the tree that for each vertex in the tree determines the number of white vertexes in the subtree. It is easy to calculate this by using a recursive function *calc*(*v*, *prev*) (*v* is the current node, and *prev* its immediate ancestor): 37 38 ``` 39 calc(v, prev) 40 { 41 d[v] = 0; 42 if (white[v]) 43 dv += 1; 44 for all vertexes u such that there is the edge (u,v) or (v,u), u != prev: 45 calc(u, v); 46 d[v] += d[u]; 47 } 48 ``` 49 50 After that we will add to answer all white vertexes *v* such that next condition is correct: *d*[*v*] = 1 51 52 Author's solution: [5306500](/contest/369/submission/5306500 "Submission 5306500 by gridnevvvit") 53 54 ### [369D - Valera and Fools](/contest/369/problem/D "Codeforces Round 216 (Div. 2)") 55 56 Let's *p*[*A*] is the *p**A* from the statement. 57 58 It's clear to understand that you can discribe the state by using pair of integers (*A*, *B*), where *A* is a number of the fool with smallest index, *B* — the second fool from the left. It is clear to understand that fool with indexes *j* ≥ *B* will be living. After that we will use bfs on the states (*A*, *B*). 59 60 State (0, 1) is always visitable, because it is initial. We will push it in the queue. After that, there are only three transitions from current state (*A*, *B*). 61 62 1. (*B* + 1, *B* + 2) — this transition is possible if and only if *p*[*A*] > 0 and there are some fool with index *j* ≥ *B*, which has non-zero value *p*[*j*] > 0. 63 2. (*A*, *B* + 1) — this transition is possible if and only if *p*[*A*] > 0 и there are no fool with index *j* ≥ *B*, which has *p*[*j*] = 100. 64 3. (*B*, *B* + 1) — this transition is possible if and only if *p*[*A*] ≠ 100 and there are some fool with index *j* ≥ *B*, which has non-zero value *p*[*j*] > 0. 65 66 After that you are to determine number of states, which has distance from state (0, 1) less or equal to *k*. Also you should be careful, that if there are only one fool, that he doesn't shot. 67 68 Author's solution: [5306516](/contest/369/submission/5306516 "Submission 5306516 by gridnevvvit") 69 70 ### [369E - Valera and Queries](/contest/369/problem/E "Codeforces Round 216 (Div. 2)") 71 72 Let's calculate sets *xs*[*y*] — all segments, whose right borders are exactly equal to *y*. Now we reduce our task to another. For each query we will count the number of segments that doesn't belong to any one point. Let's it will be the value *v*. Then the answer to the query is *n* - *v*. We add to our request the point 0 and a point *MV* + 1, where *MV* = 1000000. Let points request have the form *x*1 < *x*2... < *x**n*. Consider the *x**i* and *x**i* + 1. Let *p**i* is the number of segments that lie strictly inside *x**i* and *x**i* + 1. Then *v* = *p*1 + *p*2 + ... + *p**n* - 1. We will use following algorithm to find the values *p**i*. Let consider all such pairs (*x*, *x**i* + 1) for all requests and to add them to a second set *xQ*[*y*] — all pairs whose right boundary is equal to *r*. Then to find the values *p* of pairs (*x**i*, *x**i* + 1) we will iterate ascending the right border. Additionally, we will support Fenwick's tree, which can make + = 1 at the point, and can calculate sum of the prefix. Let *i* — the current right border. Then we can find out the value *p* for all pairs (*l*, *r*), with the right border is equal to the *i* (*l*, *i*). Let *j* left border of the pair. Then the answer for the pair is the value of *S* - *sum*(*j*), where *S* — all added to the Fenwick's left borders, and *sum*(*j*) — sum of the prefix *j*. After that, for the current coordinate *i* we need to consider all segments in the set *xs*[*i*]. Let *j* left boundary of the segment. Then we need to make + = 1 at the point *j* in our Fenwick's tree. The total solution complexity is . 73 74 Authors solution: [5306535](/contest/369/submission/5306535 "Submission 5306535 by gridnevvvit")