A hard problem

usr · 11-18-2003, 08:30 AM

I have to generate a matrix with p (1<=p<=30) lines and n columns (1<=n<=30) filled with 1 and 0 with the condition that any 2 lines need to have in the same positions exactly m numbers of 1 and 0 and there have to be no column filled just with 0 or 1. The answer will be in a file witch contains yes or no on the first line (if this matrix can be generated or not) and if yes on the following lines the matrix.
For example:
file.in
5 5 3
//5 lines, 5 columns and m=3

file.out
yes
1 1 1 0 0
1 0 0 0 0
0 1 0 0 0
1 1 0 0 1
1 1 0 1 0

This is the problem. I analyzed it and I concluded that the matrix can be generated only if n-m can be wrote as 2*2*2*...*2(x times)
But how can I generate this matrix?
It easy with backtracking but my program should work in 2 sec max.
Sorry for my math-english

Thanks!

P_Shep · 11-18-2003, 10:27 AM

Can you write that again, but this time write it so that it makes sence?

RolledOat · 11-18-2003, 11:50 AM

Do you mean to say 'Any two lines that are ANDED together' ? No come to think of it, that doesn't make sense either. I don't understand the 2*2, etc. Is it that n-m must be a factor of 2? I guess I have to agree with P_Shep.

RO

usr · 11-18-2003, 02:38 PM

Initially I didn't understood the problem but after I looked better at the example all began to make sense.

on the example:
if the matrix is

a=1 1 1 0 0
1 0 0 0 0
0 1 0 0 0
1 1 0 0 1
1 1 0 1 0

first line: 1 1 1 0 0
second line :1 0 0 0 0
positions: 1 2 3 4 5
these lines have the same numbers on columns 1(a[1][1]==a[2][1]==1),4(a[1][4]==a[2][4]==0) and 5(a[1][5]==a[2][5]==0) so there are 3 columns(m=3)

first line: 1 1 1 0 0
third line : 0 1 0 0 0
positions: 1 2 3 4 5
these lines have the same numbers on columns 2(a[1][2]==a[3][2]==1),4(a[1][4]==a[3][4]==0) and 5(a[1][5]==a[3][5]==0) so there are 3 columns(m=3)

second line: 1 0 0 0 0
third line : 0 1 0 0 0
positions: 1 2 3 4 5
these lines have the same numbers on columns 3(a[2][3]==a[3][3]==0),4(a[2][4]==a[3][4]==0) and 5(a[2][5]==a[3][5]==0) so there are 3 columns(m=3)
and the process continues with the lines: 1-4,1-5,2-4,3-5,3-4,3-5...
I hope you understood.

And yes n-m must be a factor of 2.

P.S. RolledOat what do you mean with "RO"?

RolledOat · 11-18-2003, 02:44 PM

Quote:

Originally posted by usr
P.S. RolledOat what do you mean with "RO"?

Just short for RolledOat. I was eating cerial when I registered and it seemed as good a userid as any.

R.O.

titanium_geek · 11-19-2003, 07:02 PM

what are you trying to do and with what language?
java will not support multidimensional arrays, (read: matrices) but you should be able to do it like this:
[ [1 0 0]
[0 1 0]
[0 0 1] ]

titanium_geek

usr · 11-20-2003, 12:39 PM

I want to do this probem in C++ or Pascal.

eric.r.turner · 11-21-2003, 01:51 AM

Quote:

Originally posted by titanium_geek
what are you trying to do and with what language?
java will not support multidimensional arrays, (read: matrices) but you should be able to do it like this:
[ [1 0 0]
[0 1 0]
[0 0 1] ]

Java programmers would argue that Java does indeed support multidimensional arrays. A multidimensional array in Java is, as you have indicated, an array of arrays. However, the syntax for using multidimensional arrays works as you would expect. For example:

Code:

int[][] matrix = new int[5][5];
matrix[0][1] = 10;

Here's a toy example that shows how you might write a Matrix class using multidimensional arrays in Java (compile with the -source 1.4 option):

Code:

public class MultiDimArray {

   public static void main( String[] args ) {

      Matrix a;
      Matrix b;

      a = new Matrix( 2 , 3 );
      a.setValue( 0 , 0 , 0 );
      a.setValue( 0 , 1 , 1 );
      a.setValue( 0 , 2 , 2 );
      a.setValue( 1 , 0 , 3 );
      a.setValue( 1 , 1 , 4 );
      a.setValue( 1 , 2 , 5 );

      b = new Matrix( 3 , 2 );
      b.setValue( 0 , 0 , 1 );
      b.setValue( 0 , 1 , 2 );
      b.setValue( 1 , 0 , 3 );
      b.setValue( 1 , 1 , 4 );
      b.setValue( 2 , 0 , 5 );
      b.setValue( 2 , 1 , 6 );

      a.multiply( b ).print();
   }

}


class Matrix {

   private int[][] matrix;

   public Matrix( int numRows , int numColumns ) {
      matrix = new int[numRows][numColumns];
   }

   /**
    * Set the value of a specific matrix position.
    */
   public void setValue( int row , int column , int value ) {
      matrix[row][column] = value;
   }

   public int getValue( int row , int column ) {
      return matrix[row][column];
   }

   public int getNumRows() {
      return matrix.length;
   }

   public int getNumColumns() {
      return matrix[0].length;
   }

   /**
    * Cross multiply two matrices.
    */
   public Matrix multiply( Matrix other ) {

      Matrix result = null;
      int value = 0;

      assert( getNumColumns() == other.getNumRows() );

      result = new Matrix( getNumRows() , other.getNumColumns() );

      for ( int row = 0 ; row < getNumRows() ; row++ ) {
         for ( int column = 0 ; column < other.getNumColumns() ; column++ ) {

            value = 0;

            for ( int i = 0 ; i < getNumColumns() ; i++ ) {
               value += ( getValue( row , i ) * other.getValue( i , column ) );
            }

            result.setValue( row , column , value );
        }
      }

      return result;

   }

   /**
    * Display the matrix contents.
    */
   public void print() {

      System.out.println();

      for ( int row = 0 ; row < getNumRows() ; row++ ) {
         for ( int column = 0 ; column < getNumColumns() ; column++ ) {
            System.out.print( getValue( row , column ) + " " );
         }
         System.out.println("");
         System.out.println("");
      }
   }

}

zaphodiv · 11-22-2003, 06:34 AM

Here are my ideas, might be wrong, it's your homework not mine.

m is less than n

Don't forget corner cases;

Could m be zero? You can make a valid matrix when m=0
for any value of n (alternating lines of 00000 and 11111)

If p==1 then any matrix is valid

What about n==1,p==1,m==1

n-m can be zero
00 p=2 n=2, m=2
11

000 p=3, n=3,m=3
111
000

Consider p==2 n==4 m==2
by the n-m=2^x rule this should be solveable but I can't
find a correct matrix
when p==2 you can only avoid homogeneous columns when m==0
or m==n

>I concluded that the matrix can be generated only if n-m can be wrote as 2*2*2*...*2(x times)

p=10 n=5 m=2
here n-m=3 so why is this matrix wrong?
It seems to follow the rules you gave.

00000
11100
01111
00001
11000
11111
00011
10000
11110
00111

_a really fast matrix generator_

Here is an off-the-wall idea.

30*30*30=27000 possible different combinations of p,n and m
Take only the ones where n-m=2^x and you have 3600 combinations.

If you can calculate a matrix in under 5 minutes then
with two computers running for a week you can calculate
a matrix for every p,n,m value.

Make a program that does
if (p==1 && n==1 && m==1) printf("yes\n1\n")
if (p==2 && n==1 && m==1) printf("yes\n1\n0")
etc

You will have a big source code file and the executable
file will be a few megabytes but it will produce the result really
quickly.

If you have to submit the program on paper...

//quick program to work out how many
//combinations of n and m allow a valid matrix.
//using the n-m=2^x rule
#include <stdio.h>
int p=0,n=0,m=0;
int count=0;

int mcheck(int tn, int tm)
{
int temp=0;
int answer=0;
printf("n=%d m=%d\n",tn,tm);
temp=n-m;
if (m==0) return (0);
switch (temp)
{
case 0: {answer=1; break;};
case 2: {answer=1; break;};
case 4: {answer=1; break;};
case 8: {answer=1; break;};
case 16: {answer=1; break;};
case 32: {answer=1; break;};
case 64: {answer=1; break;};
case 128: {answer=1; break;};
case 256: {answer=1; break;};
case 512: {answer=1; break;};
case 1024: {answer=1; break;};
case 2048: {answer=1; break;};
case 4096: {answer=1; break;};
case 8192: {answer=1; break;};
case 16384: {answer=1; break;};
case 32768: {answer=1; break;};
case 65536: {answer=1; break;};
case 131072: {answer=1; break;};
case 262144: {answer=1; break;};
case 524288: {answer=1; break;};
case 1048576: {answer=1; break;};
case 2097152: {answer=1; break;};
case 4194304: {answer=1; break;};
case 8388608: {answer=1; break;};
case 16777216: {answer=1; break;};
case 33554432: {answer=1; break;};
case 67108864: {answer=1; break;};
case 134217728: {answer=1; break;};
case 268435456: {answer=1; break;};
case 536870912: {answer=1; break;};
case 1073741824: {answer=1; break;};
}

return (answer);
}

int main ()
{
for (p=1;p<30+1;p++){
for (n=1;n<30+1;n++){
for (m=1;m<30+1;m++){
if (mcheck(n,m)) count++;}

}

}
printf("%d", count);
return (0);
}

_Creating the matrix_

My theory, which might be wrong;

You can take a correct matrix and swap the position of two
of the columns and it is still correct.
Also you can invert every bit in a column and the matrix stays valid.

Therefore I think that if a valid matrix is possible at all, it
is possible to make one starting with a line of zero's

I suggest the method
first line is 00000....
to create the second line invert the first n-m bits
eg if n==5 m==3 line two is
11000
make the next line by inverting n-m bits starting at the bit after
the last one you inverted to make the previous line, wrap back to
the start of the line whn necessary

for example p==12 n==5 m==3

00000
11000
11110
01111
00011
00000 pattern repeats from here
11000
11110
01111
00011
00000
11000

p=12 n==5 m==4
00000
10000
11000
11100
11110
11111
01111
00111
00011
00001
00000
10000 etc

If you havn't inverted every column at least once before
printing the last line then it's not possible to make a valid matrix.

zaphodiv · 11-25-2003, 10:15 AM

Ping USR, what do you think of my ideas?

usr · 11-25-2003, 02:13 PM

Excuse me for my late reply.
Your idea is partially good but let take a look at the 2,3 and 4 line:
10000
11000
11100
between 1 and 2 there are four matches on 1,3,4 and 5 position
but between 1 and 4 there are just three matches on 1,4 and 5 position
(4!=3 => wrong)
and there shouldn't be a line filled only with 0 or 1 like your first line (00000)