hanfei19910905's blog

By hanfei19910905, 12 years ago, In English

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

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

»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I've just noticed that official tutorial isn't translated into English.

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

208C — we can calculate f(1, i) for all i by using only one bfs. So the complexity is O(V + E)

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

    yes, you are right ... It's a better solution, because we only need to know the f(i,v) which v is on the shortest way from 1 to n, so we only need to bfs from 1 to n and from n to 1 by two times.

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

Your solution for C is not adequate, the formula works for nodes other than 1 or N. If the maximum of that function over all nodes from 2 to N-1 is less than 1.0, then the solution is exactly 1.0 (we build a station in either 1 or N)

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

Just Orz..

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

Thanks for the solutions anyway!! :D

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

In B-solitaire, if we can move any of the pile instead of the right most only, what would be the solution ? All other constraints remaining same.