string matching algorithm .
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]
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.
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).
I've just noticed that official tutorial isn't translated into English.
208C — we can calculate f(1, i) for all i by using only one bfs. So the complexity is O(V + E)
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.
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)
Yes, I forget to say ...
Just Orz..
Thanks for the solutions anyway!! :D
My pleasure
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.