TREDIFF - Editorial

@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.

Keep coding :+1:

1 Like

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.

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.

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

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

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

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

[[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

first verify yourself then post such things

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

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!

// 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

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

1 Like

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

You must have missed one of it.

1 Like

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:

1 Like

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