### MinakoKojima's blog

By MinakoKojima, 9 years ago,

。。。(; Д ;) 。

# 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.com/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)

http://codeforces.com/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 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.

Math, Number theory

(Coming Soon...)

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

Math, Probability

(Coming After D...)

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

• -10

 » 9 years ago, # |   0 It would better that this round's editorial will be similar to the last round editorial!
•  » » 9 years ago, # ^ | ← Rev. 7 →   +12 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 ..
 » 9 years ago, # |   +11 Each problem have "math" in its tags :D
 » 9 years ago, # |   +11 What is O(n) mean in problem B? n, m = 1e9. O(1e9)? Is it ok?
•  » » 9 years ago, # ^ | ← Rev. 4 →   +13 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.
 » 9 years ago, # |   +1 so "Math" is a tag for all problems!
 » 9 years ago, # |   0 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?
•  » » 9 years ago, # ^ |   0 http://codeforces.com/blog/entry/7499#comment-133575This 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.
 » 6 years ago, # |   0 Can someone explain where did the equation k * (k + 1) / 2 for pruning in div1 C come from?
 » 21 month(s) ago, # | ← Rev. 3 →   0 .