codeforces-scrape

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

403.md (10080B)


      1 Source: https://codeforces.com/blog/entry/10972
      2 
      3 ## [402A - Nuts](/contest/402/problem/A "Codeforces Round 236 (Div. 2)")
      4 
      5 Let's fix some value of boxes *ans*. After that we can get exactly *cnt* = *ans* + *min*((*k* - 1) * *ans*, *B*) of sections. So, if *cnt* * *v* ≥ *a*, then *ans* be an answer. After that you can use brute force to find smallest possible value of *ans*.
      6 
      7 ## [402B - Trees in a Row](/contest/402/problem/B "Codeforces Round 236 (Div. 2)")
      8 
      9 Let's fix height of the first tree: let's call it *a*. Of course, *a* is an integer from segment [1, 1000]. After that, for the fixed height *a* of the first tree we can calculate heights of the others trees: *a*, *a* + *k*, *a* + 2*k*, and so on. After that you should find minimal number of operations *ans* to achive such heights. After that we can use brute force to find smallest possible *ans* for each *a* from 1 to 1000. For best height of the first tree you should print all operations.
     10 
     11 ## [402C - Searching for Graph](/contest/402/problem/C "Codeforces Round 236 (Div. 2)") / [403A - Searching for Graph](/contest/403/problem/A "Codeforces Round 236 (Div. 1)")
     12 
     13 I will describe two solutions.
     14 
     15 First. Consider all pairs (*i*, *j*) (1 ≤ *i* < *j* ≤ *n*). After you should ouput the first 2*n* + *p* pairs in lexicographical order.
     16 
     17 It's clear to understand, that it is enough to prove, that 0-interesting graph is correct or  - 3 -interesting graph is correct. We will prove for  - 3 -interesting graph, that it is correct. This graph consists of triangles, which have an common edge 1 — 2. Let's fix some subset of vertexes, which does not contains vertexes 1 and 2. In such sets there are no edges. Let's fix some subset, which contains exactly one vertex (1 or 2). In such subsets there are exactly *k* - 1 edges, where *k* is the size of such subset. In other subset there are exactly 2 * (k — 2) + 1 edges, where *k* is the size of such subset.
     18 
     19 Second. Let's use some brute force, to build graphs with 0-interesting graphs with sizes 5, 6, 7, 8, 9 vertexes. Now, to build *p*-interesting graph with *n* vertexes, We will build 0-interesting graph, and after that we will add to it *p* another edges, which is not in the graph. We will build 0-interesting graphs using the following approach: Let's took *k* disjointed components, from graphs with number of vertexes from 5 to 9, in such way that there are exactly *n* vertexes in graph.
     20 
     21 ## [402D - Upgrading Array](/contest/402/problem/D "Codeforces Round 236 (Div. 2)") / [403B - Upgrading Array](/contest/403/problem/B "Codeforces Round 236 (Div. 1)")
     22 
     23 I will describe two solutions.
     24 
     25 First. Dynamic programming approach. Let's calculate an DP *d*[*i*][*j*] — which is the best possible answer we can achieve, if current prefix has length *i* and we used operation of Upgrading last time in position *j*. It is clear to understand, that we should iterate *i* from *n* to 1, and *j* from *n* to *i*. There are only two transitions:
     26 
     27 * First, *d*[*i* - 1][*j*] = *max*(*d*[*i* - 1][*j*], *d*[*i*][*j*]) — we will not use operation of upgrading of array in the current position.
     28 * Second, *d*[*i* - 1][*i* - 1] = *max*(*d*[*i* - 1][*i* - 1], *d*[*i*][*j*] + *f*(*tgcd*[*j*]) * *i* - *f*(*tgcd*[*i* - 1]) * *i* — we are using an operation of upgrading. *f*(*a*) — is a beauty of the number. *tgcd*[*i*] — *gcd* of all numbers on the prefix of length *i*. You can use function, which works in ![](https://espresso.codeforces.com/4ecb494c3ca5a6535b79d1355b65448abb6de2a4.png) to calculate the beauty. Also you can make your solution more faster, it you will precalculate some small primes. Also you can use *map* < *int*, *int* >  to store calculated values. DP base *d*[*n*][*n*] = *curBeauty* — is a current beauty of the array.
     29 
     30 Second. Greedy. Let's find position *r*, which can upgrade our answer. If there some values of *r* — we will take most right position. We will add this position to the answer and upgrade our answer. Why it's correct? Let's fix an optimal solution (sequence of position, where we used an upgrading operation) *r*1 > *r*2 > ... > *r**k*. Also we have an solution which was built by using greedy *l*1 > *l*2 > ... > *l**m*. It's clear, that *r*1 ≤ *l*1, because all position with  > *l*1 cannot upgrade anything (otherwise greedy will choose it as first position). In other hand, *r*1 ≥ *l*1, because otherwise we can upgrade in position *l*1 and make answer better. So, *r*1 = *l*1, and after that we can use our propositions for big indexes *i*.
     31 
     32 ## [402E - Strictly Positive Matrix](/contest/402/problem/E "Codeforces Round 236 (Div. 2)") / [403C - Strictly Positive Matrix](/contest/403/problem/C "Codeforces Round 236 (Div. 1)")
     33 
     34 Let's look at the matrix *a* as a connectivity matrix of some graph with n vertices. Moreover, if *a**ij* > 0, then we have directed edge in the graph between nodes (*i*, *j*). Otherwise, if *a**ij* = 0 that graph does not contains directed edge between pair of nodes (*i*, *j*). Let *b* = *a**k*. What does *b**ij* means? *b**ij* is the number of paths of length exactly *k* in our graph from vertex *i* to vertex *j*. Let *pos* is an integer, such that *a*[*pos*][*pos*] > 0. That is, we have a loop in the graph. So, if from the vertex *pos* achievable all other vertexes and vice versa, from all other vertices reachable vertex *pos*, then the answer is *YES*, otherwise the answer is *NO*. If reachability is missing, it is clear that for any *k* *a**k**ipos* = 0. If reachability there, we will be able to reach self-loop, use self-loop "to twist", and after that we will go to some another vertex.
     35 
     36 ## [403D - Beautiful Pairs of Numbers](/contest/403/problem/D "Codeforces Round 236 (Div. 1)")
     37 
     38 First, we can note, that length of sequence is not greater then 50. Ok, but why? Because all numbers *b**i* - *a**i* are different, so 0 + 1 + ... + 50 > 1000. Let's imagine, that sequence from input is a sequence of non-intersecting segments. So, *c**i* = *b**i* - *a**i* + 1 is length of segment *i*. Also, ![](https://espresso.codeforces.com/966af00906866bc23ca8d9d904226faa624f1748.png). After that let's calculate the following DP: *d*[*i*][*j*][*k*] — — number of sequences for which following holds: *c*1 < *c*2 < ... < *c**i*, *c**i* ≥ 1 , *c*1 + *c*2 + ... + *c**i* = *j* and maximal number is less then *k* (upper bound of sequence). This DP will helps us to calculate number of ways to set length to each segment in sequence. It's simple to calculate such DP:
     39 
     40 * base *d*[0][0][1] = 1,
     41 * *d*[*i*][*j*][*k* + 1] = *d*[*i*][*j*][*k* + 1] + *d*[*i*][*j*][*k*] — we increase upper bound of sequence;
     42 * *d*[*i* + 1][*j* + *k*][*k* + 1] = *d*[*i* + 1][*j* + *k*][*k* + 1] + *d*[*i*][*j*][*k*] — we are adding upper bound to the sequence.
     43 
     44 We can calculate such DP, by using only *O*(*N*2) of memory, where *N* = 1000. After that we should multiply *d*[*i*][*j*][*k*] on *i*!, because we need number of sequences *c**i*, where order does not matter.
     45 
     46 After that we can calculate answer for *n*, *k*. Let's ![](https://espresso.codeforces.com/1543ad1c265a2d6d4343167bcb9ee2cc4b63dc0d.png), where *x* — some upper bound of sequences. After that we should calculate next number: how many ways to set to distances between segments? It's clear, that we can increase distance between some segments, but we have only *n* - *len* such operations. It's well known, that answer number of ways equals to *C*(*n* - *len* + *k*, *k*). So, for each *n* we should sum by *len* following values: *sum*[*len*] * *C*(*n* - *len* + *k*, *k*).
     47 
     48 Note, that we need array *C*[*n*][*k*] (binomials) where *n* ≤ 2000, *k* ≤ 2000.
     49 
     50 ## [403E - Two Rooted Trees](/contest/403/problem/E "Codeforces Round 236 (Div. 1)")
     51 
     52 First, for each vertex of the first and second tree we calculate two values *in*[*s*], *out*[*s*] — the entry time and exit time in dfs order from vertex with number 1. Also with each edge from both trees we will assosiate a pair (*p*, *q*), where *p* = *min*(*in*[*u*], *in*[*v*]), *q* = *max*(*in*[*u*], *in*[*v*]) (values *in*, *out* for each vertex we take from tree with another color). Now for each tree we will build two segment trees (yes, totally 4 segment trees). In first segment will store all pairs in following way: we will store a pair in node of segment tree if and only if (node of segment tree is a segment (*l*, *r*)) left element of pair lies in segment (*l*, *r*). In second segment tree we will store a pair if and only if right element of the pair lies in segment (*l*, *r*) All pairs in segment trees we will store in some order (in first segment tree — increasing order, in the second tree — decreasing order). Such trees use ![](https://espresso.codeforces.com/49d24101dcdd81f4a7959288cb2ee875414fdc6a.png) of memory, also you can build it in ![](https://espresso.codeforces.com/49d24101dcdd81f4a7959288cb2ee875414fdc6a.png).
     53 
     54 Good. How to answer on query (*l*, *r*) — erase all edges from tree for which exactly one vertex have value *in*[*s*] in segment (*l*, *r*)? We will go down in our segment tree. Let's imagine, that now we in some node of segment tree. Because we store all pairs in the first segment tree in increasing order of the right element, so answer to the query is a some suffix of the array of pairs. After we can add they to the answer (if it not erased yet). After that we should modify our segment tree: for each node, where we work with suffixes, we should erase all pairs from such suffix. So, this solution in ![](https://espresso.codeforces.com/49d24101dcdd81f4a7959288cb2ee875414fdc6a.png).
     55 
     56 My solution to E: [6052738](/contest/403/submission/6052738 "Submission 6052738 by gridnevvvit")