11032 - Function Overloading

[Victor Barinov]

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]

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]

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]

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]

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

[Sedefcho]

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]

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]

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.

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]

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!

[trulo17]

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]

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]

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]

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]

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]

I have changed my code not to use so many sod-s, but I still got TLE,help.....