11361 - Investigating Div-Sum Property

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

Moderator: Board moderators

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

11361 - Investigating Div-Sum Property

Post by apurba » Sat Nov 24, 2007 9:45 pm

my code is giving correct output for first two sample but not for the third one.
is that output is correct?

need more test cases.

Title Edited by Moderator

Code: Select all

keep dreaming...

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11361-- are there all correct outputs?

Post by Robert Gerbicz » Sat Nov 24, 2007 10:11 pm

apurba wrote:my code is giving correct output for first two sample but not for the third one.
is that output is correct?

need more test cases.
The sample input/output is good!

It's easier if you use unsigned int, because A and B can be as large as 2^31-1 to avoid overflow in int type. And perhaps a clever algorithm to avoid TLE, use a large precomputed hash table to avoid the big computation of the answer.
The tricky test cases are those where A or B is divisible by a large power of 10. (It's too easy to miscompute the bounds of some variables).

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

what wrong with my code?

Post by apurba » Sat Nov 24, 2007 10:22 pm

here is my code.
what wrong with that?

Code: Select all

cut without ac
				
anyone help.
Last edited by apurba on Sun Nov 25, 2007 2:40 pm, edited 1 time in total.

Code: Select all

keep dreaming...

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: what wrong with my code?

Post by Robert Gerbicz » Sat Nov 24, 2007 11:28 pm

apurba wrote:here is my code.
what wrong with that?
Your program is completely wrong. You have to compute the sum of the digits like this way:

Code: Select all

unsigned int sumofdigits( unsigned int n)  {
    unsigned int k=n,sum=0;
    while(k)  sum+=k%10,k/=10;
    return sum;
}
And try to avoid TLE, because by only this simple sumofdigits function you'll get that.

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

Re: what wrong with my code?

Post by apurba » Sun Nov 25, 2007 12:28 am

Robert Gerbicz wrote:
apurba wrote:here is my code.
what wrong with that?
Your program is completely wrong. You have to compute the sum of the digits like this way:

Code: Select all

unsigned int sumofdigits( unsigned int n)  {
    unsigned int k=n,sum=0;
    while(k)  sum+=k%10,k/=10;
    return sum;
}
And try to avoid TLE, because by only this simple sumofdigits function you'll get that.

this is not working!!!!!!!
wrong again.

Code: Select all

keep dreaming...

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Nov 25, 2007 3:59 am

You need some kind of DP solution if you want to get this problem.
The dimensions are 10x10xKxK. But that is way out of bound, you need something more clever :)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Nov 26, 2007 9:50 am

K < 10000 was a clever trick. :wink:

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Nov 26, 2007 10:01 am

I think that, maximal possible K is 82. Because there are no numbers in inteval with larger sum of digits then 82.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Mon Nov 26, 2007 6:59 pm

I cant get the "kind of DP" idea.... can anyone give me some hints?? thanks. eric

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Nov 26, 2007 8:39 pm

sonyckson wrote:I cant get the "kind of DP" idea.... can anyone give me some hints?? thanks. eric
The dimensions for the DP:
length of number, first digit of number, sum of digit mod K, number mod K

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Nov 27, 2007 1:07 pm

sclo wrote: The dimensions for the DP:
length of number, first digit of number, sum of digit mod K, number mod K
My one is also similar to yours..
.. int dp[ length ][ sum of digit mod K ][ number mod K ] [ 1/0 depending one whether the chosen digits is a prefix of the number or not]

Eiger Yap
New poster
Posts: 4
Joined: Sun Nov 18, 2007 2:30 pm
Location: Medan-Indonesia
Contact:

Post by Eiger Yap » Thu Dec 06, 2007 3:42 pm

I also get TLE, hmmm....

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Dec 07, 2007 3:28 am

if you did the dp properly, you won't get TLE. Remember that there are no solution if K is too large.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Wed Jan 23, 2008 9:34 pm

Hello, I tried to use DP (10*10*K*K) to solve these problem

but got WA

Can someone check the I/O below? thanks.

Input:

Code: Select all

6
234 4567 8
3421 4568976 3
1232 456965 7
9909 123444 5
11111 11111111 7
980364 2147483647 11
CORRECT output:

Code: Select all

69
1521852
9306
4542
226548
17737396
Last edited by Wei-Ming Chen on Thu Jan 24, 2008 2:48 pm, edited 1 time in total.

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Post by greve » Thu Jan 24, 2008 12:35 am

You can check I/O on my page http://www.uvatoolkit.com.
Last edited by greve on Wed Oct 28, 2009 6:57 pm, edited 1 time in total.
For help with problems, visit http://www.uvatoolkit.com/

Post Reply

Return to “Volume 113 (11300-11399)”