TREDIFF - Editorial

editorial
, , , ,
125

@virtuality Although you are keeping track of repeated node values, you should also keep track of the number of nodes (call that len) in the path.
Then, keep incrementing len in the loop on line 49, whenever you add a node to the path.
After line 58, inside the loop, check whether len > 100, if yes then you can print 0 as the answer due to pigeonhole principle.

126

Keep coding :+1:

1 Like
127

No need for that because when len becomes > 100, automatically by pigeon hole principle Iā€™ll get a repeated value which my code will detect.

128

I found the problem. The problem was with unordered_map and unordered_set. I had this problem once before, so thatā€™s why I was able to guess it this time. It seems these STL hash sets donā€™t scale efficiently. So by reserving the capacity in the beginning itself, it could perform lookups in O(1) time. Here is the modified code: CodeChef: Practical coding for everyone . Added lines 109-111.

129

https://www.codechef.com/viewsolution/33596543
what is wrong in this?

130

May be the distance between nodes should be greater than 100 ? or might not be clear vector after another test case. :thinking:

131

https://www.codechef.com/viewsolution/33604155

i followed the above approach ā€¦i am not able to even get 30pts?
can u please tell me my mistake

132

I would like to know, instead of Binary Lifting,what other technique can we use to find LCA in logN time??Kindly suggestā€¦

134

[[quote=ā€œsayan_1999, post:132, topic:67092, full:trueā€]
I would like to know, instead of Binary Lifting,what other technique can we use to find LCA in logN time??Kindly suggestā€¦
[/quote]

afsdf

135

first verify yourself then post such things

136

I found no such thing on the internet.Kindly say the full nameā€¦

137

https://www.codechef.com/viewsolution/34001021
I cannā€™t find a test-case for which it fails.
Can anyone give me a test case or fix my code?

@vivek_1998299 can you help me?
Thanks!

138 
// path length
long long path_length = level[a] + level[b] - level[lca];

Just replace this :arrow_heading_up: with this :arrow_heading_down:.
Actually the distance between two nodes (a,b) = level[a]+level[b]-2*level[lca].

Here is the link to correct solution of your code ā†’ Your code

1 Like
139

Thanks for pointing that out. How did I miss this :relieved:

1 Like
140

Paramara, Pratishtha, Anushashan.
Yeh hai, coding ke teen stambh. :stuck_out_tongue:

You must have missed one of it.

1 Like
141

Actually it is level[a]+level[b]-2*level[lca]-1. Your code passed because I chose a larger value for path_legth(120) instead of 100.

Edit: Actually the test-cases are weak. Thereā€™s no case for path_length = 101 :sunny:

142
1 Like
143

The below code getting RE (NZEC) error can anybody please help me

cook your dish here

n=int(input())
while(n>0):
N,Q=map(int,input().split())
L=list(map(int,input().split()))
P=[]
C=[]
H=[0]*(N+1)
for i in range(N-1):
u,v=map(int,input().split())
P.append(u)
C.append(v)
H[v]=H[u]+1
#printĀ§
#printĀ©
#print(H)
#print(L)
while(Q>0):
u,v=map(int,input().split())

    Sl=[]
    
    while(len(Sl)<100 and u!=v):
        
        if(H[u]>H[v]):
            Sl.append(L[u-1])
            u=P[C.index(u)]
        elif(H[u]<=H[v]):
            Sl.append(L[v-1])
            
            v=P[C.index(v)]
            
        else:
            Sl.append(L[u-1])
            u=P[C.index(u)]
            Sl.append(L[v-1])
            v=P[C.index(v)]
    
    Sl.append(L[u-1])
    
    if(len(Sl)>=100):
        print(0)
        Q=Q-1
        continue
    Sl.sort()
    min=100
    for i in range(len(Sl)-1):
        if(min>Sl[i+1]-Sl[i]):
            min=Sl[i+1]-Sl[i]
            if(min==0):
                break
    print(min)
    
    Q=Q-1
    
    
n=n-1