FROGV - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

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 :smiley: .

Quick Explanation

Find for each frog the maximum distance which his message can reach. Two Frogs can only communicate if their maximum distance of communication are same.

Reason
You can easily proof by contradiction. Let us assume that there are two frogs 1 and 2 which can communicate but their maximum distances are different. You can easily contradict this , proof is left as an exercise for the reader.

Explanation

Only Challenge left is to calculate the maximum distance which each frog can message.

The First point to note is that one of the optimal strategy of each frog(say f) will be to send message to it’s nearest frog(say f1) and then it will be the responsibility of the nearest frog to carry it further.

One Line Proof : Frog’s reachable from the f in the direction of f1 is also reachable from f1.
Another point to note is that the frog on the extreme positive side of X axis(i.e Maximum A[i] , say A[j]) can communicate till A[j] + K.

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

Pre-Compute ( A , K ):
	sort(A,A+N);		//Sorted in Decreasing Order of X .
	Max_Distance[A[0].ind]=A[0].v+K;
	for(int i=1;i<N;i++)
		if((A[i-1].x-A[i].x)<=K)        
			Max_Distance[A[i].ind] = Max_Distance[A[i-1].ind];
		else
			Max_Distance[A[i].ind] = A[i].x + K;

Answer ( x , y ):
	if ( Max_Distance[x] == Max_Distance[y] ):
		return "Yes"
	else
		return "No"

Complexity:

O(N*log(N)), N * logN for sorting N integers.

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution to be uploaded soon.
Tester’s solution

6 Likes

sir i used the following logic which was giving me correct answer on ideone but i got 94 WA here… :frowning:
kindly help…

#include<iostream>
//#include<cstdlib>
long long int x,y,i,j,flag,other,n,p,index[100000],coordinate[100000],k;
using namespace std;

void qsort(long long int x[],int first,int last){
    int pivot,j,temp,i,temp2;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                  temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
                  temp2=index[i];
                  index[i]=index[j];
  		  index[j]=temp2;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         temp2=index[pivot];
         index[pivot]=index[j];
         index[j]=temp2;
         qsort(x,first,j-1);
         qsort(x,j+1,last);

    }
}


int main(void)
{
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 cout.tie(NULL);
 cin>>n>>k>>p;
/* if(n==1)
 {
  cout<<"No\n";
  exit(0);
 }*/
 for(i=0;i<n;i++)
 {
  cin>>coordinate[i];
  index[i]=i+1;
 }
 qsort(coordinate,0,n-1); 

 while(p--)
 {
  flag=0; 
  cin>>x>>y;
  if(x<=n&&y<=n)
  {
  for(i=0;i<n;i++)
  {
   if(index[i]==x)
   {
    other=y;
    for(j=i+1;(j<n)&&(coordinate[j]-coordinate[j-1]<=k);j++)
    {
     if(index[j]==other)
     {
      flag=1;
      break;
     }
    }
    if(flag==1)
     break;
   }
   else if(index[i]==y)
   {
    other=x;
    for(j=i+1;(j<n)&&(coordinate[j]-coordinate[j-1]<=k);j++)
     {
      if(index[j]==other)
      {
       flag=1;
       break;
      }
     }
     if(flag==1)
      break;
   }
  }
  if(flag==1)
   cout<<"Yes\n";
  else
   cout<<"No\n";
  }
 }
 return 0;
}

#include
#include
#include
#include
#include
using namespace std;
int main()
{
int n,k,p,a[100001],c[100001],l,count=0,p1,p2,m=0,s,b=0,d=0;
int i,j;
scanf(“%d %d %d”,&n,&k,&p);
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
c[i]=a[i];
}
sort(a,a+n);
while(p–)
{
scanf(“%d %d”,&p1,&p2);
if(p1==p2)
{printf(“Yes\n”);
goto f;}
p1=c[p1-1];
p2=c[p2-1];
b=(p1>=p2)?p1:p2;
s=(p1<=p2)?p1:p2;
for(i=0;i<n;i++)
{
if(b==a[i])
{
for(m=l;m<i;m++)
{
if(a[m+1]-a[m]<=k);else goto q;
}goto y;
} else
if(a[i]==s)
{
l=i;
}
}
q:;printf(“No\n”);
goto f;
y:;printf(“Yes\n”);
f:;
}
return(0);
}

Its complexity is around nlogn…why its showing then Time limit exceeded? It used the same concept then why its showing TLE!!!

This code can also be found at CodeChef: Practical coding for everyone

Hi ,
can u plz tell me for which Test case I am getting WA .

http://www.codechef.com/viewsolution/4277673

Thanks
rajesh

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

12 Likes

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… :frowning:

4 Likes

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

1 Like

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

I solved it using segment tree .

1 Like

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.

    #include
    #include
    #define ll long long
    #define fore(i,x) for(int i=0;i<x;i++)
    using namespace std;
    #define MAXSIZE 100001
    int binary_srch_ret_index(ll inp[MAXSIZE],ll e,int low,int high)
    {
    if(low>high) return -1;
    int mid=(low+high)/2;
    if(e==inp[mid])return mid;
    if(e<inp[mid])return binary_srch_ret_index(inp,e,low,mid-1);
    else return binary_srch_ret_index(inp,e,mid+1,high);
    }
    int searchNo()
    {

    }
    int main()
    {
    // freopen(“input.txt”,“r”,stdin);
    ll N,K,P,A,B;
    ll inp[MAXSIZE];
    ll dupinp[MAXSIZE];
    cin>>N>>K>>P;
    fore(i,N)
    {cin>>inp[i];dupinp[i]=inp[i];}
    sort(dupinp,dupinp+N);
    bool flag=true;
    while(P–)
    {
    cin>>A>>B;
    if(A==B)cout<<“Yes”<<endl;
    else{

         int locA=binary_srch_ret_index(dupinp,inp[A-1],0,N-1);
         int locB=binary_srch_ret_index(dupinp,inp[B-1],0,N-1);
         //cout<<locA<<" "<<locB<<endl;
         for(int i=locA;i<locB;i++)
         {
             //cout<<"res:"<<result[i]<<endl;
             if((dupinp[i+1]-dupinp[i])>K)
             {flag=false;break;}
         }
       if(!flag)cout<<"No"<<endl;
       else
        cout<<"Yes"<<endl;
     }
    

    }
    return 0;
    }

2 Likes

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

Hello All,
I used the following method:

  1. Treat all positions of Frogs as node in a graph.

  2. create a undirected path for nodes whose distance is distance is less than K.

  3. Used Breadth first search to find if target node is reachable or not.

Getting WA.
Please anyone tell me what’s wrong in the logic, i’ll be really helpful. Thanks!!!

sir!! please tell me where my code goes wrong!!
http://www.codechef.com/viewsolution/4330694

a simple one —

http://www.codechef.com/viewsolution/4193136
1 Like

My code runs fine offline but does not run here
http://www.codechef.com/viewsolution/4331567

Why can’t we do it like this ?

    int frogs=sc.nextInt();
	int distance=sc.nextInt();
	int pairs=sc.nextInt();
    int[] a=new int[frogs];
	for(int i=0;i<frogs;i++){a[i]=sc.nextInt();}
	while(pairs-->0){
		int n1=sc.nextInt(); int n2=sc.nextInt();
		int p1=a[n1-1]; int p2=a[n2-1]; int m=0;
		Arrays.sort(a); 
		for(int j=0;j<frogs-1;j++)
		{ 
			
		  if(a[j]==p1){
		  if(a[j+1]-a[j]<=distance){ m=a[j+1]; if(m==p2) 
          {System.out.println("Yes");break;}}
		  else{System.out.println("No");break;}
		}

I tried running it on my machine and it runs just fine for any input. gives errors when input is wrong and gives right answers as far as i’ve seen. can some1 point out the mistake in this please or the test cases for which my method fails. it took me about 6 hours to do this , since am new to java . Can some1 help me please… Thanks

Solution -->> CodeChef: Practical coding for everyone

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.

for(i=0;i<sizeB-1;i++)    
   if(B[i+1]-B[i]>k)         
      vec.push_back(B[i]);

Then I used lower_bound to check the position of both the elements (A[x-1],A[y-1]) in the vector vec.

If abs(posx-posy)>=1, the answer will be no else it will be yes.
It worked.
http://www.codechef.com/viewsolution/4191094

3 Likes

i solved it just like dp .but didnt realize it was a dp solution .first dp :stuck_out_tongue:

Please tell me why am I getting SIGSEGV so many times.

I used a 2D vector info with representation as info[i][0]:x-coordinate info[i][1]:index of the frog info[i][2]:con variable i.e. if two frogs have same con then they are connected and can talk.Then I sorted this vector by the x-coordinate(ascending) and then I clustered them according to the condition that two adjacent frogs are in different cluster if their distance is more than K,then I created an array with element at index i being con of ith frog and then checked the input and if they have same con,“yes” else “no”.I am continuously getting SIGSEGV even as the given test case and few other give right answer.I have tried declaring the vector as global variable but that doesn’t help.Please tell me why am I getting SIGSEGV. I would be really thankful.Here’s the link : CodeChef: Practical coding for everyone