@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)
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
I used Adjacency list to store the graph
max distance= position of frog + k
@gcs after writing this i read ur answer to that guy and found i was kind of using the same methodology, but wasn’t able to understand what u were saying , can u please explain why cannot we iterate from the starting to the ending index can check v[i+1]-v[i]<=k holds always true.
1 Like
Can be solved simply by Union find algorithm. Even without taking care of rank 
, just did path compression .
Procedure : Create a vector which contains V.first = co-ordinate V.second = index in array.
sort vector according to co-ordinate values . iterate over sorted vector and make Union of two adjacent V.second(indices) if V[i].first - v[i-1].first <= k .
Query 
: you can fin representative (according to union find algorithm) of both frog ,if they are same print Yes else No.
2 Likes
how this is dynamic problem question?
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner input = new Scanner(System.in);
int n = input.nextInt();
long k = input.nextLong();
int p = input.nextInt();
long[] frog = new long[n];
long[] secondFrog = new long[n];
for(int i = 0; i < n; i++)
{
frog[i] = input.nextLong();
secondFrog[i] = frog[i];
}
Arrays.sort(secondFrog);
while(p-- > 0)
{
int x = input.nextInt();
int y = input.nextInt();
boolean canSend = true;
long lastElem = frog[y-1];
for(int j = (x-1); j < (y); j++)
{
if(secondFrog[j] == lastElem)
break;
else
{
if((secondFrog[j+1] - secondFrog[j]) > k)
{
canSend = false;
break;
}
else
continue;
}
}
if(canSend)
System.out.println("Yes");
else
System.out.println("No");
}
}
}
sir this is code id dont know where it goes wrong even i run most of the test cases given in editorial
please help
Solution looks quite simple if we use maps and define the family of frogs which belongs to same range and in that range each one of them can contact each other otherwise if they don’t belong to same range then answer is No.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unordered_map<ll,ll> mp;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,K,p,i;
cin>>n>>K>>p;
mp m1;
ll A[n],B[n];
ll S[p],D[p];
for(i=0;i<n;i++)
{ cin>>A[i];
B[i]=A[i];
}
for(i=0;i<p;i++)
{
cin>>S[i];
cin>>D[i];
}
sort(A,A+n); //sorting the array after storing its duplicate in B[n];
ll c=1;
if(n>1){
m1[A[0]]=c; //initially defined frog nearest to origin in range 1 which is reprecented by c
for(i=0;i<n-1;i++)
{
if(A[i+1]-A[i]>K)
{
c++;
} //whenever the consecutive difference of distances is greater than k,increment c and keep them in next family
m1[A[i+1]]=c;
}
}
ll k=0;
if(c==1)
{ //if there is only one frog ^.^
for(i=0;i<p;i++)
cout<<"Yes\n";
}
else {
while(k!=p)
{
ll x=B[S[k]-1];
ll y=B[D[k]-1]; // Now checking whether they belong to same family or not.
if(m1[x]==m1[y])
cout<<"Yes\n";
else cout<<"No\n";
k++;
}
}
}#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
// your code goes here
int i,n,k,p;
cin>>n>>k>>p;
ll a[n+1];
for(i = 1; i<n+1; i++)
cin>>a[i];
while(p–){
ll x,y;
cin>>x>>y;
if(abs(a[x]-a[y])<=k)
cout<<“Yes”<<endl;
else{
int flag;
i = 0;
while(true){
flag = 0;
if(i>n || i<0)
break;
if(a[i]<=a[x]+k && a[i]>a[x]){
x = i;
i = 0;
if(x == y){
flag = 1;
break;
}
}else i++;}
flag == 1 ? cout<<“Yes”<<endl:cout<<“No”<<endl;} }
return 0;}
This is my code for the above program. I tried all(including my own) the test cases and its giving me the right answer. I guess some edge test cases might be left untouched. So, pls help me with this and tell me on which test cases its wrong? Thank you in advance 
Can someone please explain with a proof why frogs would communicate only if their maximum distance is equal?
Simple Solution python 3
1-store the index
2-sort the array
3-fill the DP array based on position of frogs
`import sys
n,k,p=map(int,sys.stdin.readline().split())
arr=list(map(int,sys.stdin.readline().split()))
d={}
#Maintain Position
for i in range(n):
d[arr[i]]=i
Sort
arr.sort()
dp=[0]*n
count=0
dp[d[arr[0]]]=count
for i in range(1,n):
if(abs(arr[i-1]-arr[i])<=k):
dp[d[arr[i]]]=count
else:
count+=1
dp[d[arr[i]]]=count
print(dp)
for j in range§:
a,b=map(int,sys.stdin.readline().split())
if(dp[a-1]==dp[b-1]):
print(‘Yes’)
else:
print(‘No’)
`
I have written the following code and can’t find what’s going wrong, it’s passing the test case.
#include <bits/stdc++.h>
using namespace std;
long long int fun(long long int B[],long long int a,long long int n)
{
for(long long int i=1; i<=n; i++)
{
if(B[i] == a)
return i;
}
return 0;
}
int main()
{
long long int n,k,p,i,j,m,x,y,flag;
long long int A[200000],B[200000];
cin>>n>>k>>p;
for(i=1;i<=n;i++)
cin>>A[i];
for(i=1;i<=n;i++)
B[i]=A[i];
sort(B,B+n);
while(p--)
{
cin>>x>>y;
if(A[y]>A[x])
{
i=fun(B,A[x],n);
j=fun(B,A[y],n);
flag=0;
for(m=i;m<j;m++)
{
if(B[m+1]-B[m]>k)
{
flag=1;
cout<<"No"<<endl;
break;
}
}
if(flag == 0)
cout<<"Yes"<<endl;
}
else
{
i=fun(B,A[y],n);
j=fun(B,A[x],n);
flag=0;
for(m=i;m<j;m++)
{
if(B[m+1]-B[m]>k)
{
flag=1;
cout<<"No"<<endl;
break;
}
}
if(flag == 0)
cout<<"Yes"<<endl;
}
}
}
Can any one please tell me what is wrong in my solution
https://www.codechef.com/viewsolution/33533199
If a frog f1 can communicate with f2 then f2 should be able to communicate with f1 right? Why are we checking for the max distance both can communicate?
Even i solved it using DSU. But i couldnt think of a dp solution
sir, i have exactly coded the pseudo code given above but my solution is giving WA. please check my code and tell me where i have gone wrong!!
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool compareinterval(pair<ll,ll>a,pair<ll,ll>b)
{
return a.first>=b.first;
}
int main()
{
ll n,k,t;
cin>>n>>k>>t;
vectora(n);
for(ll i=0;i<n;i++)
cin>>a[i];
pair<ll,ll>p[n];
for(ll i=0;i<n;i++)
p[i]=make_pair(a[i],i+1);
sort(p,p+n,compareinterval);
vector<ll>maxdist(n+1,0);
maxdist[p[0].second]=p[0].first+k;
for(ll i=1;i<n;i++)
{
if(p[i-1].first-p[i].first<=k)
maxdist[p[i].second]=maxdist[p[i-1].second];
else
maxdist[p[i].second]=p[i].first+k;
}
for(ll i=1;i<=t;i++)
{
ll a,b;
cin>>a>>b;
if(maxdist[a]==maxdist[b])
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
solution link: CodeChef: Practical coding for everyone
Cant figure where i am wrong please help,STUCK FOR 3 DAYS NOW