FROGV - Editorial

editorial
, , , ,
21

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

22

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

23

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

24

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

25

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

26

I used the same methodology and got WA. Can someone tell what is wrong and provide test cases for which this method fails ???

1 Like
27

a simple one —

http://www.codechef.com/viewsolution/4193136
28

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

29

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

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

31

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

1 Like
32
  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.

33

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

  1. 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”.
34

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 .

1 Like
35

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.

36

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

37

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

38

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

39

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

40

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