I haven't written it up, but I'm pretty sure this works:
1) Root the tree
2) Assign a polynomial to each vertex of the tree as follows (from the
leaves upwards to the root)
- if the vertex is a leaf, assign the polynomial 1
- otherwise, assign the product of Integral[f(t),{t,0,x}] for all
polynomials f associated with child vertices that are required to have
lower labels, and Integral[f(t),{t,x,1}] for all polynomials f associated
with child vertices that are required to have higher labels.
3) The answer is n! multiplied by Integral[f(t),{t,0,1}] where f(t) is the
polynomial associated with the leaf.
For the given example:
Children(0) = 2 (0 more than 2)
Children(2) = 3,4 (2 more than 3, 2 less than 4)
Children(3) = 1 (3 less than 1)
Children(4) = -
Children(1) = -
the polynomials are:
Poly(1) = 1
Poly(4) = 1
Poly(3) = Integral(Poly(1),{t,x,1}) = 1-x
Poly(2) = Integral(Poly(3),{t,0,x}) * Integral(Poly(4),{t,x,1}) =
(x-x^2/2) * (1-x) = x-3x^2/2+x^3/2
Poly(0) = Integral(Poly(2),{t,0,x}) = x^2/2-x^3/2+x^4/8
Integral(Poly(0),{t,0,1}) = 1/6 - 1/8 + 1/40 = 1/15
So the number of labellings is 5!/15 = 8.
On Fri, Feb 15, 2013 at 7:13 AM, Luke Pebody <[email protected]> wrote:
> 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.
