Page 1 of 1

### 11472 - Beautiful Numbers

Posted: Sun Aug 03, 2008 6:19 pm
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;
memset(dp, 0, sizeof dp);
for (int i = 0; i < 11; i++)
for (int j = 0; j < 10; j++)
if (j)
dp[i][j] = 1;
else
dp[i][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;
}
}
``````

### Re: 11472 - Beautiful Numbers

Posted: Sun Aug 03, 2008 6:27 pm
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.

### Re: 11472 - Beautiful Numbers

Posted: Sun Aug 03, 2008 8:39 pm
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?

### Re: 11472 - Beautiful Numbers

Posted: Sun Aug 03, 2008 8:58 pm

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.

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 5:33 am
Leonid wrote:

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.

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 8:30 am
Leonid wrote:

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.

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 9:31 am
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).

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 3:38 pm
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.

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 5:19 pm
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;``

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 6:20 pm
Leonid wrote: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!

### Re: 11472 - Beautiful Numbers

Posted: Mon Aug 04, 2008 8:48 pm
hamedv wrote: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.

### 11472 - Beautiful Numbers

Posted: Wed Jul 18, 2012 10:03 am
hi...

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

here's my code:

Code: Select all

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

using namespace std;

int dp;
int res;

int main ()
{
memset (dp, 0, sizeof dp);
for (int j = 1; j <= 9; j++)
dp[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;
}
``````

### Re: 11472 - Beautiful Numbers

Posted: Thu Jul 19, 2012 3:11 am
Use a debugger with the sample input. On line 23 if i=100 that's a seg fault.

### Re: 11472 - Beautiful Numbers

Posted: Thu Dec 27, 2012 7:31 pm
You can also view my suggested solution here: http://blog.tranthanhtu.com/2012/12/uva ... ution.html