FROGV Editorial - Pseudocode

editorial
, ,
1

I’m trying to understand the approach of the editorial, but a little confused and would appreciate more explanation for this pseudocode. Editorial: http://discuss.codechef.com/questions/47239/frogv-editorial

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"
  1. What is the meaning of A+N in the sort() params?
  2. Max_Distance[A[0].ind]=A[0].v+k …does this mean the index of whatever frog is on the first position in the ordered plot? What is “v”?
  3. Still don’t understand how maximum distance is constantly being updated in the loop:
    “if((A[i-1].x-A[i].x)<=K)” refers to frog at i’th position in ordered plot’s current maximum distance?

Still struggle with reading other peoples’ code too so it’s hard for me to understand what other people are doing when they don’t comment it well. Would really appreciate further explanation of this solution. (I use Java)

Thanks!

2

Let me answer them one by one.

1.What is the meaning of A+N in the sort() params?

As you are a JAVA user you may not be familiar with this code.
In java their is a function java.util.Arrays.sort(int[]) which sorts the integer array. You dont have to worry about the size of the array…
But in C++ , their is a function sort() which take two arguments first element and the last element.

A is A[0] i.e. the First Element

A+N is A[N] i.e. the Last Element

So it simply means sort the array from A[0] to A[N]. Default sorting is in ascending order unless specified.

2.Max_Distance[A[0].ind]=A[0].v+k …does this mean the index of whatever frog is on the first position in the ordered plot? What is “v”?

A[0].ind is the index of the frog before sorting which is at the first position after sorting. We have to keep it because all the queries we will be provided with indices referrin the original array.

A[0].v is the value of the frog. A[i].x is misprinted it should be A[i].v.

3.Still don’t understand how maximum distance is constantly being updated in the loop: “if((A[i-1].x-A[i].x)<=K)” refers to frog at i’th position in ordered plot’s current maximum distance?

For this sample case

5 3 3

0 3 8 5 12

1 2

1 3

2 5

values -> 0 3 8 5 12

indices-> 1 2 3 4 5

After sorting

values -> 0 3 5 8 12

indices-> 1 2 4 3 5

A[0].ind=1

A[0].v=0

first we set Maxdist[1] = A[0].v+k = 0+3 = 3

A[1].ind=2 and A[1].v=3, As A[1].v-A[0].v=3 (because k is 3 and equation is thus satisfied)

Maxdist[2] = Max_dist[1] = 3

Similarly, Maxdist[4] = Max_dist[2] = 3 and

Max_dist[3] = Max_dist[4] = 3

A[3].v = 8 and A[4].v = 12
their difference is clearly greater than k… So Max_dist[5] = A[4].v+k = 15

Now run the queries and check the answer. Hope you got it. :slight_smile:

2 Likes
3

Thanks! That’s clearer - but how do I store the index of A[i] once the array is sorted? All I can think of is copying the array and sorting one, then using binary search to find a match. But I’m sure there’s a more efficient way.

4

Take an array A[size][2].
Store the value at first position i.e. A[i][0] and index at A[i][1].
Initially A[i][1]=i, then sort this 2d array on the basis of A[i][0] using a comparator.
See this -
http://www.mkyong.com/java/java-object-sorting-example-comparable-and-comparator/

Also refer the original documentation of how to use sort function.