I think I did something isomorphic to that (unfortunately not during the round itself). Implementation at https://gist.github.com/Quantris/4747854
The vectors I kept track of are the running sums of the ones you describe: because the constraints mean we'll be interested in the sum of either a prefix or a suffix during a merge step, storing running sums lets us do each merge quickly. There was some working out to do when the thing you're merging in is more than just a [1] (I was worried about doing too much work since things were looking pretty big already); that's what all the combinatorial stuff is for. On Thursday, 14 February 2013 12:41:33 UTC-7, Bartholomew Furrow 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]<javascript:> > > 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] <javascript:>. >> To post to this group, send email to [email protected]<javascript:> >> . >> 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]. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/gIQ1xmZVA80J. For more options, visit https://groups.google.com/groups/opt_out.
