Page 1 of 1
11472 - Beautiful Numbers
Posted: Sun Aug 03, 2008 6:19 pm
by 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;
}
}
Re: 11472 - Beautiful Numbers
Posted: Sun Aug 03, 2008 6:27 pm
by 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.
Re: 11472 - Beautiful Numbers
Posted: Sun Aug 03, 2008 8:39 pm
by 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...?
Re: 11472 - Beautiful Numbers
Posted: Sun Aug 03, 2008 8:58 pm
by 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.
Re: 11472 - Beautiful Numbers
Posted: Mon Aug 04, 2008 5:33 am
by andmej
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
by hamedv
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.
Please tell me your implementation.
Re: 11472 - Beautiful Numbers
Posted: Mon Aug 04, 2008 9:31 am
by 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).
Re: 11472 - Beautiful Numbers
Posted: Mon Aug 04, 2008 3:38 pm
by 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.
Re: 11472 - Beautiful Numbers
Posted: Mon Aug 04, 2008 5:19 pm
by hamedv
Try these:
input:
correct output:
replace this line
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
by hamedv
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
by H_Hima
hamedv wrote:Try these:
input:
correct output:
replace this line
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
by 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;
}
Re: 11472 - Beautiful Numbers
Posted: Thu Jul 19, 2012 3:11 am
by brianfry713
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
by gm3t