## 11361 - Investigating Div-Sum Property

Moderator: Board moderators

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

### 11361 - Investigating Div-Sum Property

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?

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?

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?

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?

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
Contact:
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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
K < 10000 was a clever trick.

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:
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
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
Contact:
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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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:
I also get TLE, hmmm....

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
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:
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/