N numbers into 2N places

Question:

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly n number of cells between two placed locations of number n.

Sample:

One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

Solution:

We will try backtracking approach,  we move from index 0 to 2N-1, at each index, we try to place a number that hasn’t been used, and then move to next index and repeat the process, if in between we find there is no number possible at some index, that means we were incorrect, and we need to backtrack. If we reach to last index, and place a number safely there, that means its possible to have such arrangement.

#include<iostream>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cstring>
using namespace std;

#define FOR(i,a,b)      for(__typeof(b) i=(a);i<(b);++i)
#define REP(i,n)        for(__typeof(n) i=0;i<(n);i++)
#define FILL(a,b)       memset(a,b,sizeof(a))

#define SIZE 100
int N,len;
int arr[SIZE];
bool numbers[SIZE];

bool permute(int pos){
    /*if pos>=len , that means we have placed all the numbers
    from 1 to N , so we can print the array, and return
    */
    if(pos>=len){
        //nothing fancy, just printing the array
        printf("POSSIBLE for N = %d ----> ",N);
        REP(i,len){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        return true;
    }
    //if that position is already filled, that means move on 😛
    if(arr[pos]!=0){
        return permute(pos+1);
    }

    //go through all numbers
    FOR(i,1,N+1){
        //if number is not used
        if(!numbers[i]){
            //if second place is in bound
            if(pos+i+1<len&&!arr[pos]&&!arr[pos+i+1]){
                arr[pos]=i;//place the number i at index pos
                arr[pos+i+1]=i;//place the number i at index pos+i+1
                numbers[i]=true;//number i used now
                //check if this will lead us to end
                if(permute(pos+1)){
                    return true;
                }
                //BACKTRACK
                arr[pos]=0;//free the index pos
                arr[pos+i+1]=0;//free the index pos+i+1
                numbers[i]=false;//number not used now
            }
        }
    }
    return false;
}

void doThis(){
    //N number
    scanf("%d",&N);
    // 2N places
    len = 2*N;
    //initialise array with 0
    FILL(arr,0);
    FILL(numbers,false);//all numbers are free to be used

    //here we go
    if(permute(0)){
        //if possible then no need to do anything 🙂
    }else{
        printf("NOT POSSIBLE for N = %d\n",N);
    }
}

int main(){
#ifdef amy
freopen("C:\\A\\in.txt","r",stdin);freopen("C:\\A\\out.txt","w",stdout);
#endif
int t;
scanf("%d",&t);//number of test cases
while(t--){doThis();}
#ifdef amy
fprintf(stdout,"\nTIME: %.3lf sec\n",(double)clock()/(CLOCKS_PER_SEC));
#endif
return 0;
}

/*
INPUT

12
1
2
3
4
5
6
7
8
9
10
11
12

OUTPUT

NOT POSSIBLE for N = 1
NOT POSSIBLE for N = 2
POSSIBLE for N = 3 ----> 2 3 1 2 1 3
POSSIBLE for N = 4 ----> 2 3 4 2 1 3 1 4
NOT POSSIBLE for N = 5
NOT POSSIBLE for N = 6
POSSIBLE for N = 7 ----> 1 4 1 5 6 7 4 2 3 5 2 6 3 7
POSSIBLE for N = 8 ----> 1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8
NOT POSSIBLE for N = 9
NOT POSSIBLE for N = 10
POSSIBLE for N = 11 ----> 1 2 1 4 2 8 9 10 4 11 6 3 7 5 8 3 9 6 10 5 7 11
POSSIBLE for N = 12 ----> 1 2 1 3 2 8 9 3 10 11 12 5 7 4 8 6 9 5 4 10 7 11 6 12

TIME: 0.069 sec
*/
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s