11472 - Beautiful Numbers

[hamedv]

i think it's a simple DP problem but i'm getting WA

here is my code:

Code: Select all

#include <iostream>

using namespace std;

int main()
{
	long long dp[11][101][10];
	memset(dp, 0, sizeof dp);
	for (int i = 0; i < 11; i++)
		for (int j = 0; j < 10; j++)
			if (j)
				dp[i][1][j] = 1;
			else
				dp[i][1][j] = 0;
	for (int base = 2; base <= 10; base++)
		for (int len = 2; len <= 100; len++)
			for (int lastd = 0; lastd < base; lastd++)
			{
				if (lastd == 0)
					dp[base][len][lastd] = dp[base][len-1][lastd+1];
				if (lastd == base-1)
					dp[base][len][lastd] = dp[base][len-1][lastd-1];
				if (lastd > 0 && lastd < base-1)
					dp[base][len][lastd] = (dp[base][len-1][lastd-1] + dp[base][len-1][lastd+1]) % 1000000007;
			}
	int N, M, t;
	cin >> t;
	while (t--)
	{
		cin >> N >> M;
		long long ans = 0;
		for (int l = 1; l < M; l++)
			for (int ld = 0; ld < N; ld++)
				ans = (ans + dp[N][l][ld]) % 1000000007;
		cout << ans << endl;
	}
}

[Robert Gerbicz]

Yes, this is dp, but what is fantastic that it is solvable by recursion, for every B(ase) there is a linear recursion (but this way is a little heavier than the dp). But you send also a precomputed (large) table, because there are 9*101 required numbers and that fits in the 40 Kbyte.

[hamedv]

yes you are right but can you tell me why i'm getting WA:

mydpfunction(BASE, DIGITS, LASTDIGIT) = number of the beautiful numbers in base BASE which have DIGITS digits and their last digit is LASTDIGIT.
if (LASTDIGIT = 0 and DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;
if (DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 1;
if (LASTDIGIT = 0)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = mydpfunction(BASE, DIGITS-1, LASTDIGIT+1);
if (LASTDIGIT = BASE-1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = mydpfunction(BASE, DIGITS-1, LASTDIGIT-1);
if (LASTDIGIT = 1 to BASE-2)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = (mydpfunction(BASE, DIGITS-1, LASTDIGIT-1) + mydpfunction(BASE, DIGITS-1, LASTDIGIT-1)) % 1000000007;

Is my implementation wrong?
Please help me...?

[Leonid]

Code: Select all

if (LASTDIGIT = 0 ans DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;

IMHO the problem may be here. Don't assume, that the number 0 can't be used in DIGITS > 1. Since the number 10 is produced by adding 1 to zero.
Once you have found the answer of a particular length. You can iterate the length and sum up all valid states excluding the states where a number begins with 0. I got AC with a different O(2^N * N * M) solution.

[andmej]

Code: Select all

if (LASTDIGIT = 0 ans DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;

IMHO the problem may be here. Don't assume, that the number 0 can't be used in DIGITS > 1. Since the number 10 is produced by adding 1 to zero.
Once you have found the answer of a particular length. You can iterate the length and sum up all valid states excluding the states where a number begins with 0. I got AC with a different O(2^N * N * M) solution.

I also used an O(2^N * N * M) solution. My state is dp[length][used digits][first digit], where dp[j][k] = number of ways to form a number with i digits, such that the first digit is k and j is a bitwise mask indicating which digits I have used. This method took 1 second (slow!) using memoization.

[hamedv]

Code: Select all

if (LASTDIGIT = 0 ans DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;

IMHO the problem may be here. Don't assume, that the number 0 can't be used in DIGITS > 1. Since the number 10 is produced by adding 1 to zero.
Once you have found the answer of a particular length. You can iterate the length and sum up all valid states excluding the states where a number begins with 0. I got AC with a different O(2^N * N * M) solution.

It's not ANS. it's AND my function produces 0 if LASTDIGIT = 0 and it is a 1 digit number which there can be only zero.
Please tell me your implementation.

[Leonid]

I keep track of used numbers so far a the first dimension of an array. The other 2 dimensions are length and the last digit. For example 5 (101) means that I used numbers (0 and 2). When I find answers for each length I iterate through (111) values for each length and every digit to the left of the number (except 0, since the number can't start with 0).

[H_Hima]

hi.

the introduced method was useful but I code a O(N^2 * M) method and this is my code.
but why I got WA.
may anybody send me some testcases in the wrong positions or tell me what is wrong here.

fun2(b,len,ld) : count of numbers in base b with length len and with the last digit ld that all of the digits appears in it.
fun(b,len,ld) : count of numbers in base b with length len and with the last digit ld that all of the digits appears in it and the first digit is not zero.

then I used DP for filling the tables.

this is my code.

Code: Select all

deleted after acc with help of hamedv.

thanks.

[hamedv]

Try these:

input:

Code: Select all

1
5 100

correct output:

Code: Select all

778091614

replace this line

Code: Select all

tabl[i][j]+=fun(i,j,k)

by this:

Code: Select all

tabl[i][j]=(tabl[i][j]+fun(i,j,k))%1000000007;

[hamedv]

I keep track of used numbers so far a the first dimension of an array. The other 2 dimensions are length and the last digit. For example 5 (101) means that I used numbers (0 and 2). When I find answers for each length I iterate through (111) values for each length and every digit to the left of the number (except 0, since the number can't start with 0).

Thank you!
I misunderstood the problem!

[H_Hima]

Try these:

input:

Code: Select all

1
5 100

correct output:

Code: Select all

778091614

replace this line

Code: Select all

tabl[i][j]+=fun(i,j,k)

by this:

Code: Select all

tabl[i][j]=(tabl[i][j]+fun(i,j,k))%1000000007;

Special Thanks Hamedv. what a silly bug.
you exactly found the bug and the code got ACC.

again thanks.

[Blackwizard]

hi...

I've written this code for 11472 but it takes RUNTIME ERROR!
I don't know what is it's reason!!!

please help me to solve this problem... thanks!
here's my code:

Code: Select all

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int dp[101][10][1024];
int res;

int main ()
{
	memset (dp, 0, sizeof dp);
	for (int j = 1; j <= 9; j++)
		dp[1][j][1<<j] = 1;
	for (int i = 1; i < 101; i++)
		for (int j = 0; j < 10; j++)
			for (int k = 1; k < 1024; k++)
			{
				int nx = j+1;
				int pr = j-1;
				if (nx < 10)
				{
					res = dp[i+1][nx][k|(1<<nx)];
					dp[i+1][nx][k|(1<<nx)] = (res + dp[i][j][k]) % 1000000007;
				}
				if (pr >= 0)
				{
					res = dp[i+1][pr][k|(1<<pr)];
					dp[i+1][pr][k|(1<<pr)] = (res + dp[i][j][k]) % 1000000007;
				}
			}	
	int n, m, t;
	cin >> t;
	for (; t != 0 && cin >> n >> m; t--)
	{
		res = 0;
		int all = (int)pow (2., n) - 1;
		for (int i = n; i <= m; i++)
			for (int j = 0; j < n; j++)
				res = (res + dp[i][j][all]) % 1000000007;
		cout << res << endl;
	}
	return 0;
}

[brianfry713]

Use a debugger with the sample input. On line 23 if i=100 that's a seg fault.

[gm3t]

You can also view my suggested solution here: http://blog.tranthanhtu.com/2012/12/uva ... ution.html