11270 - Tiling Dominoes

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

11270 - Tiling Dominoes

Post by tryit1 » Sun Nov 30, 2008 6:45 am

Did anyone get the recurrence for the general nxm board ? or used the closed form at http://en.wikipedia.org/wiki/Domino_tiling

Say i didn't know closed form the url , how do i go about solving it ?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11270 - Tiling Dominoes

Post by Jan » Fri Feb 27, 2009 12:49 pm

Pre generate the values and store the result in a file. Then store the values in an array. Finally, print the values from the array. That's what I did.
Ami ekhono shopno dekhi...
HomePage

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11270 - Tiling Dominoes

Post by mak(cse_DU) » Tue Jun 22, 2010 3:26 pm

I pre-calculated all M*N value in a 2D array.
Complexity O(10 * 2^10 * 2^10) .
State F(Row,Mask) .
But my timing 0.044.:(

Some Input/Output for future reference:

Code: Select all

34 2
10 10
8 9
3 3
3 10
4 20
4 25
0 3
9 11
8 12
AC output:

Code: Select all

9227465
258584046368
108435745
0
571
616891945
114079985111
0
0
82741005829
Mak
Help me PLZ!!

mehdiii
New poster
Posts: 9
Joined: Fri Nov 02, 2012 1:35 pm

Re: 11270 - Tiling Dominoes

Post by mehdiii » Wed Mar 27, 2013 10:22 pm

neither n nor m is zero in the judge data.

I have a problem here :
When I produce all possible inputs and I put it in my source code just to print in UVa OJ it gets ACCEPTED.

....
mat[25][4] = 114079985111LL;
mat[26][1] = 1LL;
mat[26][2] = 196418LL;
mat[26][3] = 21489003LL;
....

But when I calculate it in my code instead of writing it in a file, it gets WA.
Is it because of compiler behavior? Or I have a bug in my code?

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <cstdio>
using namespace std;
#define ll long long

map < vector<int>, ll > dp;
int a, b;

ll f(int row, vector <int> v)
{
	if(dp.count(v))
		return dp[v];

	if(v[row] == 0)
		return dp[v] = f(row+1, v);

	ll &ref = dp[v];
	ref = 0;
	for(ll j = 0; j < b-1; j ++)
	{
		if( v[row]&(1<<j) && v[row]&(1<<(j+1)) )
		{
			v[row] = v[row] ^ (1<<j) ^ (1<<(j+1));
			ref += f(row, v);
			v[row] = v[row] | (1<<j) | (1<<(j+1));

			if(row < a-1)
			{
				if( v[row+1] & (1<<j) )
				{
					v[row] = v[row] ^ (1<<j);
					v[row+1] = v[row+1] ^ (1<<j);
					ref += f(row, v);
				}
			}
			return ref;
		}
	}
	if(row < a-1)
	{
		for(ll j = 0; j < b; j ++)
		{
			if(v[row]&(1<<j) && v[row+1]&(1<<j))
			{
				v[row] = v[row] ^ (1<<j);
				v[row+1] = v[row+1] ^ (1<<j);
				ref += f(row, v);
				return ref;
			}
		}
	}
	return ref;
}

ll mat[128][128];

int main()
{
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);

	memset(mat, -1, sizeof mat);

	for(int x = 1; x <= 100; x ++)
		for(int y = 1; y <= 100; y ++)
	//while(cin >> a >> b)
	{
		if(x*y > 100)
			continue;
		a = x;
		b = y;

		dp.clear();
		//if(a == 0 || b == 0)
			//while(true);

		if(a < b)
			swap(a, b);

		vector <int> v(a, 0);
		dp[v] = 1;
		for(int i = 0; i < a; i ++)
			v[i] = (1<<b)-1;

		ll res;
		if( a*b % 2 == 1 )
			res = 0;
		else
			res = f(0, v);
		mat[a][b] = mat[b][a] = res;
		//cout << res << endl;
	}
	while(cin >> a >> b)
	{
		if(mat[a][b] == -1 && mat[b][a] == -1)
			while(true);

		//printf("%lld\n", res);
		/*if(mat[a][b] == -1)
			cout << mat[b][a] << endl;
		else
			cout << mat[a][b] << endl;*/
		if(a < b)
			swap(a, b);
		printf("mat[%d][%d] = %lldLL;\n", a, b, mat[a][b]);
	}

	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11270 - Tiling Dominoes

Post by brianfry713 » Thu Mar 28, 2013 9:41 pm

Your code is producing zeros and doesn't match the sample I/O. See:https://ideone.com/k5lfQq
Check input and AC output for thousands of problems on uDebug!

mehdiii
New poster
Posts: 9
Joined: Fri Nov 02, 2012 1:35 pm

Re: 11270 - Tiling Dominoes

Post by mehdiii » Fri Mar 29, 2013 12:20 am

That's so strange, last night I was testing my program with Visual Studio 2010, and it worked very good, generated correct output as I said in my previous post,
but now, after your reply I tested it with MinGW/G++ and it didn't work, I checked my code again and noticed line 19 :

Code: Select all

      return dp[v] = f(row+1, v);
Make long story short, I think MinGW and VS2010 have different behavior about the above code,
VS2010 first invokes f(row+1, v) and then inserts it to dp, in f(row+1, v), dp.count(v) is zero.
but MinGW first assigns memory for dp[v], then invokes f(row+1, v) and at the end assigns the value to dp[v], in f(row+1, v), dp.count(v) is 1.

I don't know which standard is better :-)

mehdiii
New poster
Posts: 9
Joined: Fri Nov 02, 2012 1:35 pm

Re: 11270 - Tiling Dominoes

Post by mehdiii » Fri Mar 29, 2013 12:22 am

By the way, Thank you, I changed it a little bit and got ACCEPTED ;-)

Post Reply

Return to “Volume 112 (11200-11299)”