## 11032 - Function Overloading

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

Moderator: Board moderators

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### 11032 - Function Overloading

Hello, everybody!!!

How to solve this problem?

I think that we can optimize function fun(int a) by replacing line:

Code: Select all

`` for(i=1; i<=a; i++){``
to

Code: Select all

`` for(i=max(1, a-100); i<=a; i++){``
But what to do with fun(int a, int b) ???

Thanks, bye!

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
i got this one ac(3.5 seconds, but not in contest time)
What i'm doing is to put in an array every 1<=i<=10^7 such that i!=(j+sod(j)) for j<=i, this can be done in linear time.
Let's call this "i" special numbers.
after precalculating this i answer query for fun(a) with the idea you explained above and querys for fun(a,b) using binary search(if you analize fun(a,b) you'll realize what you want is the number of special numbers between a and b).

Anyway precalculating the table is still too expensive(at least if you wanted to get ac in contest)

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:
Those special numbers are actually called self numbers. Seeing the runtime and memory needed for sohel in the ranklist I think there is a formula. I've no idea though.

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### Formula, hm...

I tried to take out a formula on contest. So, if we whant to know value fun( 0, a ) and a < 1000 , we can evalute it by next:

Code: Select all

``floor(a / 101) * 10 + floor( (a % 101) / 11 ) + 4``
But I had problems with numbers grater than 1000...
Any more ideas?

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### Re: 11032 - Function Overloading

Victor Barinov wrote:Hello, everybody!!!

How to solve this problem?

I think that we can optimize function fun(int a) by replacing line:

Code: Select all

`` for(i=1; i<=a; i++){``
to

Code: Select all

`` for(i=max(1, a-100); i<=a; i++){``
But what to do with fun(int a, int b) ???

Thanks, bye!
hi ......
your fun function to find "a input number" is almost the same as mine
and my method for "tow input numbers" is very silly
find all not "self number" and add them into a array
then you can do a fast search

but can someone give me some hint to solve it in a very fast time and no need to use a huge memory
thanks
studying @ ntu csie

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
There is no mathematical formula. At least not till now

Check this:
http://www.wschnei.de/digit-related-num ... mbers.html

I still haven't solved it. But it is a nice problem.

See this theorem. I think it can be used.

For even bases b the following can be proven:
If n ≥ b is a self number then n has the form n = (b-1) + a1(b^1+1) + a2(b^2+1) + ... with 0 ≤ ai < b.

Note that the reverse direction is not true.

This means each self number in the interval [1, 10 000 000] has
the form :
N = 9 + 11*a1 + 101*a2 + 1001*a3 +
10001*a4 + 100001*a5 + 1000001*a6
where a1,a2,a3,a4,a5,a6 are decimal digits.

I guess you will also find the following links interesting.
http://en.wikipedia.org/wiki/Self_number
http://mathworld.wolfram.com/SelfNumber.html

Good luck.

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Code: Select all

``````for(i=1;i<=10000000;++i)    B[i+sod(i)]=true;
for(i=1;i<=10000000;++i)
if(!B[i])    A[ct++]=i;``````
This is how i'm generating my table, i see almost every one is precalculating too(huge memory use). Any better way of precalculating?
Btw, don't you think time limit at contest was way too strict?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:
Try to get rid of function, sod(). It's all divisions and consumes a lot of time.

I solved the problem in little more than a second which exceeds the problem's actual timelimit. The average runtime at the top of the ranklist is around 1 sec. other than sohel. I should think the time limit was very strict unless the input file had been lengthened considerably after the contest.
Sedefcho wrote:For even bases b the following can be proven:
If n ≥ b is a self number then n has the form n = (b-1) + a1(b^1+1) + a2(b^2+1) + ... with 0 ≤ ai < b.
That's a nice idea. May pass the timelimit. I had also checked those papers but overlooked this point. Maybe was concentrating on some other formula.

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

### why TLE

I precalculated all self-number and filled the table with 0, or else is the value in the table 1, so I used linear time to search,but i got TLE,why??
BTW it runs very quickly on my pc(<3s),and I have tried with input 1 10000000!
Last edited by C on Mon May 15, 2006 6:53 pm, edited 3 times in total.

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
mamun wrote:Try to get rid of function, sod(). It's all divisions and consumes a lot of time.
any hints for avoiding sod(),but still in a precalculating approach?

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am
I am always getting memory limit exceeded.

My soln is as follows
1) Generate 1 to MAX (10000000)
arr[ i + sumofdig(i)]=i;
if(arr==0)
arr1[cnt++]=i;

now i use binary search on arr1 to find the differenece if it is 2 inputs else
i refer arr if only 1 input.

Below is my code

Code: Select all

``````
#include<cstdio>
#include<algorithm>
using namespace std;

#define MAX 10000001
int arr[MAX],arr1[MAX/10];
int main ()
{
int i, k, sum,cnt,a,b,no;
char str[30],*p,*y;
cnt=1;
for (i = 1; i < MAX; i++)
{
k = i;
sum = 0;
while (k)
{
sum += k % 10;
k /= 10;
}

if ( (i + sum < MAX) && arr[i+sum]==0)
{
arr[i + sum] = i;
}
if(arr[i]==0)
arr1[cnt++]=i;
}

/*      for(i=0;i<cnt;i++)
printf("%d\n",arr1[i]);
*/
//       printf("%d\n",cnt);
scanf(" %d\n",&no);

for(i=1;i<=no;i++)
{
fgets(str,25,stdin);
b=-1;
y=str;
k=0;
while((p=strtok(y," "))!=NULL)
{

if(k==0)
a=strtoul(p,NULL,10);

if(k==1)
b=strtoul(p,NULL,10);

y=NULL;

k++;
}

printf("Case %d: ",i);

if(k==1)
printf("%d\n",(arr[a]==0)?-1:arr[a]);
else
{
int *pos1,*pos2;
pos1=lower_bound(arr1,arr1+cnt,a-1);
pos2=lower_bound(arr1,arr1+cnt,b);

printf("%d\n",-distance(arr1,pos1)+distance(arr1,pos2));

}

}

return 0;
}

``````
Regards
Nik

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

### getting Runtime error

Hi all,
I am getting either Runtime error or Compile error everytime i submit the code. Here it is :

Code: Select all

``````#include<cstdio>
#include<ctype.h>
#include<iostream>
int max(int a,int b){
if(a>b)
return a;
return b;
}
int main(){
char string[50];
int num1,num2,c,cnt,test,i,l,sum,j,cas=0;
int i1,i2,i3,i4,i5,i6;
bool arr[10000001]={0};
arr[1]=arr[3]=arr[5]=arr[7]=1;
for(i1=0;i1<10000000;i1+=1000001){
for(i2=0;i2<1000000;i2+=100001){
for(i3=0;i3<100000;i3+=10001){
for(i4=0;i4<10000;i4+=1001){
for(i5=0;i5<1000;i5+=101){
for(i6=0;i6<100;i6+=11){
sum=i1+i2+i3+i4+i5+i6+9;
arr[sum]=true;
}
}
}
}
}
}
scanf("%d",&test);
while(test>0){
scanf(" %[^\n]",string);
l=strlen(string);
c=0;
cas++;
for(i=0;i<l;i++){
if(isdigit(string[i])){
sum=0;
while(isdigit(string[i])){
sum=sum*10+string[i]-'0';
i++;
}
c++;
if(c==1)
num1=sum;
else
num2=sum;
}
}
printf("Case %d: ",cas);
if(c==1){
if(arr[num1]==false){
printf("-1\n");
}
else{
i=max(1,num1-90);
cnt=0;
for(;i<=num1;i++){
j=i;
sum=0;
while(j>0){
sum+=j%10;
j/=10;
}
if(i+sum==num1){
printf("%d\n",i);
break;
}
}
}
}
else if(c==2){
cnt=0;
for(i=num1;i<=num2;i++)
if(arr[i]==false)
cnt++;
if(cnt==0)
printf("-1\n");
else
printf("%d\n",cnt);
}
test--;
}
return 0;
}
``````
Please tell me whats wrong with this code.
First i had included the header file stdbool.h also.
But it gave compile error:
In file included from 04575130_24.c:4:
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/include/stdbool.h:9:
parse error before `false'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/include/stdbool.h:11:
declaration does not declare anything

Then i removed that line and it gave runtime error.

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### Wow, AC in 0.010 sec :-)

Wow, AC in 0.010 sec

I so happy!!! I used the same that said Sedefcho. I spent all day to solve it . I think that we can find out formula or not complicated rule for function fun(0,a).

Thanks to Sohel Hafiz for this NICE problem

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
congratulations victor for top place
i finally managed to get it within 1 second time limit
althought with a not so good time (0.891)
anyway i still think the time limit was very strict at contest(unless that input was shorter as mamun says)
only thing i did to improve was this:
sod(i) = i, 1<=i<=9
sod(i) = i%10+sod(i/10), i>9
so using a table we can precalculate faster(using previous results)
this may seem too obvious, but just in case it can help someone

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
I have changed my code not to use so many sod-s, but I still got TLE,help.....