FROGV - Editorial

editorial
, , , ,
41

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

42

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

43

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

44

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

45

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

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

46

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 !

47

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

48

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

49

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

50

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

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

51

I used Adjacency list to store the graph

52

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

53

max distance= position of frog + k

54

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 : http://ideone.com/UwJ1IX

55

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

56

@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

57

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

58

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

59

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

60

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