Overview ...

。。。(; Д ;) 。

Tutorial ...

• Problem 2A. Pythagorean Theorem II

Math, implementation

This problem can be solve by brute-force, but it come up with a nicer solution if we involve some math.

Check the following article if you are interested.

http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple

• Problem 2B. Calender

Math, implementation

This problem can be solve by brute-force, but it come up with a nicer solution if we involve some math.

Check kabar's code if you are interested.

http://codeforces.me/contest/304/submission/3715756

• Problem A. Lucky Permutation Triple

Math, Constructive algorithms, Congruent

• when n is odd, A[i] = B[i] = i
• when n is even, there is no solution. So why? Because:

S = \Sum_{i=0}^{n-1} i = n/2 (mod n) but 2*S = 0 (mod n)

See also at:

http://codeforces.me/blog/entry/7499#comment-133446

• Problem B. Rectangle Puzzle II

Math, Geometry

Give you n, m, x, y, a, b.

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.

Split the problem into x-axis and y-axis. Then you can solve the sub tasks in O(1).

d = gcd(a,b)
a /= d
b /= d
t = min(n/a, m/b)
a *= t
b *= t

Be careful, when the length is outside the original rectangle.

• Problem C. Minimum Modular

Math, Graph theory, Brute-force, Congruent

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.

So ans is legal <=> diff[ans], diff[2*ans] … are false.

The time-complexity O(n² + mlogm). Here m is the maximum a_i.

Consider on k > 0, we need to know how many pairs which has difference x. Store them in
vector<pair <int, int> > diff[x];

Then use a dsu to maintain the how many a_i are congruent when enumerate on the ans.

• Problem D. Rotatable Number

Math, Number theory

(Coming Soon...)

http://codeforces.me/blog/entry/7499#comment-133342

• Problem E. Random Ranking

Math, Probability

(Coming After D...)

http://codeforces.me/blog/entry/7499#comment-133488