arpit_aditya's blog

How to Solve this problem!! please help.
By arpit_aditya, history, 10 months ago, In English

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.

*************************************************************/

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arpit_aditya (previous revision, new revision, compare).

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There was slight input mismatch the first line contains number of nodes and the secod line contains all the out-degree.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arpit_aditya (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arpit_aditya (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It was asked in hackon with amazon hackathon. I was not able to solve this, that's why i posted it here.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think it will be something like this, it might be wrong, let's see-

      1. 2-->4--->1 | V 3

      2. 2-->1<--4 | V 3

      3. 2-->3<--4 | V 1

      4. 1<---2<--4 | V 3

      5. 3<--2<--4 | V 1

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please read 4|V as a down arrow directed towards the other node

        → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply