I didn't enter HC round 1, because I knew I couldn't enter HC Round 3 (day after my birthday - having a gathering). So this is the first time I have read the question. But my initial thoughts were similar to Bartholomew's: construct the tree one leaf at a time. We just need to keep track of enough information to get the answer for the k vertex tree ans(k) from ans(k-1).
I have come up with a reformulation that might be helpful: ans(k)/k! is the probability that a uniformly random permutation satisfies all of the edge constraints. This is equal to the probability that if you choose k random variables uniformly from [0,1] that these variables satisfy all of the edge constraints. Thus ans(k)/kans(k-1) is the conditional property that these k random variables satisfy the (k-1)th constraint given they satisfy the first k-2 constraints. At this stage we have k-1 random variables we know to be connected by constraints, and we want to know the probability (conditional on these constraints) that a new random variable uniform on [0,1] is less (or more) than a specific one of these variables. The probability that a random variable uniform on [0,1] is less than X(i) is simply the expected value of X(i), so if we CAN keep track of the distributions of each of the vertices, we can solve the problem. However, at first glance this seems hard: how does (in your example) knowing that X(4)<X(2) affect the distribution of X(1)? My idea, which I don't know the quality of, is to keep track of the joint distribution of the two endpoints for each edge. Then, when you add a new edge to the tree, you can spread out the effect through the tree. Then I would try it on a few cases to see what these distributions look like. More deets later. Got to go to work. Sent from my iPad On 14 Feb 2013, at 19:41, Bartholomew Furrow <[email protected]> wrote: > I didn't end up finishing my implementation, but you're right that it's a > tree. You can collapse the tree one leaf node at a time. Each node starts > off with a vector representing sequences that contain only that node: [1]. > When you merge your 1 into your 3, you're merging a [1] with a [1], and you > care about the position of the 3. The merged node looks like (3, [1 0]): you > care about the position of the 3, which is in the first position of 1 > permutation that involves those two nodes, and the second position of 0 > permutations. The only permutation looks like (3, x). > > Next you can merge the 3 into the 2. You're merging (2, [1]) with (3, [1 > 0]); 2>3; and you care about the position of 2 (the non-leaf node). The > result looks like (2, [0 1 1]): there's one permutation of those three nodes > that has 2 in the second position, one that has it in the third position, and > none in the first. The permutations look like (x,2,x) and (2,x,x). > > Then merge in the (4, [1]), keeping the 2 (the non-leaf node), which (I > think) looks like (2, [0 2 1 0]). The permutations now look like (x, 2, x, > x), (x, 2, x, x), (x, x, 2, x). Finally bring in the 0, which has to be > greater than the 2, and you have (x, 2, x, x, x) * 6, (x, x, 2, x) * 2. > That's the same as (2, [0, 6, 2, 0, 0]). A total of 8 permutations. > > Cheers, > Bartholomew > > > On Thu, Feb 14, 2013 at 8:56 AM, Matt Weaver <[email protected]> wrote: >> Did anyone here manage to get this one? I've been trying to figure it out >> without any luck. I will copy the problem at the end. >> >> My best guess so far is to consider it a graph with an edge for each >> dependency, then due to their restrictions if you treat the edges as >> undirected the graph forms a tree. Then do some sort of DP in DFS order to >> get the answer? >> >> I'm stuck on situations like this though: >> >> 0 >> | >> v >> 2 >> / ^ >> v \ >> 3 4 >> ^ >> | >> 1 >> >> (0 > 2, 2 > 3, 2 < 4, 3 < 1). >> >> One valid permutation is 32041. Here, 1 is to the right of 2, even though >> it is part of 2's left subtree. >> >> Would appreciate any thoughts. >> In this problem you need to count number of possible permutations p of the >> first N integers, given N-1 constraints of the form pi < pj. >> >> Input >> The first line contains an integer T, T ≤ 20, followed by T test cases. Each >> test case begins with an integer N, N ≤ 1000, which is the number of >> integers in the permutation. The next N - 1 lines each contain a single >> constraint in the following format: "i sign j", where 0 ≤ i, j ≤ N - 1 and >> sign is either "<" or ">", which denotes whether the i-th element of the >> permutation should be less than or greater than the j-th element. >> >> It is guaranteed that it is not possible to partition indices into two >> disjoint sets A and B such that there is no constraint involving elements >> from both A and B. >> >> Output >> For each test case, output one single line with the number of permutations >> that satisfy all the constraints, following the output format shown in the >> example. The answer may be very large, so you should give the result modulo >> 1000000007. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
