SPOJ : KURUK 14 (Genie Sequence)

Hints: Consider the fact that for a sequence to be a genie sequence all the possible positions must be satisfied

Solution:
consider 6 elements 5 4 3 2 1 0
This forms a genie sequence as all the possible positions are covered respectively
But the position can be from either sides i.e the first number can be 5 or 0
                                                                       second number can be 4 or 1
                                                                       third number can be 3 or 2
and so on...
notice that sum of this combination ie always n - 1 here it is 6 - 1 = 5
(5+0) , (4+1),(3+2)... = 5

->  Thus create an array and input elements,intialise the array to 0
for each element mark in the arrray as 1 if it is already marked 1 , then mark the pair of that element..
for example if 5 is entered mark array[5] = 1 , but if 5 is entered again mark array[ n - 1 - 5] = 1

->after this process again iterate through the array, if u encounter an element with value 0 that means this cant form a genie sequence..


C code:
#include <stdio.h>
#include <stdlib.h>

int main(void) {
int t,n,temp,i,j,flag;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int *a;
flag = 0;
a = calloc(n+1,sizeof(int));
for ( i = 0 ; i < n ; i++)
{
scanf("%d",&temp);
if(temp < n)
{
if(a[temp] == 0)
a[temp] = 1;
else
a[n -1 - temp] = 1;

}
}

for( i = 0 ; i<n;i++)
{

if(a[i] == 0)
{
flag  = 1;
break;
}
}
if(flag == 1)
printf("NO\n");
else
printf("YES\n");
}

return 0;

}