codeforces-scrape

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

559.md (7129B)


      1 Source: https://codeforces.com/blog/entry/19237
      2 
      3 [560A - Currency System in Geraldion](/contest/560/problem/A "Codeforces Round 313 (Div. 2)")
      4 
      5 If there is a banlnot of value 1 then one can to express every sum of money. Otherwise one can't to express 1 and it is minimum unfortunate sum.
      6 
      7 [560B - Gerald is into Art](/contest/560/problem/B "Codeforces Round 313 (Div. 2)")
      8 
      9 It is easy to see that one can snuggle paintings to each other and to edge of board. For instance one can put one of painting right over other. Then height of two paintings equals to sum of two heights and width of two paintings is equals to maximum of two widths. Now we can just iterate orientation of paintings and board.
     10 
     11 [559A - Gerald's Hexagon](/contest/559/problem/A "Codeforces Round 313 (Div. 1)") & [560C - Gerald's Hexagon](/contest/560/problem/C "Codeforces Round 313 (Div. 2)")
     12 
     13 Let's consider regular triangle with sides of *k* Let's split it to regular triangles with sides of 1 by lines parallel to the sides. Big triange area *k*2 times larger then small triangles area and therefore big triangle have splitted by *k*2 small triangles.
     14 
     15 If we join regular triangles to sides *a*1, *a*3 and *a*5 of hexagon we get a triangle sides of *a*1 + *a*2 + *a*3. Then hexagon area is equals to (*a*1 + *a*2 + *a*3)2 - *a*12 - *a*32 - *a*52.
     16 
     17 ![ ](/predownloaded/78/ba/78ba496fdcbe804843bcbcefcff1389d054ef5f2.png)
     18 
     19 [559B - Equivalent Strings](/contest/559/problem/B "Codeforces Round 313 (Div. 1)") & [560D - Equivalent Strings](/contest/560/problem/D "Codeforces Round 313 (Div. 2)")
     20 
     21 Let us note that "equivalence" described in the statements is actually [equivalence relation](https://en.wikipedia.org/wiki/Equivalence_relation), it is reflexively, simmetrically and transitive. It is meant that set of all string is splits to equivalence classes. Let's find lexicographic minimal strings what is equivalent to first and to second given string. And then check if its are equals.
     22 
     23 It is remain find the lexicographic minimal strings what is equivalent to given. For instance we can do it such a way:
     24 
     25 ```
     26 String smallest(String s) {
     27     if (s.length() % 2 == 1) return s;
     28     String s1 = smallest(s.substring(0, s.length()/2));
     29     String s2 = smallest(s.substring(s.length()/2), s.length());
     30     if (s1 < s2) return s1 + s2;
     31     else return s2 + s1;
     32 }
     33 ```
     34 
     35 Every recursive call time works is *O*(*n*) (where *n* is length of strings) and string splitten by two twice smaller strings. Therefore time of work this function is ![](https://espresso.codeforces.com/8be993eafecdfb87ed795da91da8626cc7b54983.png), where *n* is length of strings.
     36 
     37 [559C - Gerald and Giant Chess](/contest/559/problem/C "Codeforces Round 313 (Div. 1)") & [560E - Gerald and Giant Chess](/contest/560/problem/E "Codeforces Round 313 (Div. 2)")
     38 
     39 Let's denote black cells ad *A*0, *A*1, ..., *A**k* - 1 . First of all, we have to sort black cells in increasing order of (row, column). If cell *x* available from cell *y*, *x* stands after *y* in this order. Let *A**k* = (*h*, *w*). Now we have to find number of paths from (1, 1) to *A**k* avoiding *A*0, ..., *A**k* - 1.
     40 
     41 Let *D**i* is number of paths from (1, 1) to *A**i* avoiding *A*0, ..., *A**i* - 1. It's easy to see that *D**k* is answer for the problem. Number of all paths from (1, 1) to (*x**i*, *y**i*) is ![](https://espresso.codeforces.com/e7c973271ced4e6deefa88d7919d1b19533abe8c.png). We should subtract from that value all paths containing at least one of previous black cells. We should enumerate first black cell on the path. It could be one of previous cell that is not below or righter than *A**i*. For each such cell *A**j* we have to subtract number of paths from (1, 1) to *A**j* avoiding black cells multiplied by number of all paths from *A**j* to *A**i*.
     42 
     43 We have to calculate factorials of numbers from 1 to 2·105 and inverse elements of them modulo 109 + 7 for calculating binomial coefficients.
     44 
     45 [559D - Randomizer](/contest/559/problem/D "Codeforces Round 313 (Div. 1)")
     46 
     47 We can use [Pick's theorem](https://en.wikipedia.org/wiki/Pick%27s_theorem) for calculate integer points number in every polygon. Integer points number on the segment between points (0, 0) and (*a*, *b*) one can calculate over *GCD*(*a*, *b*).
     48 
     49 Integer points number in some choosen polynom is integer points number in basic polynom minus integer points number in segmnent of basic polynom separated by every segment of choosen polynom.
     50 
     51 Let consider every potencial segment of polygon. We can calculate integer points number in his segment and probability that we will meet it in choosen polygon.
     52 
     53 Probability of segment *A**i**A**i* + *k* is ![](https://espresso.codeforces.com/01b3d29a44e4628ff71786adc2496e02b4f316c2.png). Let use note that we can calculate only segments with *k* < 60 because of other segmnet propapility is too small.
     54 
     55 [559E - Gerald and Path](/contest/559/problem/E "Codeforces Round 313 (Div. 1)")
     56 
     57 Lighted part of walking trail is union of ligted intervals. Let's sort spotlights in increasing order of *a**i*. Consider some lighted interval (*a*, *b*). It's lighted by spotlights with numbers {*l*, *l* + 1, ..., *r*} for some *l* and *r* ("substring" of spotlights). Let *x*0, ..., *x**k* is all possible boundaries of lighted intervals (numbers *a**i* - *l**i*, *a**i* и *a**i* + *l**i*).
     58 
     59 Imagine, that we know possible lighted intervals of all substrings of spotlights. Let *left*[*l*][*r*][*j*] is least possible *i* such that set of spotlights with numbers {*l*, *l* + 1, ..., *r*} lighting [*x**i*, *x**j*].
     60 
     61 With *left* we can calculate value *best*[*R*][*i*] maximum possible length of walking trail that could be lighted using first *L* spotlights in such way that *x**i* is rightmost lighted point. It's easy to do in *O*(*n*4) because ![](https://espresso.codeforces.com/a7b62d0b03e6e62656a76006eaa164274d942386.png).
     62 
     63 Now all we have to do is calculate *left*. Consider some substring of spotlights [*l*, *r*]. Let all spotlights in the substring oriented in some way lighting some set of points. We could consider most left (*i*) and most right (*j*) lighted points, and left bound of first lighted interval (*t*). If set of lighted points is interval *t* = *j*. Consider how all the values change when we add spotlight *r* + 1 and choose its orientation. We have new lighted interval [*a*, *b*] which is equal to [*a**i* - *l**i*, *a**i*] or [*a**i*, *a**i* + *l**i*]. Now most left lighted point is *min*(*a*, *x**i*), most right is *max*(*b*, *x**j*). Right bound of leftmost lighted interval does not changes if *a* > *t* or becomes equal to *b*, if *a* ≤ *t*.
     64 
     65 Not for each *L* we can calculate *dp*[*r*][*j*][*y*] least possible *i* that it's possible to orient spotlights from [*L*, *r*] in such way that *x**i* is most left lighted point *x**j* is most right one and right bound of leftmost lighted interval is *x**t*. Thet it's easy to calculate *left*[*L*][][]. That part is done in *O*(*n*4) too.