The usual rules apply: if you're the first to post a solution in the comments, you get eternal glory. (If you post annonymously, claim your glory some time during the next eternity.)
Problem Fountain. Consider an undirected graph with costs (all costs are distinct) and the following traversal procedure. If we arrived at node v on edge e, continue on the cheapest edge different from e. If the node has degree 1, go back on e. A walk following these rules is called a "valid walk."
You also have a prescribed target node, and an integer k. Count the number of valid walks of exactly k edges which end at the prescribed target node. Running time O~(n+m) ["O~" means "drop logs"]
Problem Race. You have a tree with integer weights on the edges. Find a path with as few edges as possible and total length exaclty X. Running time O(nlg n) [log^2 may be easier.]
Problem RiceHub. N rice fields are placed at integer coordinates on the line. The rice must be gathered at some hub, which must also be at an integer coordinate on the line (to be determined). Each field produces one truck-load of rice, and driving the truck a distance d costs exactly d. You have a hard budget constraint of B. Find the best location for the hub, maximizing the amount of rice that can be gathered in the budget constraint.
Running time: O~(N).
Take some edge e, with endpoints a and b; the desired path either passes through that edge (in which case we need one path rooted at a and one rooted at b such that their length is exactly X - len(e) (*)) or doesn't pass through e (in which case we can solve the problem recursively for the 2 trees that are left, when e is removed).
ReplyDelete(*) This is essentially checking whether there are indices i and j, such that A[i] + B[j] = const, which can be solved in O(N) with hashtable.
Choosing such an edge e that separates the the tree into two trees of almost equal sizes leads to O(N log N) divide and conquer solution.
Eternal glory goes to Anton Anastasov. Congrats! :)
ReplyDeleteI just want to add a minor detail, that is one can not necessarily partition the tree into two balanced trees by removing an edge (imagine a tree with a vertex of degree n-1 and all other nodes of degree 1). You can do this by removing a vertex, but then you may have consider more than 2 subtrees where your two paths may be coming from.
ReplyDeleteAnon, thanks for pointing this out. I still think Anton gets the kudos since the idea is essentially the same.
ReplyDeleteI just wish to point out, as an addendum to what Anton said, that no hashtable is necessary, just counting sort and merging.
I agree.
ReplyDeleteNow the first problem. For each directed edge e compute the next edge in the walk after edge e, Next[0][e].
The super simple solution:
For each i between 1 and the greatest power of 2 less than or equal to k, compute Next[i][e] = Next[i-1][Next[i-1][e]]. Now it's easy to compute in O(log k) time the kth edge in the walk assuming we start at a edge e. We compute this for the first edge in the walk that starts at every given vertex and verify if the final vertex is the target node. Running time O((n+m) log k).
The better solution:
Look at the directed graph where vertices are the edges of the initial graph, and edges consist of pairs (Next[0][e], e). Since all "vertices" have in-degree 1, our graph looks like a set of cycles with trees attached to them.
Each starting vertex corresponds to a single "vertex" in our new graph since that's the first edge on the walk starting at that vertex. For each possible ending vertex (a directed edge uv in the initial graph, where v is the target node) we want to see which starting vertices can be reached in k-1 steps. Due to the structure of our graph, this can only be done by first covering for a number of times the cycle that this ending vertex is part of (which may consist of 0 edges), and then going straight to the desired starting vertex. This will then require x*length_of_cycle_containing_ending_vertex + length_of_path_from_ending_vertex_to_starting_vertex, for any nonnegative integer x. We can compute the length of the cycle and the distances to all other vertices in O(m) time with a breadth first search.
So the problem reduces to solving an equation of the form ax+b=k-1 for every possible starting vertex.
But there are several possible ending vertices. Again, looking at the structure, we see that there can be at most a constant number of such vertices per cycle, so the total running time is linear.
Very nice, Anon!
ReplyDeleteA small variation on your Solution #1 gets O(nlg k + m), which is enough for full score in the IOI.
The third problem:
ReplyDeleteFor a given set of k points the point that minimises the set of distances to it is at k/2 or k/2 + 1.
So you can do a solution that involves 2 moving pointers, where the first pointer i goes through each point and the second pointer is the rightmost point j for which the x[i..j] has a valid cost.
BTW I've heard the problem of finding a downwards path in a tree of sum S from a Microsoft interview last year, so at least that subproblem is pretty well known.
Queries in the first problem can be answered in O( log N ).
ReplyDeleteAfter making the cycle graph there are at most two important nodes ( let's call them P and P' ). For each node you can easily calculate the distance from P and P', these being d( P ) and d( P' ) respectively.
Now let count( n, k ) equal the number of nodes leading to n in exactly k steps. Our solution becomes count( P, k ) + count( P', k ).
We can assume in count( n, k ) that n is a part of a cycle, as it is trivial to calculate if it were not. So let len( n ) be the length of the cycle containing n.
Now you can precompute ( for P and P' ) some vectors... Let v[0][x] be the vector of distances from P that give x modulo len( P ), and v[1][x] the same vector for P'.
Now let's say we're given a distance k, and that m0 = ( k mod len( P ) ).
We're looking for all the nodes whose distances give m0 modulo len( P ), but are also greater than or equal to k.
This is easily done by a binary search on the vector v[0][m0]...
I coded this during the contest cause I didn't see that the number of queries is equal to 2000 in the largest subtask...
I should also mention that a similar complexity can be achieved for queries where P changes too, so the problem had a much bigger potential :)