69-64-79's blog

Round# 47 simple tutorial
By 69-64-79, 14 years ago, In English
  1. A
    n*m/2.
  2. B
    Record the occurrences' number of each letters, signed as cnt[char].
    For each char in string, get the cnt[c]^2 plus together, and this is the answer.
  3. C
    Calculate the Convex Hull. 
    The sum of the max value between x-difference and y-difference of each adjacent points in the convex hull's set and 4 is the answer.
    4 step can make a circle of 360 degree.
  4. D
    Counting the answer with Half, and check the answer using Dynamic Programming.
    Let dp[i][j] means the probability of first i objects where j of them exploded, and the transfering formular is:
    dp[i][j] = P(i) * dp[i - 1][j - 1] + (1 - P(i)) * dp[i - 1][j], where P(i) means the i-th object exploding's probability.

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

Comments Comments (3)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks for the tutorial :)
→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

problem E tutorial :
My AC code: https://codeforces.net/contest/50/submission/210541474

  • Observations:
  • We can classify roots into two types, rational and irrational.
  • We observe that irrational roots are always unique.
proof
  • So, we can count rational and irrational roots separately.
  • For counting irrational root, iterate on $$$b$$$ from 1 to $$$N$$$, and try to find several valid c such that $$$b^2 - c$$$ is not a perfect square. This can be done by a contradictory way of first finding all $$$(b,c)$$$ pairs where $$$b^2 - c$$$ is a perfect square and subtracting from the possible ways in $$$O(1)$$$.

  • This first part of the solution can be done in $$$O(N)$$$ overall. Even binary search can be done to find $$$C$$$'s lower and upper limits for a fixed $$$B$$$. This takes $$$O(NlogN)$$$, which is also accepted.

    The second part of the solution is to count all integer roots, which can be done in $$$O(N)$$$.

  • It is easy to show that our roots lie in the range $$$[-N, -1]$$$.
  • We can iterate over root, say R from $$$[-N, -1]$$$ to count the answer.
  • For each R, check whether a valid $$$B$$$ and $$$C$$$ exist; this can be checked by following the relation $$$r^2 +2br + c = 0$$$.
math proof for checking root is valid
  • The overall solution becomes $$$O(N)$$$ which is accepted due to the time limits (~5sec).
→ Reply