PROBLEM LINK:Author: Dmytro Berezin DIFFICULTY:SIMPLE PREREQUISITES:Basic Dynamic Programming PROBLEM:Given Frog's location on the X axis and they can communicate their message to another frog only if the distance are less than or equal to K , now you need to answer if given two frogs can communicate or not. Assumption : Frog's are cooperative in nature and will transfer the message without editing it :D . Quick ExplanationFind for each frog the maximum distance which his message can reach. Two Frogs can only communicate if their maximum distance of communication are same. ExplanationOnly Challenge left is to calculate the maximum distance which each frog can message. Using these observation , one can use a simple dp to calculate the maximum distance . But how ? Sort A[i]'s but do not loose the index of frog's while sorting. Let the sorted array be Frog[] . Now if Frog[i] can communicate to Frog[i+1] , then Frog[i] can communicate as mcuh distance as Frog[i+1] can communicate. Pseudo Code
Complexity: O(N*log(N)), N * logN for sorting N integers. AUTHOR'S and TESTER'S SOLUTIONS:Author's solution to be uploaded soon.
This question is marked "community wiki".
asked 14 Jul '14, 15:01
showing 5 of 18
show all

alternatively, make an another array containing indices, sort them using the first array. then assign some common number to those frogs who can communicate. ( In sample test case, indices becomes 0 1 3 2 4 and we have to check if v[1]v[0]<=k) if yes then assign some common value to them ). Link to code: http://ideone.com/nGyLo9 answered 14 Jul '14, 16:56

I solved the problem in two ways: Using Segment Trees, Using concept of connected component as pointed out by @brobear1995 But I haven't thought of a DP solution...I always miss out on DP.. :( answered 14 Jul '14, 17:10

Methodology Used: 1. Keep the input array 2. Create a duplicate array of it. 3. Sort the duplicate array. 4. Use the input index to get the element from original array, use Binary search ti find the index of that element in the duplicate sorted array. 5. Iterate through the starting index to the last index and check for <=K while iterating (a[i+1]a[i]<=K). 6. If reaches to the end, output Yes else No. 7. Giving WA.
answered 14 Jul '14, 20:29
1
I used the same methodology and got WA. Can someone tell what is wrong and provide test cases for which this method fails ???
(14 Jul '14, 23:19)
I used the same methodology and got AC. http://www.codechef.com/viewsolution/4186145 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.
(15 Jul '14, 16:59)

I copied the original array A into another array B and sorted it in increasing order, while maintaining the index.Then I copied the elements which fail the condition mentioned.
Then I used lower_bound to check the position of both the elements (A[x1],A[y1]) in the vector vec. If abs(posxposy)>=1, the answer will be no else it will be yes.
It worked. answered 15 Jul '14, 11:03

Hi , can u plz tell me for which Test case I am getting WA . http://www.codechef.com/viewsolution/4277673 Thanks rajesh answered 14 Jul '14, 16:44

Same thing I do but still getting TLE I sorted them using quick sort and then go through min coordinate to max coordinate and note down every starting point after breaking point say if coordinates are 0 8 5 3 12 and distance is 3 than i stored 0 12 in new array than i take input from user and get coordinate of there position and look for whether they belong to same interval or not if yes than answer is yes else no. Link to solution Please tell me what wrong in my code answered 14 Jul '14, 17:31

Sir, i have used this code and getting correct answer for all the test cases which i have tried....i am still getting WA...please help where is the error in the code?? http://www.codechef.com/viewsolution/4254933 answered 14 Jul '14, 17:33

Sir, I have used my code for most of the test cases and getting the desired output.....still I am getting WA....Kindly tell the respective cases for which my code was wrong....Thank you http://www.codechef.com/viewsolution/4297541 answered 14 Jul '14, 21:21
1
You are assuming that a[q1] < a[m1] 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 .
(15 Jul '14, 16:30)

I know i solved it with more complexity added but i have used the Segment tree . http://www.codechef.com/viewsolution/4217571
I did the problem using union find algorithm
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.
@devuy11 ...can u plz take the pain of explaining how max distance is calculated??
@prem_93 : There is no pain in explaining :D.Let's first sort each frog with it's XCordinate.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 :D , 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.
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: http://www.codechef.com/viewsolution/4319695
@prem_93 : right :) . Your code seems to be tough one for me to understand :( .
my algorithm is as follows:
1) used merge sort to sort the x coordinates.
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 :(
1) 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 (51>k) and(86>k).
3) 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".
Hi, how do you prove by contradiction that both frogs can only communicate if they can reach the same maximal distance?
@kuruma  suppose frog at x coordinate = 1 can send message to maximum x=10, this means all frogs between x=1 and x=10 can send message to x=10. And this means frog at x=1 cannot send message to frog at x>10(because max distance he can send message is 10) .. And suppose frog at x=15 can send message to maximum x=20 and frog at x=10 is able to send message to x=15.. so the maximum distance frog at x=10 can send msg is x=20 and maximum distance frog at x=15 can send msg is x=20. that means frog at x=10 and x=15 can communicate (because all frog between x=10 and x=20 can communicate)
@kuruma
PROOFBYCONTRADICTION
STATEMENT:Twofrogs which have same maximal distances cannot communicate with each other.
let the common maximal distance be Y.
let position(frog'1') be a and pos(frog'2') be b.
letY>=b>=a.
Since,1stfrog can communicate till"Y",it should also mean that it can communicate to all the frogs whose positions are in the interval [a,Y].Since"b"is a position which satisfies this condition it can communicate with 2nd frog but this contradicts our statement and hence we have proved it false.
thus this proves that 2 frogs with same max distance can communicate.
@kuruma you can also prove the statement:
"Two frogs which have differnet maximal distances can communicate with each other." to be false in a similar way.
And from these 2 proofs you can conclude that "Two frogs can communicate with each other only if their maximal distances are the same."
@ShangJingbo and @GeraldAgapov can u please provide the test case for which my code gave TLE?? http://www.codechef.com/viewsolution/4327814
max distance= position of frog + k