CareerCup

Hi frnds,

I was wondering first of all how this (n*n) + n possible ways.
After few trails I could get it and hence want to share.

Please correct if anything wrong:

Given n * n numbers, say for example n=3, means given numbers are
1 2 3 4 5 6 7 8 9.

1) make it into n blocks
( 1 2 3) (4 5 6) ( 7 8 9)

2) for every one element from 1st set, select another number from second set
this fills up two positions - possible n*n ways
third position is a sort of determined
something like - ( 1 4) ( 1 5) (1 6)
no option for placing third element, have to place it directly
1 4 7 is selected, we cannot say 1 4 8 now which is invalid

hence, n * n subsets formed

2) repeat the same with second element from first set, but this time the third set rotated once
so it will be ( 1 2 3) ( 4 5 6) (9 7 8)

follow similar procedure.....

at the end, each block themselves are a subset that is n subsets again

so all togethere (n * n) + n sets

Please correct guys, if my understanding is wrong.

Thanks

Here is another observation that I got

Consider the n*n as a matrix

1 2 3
4 5 6
7 8 9

The possible solutions are ;
a) All rows iterated
b) All columns iterated
c) Both diagonals iterated
d) Spiral or '7' shaped elements from all 4 corners
ie
1,6,8
3,4,8
9,4,2 (which is 2,4,9)
7,6,2 (which is 2,6,7)

In case of n=4, the similar structure will reveal all the elements.
The sort of '7' shaped path will have 4 elements


Please correct me if this is wrong.

Question mentions "each subset has one and only one matching number from any other subset", but in the example subsets 1 and 11 don't have any matching number.

#include<stdio.h>

int n;

int main()
{
    int i, j, shift, a, b;

    printf("\nn=");
    scanf("%d",&n);

    for(i=1;i<=n*n;)
    {
        j=0;
        printf("\n");
        while(j<n)
        {
            j++;
            printf("%3d",i);
            i++;
        }
    }

    for(shift=0; shift<n; shift++)
    {
        for(i=1;i<=n;i++)
        {
            printf("\n%3d",i);
            a=i;
            for(j=1;j<n;j++)
            {
                a=a+n+shift;
                if(a>(n+n*j))
                {
                    b=a%n;
                    a=j*n+b;
                }
                printf("%3d",a);
            }
        }
    }
    return 0;
}

can anyone please explain the algo?

Please help me understand the question : if it is max. subsets (n*n+n)
why can't we just take one element of 1 to n^2 common for all ...then we have to fill n^2-1 elements in the subsets of size n where 1 element we have already places => n-1 elements ... (n^2-1)/(n-1)=(n+1) subsets that is less than (n*n+n) subsets..
e.g.
1,2,3,4,5,6,7,8,9

1,2,3
1,4,5
1,6,7
1,8,9

int permutationTest(int n){
	int i, j, k;
	printf("n=%d\n", n); 
	
	for(i=1; i<=n*n;) {
		printf("\n");
		for (int j=1; j<=n; j++) {
			printf("%3d",i++);
		}
	}
	for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			printf("\n%3d%3d", i+1, n+j+1);
			for (k=2; k<n; k++) {
				int s = (i*(k-1)+j)%n + 1;
				printf("%3d", k*n+s);
			}
		}
	}
	return 0;
}

The first n sets would be 1..n,n+1..2n,2n+1..3n,...,..n*n
2. Set n+1 = {1 ,1+n,1+2n...,1+(n-1)(n)}
3. Set n+2 = {1 , 1+(n+1),1+(2n+1)...,1+( (n-1)n+1 )}
4. Set n+3 = {1 , 1 + (n+2), 1+ (2n+2) ........................}
...

@Anonymous
1,4,7 and 2,5,8 are completely disjoint so won't work

based on the question, if i can write the arrayas
1 2 3 1 2
4 5 6 4 5
7 8 9 7 8
then any parallel lines formed by three elements break the requirement of having exactly one match as they will have none.
so the only possible solution for this is
n+1 such combinations
1 2 3
1 4 7
1 5 9
3 5 7
any other combination will break the rule of having exactly one match with "any other set"

Can someone please explain how number of sub-sets is n(n+1) ??

Is the solution provided in the question correct? I do see few subsets which don't have anything in common.
sub-set 1 and sub-set 12,
sub-set 1 and sub-set 11
sub-set 3 and sub-set 10
sub-set 4 and sub-set 6.
sub-set 2 and sub-set 5.
sub-set 7 and sub-set 10.
sub-set 11 and sub-set 12.

What I noticed is that for every sub-set listed has one sub-set not matching anything in this list.

This sub-set from 1-12 seems to be arranging of elements into n*n matrix.

sub-set 1 = 1,2,3
sub-set 2 = 1, 4, 7
sub-set 3 = 1, 5, 9
sub-set 4 = 1, 6, 8
sub-set 5 = 2, 5, 8
sub-set 6 = 2, 4, 9
sub-set 7 = 2, 6, 7
sub-set 8 = 3, 6, 9
sub-set 9 = 3, 5, 7
sub-set 10 = 3. 4, 8
sub-set 11 = 4, 5, 6
sub-set 12 = 7, 8, 9

Someone please explain the question , why it is that in the question it is mentioned that there is exactly one and only one element matching with any other subset AND in the answer no element is shared between (1,2,3) and (7,8,9) .....

Matrix approach is good.
Here is the formula that I derived by hit and trial...
for n = 1, there are two such sets, (1), (1).
for n = 2, there are 2*2+f(1) = 6...
e.g. for
12
34
12, 34,13,24 + (1) paired with disjoint sets of minor matrix of 1, (2) paired with disjoint sets of minor matrix of (2)..

*Minor matrix of (aij) = matrix formed by deleting rows and columns corresponding to aij..

Similarly, for n=3
e.g.
123
456
789

there are 2*n rows and column sets.. for others, we do recursively..
(1) paired with disjoint sets of minor matrix {(5,6), (8,9))..
(2) paired with disjoint sets of minor matrix {(4,6),(7,9)}
(3) paired with disjoint sets of minor matrix {(4,5),(7,8)}

So, all inner loops of recursive calls have to return disjoint sets.. only outer multiplication will allow for for 1 duplicate.... when pairing with outer elements
Another key thing while returning disjoint sets.. no two elements should not be on same row or column, otherwise it will intersect with row/column zones...

So, recurrence relation becomes
F(n) = 2*n + n*(n-1)
= 2n + n^2 - n = n^2 + n.

So, when taking cross product of outer elements with returned subsets of sub problem..
only consider non-trivial solutions (non rows/columns), which form disjoint sets and no two points are on same row/column.
Choosing minor matrix for inner solution ensures that when taking product, no inner subset would lie on same row/column..

Here's my solution, using matrix...

#include <iostream>
#define N 100
using namespace std;

int temp[N][N];

int main() {
    int n = 3;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            temp[i][j] = i + 1 + j * n;
        }
    }
    int count = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout << temp[i][j] << " ";
        }
        cout << endl;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout << temp[j][i] << " ";
        }
        cout << endl;
    }
    for(int i = 0; i < n; i++) {
        cout << temp[i][i] << " ";
    }
    cout << endl;
    for(int i = 0; i < n; i++) {
        cout << temp[i][n-1-i] << " ";
    }
    cout << endl;
    return 0;
}

In the question itself, the subsets are wrong. Check subset 3 {1, 5, 9} and subset 7 {2, 6, 7} donot have an element in common..