codeforces-scrape

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

303.md (3212B)


      1 Source: https://codeforces.com/blog/entry/7641
      2 
      3 # Overview ...
      4 
      5 。。。(; Д ;) 。
      6 
      7 # Tutorial ...
      8 
      9 * [Problem 2A. Pythagorean Theorem II](//codeforces.com/problemset/problem/304/A)
     10 
     11 Math, implementation
     12 
     13 This problem can be solve by brute-force, but it come up with a nicer solution if we involve some math.
     14 
     15 Check the following article if you are interested.
     16 
     17 [http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple](https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple)
     18 
     19 * [Problem 2B. Calender](//codeforces.com/problemset/problem/304/B)
     20 
     21 Math, implementation
     22 
     23 This problem can be solve by brute-force, but it come up with a nicer solution if we involve some math.
     24 
     25 Check [kabar](/profile/kabar "Эксперт kabar")'s code if you are interested.
     26 
     27 [http://codeforces.com/contest/304/submission/3715756](//codeforces.com/contest/304/submission/3715756)
     28 
     29 * [Problem A. Lucky Permutation Triple](//codeforces.com/problemset/problem/303/A)
     30 
     31 Math, Constructive algorithms, Congruent
     32 
     33 * when n is odd, A[i] = B[i] = i
     34 * when n is even, there is no solution. So why? Because:
     35 
     36 S = \Sum_{i=0}^{n-1} i = n/2 (mod n) but 2*S = 0 (mod n)
     37 
     38 See also at:
     39 
     40 [http://codeforces.com/blog/entry/7499#comment-133446](//codeforces.com/blog/entry/7499#comment-133446)
     41 
     42 * [Problem B. Rectangle Puzzle II](//codeforces.com/problemset/problem/303/B)
     43 
     44 Math, Geometry
     45 
     46 Give you *n*, *m*, *x*, *y*, *a*, *b*.
     47 
     48 Find a maximum sub-rectangle within (0, 0) — (*n*, *m*), so that it contains the given point(*x*, *y*) and its length-width radio is exactly (*a*, *b*). If there are multiple solutions, find the rectangle which is closest to (*x*, *y*). If there are still multiple solutions, find the lexicographically minimum one.
     49 
     50 Split the problem into *x*-axis and *y*-axis. Then you can solve the sub tasks in *O*(1).
     51 
     52 ```
     53 d = gcd(a,b)
     54 a /= d
     55 b /= d
     56 t = min(n/a, m/b)
     57 a *= t
     58 b *= t
     59 ```
     60 
     61 Be careful, when the length is outside the original rectangle.
     62 
     63 * [Problem C. Minimum Modular](//codeforces.com/problemset/problem/303/C)
     64 
     65 Math, Graph theory, Brute-force, Congruent
     66 
     67 It is hard to solve this problem at once, so at first, let us consider on k = 0, this easier case can be solved by enumerate on the *ans*. Let us define a bool array diff[], which diff[x] is weather there are two number, *a**i*, *a**j*, such that *abs*(*a**i* - *a**j*) = *x*.
     68 
     69 So *ans* is legal <=> diff[ans], diff[2*ans] … are false.
     70 
     71 The time-complexity *O*(*n*2 + *mlogm*). Here *m* is the maximum *a**i*.
     72 
     73 Consider on *k* > 0, we need to know how many pairs which has difference x. Store them in  
     74 `vector<pair <int, int> > diff[x];`
     75 
     76 Then use a [dsu](https://en.wikipedia.org/wiki/Disjoint_sets) to maintain the how many a_i are congruent when enumerate on the *ans*.
     77 
     78 * [Problem D. Rotatable Number](//codeforces.com/problemset/problem/303/D)
     79 
     80 Math, Number theory
     81 
     82 (Coming Soon...)
     83 
     84 [http://codeforces.com/blog/entry/7499#comment-133342](//codeforces.com/blog/entry/7499#comment-133342)
     85 
     86 * [Problem E. Random Ranking](//codeforces.com/problemset/problem/303/E)
     87 
     88 Math, Probability
     89 
     90 (Coming After D...)
     91 
     92 [http://codeforces.com/blog/entry/7499#comment-133488](//codeforces.com/blog/entry/7499#comment-133488)