Комментарии
|
0
That is actually written in the blog post itself :D
|
|
0
I've got a segment tree solution for problem D. It's an offline algorithm, I find all values which I can have. Then I sort and take the unique elements. This is the reference array for my segment tree. The actual array for the segment tree is a boolean valued array, which represents if the i-th element exists in the set or not.
I run a dp/segment tree kind of query from the root for each sum query. I compute the number of elements in the left subtree (using another count dp/segtree). The the offset for the right subtree is (parentOffset + left)%5 In this way I get the list of all elements in log(n) For every update, I start at the leaf and proceed towards the root, unsetting all the dp values. I liked this idea, it was going around in my head for a while, finally implemented it today :) |
|
0
Hi,
Usually I solve most problems of this type like this : Basically lets say that you go from state X to state Yi with time ti and probability pi The part of the expected cost would be f(X) = sum pi*( ti + f(Y) ) Lets just think of this like a graph, now, if this is like a DAG kind of a graph, then you can easily use a recursive solution with memoization. If not, then it gets interesting, basically you'd get a set of equations you've to solve now. For example f(A) = 1 + 0.5 * f(B) + 0.5*f(C) f(B) = 1 + 0.5 * f(A) + 0.5*f(C) f(C) = 0 You need to solve these equations, maybe a problem has a pattern (most recent Topcoder Div1 900), if it doesn't you can use Gaussian Elimination to compute your required answers. This is rather terse but I hope this helps. |
|
+13
When will ratings be made public?
|
|
0
I think they are UVA contests, maybe their link / time has changed.
|
|
0
This is very cool. I hope there is more integration with Social Networking Sites to improve the participation :)
|
|
+1
When is the next round?
I would suggest if you could keep the calendar as a Google Calendar, it will be very convenient and also be displayable easily in a web-page. Thanks for this amazing site! |
|
+1
He is a target :P
|