I know i solved it with more complexity added but i have used the Segment tree . CodeChef: Practical coding for everyone
I did the problem using union find algorithm
11 Likes
Your code gives wrong answer for input:6 3 2
0 3 8 14 12 5
1 1
2 2
answer should be Yes Yes.
And there is no need of printing the answers in the last.You can print them just after solving that particular case. 
In the editorial it is given as ,any two frogs which have same maximum distances can communicate with each other. i am not able to clearly understand this statement.for example let us take this sample test case:
5 1 1
0 1 5 6 8
2 4
the second frog has a max distance of 1,and the fourth frog also has a maximum distance of 1.but they cant communicate with each other …can sumone clarify??
@prem_93 : Maximum distance of communication of frog 2 is 1+1(=k) = 2 , whereas frog 4 has maximum distance of 6+1 = 7 , so they cannot communicate.
@prem_93 : There is no pain in explaining :D.Let’s first sort each frog with it’s X-Cordinate.Look closely at the last frog,he can communicate till Last_Frog_Position + K,Now look at the second last frog,If the message sent by the second last frog can reach last frog , then we can assume that the last frog will communicate the message of second last frog without editing 
, otherwise second_last_frog can send it up to second_last_frog position + K . Point to observe is that in calculation of maximum distance of second last frog , only last frog is needed . I hope you can extent it from here.
1 Like
thnks that helped…i actually misunderstood the maximum distance of a specific frog as the maximum distamce itz message can reach…for example in the test case which i have given the fourth frog can transmit itz message over a maximum distance of 1 unit.but the max distance here the editorial specifies the maximum coordinate …right…also my solution with complexity O(nlogn) is giving tle…how should i correct it??prob link: CodeChef: Practical coding for everyone
my algorithm is as follows:
- used merge sort to sort the x co-ordinates.
2)after sorting, i found the points in which the communication path is disconnected.ie)the x coordinates for which , the distance between them and the next cordinate (in the sorted order) is greater than k.
i stored these values in a new array callect disconnect.
3)now given x and y(nos of the frogs) i calculate their x coordinates and check if there is any value “v” in disconect array satisfying the condition:pos(x)<=v<pos(y)…if yes…then i output “no” and “Yes” if otherwise.
Please explain in a more readable manner. The English is sort of broken and I cannot understand the solution properly 
sir!! please tell me where my code goes wrong!!
CodeChef: Practical coding for everyone
passing even the teastcase u have given 6 3 2 0 3 8 14 12 5 1 1 2 2
I used the same methodology and got WA. Can someone tell what is wrong and provide test cases for which this method fails ???
1 Like
- i ued merge sort to sort the x coordinates.
2)then,i took the new sorted array and traversed through each element ,finding the elements for which this condition is satisfied:
arr[i+1]-arr[i]>k.i stored these in a new array (let it be p array).
3)now in each query I take in the values of x and y(frog nos),and find
their respective positions(x coordinates)…let them be pos(x) and pos(y)…now i go through the “p” array and check if there is any value in it that satisfies this condition:pos(x)<=value<pos(y).
if there is such a value the answer is “NO” and “YES” if otherwise.
For example:
INPUT:
5 1 1
0 1 5 6 8
2 4
1)here after sorting the array is:0 1 5 6 8
2)in this case my “p” array would contain the elements 1 6…bcoz
(5-1>k) and(8-6>k).
- now in the query i have x=2,y=4…pos(2)=1 and pos(4)=6.
now there is an element(1) in my p array which satisfies the condition 1<=1<6 and hence my answer would be “NO”.
You are assuming that a[q-1] < a[m-1] which may not be true . Even if you are able to debug your code , You will get a TLE as the worst case complexity of your algorithm is O(N*P) where N <= 10^5 and P <= 10^5 .
1 Like
I used the same methodology and got AC. CodeChef: Practical coding for everyone You should not check if it reaches the end, rather check if they reach the same block in the end. Its like finding out which islands they stay in.
brobear has used the same approach.
Please put correct check on constraints.
if(a[0]>=1 && a[0]<=100000)
And further, you don’t need to check the constraints.
how did you store the graph??
Using adjacency matrix or List?
Hi, how do you prove by contradiction that both frogs can only communicate if they can reach the same maximal distance?