1 / 5
Jul 2011

A C++ code is given here.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
bool mark[20];
vector<int> v[20];
int count=0,n;
void solve(int row)
{
        if(row==n)count++;
        else
    for(int i=0;i<v[row].size();i++)
    {
            if(!mark[v[row][i]])
            {
                    mark[v[row][i]]=true;
                    solve(row+1);
                    mark[v[row][i]]=false;
            }
    }
}
int main()
{
        int x, t;cin>>n;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
                cin>>x;
                if(x)v[i].push_back(j);
        }
        memset(mark,false,sizeof(mark));
    solve(0);

    cout<<count<<endl;
}

I want to write the corresponding C++ code into C. Here's the equivalent code in C but it is in infinite loop. I can't figure out where it's wrong.
[code]

include

include

define INF 100

int count =0, numvertex;
int color[20];

int matrix[20][21];

void solve (int cur_row)
{
if( cur_row == numvertex)count++;
else{int k;
for(k=0;matrix[cur_row][k] != INF;k++){
if( !color[matrix[cur_row][k]] ){
color[matrix[cur_row][k]]=1;
solve(cur_row+1);
color[matrix[cur_row][k]]=0;
}
}
}}

int main()
{
int t;
for(scanf("%d",&t);t--wink
{
int I, J, temp;
memset (matrix, 0, sizeof matrix); count=0;
memset (color, 0, sizeof color);
scanf("%d",&numvertex);
for(I=0;I int ind=0;
for(J=0;J scanf("%d",&temp);
if(temp)matrix[I][ind++]=J;
}
matrix[I][ind]=INF;
}

solve(0);
printf("%d\n",count);
	}
return 0;
}[/code]

Several n by n boolean matrices are in input. ( n <= 20)

  • created

    Jul '11
  • last reply

    Jul '11
  • 4

    replies

  • 312

    views

  • 2

    users

  • 1

    link

What test case has it in an infinite loop? What problem are you trying to solve?

Problem Statement:

We are given n by n boolean matrix ( n <= 20). Output of matrix should
be such that every row and every column should have only one true
value ( true=1, false=0). Input matrix can have any number of 1's and
there will be no row or column having all zero values. Example: let
n=4
Input Matrix:
1 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
Final Matrix could have many correct answers. One of them is:
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
We've to find out the number of ways to get the desiered output.

The problem is somehow solved on its own. I don't believe much in magic but the same code I posted above in C wasn't working fine at that time. I've no idea why it's OK now although I hadn't change anything in it. astonished

Well, Acutally the real problem statement is:
https://www.spoj.pl/problems/ASSIGN/
This approach is giving TLE and it must be as of big-O(20!). How could I do faster?

I haven't solved this problem, but I can get to an O(n^2*2^n) but I don't know if that would be fast enough.

For n = 20 your proposed algo is of big-O(10^9). Time limit is of 20 seconds. It might pass. Well whatever it is, it's faster than mine which is of factorial complexity. Can you suggest some way how you could get this limit?

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 13 5d

Want to read more? Browse other topics in C and C++ or view latest topics.