Overview ...
。。。(; Д ;) 。
Tutorial ...
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
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.net/contest/304/submission/3715756
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.net/blog/entry/7499#comment-133446
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.
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, ai, aj, such that abs(ai - aj) = x.
So ans is legal <=> diff[ans], diff[2*ans] … are false.
The time-complexity O(n2 + mlogm). Here m is the maximum ai.
Consider on k > 0, we need to know how many pairs which has difference x. Store them invector<pair <int, int> > diff[x];
Then use a dsu to maintain the how many a_i are congruent when enumerate on the ans.
Math, Number theory
(Coming Soon...)
http://codeforces.net/blog/entry/7499#comment-133342
Math, Probability
(Coming After D...)
It would better that this round's editorial will be similar to the last round editorial!
This is the worst round I have ever seen ... the round is going completely out of our control .... I am spending all of my time on reply the question during the contest ... There are a lot misunderstanding during the last day translation phase, and I am off-line during that time and come back so late ... Also, the solution for 1E have some spot on precision issue which we should discover it in last month. Although it has been solved now, we are going to see why it happened and give you a approving result on how to avoid such issue.
Anyway, I am going to improve it during this week, but I don't want you waiting so long ... m(_ _)m ..
Each problem have "math" in its tags :D
What is O(n) mean in problem B? n, m = 1e9. O(1e9)? Is it ok?
Fixed ... Thank you for feedback ... )
The length and width for the max sub rectangle can be calculated in O(1) whatever the a, b they are.
so "Math" is a tag for all problems!
What do you mean under "Then use a dsu to maintain the how many a_i are congruent when enumerate on the ans" in explanation of problem C? Can you give some example, please?
http://codeforces.net/blog/entry/7499#comment-133575
This one is better then mine ... In the last step, he mentioned about "size of array". And that is what we need to maintain by dsu or any other method you can come up with.
Can someone explain where did the equation k * (k + 1) / 2 for pruning in div1 C come from?
I tried a bruteForce implementation, but it doesn't pass the test number 31