KURUK14

GENIE SEQUENCE

Link to the question : KURUK14 

HINT :

It is said that a genie sequence is a sequence of numbers which can be arranged in such a way that they either tell the number of elements behind or number of elements in front of them. In order for a n elements sequence to follow the rule, if it contains c then it should also contain n-c or c, because if at the (c+1)th position we say there are c elements behind it, then at (n-c + 1)th we can say there are n-c elements behind it or c elements in front of it. So either 2 c's or 2 (n-c)'s  or 1 c and 1 (n-c) must be present. So in the case of 2 c's or 2 (n-c)'s we make them 1 c and 1 (n-c) then we will get all numbers from 0 to n-1 in the genie sequence. So we just need to check all 0 to n-1 numbers are present or not after converting repeating numbers to n-x form. 

SOURCE CODE :

/* Genie Sequence - (KURUK 14) */
/* Sushant Gupta */

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,i,f=0,c;
        scanf("%d",&n);
        int a[n];
        for(i=0;i<n;i++)
            a[i]= 0;
        for(i=0;i<n;i++)
        {
             scanf("%d",&c);
             if(c<n)
             {
                 if(a[c]==0)
                    a[c]=1;
                 else
                    a[n-1-c]=1;
             }

        }
        for(i=0;i<n;i++)
        {
            if(a[i]==0)
                f=1;
        }
        if(f==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}