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 <luke.peb...@gmail.com
<mailto:luke.peb...@gmail.com>> 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 <fur...@gmail.com
<mailto:fur...@gmail.com>> 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
<mwea...@mailbolt.com <mailto:mwea...@mailbolt.com>> 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*p_i < p_j .*
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 google-code+unsubscr...@googlegroups.com
<mailto:google-code%2bunsubscr...@googlegroups.com>.
To post to this group, send email to
google-code@googlegroups.com
<mailto:google-code@googlegroups.com>.
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 google-code+unsubscr...@googlegroups.com
<mailto:google-code+unsubscr...@googlegroups.com>.
To post to this group, send email to google-code@googlegroups.com
<mailto:google-code@googlegroups.com>.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
