- Forum
- General C++ Programming
- Tree Painitng
Tree Painitng
Hello, please help me. Below is the task description, and below that is my thoughts on the problem.
I know trying all possible orders is too slow.And also doing a BFS into the solutions uses too much space. Do any of you have any other solutions?
Task The tree consists of N branches numbered 1 to N. Branch 1 is the trunk and does not have a parent; every other branch has a “parent”, whose number is smaller than its own. The gardener will only paint one branch at a time and to make sure he doesn't miss a branch, he will only paint a branch if its parent is already painted. You have been asked to calculate the correct number of orders. Since the number is large you only need to find the answer modulo 10 007. Example If the tree has a trunk which splits into two branches (2 and 3), and 2 has a child 4 then there are three orders the gardener can paint the tree: • 1, 2, 3, 4 • 1, 2, 4, 3 • 1, 3, 2, 4. Input The first line of input contains an integer N. For i = 2, 3, . . . ,N, line i contains a single integer, the number of the parent of branch i. Sample input 4 1 1 2 Output The output consists of a single line containing single integer between 0 and 10 006, the number of ways the gardeners can paint the tree, modulo 10 007. Sample output 3 Constraints N<1000 Time limit 1 second |
I know trying all possible orders is too slow.And also doing a BFS into the solutions uses too much space. Do any of you have any other solutions?
it's an algorithm problem, and is it coming from an ACM / ICPC contest? if so, please give me the online judge address, otherwise I cannot give you the correct code.
briefly, you can create a tree first, which is simple.
and for each node, the way to paint it with its sub tree can be calculated by
F(n) = F(n.left) * F(n.right) * C(N(n.left), N(n.left) + N(n.right))
n.left means the left sub tree, n.right means the right sub tree, C(x, y) means the total count of methods select x elements from y elements. N is the function to return all the node count in the sub tree, include the root.
let me explain it a little bit,
so first of all, you need to paint all the nodes, but you need to paint the node n first, then left or right sub tree. since the count of nodes in left and right sub tree are constants, and you always can paint 'half of the left tree', then go to 'right tree', then finish 'the other half of the left tree', so the order between nodes in left and right tree is irrelevant. this is the reason of C(N(n.left), N(n.left) + (n.right)). but since you can paint N(n.left) nodes in F(n.left) ways, and paint N(n.right) nodes in F(n.right) ways, so you can get the final F function.
use a more complex sample as example,
6
1 1 2 3 3
it's
1
|\
2 3
| |\
4 5 6
so F(1) = F(2) * F(3) * C(N(2), N(2) + N(3))
C(N(2), N(2) + N(3)) = C(2, 5) = 5 * 4 / 2 = 10
F(2) = 1
F(3) = F(5) * F(6) * C(N(5), N(5) + N(6)) = 1 * 1 * C(1, 2) = 2 / 1 = 2
F(1) = 1 * 2 * 10 = 20
say
1 2 4 3 5 6
1 2 4 3 6 5
1 2 3 4 5 6
1 2 3 4 6 5
1 2 3 5 4 6
1 2 3 6 4 5
1 2 3 5 6 4
1 2 3 6 5 4
1 3 2 4 5 6
1 3 2 4 6 5
1 3 2 5 4 6
1 3 2 6 4 5
1 3 2 5 6 4
1 3 2 6 5 4
1 3 5 2 4 6
1 3 5 2 6 4
1 3 6 2 4 5
1 3 6 2 5 4
1 3 5 6 2 4
1 3 6 5 2 4
you will see the order of 3 5 6 and the order of 2 4 are irrelevant, so you can combine them with C function.
p.s. this is just the algorithm, you still need to do some optimize for 1 second limitation, say, prepare the tree, so you can get the result of N function in O(1), pre-compute C(x, y), attention, C(x, y) = C(y - x, y), the max value of C(500, 1000) is totally not acceptable in int, it's 1000! / 500! / 500!, but you can modulo 10007 first, since other operations are all multiplies.
briefly, you can create a tree first, which is simple.
and for each node, the way to paint it with its sub tree can be calculated by
F(n) = F(n.left) * F(n.right) * C(N(n.left), N(n.left) + N(n.right))
n.left means the left sub tree, n.right means the right sub tree, C(x, y) means the total count of methods select x elements from y elements. N is the function to return all the node count in the sub tree, include the root.
let me explain it a little bit,
so first of all, you need to paint all the nodes, but you need to paint the node n first, then left or right sub tree. since the count of nodes in left and right sub tree are constants, and you always can paint 'half of the left tree', then go to 'right tree', then finish 'the other half of the left tree', so the order between nodes in left and right tree is irrelevant. this is the reason of C(N(n.left), N(n.left) + (n.right)). but since you can paint N(n.left) nodes in F(n.left) ways, and paint N(n.right) nodes in F(n.right) ways, so you can get the final F function.
use a more complex sample as example,
6
1 1 2 3 3
it's
1
|\
2 3
| |\
4 5 6
so F(1) = F(2) * F(3) * C(N(2), N(2) + N(3))
C(N(2), N(2) + N(3)) = C(2, 5) = 5 * 4 / 2 = 10
F(2) = 1
F(3) = F(5) * F(6) * C(N(5), N(5) + N(6)) = 1 * 1 * C(1, 2) = 2 / 1 = 2
F(1) = 1 * 2 * 10 = 20
say
1 2 4 3 5 6
1 2 4 3 6 5
1 2 3 4 5 6
1 2 3 4 6 5
1 2 3 5 4 6
1 2 3 6 4 5
1 2 3 5 6 4
1 2 3 6 5 4
1 3 2 4 5 6
1 3 2 4 6 5
1 3 2 5 4 6
1 3 2 6 4 5
1 3 2 5 6 4
1 3 2 6 5 4
1 3 5 2 4 6
1 3 5 2 6 4
1 3 6 2 4 5
1 3 6 2 5 4
1 3 5 6 2 4
1 3 6 5 2 4
you will see the order of 3 5 6 and the order of 2 4 are irrelevant, so you can combine them with C function.
p.s. this is just the algorithm, you still need to do some optimize for 1 second limitation, say, prepare the tree, so you can get the result of N function in O(1), pre-compute C(x, y), attention, C(x, y) = C(y - x, y), the max value of C(500, 1000) is totally not acceptable in int, it's 1000! / 500! / 500!, but you can modulo 10007 first, since other operations are all multiplies.
Last edited on
There is a high possibility that my algorithm would be flawed but following is an interesting idea. That is if it is good enough to be explored.
Example, 1 has 3 children (2, 3, 4).
2 has 2 children (5, 6).
1. Start with the root node ( 1 ).
2. Calculate the total number of nodes in each child branch ( 3, 1, 1 ).
Lets say we mark them as x1, x2, x3, y and z. Now assuming x1, x2, x3 have already been sorted, we arrange these 5 nodes in 5 x 4 x 1 ways. = 20 ways.
3. For each child, if there is a subchild, then goto step 1 for that sub-child.
We know that node 2 has 2 children and the number of nodes in each branch is (1, 1)
So number of arrangements = 2.
Hence the total number of arrangements = 20 x 2 = 40.
EDIT: Step 2 calculation error corrected.
Example, 1 has 3 children (2, 3, 4).
2 has 2 children (5, 6).
1. Start with the root node ( 1 ).
2. Calculate the total number of nodes in each child branch ( 3, 1, 1 ).
Lets say we mark them as x1, x2, x3, y and z. Now assuming x1, x2, x3 have already been sorted, we arrange these 5 nodes in 5 x 4 x 1 ways. = 20 ways.
3. For each child, if there is a subchild, then goto step 1 for that sub-child.
We know that node 2 has 2 children and the number of nodes in each branch is (1, 1)
So number of arrangements = 2.
Hence the total number of arrangements = 20 x 2 = 40.
EDIT: Step 2 calculation error corrected.
Last edited on
seems I have made a mistake, I thought it's binary tree only,
but if it could be a more generic tree, the function
F(n) = F(n.left) * F(n.right) * C(N(n.left), N(n.left) + N(n.right))
can almost still work,
just a little bit change to
F(n) = F(n.sub1) * F(n.sub2) * ... * F(n.subX) * C(N(n.sub1), N(n) - 1) * C(N(n.sub2), N(n) - 1 - N(n.sub1)) * ... * C(N(n.subX), N(n) - 1 - N(n.sub1) - N(n.sub2) - ... - N(n.subX-1))
so in abhishekm71's case
1
/ | \
2 3 4
| \
5 6
it should be
F(1) = F(2) * F(3) * F(4) * C(1, 5) * C(1, 4) * C(3, 3)
F(2) = F(5) * F(6) * C(1, 2) * C(1, 1) = 1 * 1 * 2 * 1 = 2
F(3) = 1, F(4) = 1
F(1) = 2 * 1 * 1 * 5 * 4 = 40
but if it could be a more generic tree, the function
F(n) = F(n.left) * F(n.right) * C(N(n.left), N(n.left) + N(n.right))
can almost still work,
just a little bit change to
F(n) = F(n.sub1) * F(n.sub2) * ... * F(n.subX) * C(N(n.sub1), N(n) - 1) * C(N(n.sub2), N(n) - 1 - N(n.sub1)) * ... * C(N(n.subX), N(n) - 1 - N(n.sub1) - N(n.sub2) - ... - N(n.subX-1))
so in abhishekm71's case
1
/ | \
2 3 4
| \
5 6
it should be
F(1) = F(2) * F(3) * F(4) * C(1, 5) * C(1, 4) * C(3, 3)
F(2) = F(5) * F(6) * C(1, 2) * C(1, 1) = 1 * 1 * 2 * 1 = 2
F(3) = 1, F(4) = 1
F(1) = 2 * 1 * 1 * 5 * 4 = 40
And we need to only calculate each term modulo 10007
since
Max value for any product is 10006*10006; arithmetic using
since
(a*b) % m == ( (a%m) * (b%m) ) % m.Max value for any product is 10006*10006; arithmetic using
int would suffice.
Last edited on
| please give me the online judge address, otherwise I cannot give you the correct code. |
The judge is private and can only be accessed by members of my training division.
| so you can get the result of N function in O(1) |
That can be done easily, thank you.
| pre-compute C(x, y) |
And store the results where and how: there are 63 001 numbers minimum to store (assuming you remove duplicates C(x, y) == C(y-x,y))
Also, thank you for your help thus far. It is really appreciated :)
Last edited on
@Hzj jie
Nice!
For the general case, actually the problem of C(N(n.sub1), N(n) - 1) * C(N(n.sub2), etc is same as:
In how many ways can n objects be arranged out which p are alike, q are alike and r are alike.
factorial(n)
= ---------------------------
fact(p) * fact(q) * fact(r)
Nice!
For the general case, actually the problem of C(N(n.sub1), N(n) - 1) * C(N(n.sub2), etc is same as:
In how many ways can n objects be arranged out which p are alike, q are alike and r are alike.
factorial(n)
= ---------------------------
fact(p) * fact(q) * fact(r)
Well I have coded this, let me know what you think.
And the code that created the fact sequence:
|
|
And the code that created the fact sequence:
|
|
oops, the fact you have mentioned in your code and reply seems not what i said.
the C is a function of combination, while this is the wikipedia page about it
http://en.wikipedia.org/wiki/Combination
so, it has two parameters, say a, b
C(a, b) means the count of methods to select a elements from b elements, a <= b. so C(a, b) = b! / a! / (b - a)!
so you need to have an 2d array, say C[1001][1001], it will use about 1M * 4 = 4M memory. but this should not be the limitation.
the C is a function of combination, while this is the wikipedia page about it
http://en.wikipedia.org/wiki/Combination
so, it has two parameters, say a, b
C(a, b) means the count of methods to select a elements from b elements, a <= b. so C(a, b) = b! / a! / (b - a)!
so you need to have an 2d array, say C[1001][1001], it will use about 1M * 4 = 4M memory. but this should not be the limitation.
@Hzj jie
I do not think you read abhishekm71's suggestion.
It is the same as the one you suggested with C(x,y), however it uses far less space.
But, the question remains: What do you guys think of my code?
I do not think you read abhishekm71's suggestion.
| In how many ways can n objects be arranged out which p are alike, q are alike and r are alike. factorial(n) = --------------------------- fact(p) * fact(q) * fact(r) |
It is the same as the one you suggested with C(x,y), however it uses far less space.
But, the question remains: What do you guys think of my code?
Well i'm not experienced enough to comment about anyone's code but I tried to run your code and it gives the correct answer for the test cases that I tried. Couple of points that come to my notice are:
1. You seem to have a memory leak in your main function.
2. Instead of dynamically allocating memory for your A array, I would have prefered to use a vector.
1. You seem to have a memory leak in your main function.
2. Instead of dynamically allocating memory for your A array, I would have prefered to use a vector.
| You seem to have a memory leak in your main function. |
Problem should be solved thank you.
|
|
Topic archived. No new replies allowed.