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 [email protected].
To post to this group, send email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
