FROGV - Editorial

editorial
, , , ,
30

@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 =>CodeChef: Practical coding for everyone

31

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

32

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 : CodeChef: Practical coding for everyone

1 Like
33

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

34

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

35 
#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

36

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

37

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

38

Hello People,

I have tried this problem almost 3 times with the logic give by @brobear1995 still get WA. Please help me out. Link to the solution.

39

Can anyone tell me why the algorithm given below gives TLE…?
let all a[i] form the nodes of an undirected graph.
create a c++ set for all unvisited nodes.(initially containing all a[i])
initialize vis[] by all -1
now, call dfs for all nodes having vis[node]==-1
& set vis[node]=caller function to ensure that vis[node] will have same value for all nodes forming a connected component.
In dfs, recur for all nodes currently in unvisited(set) which have abs(a[i]-node)<=k.

Finally, for each query x and y:
if(vis[x]==vis[y])–>yes
else–>no

40

Can someone help me with this code?

I tried many cases myself and I am getting the desired answer.
But on submission it is showing WA.

Please help.

41

I know i solved it with more complexity added but i have used the Segment tree . CodeChef: Practical coding for everyone

42

I did the problem using union find algorithm

11 Likes
43

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

44

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

45

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

46

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

47

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

1 Like
48

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: CodeChef: Practical coding for everyone

49

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