absy's blog

By absy, history, 7 weeks ago, In English

913B - Christmas Spruce

119557653

n= int(input())
ls=[]
for i in range(n):
    ls.append([])
 
for i in range(2,n+1):
    j=int(input())
    ls[j-1].append(i)
    
for i in ls:
    for j in i:
        if ls[j-1]:
            i.remove(j)
 
 
ls = list(filter(([]).__ne__, ls))
 
if len(min(ls))<3:
    print('No')
else:
    print('Yes')

Basically, I create a nested list where I store each node's child vertexes in different elements(eg: indexes of the child vertexes of the root node are in the 0th element/ the first element) of the list. Then, I remove the index of the child vertex (if that child vertex has further children) from the element associated with the parent vertex.

For eg: if 1 had 3 children, 2 3 and 4, and if 2 had further children, then we remove 2 from the element associated with the root, i.e. the 0th element in the list.

so before change -> [[2,3,4],[5,6,7]] after change -> [[3,4],[5,6,7]]

I'd appreciate the help especially since I'm a noob at coding :)

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You are using a data structure known as adjacency list. I am not sure exactly what you are doing, but I think it would suffice to check if the number of elements in each list you created is either 0 or >=3, (0 for a leaf vertex).

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. Lemme give an example:

    The second test run: 7 1 1 1 2 2 2

    So in the 1st for loop, I create a nested list with size n(Here 7). [[], [], [], [], [], [], []]

    for i in range(2,n+1):
        j=int(input())
        ls[j-1].append(i)
    

    The next inputs are ( This happens in the 2nd for loop) 1 (index of parent node for the 2nd node) 1 (index of parent node for the 3rd node) 1 for the 4th 2 for the 5th till 7th.

    So in this way, I add 2,3 & 4 to the 0th element j-1 (0 being the index for the 1st element in a list) and 5,6,7 to the 2nd element. Hence the range starts from 2 to n+1(8 here).

    for i in ls:
        for j in i:
            if ls[j-1]:
                i.remove(j)
    

    In the last for loop, I check every element of the list, and if a certain element of a sublist has other nodes attached to it, then we remove that element from the sublist. eg: [[2,3,4], [5,6,7]] changes to [[3,4], [5,6,7]](I'm removing the empty sublists here) since the 2nd node has elements in the list attached to it.

    Finally, I remove all the empty sublists and check if all the sublists have atleast 3 elements, If not print('No') .

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah now I get it, my bad I read the problem statement wrong. I don't think there is anything wrong with your logic, however, I have limited knowledge of python so I couldn't completely debug your code. Nevertheless, I can see two issues with it.

      1. if len(min(ls))<3:
        
        This finds the length of the list with the minimum value and not what you want it to do which is to find the minimum length of the list in ls. For this you can iterate through each element in ls and check the length.
      2. for j in i:
            if ls[j-1]:
                i.remove(j)
        

        The issue here is that you are editing the list that you are going through, which can lead to many errors. To avoid this, you can append to a list all the elements you want to remove, and then after complete iteration, you can go through the additional list you created and remove the elements from ls. It might look somewhat like this:

      for i in ls:
          removeElements = [];
          for j in i:
              if ls[j-1]:
                  removeElements.append(j)
          for j in removeElements:
              i.remove(j)
      
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For the 1st issue: a=[[2,3,4],[5,6,7],[],[]] . len(min(a)) would give 0 & a=[[2,3,4],[5,6,7]] would give 3. What you're saying is that this would give the length of the list with the min value, but I don't think that's possible when there are more one elements in each sublist of a nested list.

        2nd issue:

        for j in removeElements:
                i.remove(j)
        

        In this if I try to remove 5 from the nested list eg above, then the computer won't find it and it throws a ValueError: list.remove(x): x not in list .I'd say that that's happening as there are multiple elements in each sublist of the list.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Try this testcase for the first issue: a = [[0,0,0],[1000]], it will give 3 instead of 1. The way lists are compared is similar to how English words are compared, if the first element is greater than the first element in the second list, then the first list is greater, otherwise it is smaller. However, if it is equal, then we move on to comparing the second element.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I get what you're saying. It's the same as using [[2],[3,4,5]]. Here we remove 2 from the first but then that removes the first element too at the end.

            Got the code working with a different logic now.