codeforces-scrape

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

300.md (5639B)


      1 Source: https://codeforces.com/blog/entry/7497
      2 
      3 ### [300A - Array](/contest/300/problem/A "Codeforces Round 181 (Div. 2)")
      4 
      5 In this problem you just need to implement following algorithm. Split input data into 3 vectors: first will contain negative numbers, second positive numbers, third zeroes. If size of first vector is even move one number from it to the third vector. If second vector is empty, then move two numbers from first vector to the second vector. This solution works in *O*(*n*).
      6 
      7 [Аuthor's solution](http://pastebin.com/8aVCeRYx)
      8 
      9 ### [300B - Coach](/contest/300/problem/B "Codeforces Round 181 (Div. 2)")
     10 
     11 Input data represents a graph. If there is a connected component with at least 4 vertexes, then answer is  - 1. Every connected component with 3 vertexes is a complete team. Other teams are made from 1 or 2-vertex components. If amount of 2-vertex components is greater than 1-vertex answer is  - 1. Otherwise match 2-vertex components with 1-vertex. If there are some 1-vertex components left then split them into groups of three. This algorithm works in *O*(*n* + *m*). Also you could implement *O*(*n*4) solution.
     12 
     13 [Аuthor's solution](http://pastebin.com/2q8CThPh)
     14 
     15 ### [300C - Beautiful Numbers](/contest/300/problem/C "Codeforces Round 181 (Div. 2)")
     16 
     17 Let's *MOD* = 1000000007. Let's precalc factorial values modulo *MOD*. *fact*[*i*] = *i*!%*MOD*, ![](https://espresso.codeforces.com/f691c5d2e09040e3b2eb0fd91ef55156145242f3.png). Let *i* be an amount of digits equal to *a* in current excellent number. In this case we can find sum of digits in this number: *sum* = *ai* + *b*(*n* - *i*). If *sum* is good, then add *C*[*n*][*i*] to answer. In this problem it's impossible to calculate binomial coefficients using Pascal's triangle, because of large *n*. However it can be done this way *C*[*n*][*i*] = *fact*[*n*]*inv*(*fact*[*n* - *i*]*fact*[*i*]). *inv*(*a*) is multiplicative inverse element(modulo *MOD*). *MOD* is a prime number, so *inv*(*a*) = *a**MOD* - 2. Calculating this values for each *i* from 0 to *n* will give correct answer in *O*(*nlog*(*MOD*)).
     18 
     19 [Аuthor's solution](http://pastebin.com/XwP7MmEa)
     20 
     21 ### [300D - Painting Square](/contest/300/problem/D "Codeforces Round 181 (Div. 2)")
     22 
     23 This picture is helpful for understanding.
     24 
     25 ![This picture is helpful for understanding.](/predownloaded/3a/7e/3a7e69567dacc004151558dfb142a6d668ac098b.png)
     26 
     27 Let's consider problem *D* in graph terms:
     28 
     29 We have matrix *n* × *n*, which represents a graph:
     30 
     31 1. It is tree.
     32 2. Every vertex, except leaves, has 4 children.
     33 3. There are 4*k* distinct vertexes, with distance *k* from root.
     34 
     35 We need to color *k* vertexes of this graph. By that we mean also to color all vertexes on path from *i* to 1(root).
     36 
     37 Knowing *height* of tree we can build it in unique way. Let's find height of tree in this way:
     38 
     39 ```
     40 int height = 0;
     41 while (n > 1 && n % 2 == 1) {
     42  n /= 2; height++;
     43 }
     44 ```
     45 
     46 Let's consider following DP: *z*[*i*][*j*] — number of ways to color graph height *i* in *j* steps.
     47 
     48 Naive solution in *O*(*k*4*log*(*n*)):
     49 
     50 ```
     51 z[0][0] = 1; z[0][i] = 0, i > 0; z[i][0] = 1, i > 0
     52 z[i][j] = 0;
     53 for(int k1 = 0; k1 <= j - 1; k1++) 
     54   for(int k2 = 0; k2 <= j - 1 - k1; k2++)
     55     for(int k3 = 0; k3 <= j - 1 - k1 - k2; k3++)
     56       {
     57          int k4 = j - 1 - k1 - k2 - k3;
     58   z[i][j] += z[i-1][k1] * z[i-1][k2] * z[i-1][k3] * z[i-1][k4];
     59   z[i][j] %= mod;
     60       }
     61 ```
     62 
     63 But it is not what we whant in time terms. Let's consider current DP as polynomial coefficients: *z*[*i*][*j*] — coefficient of power *j* of polynomial *i*. In that case *z*[*i* + 1][*j* + 1] — coefficient of power *j* of polynomial *i* to the 4-th power. This approach allows to solve problem in *O*(*k*2*log*(*n*)). However this solution is quite slow, because of modulo operations. As you see, this modulo is not so big ( ≤ 107), that allows us to reduce number of modulo operations, thus giving huge perfomance boost. Also it is possible to use FFT to solve in *O*(*klog*(*k*)*log*(*n*)).
     64 
     65 [Аuthor's solution. Uses FFT](http://pastebin.com/iXMrR6Cd)
     66 
     67 [Аuthor's solution. Without FFT](http://pastebin.com/RfMiXe6K)
     68 
     69 ### [300E - Empire Strikes Back](/contest/300/problem/E "Codeforces Round 181 (Div. 2)")
     70 
     71 Let's ![](https://espresso.codeforces.com/f6eecdc8800d07a0c3d9724c686e517bd751580d.png). *val* is upper bound for answer. *val*! is divisible by ![](https://espresso.codeforces.com/963364c50ba38cacc540ee46147761823a704f24.png), you can easily prove it using facts about prime powers in factorial and following inequality ![](https://espresso.codeforces.com/87a7c075411ce1d8ab28d99f7af159a9aa7f9faf.png). By the way, ![](https://espresso.codeforces.com/9f99a6e808fdf9f4006e5703bd89e203c0231135.png) is called multinomial coefficient. So answer can't exceed 1013.
     72 
     73 If *n*! divisible by *den*, then (*n* + 1)! is also divisible by *den*. That means that function of divisibility is monotonic and we can use binary search.
     74 
     75 For every *i*, *i* = 2..., 107, let's precalc max prime in *i* using linear sieve of Eratosthenes. For *i* it will be *lp*[*i*]. After that let's create a vector, with all primes less then 107.
     76 
     77 Now let's calculate following values *cnt*[*i*] — amount of numbers *a*, *i* <  = *a*.
     78 
     79 Now me can factorize denominator like this:
     80 
     81 ```
     82 for(int i = max; i>=2; i--) {
     83  if (lp[i] != i) 
     84   cnt[lp[i]] += cnt[i];
     85  cnt[i / lp[i]] += cnt[i];
     86 }
     87 ```
     88 
     89 Finally we use binary search from *lf* = 1 to ![](https://espresso.codeforces.com/bc4de10f7f2a9ff635ea8258f96907dae528cceb.png).
     90 
     91 [Аuthor's solution](http://pastebin.com/71vYY41X)