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.
