# SIGSEGV for Chefs and Frogs (FROGV)

This is the problem:

My Logic:

1. Accept N, K, P.
2. Accept the all input locations in one array called ‘array’.
3. Store elements from ‘array’ to ‘sorted’ but while doing this, remove the repeating elements. And then sort the array using shell sort.
4. Then traverse the ‘sorted array’ and check 2 consecutive elements, if distance between the two is less than or equal to K, union both the elements using weighted union find algorithm.
5.Then accept each query and check if the two are connected using connected function. And print ‘Yes’ or ‘No’ accordingly.

I’m guessing that this logic is correct. But I’m getting SIGSEGV.

This is my code:

``````#include< stdio.h >
#include< stdlib.h >

long long int *id, *iz;

void shellSort(long long int numbers[], long long int array_size)
{
long long int i, j, increment, temp;

increment = 3;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}

long long int root(long long int i)
{
while(i != id[i])
{
id[i] = id[id[i]];
i = id[i];
}

return i;
}

int connected(long long int p, long long int q)
{
return root(p) == root(q) ? 1 : 0;
}

void unin(long long int p, long long int q)
{
long long int i = root(p);
long long int j = root(q);

if(iz[i] < iz[j])
{
id[i] = j;
iz[j] += iz[i];
}
else
{
id[j] = i;
iz[i] += iz[j];
}
}

int main()
{
short *repeats;
long long int n, p, k, *array, *sorted, i, j, x, y;

scanf("%lld %lld %lld", &n, &k, &p);

array = (long long int*)malloc((n+1)*sizeof(long long int));
sorted = (long long int*)malloc((n+1)*sizeof(long long int));

repeats = (short*)calloc(1000000002, sizeof(short));

j = 0;
for (i = 0; i < n; i++)
{
scanf("%lld", &array[i]);

if (repeats[array[i]] == 0)
{
sorted[j++] = array[i];
repeats[array[i]] = 1;
}
}

shellSort(sorted, j);

id = (long long int*)malloc((sorted[j - 1] + 1) * sizeof(long long int));
iz = (long long int*)malloc((sorted[j - 1] + 1) * sizeof(long long int));

for (i = 0; i <= sorted[j-1]; i++)
{
id[i] = i;
iz[i] = 1;
}

if (j > 1)
{
for (i = 1; i < j; i++)
{
if(sorted[i] - sorted[i-1] <= k)
{
unin(sorted[i-1], sorted[i]);
//printf("%lld and %lld unioned\n", sorted[i-1], sorted[i]);
}
}
}

while(p--)
{
scanf("%lld %lld", &x, &y);

//printf("%lld and %lld\n", root(array[x-1]), root(array[y-1]));
//printf("%lld and %lld\n", id[array[x-1]], id[array[y-1]]);

if (connected(array[x-1], array[y-1]))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}

return 0;
}
``````