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

Post by Victor Barinov » Sat May 13, 2006 7:51 pm

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

Post by trulo17 » Sun May 14, 2006 3:15 am

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:

Post by mamun » Sun May 14, 2006 10:43 am

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...

Post by Victor Barinov » Sun May 14, 2006 12:21 pm

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

Post by SRX » Sun May 14, 2006 3:54 pm

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 :P
studying @ ntu csie

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sun May 14, 2006 7:59 pm

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

Post by trulo17 » Sun May 14, 2006 8:15 pm

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:

Post by mamun » Sun May 14, 2006 8:30 pm

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. :P

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

why TLE

Post by C » Sun May 14, 2006 8:40 pm

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

Post by trulo17 » Sun May 14, 2006 9:07 pm

mamun wrote:Try to get rid of function, sod(). It's all divisions and consumes a lot of time.
:P
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

Post by temper_3243 » Sun May 14, 2006 9:21 pm

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

Post by Ankur Jaiswal » Sun May 14, 2006 9:25 pm

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

Post by Victor Barinov » Sun May 14, 2006 11:26 pm

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

Post by trulo17 » Mon May 15, 2006 12:01 am

congratulations victor for top place :D
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 8)

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

Post by C » Mon May 15, 2006 12:22 am

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

Post Reply

Return to “Volume 110 (11000-11099)”