hanfei19910905's blog

By hanfei19910905, 7 years ago, In English,

First of all. Forgive my poor English .......

288A - Пингвин Поло и строки

Just arrange "abababa..." greedy ,and then "cdef..." . Note the condition of k=1

288B - Пингвин Поло и дома

for array [k+1 ... n] , the answer is pow((n-k),(n-k)). Because for every last n-k position, there are n-k choices.

for [1 .. k], my solution is DP.DP[k] stands for the number of valid conditions for p[2..k], without considering p[1]. Supposing that we erase the last entry p[k], then there may x's items that point to 1 directly or indirectly, and k -2 -x point to k directly or indirectly.

So DP[k] is sum(dp[x] * dp[k-1-x] * C(k-2,x)) for every x that fits 0 <= x <= k — 2 . So for [1..k] the answer is dp[k] * k. because p[1] can be any positive number that no greater than k.

288C - Пингвин Поло и операция XOR

It's so easy for problem C ... We list every number S from N to 1. Supposed that S is a n-bit binary number [bn-1 .. b0] that bn-1 is 1 , find a n-bit binary number [cn-1 ... c0] = X that X xor S = pow(2,n) — 1, then we shouldn't consider X any more ..

288D - Пингвин Поло и дерево

We can use tree DP to solve this: Let the node 1 be the root . {path u} can stand for all paths whose node which is closest to root is u . (That is to say, these nodes' LCA is u)

For node u, we can count all {path {v that is not in the subtree of u}} that not intersect with {path u} easily . It's C(2, n — number of nodes in u's subtree (short for sum(u))) .

for v in u's subtree . Supposing we have known the number of {path v}. we want to know the number of path that belongs to {path u} and not intersects with u. we can calculate all the paths that both belong to u and v. supposing u's son is S0 ... Sm-1, v belong to Si the answer for v is path(u)-(sum(u)-sum(Si))*sum(v) . Is it easy :) ? for all v in Si , the answer is sum(Si)*path(u)-(sum(u)-sum(Si)) * sumsum(Si); It's easy to calculate every node's sumsum and sum .

for v , path(v) = sum(sum(Si) * (sum(u)-sum(Si)-1)) + sum(u)-1; It's easy too , Isn't it ? :)

288E - Пингвин Поло и счастливые числа . ans(l..r) = f(r)-f(l).

if we know the answer of f(b[0...m-1]) it's not hard to calculate b[0...m], b[m] = 4 or 7

f(b[0...m-1]) = a0 * a1 + a1 * a2 + ... an-1 * an (a0 = '444...44') there are m's 4.

so b[0 .. m] = (a0*10+4) * (a0 *10 + 7) + (a0 * 10 + 7) * (a1 * 10 + 4) + .....

there are two parts: (ai * 10 + 4) + (ai * 10 + 7) for i = (0 .. n) is equal to 100 * ai * ai + 110 * ai + 28

we should know sum^2(ai) and sum(ai)

another part is (ai * 10 + 7) * (ai+1 * 10 + 4) is equal to 100 * (ai * ai+1) + 70 * ai+1 + 40 * ai + 28 for i = (0... n) if b[m] = 7 for i = (0... n-1) if b[m] = 4

It's hard to explain all the details and I'm too tired :( Bye!

  • Vote: I like it
  • +52
  • Vote: I do not like it

7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you add more details in explanation of problem D? It's almost impossible to understand this formulas without good explanation.

  • »
    7 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    After reading a bunch of codes and some thinking, I got to understand one way to approach this problem. I think it's different from the way mentioned in this editorial, where he counts the number of good pairs instead of bad pairs. Reference: 3562494

    Number of pairs of paths that we want = total pairs of paths — pairs of paths that intersect.

    total pairs of paths = S(S-1)/2, where S = size of entire tree

    As for the pairs of paths that intersect...

    We count for each node, the number of pairs of paths whose toppest intersected node is that node. If the intersection of two paths result in a path, we take the node in that intersected path that is closest to the root.

    For such "toppest intersected node", we note that the pairs of paths can either be:

    (a) one path lies entirely under the subtree rooted at the intersected node, whereas the other path extends up above the subtree and has its other end touching the intersected node.

    (b) both paths lie entirely under the subtree, and touch the intersected node

    (c) (NOT POSSIBLE) -> both paths go above the intersected node and also touch intersected node. This would contradict the fact that their current toppest intersected node is this node we are talking about.

    We can then count the bad pairs of paths Let touchAndInSubtree = #paths that touch the subtree root, and is contained by the subtree touchAndAboveSubtree = #paths that touch the subtree root, but has nodes that goes up the subtree So for

    case (a) -> touchAndInSubtree^2

    case (b) -> 2*touchAndInSubtree * touchAndAboveSubtree

    More calculations for each smaller term...

    touchAndInSubtree = number of paths in subtree — number of paths that dont touch the subtree root.

    The term to deduct here is just the total number of paths of each subtree rooted at this node's children.

    touchAndAboveSubtree = size of subtree * (total nodes -size of subtree) One end of the path has to be within the subtree, and the other has to be above the subtree.

    And after we have computed all that... answer is total pair of paths — intersect pairs at each node

    • »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for very comprehensive editorial, got it now.

7 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Четвертый вопрос Что это значит??????