304.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)