FROGV - Editorial

Can anybody tell me why my code is giving WA ? Is my approach correct or not?
Code: 5YUtQY - Online C Compiler & Debugging Tool - Ideone.com

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

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

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 : CodeChef: Practical coding for everyone. Any testcase where this will give a WA would be greatly appreciated. Thanks !

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

Can any expert out there help me with this solution. Its giving WA. I implemented pseudo-code given in Editorial, but not working. : CodeChef: Practical coding for everyone

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

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

@all
can u please provide the test case for which my code gave TLE??
CodeChef: Practical coding for everyone. I checked even the worst case but my code gave correct output within the time limit. Any suggestions for tricky test case ??

It can easily be done by using find and dp algo :stuck_out_tongue: .

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

My code : UwJ1IX - Online C++ Compiler & Debugging Tool - Ideone.com

1 Like

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

3 Likes

@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

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

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

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

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


#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

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

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

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.

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

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.