codeforces-scrape

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

450.md (6535B)


      1 Source: https://codeforces.com/blog/entry/13112
      2 
      3 #### [450A - Jzzhu и дети](/contest/450/problem/A "Codeforces Round 257 (Div. 2)")
      4 
      5 You can simply simulate it or find the last maximum *ceil*(*a**i* / *m*).
      6 
      7 #### [450B - Jzzhu и последовательности](/contest/450/problem/B "Codeforces Round 257 (Div. 2)")
      8 
      9 We can easily find that every 6 numbers are the same. It's like {*x*, *y*, *y* - *x*,  - *x*,  - *y*, *x* - *y*, *x*, *y*, *y* - *x*, ...}.
     10 
     11 #### [449A - Jzzhu и шоколад](/contest/449/problem/A "Codeforces Round 257 (Div. 1)") / [450C - Jzzhu и шоколад](/contest/450/problem/C "Codeforces Round 257 (Div. 2)")
     12 
     13 We assume that *n* ≤ *m* (if *n* > *m*, we can simply swap *n* and *m*).
     14 
     15 If we finally cut the chocolate into *x* rows and *y* columns (1 ≤ *x* ≤ *n*, 1 ≤ *y* ≤ *m*, *x* + *y* = *k* + 2), we should maximize the narrowest row and maximize the narrowest column, so the answer will be *floor*(*n* / *x*) * *floor*(*m* / *y*).
     16 
     17 There are two algorithms to find the optimal (*x*, *y*).
     18 
     19 1. Notice that if *x* * *y* is smaller, the answer usually will be better. Then we can find that if *k* < *n*, the optimal (*x*, *y*) can only be {*x* = 1, *y* = *k* + 1} or {*x* = *k* + 1, *y* = 1}. If *n* ≤ *k* < *m*, the optimal (*x*, *y*) can only be {*x* = 1, *y* = *k* + 1}. If *m* ≤ *k* ≤ *n* + *m* - 2, the optimal (*x*, *y*) can only be {*x* = *k* + 2 - *m*, *y* = *m*}, because let *t* = *m* - *n*, *n* / (*k* + 2 - *m*) ≥ (*n* + *t*) / (*k* + 2 - *m* + *t*) ≥ 1.
     20 2. *floor*(*n* / *x*) has at most ![](https://espresso.codeforces.com/6b8f80d5708602c9727bc53c820fc6ad559209a0.png) values, so we can enum it and choose the maximum *x* for each value.
     21 
     22 #### [449B - Jzzhu и города](/contest/449/problem/B "Codeforces Round 257 (Div. 1)") / [450D - Jzzhu и города](/contest/450/problem/D "Codeforces Round 257 (Div. 2)")
     23 
     24 We consider a train route (1, *v*) as an undirected deletable edge (1, *v*).
     25 
     26 Let *dist*(*u*) be the shortest path between 1 and *u*. We add all of the edges (*u*, *v*) weighted *w* where *dist*(*u*) + *w* = *dist*(*v*) into a new directed graph.
     27 
     28 A deletable edge (1, *v*) can be deleted only if it isn't in the new graph or the in-degree of *v* in the new graph is more than 1, because the connectivity of the new graph won't be changed after deleting these edges. Notice that you should subtract one from the in-degree of *v* after you delete an edge (1, *v*).
     29 
     30 #### [449C - Jzzhu и яблоки](/contest/449/problem/C "Codeforces Round 257 (Div. 1)") / [450E - Jzzhu и яблоки](/contest/450/problem/E "Codeforces Round 257 (Div. 2)")
     31 
     32 Firstly, we should notice that 1 and the primes larger than *N* / 2 can not be matched anyway, so we ignore these numbers.
     33 
     34 Let's consider each prime *P* where 2 < *P* ≤ *N* / 2. For each prime *P*, we find all of the numbers which are unmatched and have a divisor *P*. Let *M* be the count of those numbers we found. If *M* is even, then we can match those numbers perfectly. Otherwise, we throw the number 2*P* and the remaining numbers can be matched perfectly.
     35 
     36 Finally, only even numbers may be unmatched and we can match them in any way.
     37 
     38 #### [449D - Jzzhu и числа](/contest/449/problem/D "Codeforces Round 257 (Div. 1)")
     39 
     40 Firstly, we can use inclusion-exclusion principle in this problem. Let *f*(*x*) be the count of number *i* where *A**i*&x = *x*. Let *g*(*x*) be the number of 1 in the binary respresentation of *x*. Then the answer equals to ![](https://espresso.codeforces.com/24951c1e42cb3e62b989d38473d55419f05e8abb.png).
     41 
     42 Now the task is to calculate *f*(*x*) for every integer *x* between 0 and 220. Let *f**k*(*x*) be the count of number *i* where *Y*0&X0 = *X*0 and *X*1 = *Y*1 (they are defined below).
     43 
     44 We divide *x* and *A**i* into two parts, the first *k* binary bits and the other 20 - *k* binary bits. Let *X*0 be the first part of *x* and *X*1 be the second part of *x*. Let *Y*0 be the first part of *A**i* and *Y*1 be the second part of *A**i*.
     45 
     46 We can calculate *f**k*(*x*) in *O*(1):
     47 
     48 ![](https://espresso.codeforces.com/bc85bc389336436b41cac28da31d21c855eb4608.png)
     49 
     50 The problem can be solved in *O*(*n* * 2*n*) now (*n* = 20 in this problem).
     51 
     52 #### [449E - Jzzhu и квадраты](/contest/449/problem/E "Codeforces Round 257 (Div. 1)")
     53 
     54 Consider there is only one query.
     55 
     56 ![ ](https://yc5-yc.github.io/psb.jpg)
     57 
     58 Let me descripe the picture above.
     59 
     60 A grid-square can be exactly contained by a bigger square which coincide with grid lines. Let *L* be the length of a side of the bigger square. Let *i* be the minimum distance between a vertice of the grid-square and a vertice of the bigger square. Let *f*(*L*, *i*) be the number of cells which are fully contained by the grid-square.
     61 
     62 We can divide a grid-square into four right triangles and a center square. For each right triangle, the number of cells which are crossed by an edge of the triangle is *L* - *gcd*(*i*, *L*). Then, the number of cells which are fully contained by the triangle is [*i*(*L* - *i*) - *L* + *gcd*(*i*, *L*)] / 2.
     63 
     64 *f*(*L*, *i*) = (*L* - 2*i*)2 + 2[*i*(*L* - *i*) - *L* + *gcd*(*i*, *L*)] = *L*2 - 2*iL* + 2*i*2 - 2*L* + 2*gcd*(*i*, *L*)
     65 
     66 Firstly, we enum *L* from 1 to *min*(*N*, *M*). Then the task is to calculate ![](https://espresso.codeforces.com/c09de3bdab9473d49f5ce34b027a01320bc85629.png). ![](https://espresso.codeforces.com/700369aa29aa82bd603a86deea43769b4a919ee3.png) can be calculated by the following steps:
     67 
     68 1. Enum all of the divisor *k* of *L* and the task is to calculate the count of *i* where *gcd*(*i*, *L*) = *k*.
     69 2. The count of *i* where *gcd*(*i*, *L*) = *k* equals to φ(*L* / *k*).
     70 
     71 Finally, ![](https://espresso.codeforces.com/dbd4ac9660af95b977a213f3bedb816c4fce2761.png).
     72 
     73 If there are multiple queries, we can calculate the prefix sum of ![](https://espresso.codeforces.com/0f2866cc85296f75fab9cde57b33f257c3acedc5.png), ![](https://espresso.codeforces.com/9895b11ba32a49fbf91b3567e2f072de947c7c3f.png) and ![](https://espresso.codeforces.com/386045d588be4839844d7125ba56c63fbc27340b.png), then we can answer each query in *O*(1).