Hey, fellow programmers. Hope you all are doing good.I don't want to waste your precious time so let's cut to the chase. As you can see I'm a newbie so pardon me if what i ask is way above my league. Believe me I'm trying but this competitive programming is difficult for me but sooner or later i will become good at this.
This was one of the questions asked in Amazon Hackathon round please help me solve this. Since I'm a newbie you can also share the links to article and knowledge resources that might be required to solve this. Please do not provide code directly as answer. Let me know how to solve and approach this problem.
The question is as follows-
/*****************************************
You are given N non negative integers namely-D1,D2,D3...DN. You have to find all the labelled trees that can be constructed such that the out-degrees of each vertex(1<=i<=N) is Dn. It is guaranteed that the sum of D1,D2....Dn is N-1.
Example test case- First line is number of integer and second line contains degree of each edges. Input-
4
0 1 0 2
--------------------------------------------------------------- Output- 5
A total of 5 labelled trees can be formed with given out-degrees.
Input-
5
0 1 1 1 1
Output-
125
A total of 125 labelled trees can be formed with given out-degrees.
*************************************************************/
Now this is an interesting problem because, although it might not look so, it involves quite a bit of number theory. Since each tree node has Di edges, we want to take the gcf of all Di. This will tell us the minimum number of trees we can create. Now we can take the lcm of all Di, and our answer will simply be lcm — gcd.
hey, the input output is something like this- N-4 0 1 0 2
Output- 5
N-5
0 1 1 1 1
output-125
kindly let me know wether this will follow same logic or not.
Oops, neglect the zeros and the answer will be (lcm — gcd)!. This is because nodes with zero connections don't really matter in the grand scheme of things except for different permutations. It should run smoothly after this bug fix.
but still second question is like 0 1 1 1 1 consisting of 5 nodes for this lcm and hcf will be same and answer will be 0!=1, but the output is 125.
Auto comment: topic has been updated by arpit_aditya (previous revision, new revision, compare).
There was slight input mismatch the first line contains number of nodes and the secod line contains all the out-degree.
Auto comment: topic has been updated by arpit_aditya (previous revision, new revision, compare).
Auto comment: topic has been updated by arpit_aditya (previous revision, new revision, compare).
Add explanation for first test case. I able to create only such 3 trees. If w we fix the outdegree of 4th vertex(3 cases), then there is only 1 way to arrange outdegree of vertex.
It was asked in hackon with amazon hackathon. I was not able to solve this, that's why i posted it here.
I think it will be something like this, it might be wrong, let's see-
2-->4--->1 | V 3
2-->1<--4 | V 3
2-->3<--4 | V 1
1<---2<--4 | V 3
3<--2<--4 | V 1
Please read 4|V as a down arrow directed towards the other node
Guys i was not able to find any answers but I cane across something known as cayley formula you guys can see if that can provide the solution and please tell me if i have done anything wrong. this question was downvoted, this is my first time posting a query so i don't have much idea. Overall thank you everyone who helped me.