FROGV - Editorial

devuy11 · July 14, 2014, 3:01pm

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 .

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

dev8546 · July 14, 2014, 3:16pm

I know i solved it with more complexity added but i have used the Segment tree . http://www.codechef.com/viewsolution/4217571

dpraveen · July 14, 2014, 3:16pm

I did the problem using union find algorithm

karankapoor · July 14, 2014, 3:23pm

sir i used the following logic which was giving me correct answer on ideone but i got 94 WA here…
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;
}

aforapple · July 14, 2014, 3:41pm

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.

sandeep9 · July 14, 2014, 4:28pm

#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 http://www.codechef.com/viewsolution/4327427

rajeshtiwari · July 14, 2014, 4:44pm

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

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

Thanks
rajesh

brobear1995 · July 14, 2014, 4:56pm

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

akumar3 · July 14, 2014, 5:10pm

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…

himanshu_9419 · July 14, 2014, 5:31pm

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

raghu_nsit · July 14, 2014, 5:33pm

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

anuj95 · July 14, 2014, 5:55pm

I solved it using segment tree .

prem_93 · July 14, 2014, 6:17pm

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??

devuy11 · July 14, 2014, 6:44pm

@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 · July 14, 2014, 7:30pm

@devuy11 …can u plz take the pain of explaining how max distance is calculated??

devuy11 · July 14, 2014, 7:42pm

@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.

prem_93 · July 14, 2014, 7:57pm

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

devuy11 · July 14, 2014, 8:13pm

@prem_93 : right . Your code seems to be tough one for me to understand .

complexgene · July 14, 2014, 8:29pm

Methodology Used:

Keep the input array
Create a duplicate array of it.
Sort the duplicate array.
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.
Iterate through the starting index to the last index and check for <=K while iterating (a[i+1]-a[i]<=K).
If reaches to the end, output Yes else No.
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;
}

prem_93 · July 14, 2014, 8:36pm

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.