codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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. ![](https://espresso.codeforces.com/47e2303302db0ffb6f9949e3e58c6b7fe7523b52.png);
     15 3. ![](https://espresso.codeforces.com/8fe2af313631f245cc345942939e9933b0522656.png);
     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 ![](https://espresso.codeforces.com/f772de0aeabf10bb1f0f9e6ee317650e435e686c.png).
     73 
     74 Authors solution: [5306535](/contest/369/submission/5306535 "Submission 5306535 by gridnevvvit")