A difficult problem which no one haven't solve

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

A difficult problem which no one haven't solve

Post by nghiank » Wed Nov 27, 2002 6:24 am

test
Last edited by nghiank on Sun Apr 22, 2007 3:38 pm, edited 1 time in total.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sun Jan 05, 2003 11:27 pm

I recently analyzed a similar problem: How many boolean NxN matrices are there that don't contain the same value three times in a row (horizontally or vertically)?

Examples for n=4:

0010
0010
1101
0010
(good)

0001
0010
1101
0010
(bad because of the three 0's in the first row)


So far I've only attacked it with naive brute force (generate all matrices recursively and count). These are the results for the first few values of N:

2
16
102
2030
60232
3858082

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Post by SnapDragon » Fri Jan 24, 2003 11:36 pm

I tried a short DP algorithm (looking at the matrix as a string of length n^2, only the last 2n choices are relevant to any remaining choices.) Made it up to 11 before running out of memory. I'm not sure how you'd improve this. (I used doubles instead of BigInts, so the last answer's inexact :))

size=1: 2
size=2: 16
size=3: 102
size=4: 2030
size=5: 60232
size=6: 3858082
size=7: 446672706
size=8: 101578277384
size=9: 43680343039806
size=10: 36133311325799776
size=11: 57061338836892852xxx

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Post by SnapDragon » Fri Jan 24, 2003 11:41 pm

Here's my code, if someone wants to tweak it.

Code: Select all

#include <cstdio>
#include <map>
using namespace std;
typedef signed long long i64;

int size;
map<i64, double> memo;
double nmat(i64 x) {
	double &ret = memo[x];
	if( ret != 0.0 ) return ret-1;
	ret = 1;
	int d = (x>>(2*size));
	if( d == size*size ) return (ret=2)-1;
	int b = (x&((1<<(2*size))-1)), b2 = ((x&((1<<(2*size-1))-1))<<1);
	if( (d < 2*size || (b&(1<<(2*size-1))) || (b&(1<<(size-1)))) &&
		(d%size < 2 || (b&3)) ) {
		ret += nmat(b2 + ((d+1)<<(2*size)));
	}
	if( (d < 2*size || !(b&(1<<(2*size-1))) || !(b&(1<<(size-1)))) &&
		(d%size < 2 || ((b&3) != 3)) ) {
		ret += nmat(b2+1 + ((d+1)<<(2*size)));
	}
	return ret-1;
}

main() {
	for( size = 1;; size++ ) {
		memo = map<i64, double>();
		printf( "size=%d: %30lf\n", size, nmat(0) );
	}
}

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Help me, SnapDragon

Post by nghiank » Wed Jan 29, 2003 8:22 am

test

Post Reply

Return to “Algorithms”