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!

here is my submission , which got a WA on 17th test 3219752

My solution is regarding the segments as the stones in NIM game. The correctness can be proved by SG theorem .

In the 17th test . The number of rest sticks is 1 1 4 1 1 4 (for the same Y) and 2 1 1 3 1 2 . my answer is change 3 to 1 in order to make the xor value to 0.

The system answer is to cut 2,0 2,5 . but 2,3 — 2,4 has been cut before. Is it valid ?? And why my answer is wrong ? Thx :)

Tomorrow is the 37th ICPC regional contest in Asia, Changchun Site . Wish everyone can do his best during the contest.

harbin engineering university's team is

hanfei19910905 2008061626 excalibure

silver__bullet zzxchavo acmzhy

lenohoo Li Run Ling Li Cong

gool luck and have fun in regional contest.

As my handle is hanfei19910905 , I am born in Harbin , China at Sep 5th , 1991 .

I am happy to make friends with all of you , here is my vk profile link

208A - Dubstep

string matching algorithm .

208B - Solitaire

Dynamic Programming. DP[i,a,b,c] stands for whether this case is valid if there are i piles and pile[i]'s top card is c, pile[i-1]'s is b, pile[i-2]'s is c.

DP[i,a,b,c] = DP[i,c,a,b] or DP[i,num[i-3],a,c]

208C - Police Station

let f(s,e) is the number of shortest path from s to e. for any node v which is one of the shortest path between 1 and n , the answer is 2*f(1*v)*f(v,n)/f(1,n).

we can calculate f(s,e) in O(V+E) time(using bfs). so the total time cost is O(V*(V+E)).

208D - Prizes, Prizes, more Prizes

Greedy. Note that we should use mod operator when exchanging prize but not subtraction.

208E - Blood Cousins

At first you should calculate every node's 2^i-ancestor so that we can find any node's k-ancestor in O(logV) time. Then we put the nodes whose deep is k into a dynamic array (say vector in C++), any sort by the first time stamp.

For every query, we find the v's k-ancestor p, and try to find the number of p's k+deep[p] child. In array[k + deep[p]], we can find the first element whose first time stamp is larger than p's, say array[][i], and we can also find the first element whose first time stamp is larger than p's second time stamp, say array[][j]. the answer is j-i+1.

When we use binary search , the time cost for every query is O(logV).

Qualification Round 1

A 158A - Next Round

Just sort. Notice 0 in the array.

B 158B - Taxi

Choose the 3 and 1 as much as possible. And let 2 combine with themselves. If there are more 1s and 2s, let two 1s combine with 2, and every four 1s take same taxi.

C 158C - Cd and pwd commands

Implement with stack. If the string begin with '/', let top = 0, else remain the top; Then process the substring one by one, when meeting ".." , top--; else remain the top;

D 158D - Ice Sculptures

The number of new regular polygon's edges must be the factor of the given polygon. Listing all the factors take O(sqrt(n)) time. Then choose the best point take O(n). So the time complexity is O(n*sqrt(n)).

E 158E - Phone Talks

It's a classic DP problem. Array dp[i][j] stands for the min rightmost endpoint when choosing at most j segments from the first i segments . dp[i][j] =dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]). When the dp array is completed , find the max value of left[i+1]-dp[i][k] and rightmost point — dp[n][k]. Totally take O(n*n).

Qualification Round 2

A 159A - Friends or Not

Compare every two records and find the right friends. Give every name a unique number so as to avoid counting same friend twice. If a and b is friends, let friend[a][b] = true.

B 159B - Matchmaker

Establish two hash tables counting the number of the size (say 2) exiting in set makers and set caps. Obviously the sum of min number of every size in two sets is the first answer. Similarly establish two hash tables in order to count the number of the same size and same color. The hash function can be hash(color, size) = color*1000+size.

C 159C - String Manipulation 1.0

Because the length of string is at most 100*2000, so we can build 26 line-segment-trees to count the 26 Latin letters. The way to build tree and find the position of K-th letter is quite simple if you under stand line-segment-tree :)

D 159D - Palindrome pairs

A dp method is really great~ , sum[i] stands for the number of palindrome string in the first i letters. palindrome[i][j] judges weather the substring i...j is a palindrome string. dp[i] is the answer for the first i letters. dp[i] = dp[i-1]+Sum( palindrome[j][i]*sum[j-1] ) for all j<=i && j>0 . sum[i] = sum[i-1]+Sum(palindrome[j][i]) for all j<=i.

E 159E - Zebra Tower

sort the array with compare condition (cube[i].color < cube[j].color ||(cube[i].color==cube[j].color && cube[i].size>cube[j].size)). Then for the first i cubes , there is a array Max_cube, Max_cube[j] records the max sum of j cubes' size with same color. To the cube i+1, if it's the k-th largest size of its color. Compare the answer with cube[i+1].size + max(Max_cube[k],Max_cube[k+1],Max_cube[k-1]). The time complexity is O(n*logn).

Forgive my poor English :)

gl and hf tonight!

I am a Chinese student from Harbin Engineering University , where the 2010 ACM/ICPC world final was held.

My name is Fei Han. Han is my family name. As the Chinese custom, we usually speak family name first. So you can call me Han Fei.

I register in VK.com recently and I want to make friends with the programmer here in VK.com.

I can speak English and Chinese. But my English is poor.

I am a ACM/ICPC participator. We can discuss something about Algorithm and programming.

Besides these , I also like Japanese Cartoon , say, Silver Soul, Naruto , One Piece ....

I'm glad to make friends with you ~~

My email is [email protected]

I didn't have a twitter or facebook account , I can't enter these website in China ,you know ~

My VK.com account profile link : http://vk.com/id165844360

forgive me   :D