First of all. Forgive my poor English .......
288A - Polo the Penguin and Strings
Just arrange "abababa..." greedy ,and then "cdef..." . Note the condition of k=1
288B - Polo the Penguin and Houses
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 - Polo the Penguin and XOR operation
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 - Polo the Penguin and Trees
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 - Polo the Penguin and Lucky Numbers . 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!
Could you add more details in explanation of problem D? It's almost impossible to understand this formulas without good explanation.
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
Thank you for very comprehensive editorial, got it now.