SIGSEGV for Chefs and Frogs (FROGV)

general
,
1

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

Please Help! Thank you!

2

The calloc(2Gb) fails on my humble test box… since you don’t test for NULL return value, the code happily continues on to access invalid memory.

might also be worth rethinking the need to allocate 2G

1 Like