You are not logged in. Please login at www.codechef.com to post your questions!

×

FROGV - Editorial

5
1

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

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

This question is marked "community wiki".

asked 14 Jul '14, 15:01

devuy11's gravatar image

4★devuy11 ♦♦
46273842
accept rate: 0%

edited 14 Jul '14, 15:17

admin's gravatar image

0★admin ♦♦
16.9k347485513

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

(14 Jul '14, 15:16) dev85462★
11

I did the problem using union find algorithm

(14 Jul '14, 15:16) dpraveen ♦♦4★

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

(14 Jul '14, 18:17) prem_933★

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

(14 Jul '14, 18:44) devuy11 ♦♦4★

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

(14 Jul '14, 19:30) prem_933★

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

(14 Jul '14, 19:42) devuy11 ♦♦4★

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

(14 Jul '14, 19:57) prem_933★

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

(14 Jul '14, 20:13) devuy11 ♦♦4★

my algorithm is as follows:

1) 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.

(14 Jul '14, 20:36) prem_933★

Please explain in a more readable manner. The English is sort of broken and I cannot understand the solution properly :(

(14 Jul '14, 22:16) nisargshah953★

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.

(15 Jul '14, 11:19) prem_933★

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 (5-1>k) and(8-6>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".

(15 Jul '14, 11:24) prem_933★

Hi, how do you prove by contradiction that both frogs can only communicate if they can reach the same maximal distance?

(18 Jul '14, 02:55) kuruma2★

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

(18 Jul '14, 03:56) shivam2174★

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

(18 Jul '14, 10:08) prem_933★

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

(18 Jul '14, 10:14) prem_933★

@ShangJingbo and @GeraldAgapov can u please provide the test case for which my code gave TLE?? http://www.codechef.com/viewsolution/4327814

(30 Jul '14, 15:31) krobin_932★

max distance= position of frog + k

(10 Jan '15, 16:05) nil963★
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

link

answered 14 Jul '14, 16:56

brobear1995's gravatar image

2★brobear1995
1561511
accept rate: 0%

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

link

answered 14 Jul '14, 17:10

akumar3's gravatar image

3★akumar3
1416
accept rate: 0%

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 <iostream>
#include <algorithm>
#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;
}
link

answered 14 Jul '14, 20:29

complexgene's gravatar image

2★complexgene
164
accept rate: 0%

edited 15 Jul '14, 08:03

garakchy's gravatar image

1★garakchy
1.1k163048

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) mrigank1★

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) gkcs4★

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

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

Thanks rajesh

link

answered 14 Jul '14, 16:44

rajeshtiwari's gravatar image

2★rajeshtiwari
162
accept rate: 0%

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

link

answered 14 Jul '14, 17:31

himanshu_9419's gravatar image

3★himanshu_9419
111118
accept rate: 18%

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

link

answered 14 Jul '14, 17:33

raghu_nsit's gravatar image

2★raghu_nsit
1
accept rate: 0%

I solved it using segment tree .

link

answered 14 Jul '14, 17:55

anuj95's gravatar image

4★anuj95
2882614
accept rate: 12%

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

link

answered 14 Jul '14, 21:21

tanaymathur4's gravatar image

2★tanaymathur4
11
accept rate: 0%

1

You are assuming that a[q-1] < a[m-1] 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) anuj954★

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

link

answered 14 Jul '14, 21:47

saurabh73's gravatar image

3★saurabh73
11
accept rate: 0%

how did you store the graph?? Using adjacency matrix or List?

(17 Jul '14, 00:33) saroj3★

I used Adjacency list to store the graph

(10 Aug '14, 14:54) saurabh733★

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

link

answered 14 Jul '14, 22:09

v_nishanth's gravatar image

2★v_nishanth
11
accept rate: 0%

edited 14 Jul '14, 22:11

link

answered 15 Jul '14, 02:04

razkverma's gravatar image

2★razkverma
1
accept rate: 0%

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

link

answered 15 Jul '14, 02:58

ratiko's gravatar image

2★ratiko
1
accept rate: 0%

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;}
        }
link

answered 15 Jul '14, 04:52

rach8's gravatar image

2★rach8
13
accept rate: 0%

edited 15 Jul '14, 04:56

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

link

answered 15 Jul '14, 05:47

nemesis10549's gravatar image

0★nemesis10549
1
accept rate: 0%

Please put correct check on constraints. if(a[0]>=1 && a[0]<=100000) And further, you don't need to check the constraints.

(16 Jul '14, 16:09) AnkitAti1★

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

link

answered 15 Jul '14, 11:03

rtheman's gravatar image

5★rtheman
593
accept rate: 0%

edited 15 Jul '14, 11:13

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

link

answered 15 Jul '14, 17:06

minato_namikaz's gravatar image

1★minato_namikaz
5052311
accept rate: 10%

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

link

answered 15 Jul '14, 18:16

armaanjk's gravatar image

2★armaanjk
1
accept rate: 0%

Can anybody tell me why my code is giving WA ? Is my approach correct or not? Code: http://ideone.com/5YUtQY

link

answered 18 Jul '14, 20:38

depp1993's gravatar image

2★depp1993
11
accept rate: 0%

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

plz help me out . whats d problem in this solution ?

link

answered 19 Jul '14, 01:30

testcaser's gravatar image

2★testcaser
1
accept rate: 0%

Hi all,

My solution is O(N*P) and will most likely get a TLE. But right now I am not able to figure out why it is giving a WA. The approach that I follow is :

  1. I Sort the array, keeping track of the indices.
  2. For query indices i1 and i2, I look for their appropriate positions in the sorted array.
  3. Starting from x-position of frog at index i1 I move till I reach the x-position of frog at index i2, for each adjacent pair of frogs between frogs at index i1 and i2 I check if pos[i+1]-pos[i]<=k.
  4. If I am able to reach the position of the frog at index i2 , I report Yes otherwise No.

Here's my code : http://www.codechef.com/viewsolution/4367483. Any testcase where this will give a WA would be greatly appreciated. Thanks !

link

answered 23 Jul '14, 00:22

adirastogi's gravatar image

1★adirastogi
1
accept rate: 0%

Please help me http://www.codechef.com/viewsolution/4289736 I got WA for the above solution. Don't know where I am wrong.

link

answered 27 Jul '14, 18:01

shivanshu946's gravatar image

2★shivanshu946
1
accept rate: 0%

Can any expert out there help me with this solution. Its giving WA. I implemented pseudo-code given in Editorial, but not working. : http://www.codechef.com/viewsolution/4405490

link

answered 30 Jul '14, 20:31

vickywiz's gravatar image

2★vickywiz
914
accept rate: 0%

I am still getting wrong answer ..pls tell me where my code goes wrong...

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

link

answered 09 Aug '14, 00:37

amar555's gravatar image

3★amar555
1
accept rate: 0%

@all can u please provide the test case for which my code gave TLE?? http://www.codechef.com/viewsolution/4327814. I checked even the worst case but my code gave correct output within the time limit. Any suggestions for tricky test case ??

link

answered 18 Aug '14, 00:07

krobin_93's gravatar image

2★krobin_93
24126
accept rate: 0%

edited 20 Aug '14, 23:19

It can easily be done by using find and dp algo :p . 1) Just sort according to position (dont forgot to keep index). 2) iterate 1 to n and if distance is <= k then put index of second to index of first. 3) not whenever query is asked find parent ie fint which set they belong , if same -> Yes else No. :)

My code : http://ideone.com/UwJ1IX

link

answered 27 Jun '15, 15:57

mladia163's gravatar image

4★mladia163
1
accept rate: 0%

I solved using disjoint set data structure https://www.codechef.com/viewsolution/9496601

link

answered 27 Feb '16, 18:45

maverick_10's gravatar image

3★maverick_10
1
accept rate: 0%

@devyug11 or any other expert,

problem => passed the test case, now unable to identify where the problem is

my approach => made 2 vectors, one storing the original input and other storing the input after sorting, then ,then iterated from starting frog to target frog in the sorted vector and kept checking that the consecutive distance is less then k

my solution =>https://www.codechef.com/viewsolution/10092569

link

answered 16 May '16, 17:39

aggharshit's gravatar image

0★aggharshit
1
accept rate: 0%

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

(16 May '16, 20:25) aggharshit0★

i think it can also be solved using dfs/bfs;

link

answered 24 Jan, 08:08

akshay29's gravatar image

2★akshay29
894
accept rate: 0%

For those who are solving treating frogs as nodes and are imagining an edge between two graphs , if they can communicate ; you need not use matrix or list to store the graph. You can find the different components as follows :

  1. Sort the frogs according to their position on x axis and maintain the indices. Then, just use the following thing. :

compo=1;

component[a[0].ind]=1;

for(i=1;i<n;i++)
{
    if(a[i].val-a[i-1].val<=k)
    component[a[i].ind]=compo;
    else
    component[a[i].ind]=++compo;
}

2 frogs can communicate iff they are part of same component.

Link to the complete solution : https://www.codechef.com/viewsolution/12633965

link

answered 24 Jan, 16:56

pankajkhan's gravatar image

5★pankajkhan
9419
accept rate: 14%

edited 24 Jan, 16:57

Can't we use DSU to solve this by sorting it.

link

answered 17 Feb, 01:27

diii's gravatar image

4★diii
1
accept rate: 0%

it can be solved with union-find method too and it's implementation is very easy..

link

answered 05 Apr, 14:46

amandal799's gravatar image

5★amandal799
11
accept rate: 0%


#include<stdio.h>
 void sort(int b[], int n)
{
   int i,j;
   int temp;
    for(i=1;i<=n-1;i++)
   {
       for(j=1;j<=n-i-1;j++)
       {
           if(b[j]>b[j+1])
           {
               temp = b[j]; 
               b[j] = b[j+1];
               b[j+1] = temp;
           }
   }
}}
int main()
{
    int n,k,p,a[100005],i,frog[2],c1=0,c2=0;
    int n1,n2,b[100005],diff1=0,diff2=0;
    scanf("%d%d%d",&n,&k,&p);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
      for(i=1;i<=n;i++)
    {
        b[i] = a[i];
    }
     sort(b,n+1);
      while(p--)
       {
           scanf("%d%d",&n1,&n2);
           if(1<=n1<=n && 1<=n2<=n)
          {
            frog[0] = a[n1];
           frog[1] = a[n2];
           c1 = 1;
           for(i=1;i<=n;i++)
           {
               if(b[i]!=frog[0])
               c1++;
               else break;
           }
           c1 =c1;
           c2 = 1;
           for(i=1;i<=n;i++)
           {
               if(b[i]!=frog[1])
               c2++;
               else break;
           }
           c2 = c2;
           diff1 = c2 - c1;
           diff2 = 0;
           for(i=c1;i<c2;i++)
           {
              if(b[i+1]-b[i]<=k)
                diff2++;
              else break;
           }
           if(diff1==diff2)
            printf("Yes\n");
           else
            printf("No\n");
       }
       }
     }
what is wrong in this code

`` codeblocks giving right answer every test case is satisfied

link

answered 10 Apr, 18:19

albert_012's gravatar image

2★albert_012
11
accept rate: 0%

It's simple just calculate the distance between every from...and if it is more than the value of k than the message can not be transferred

link

answered 10 Apr, 23:03

divyanshu_shuk's gravatar image

2★divyanshu_shuk
411
accept rate: 0%

It can also be done with the help of DSU data structure.

link

answered 21 Oct, 22:06

kk_pheonix's gravatar image

4★kk_pheonix
1
accept rate: 0%

-2

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;
}
link

answered 14 Jul '14, 15:23

karankapoor's gravatar image

2★karankapoor
-112
accept rate: 0%

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

(14 Jul '14, 15:41) aforapple1★

sir!! please tell me where my code goes wrong!! http://www.codechef.com/viewsolution/4330694 passing even the teastcase u have given 6 3 2 0 3 8 14 12 5 1 1 2 2

(14 Jul '14, 22:16) v_nishanth2★
-2

#include <iostream>

include <algorithm>

include <cstdlib>

include <cmath>

include<cstdio>

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

link

answered 14 Jul '14, 16:28

sandeep9's gravatar image

3★sandeep9
4782627
accept rate: 4%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,984
×1,291
×795
×22
×22

question asked: 14 Jul '14, 15:01

question was seen: 11,401 times

last updated: 21 Oct, 22:06