MinakoKojima's blog

Codeforces Round #183 Editorial
By MinakoKojima, 12 years ago, In English

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://mirror.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)

See also at:

http://mirror.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://mirror.codeforces.com/blog/entry/7499#comment-133342

Math, Probability

(Coming After D...)

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

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would better that this round's editorial will be similar to the last round editorial!

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 7   Vote: I like it +12 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Each problem have "math" in its tags :D

→ Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

What is O(n) mean in problem B? n, m = 1e9. O(1e9)? Is it ok?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

so "Math" is a tag for all problems!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain where did the equation k * (k + 1) / 2 for pruning in div1 C come from?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried a bruteForce implementation, but it doesn't pass the test number 31

→ Reply