11472 - Beautiful Numbers

All about problems in Volume 114. 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
hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

11472 - Beautiful Numbers

Post by hamedv » 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[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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11472 - Beautiful Numbers

Post by Robert Gerbicz » 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.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11472 - Beautiful Numbers

Post by hamedv » 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?
Please help me...?
Last edited by hamedv on Mon Aug 04, 2008 8:23 am, edited 1 time in total.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11472 - Beautiful Numbers

Post by Leonid » 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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11472 - Beautiful Numbers

Post by andmej » 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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11472 - Beautiful Numbers

Post by hamedv » 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.
Please tell me your implementation.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11472 - Beautiful Numbers

Post by Leonid » 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).

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Re: 11472 - Beautiful Numbers

Post by H_Hima » 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.
Last edited by H_Hima on Mon Aug 04, 2008 8:50 pm, edited 1 time in total.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11472 - Beautiful Numbers

Post by hamedv » 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;

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11472 - Beautiful Numbers

Post by hamedv » 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!

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Re: 11472 - Beautiful Numbers

Post by H_Hima » 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.

Blackwizard
New poster
Posts: 12
Joined: Fri May 25, 2012 5:36 pm

11472 - Beautiful Numbers

Post by Blackwizard » 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!!!

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11472 - Beautiful Numbers

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

gm3t
New poster
Posts: 1
Joined: Thu Dec 27, 2012 7:26 pm

Re: 11472 - Beautiful Numbers

Post by gm3t » Thu Dec 27, 2012 7:31 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”