@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
My code is exactly like yours but still giving WA. Can you point out what is wrong here.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,p;
cin>>n>>m>>p;
int y[n];
pair<int,int>e[n];
for (int i=0;i<n;i++)
{
cin>>e[i].first;
e[i].second = i;
}
sort(e,e+n);
y[0] = 1;
int g = 1;
/for (int i=0;i<n;i++)
cout<<e[i].first<<" ";
cout<<endl;/
for (int i = 1;i<n;i++)
{
if (e[i].first-e[i-1].first <= m)
y[e[i].second] = g;
else
{
g++;
y[e[i].second] = g;
}
}
vectorv;
while(p–)
{
int a,b;
cin>>a>>b;
if (y[a-1] == y[b-1])
v.push_back(“Yes”);
else
v.push_back(“No”);
}
for (int i=0;i<v.size();i++)
cout<<v[i]<<endl;
}
Can’t figure out why I’m getting WA on my recursive solution, I am expecting TLE only.
https://www.codechef.com/viewsolution/40910014
The recurrence makes sense on paper, and I can’t figure out a contradiction.
Can someone help why i am getting NZEC while submitting the code
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class frog
{
int dist,indic,point;
public frog(int dist,int indic,int point)
{
this.dist=dist;
this.indic=indic;
this.point=point;
}
}
class sort implements Comparator
{
public int compare(frog f,frog e)
{
return f.dist-e.dist;
}
}
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int w=sc.nextInt();
frog arr[]=new frog[n];
frog arr1[]=new frog[n];
for(int i=0;i<n;i++)
{
int dist=sc.nextInt();
frog ff=new frog(dist,i,0);
arr[i]=ff;
}
Arrays.sort(arr,new sort());
int count=0;
for(int i=n-1;i>0;i–)
{
if(arr[i].dist-arr[i-1].dist<=k)
{
arr[i-1].point=arr[i].point;
}
else
{
arr[i].point=count;
arr[i-1].point=count+1;
count++;
}
arr1[arr[i].indic]=arr[i];
}
arr1[0]=arr[0];
for(int i=0;i<w;i++)
{
int l=sc.nextInt();
int h=sc.nextInt();
if(arr1[l-1].point==arr1[h-1].point)
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
}