11032 - Function Overloading

little joey · Post by **little joey** » Wed May 17, 2006 11:21 am

Sedefcho wrote:There is no mathematical formula. At least not till now

[...]

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.

[...]

Thanks for the hint!
Well, there is a mathematical formula. Let all the numbers generated by the formula that are not selfnumbers be called 'pseudo-selfnumbers'. If you list the pseudo-selfnumbers along with the coefficients a1, a2, ..., you will discover a regularity which will give an almost constant time algorithm to determine the rank of any selfnumber within the ordered set of all selfnumbers.

To the problemsetter:
Nice problem and a nice contest problemset!
Just one thing: I think it's better to avoid letting the input-format depend on the positions of line-breaks in the input-file. Even if you deliver a well formed input-file as problemsetter, you can never be sure what happens with it in the future; people may edit it, add or remove cases and then accidentally remove or add newlines. This happened on UVA on several occasions, leading to very hard to find bugs.
You could have avoided this, by adding a problem type indicator with every case, or writing it out explicitly:

Code: Select all

3
fun(101)
fun(1,9)
fun(20)

Just my 2 cents worth of advice

sohel · Post by **sohel** » Wed May 17, 2006 2:09 pm

little joey wrote: To the problemsetter:
Nice problem and a nice contest problemset!

Thanks.

And, about the input format.. yes you are right. And i tried my best to make sure there was no error in the input file in terms of line break.
I will consider your advice, the next time i set a problem !!!

mamun wrote: The gaps are not that periodic unless I misunderstood you.

Gap between first 5 consecutive self numbers is 2 and then 11 fro a while until we reach 108. Here we have another self number just after 2, ie. 110. Likewise we can see another variation in set {1006,1021,1032}. There are many more. Or did you mean periodic in this variation also?

you are right, it is not 100% periodic, but very close to 100.
If you observe closely, you will notice the periodicity.

Sedefcho · Post by **Sedefcho** » Wed May 17, 2006 4:25 pm

little joey,

maybe there's some regularity ... if u say so...
i was just left with the impression that there's no regularity
after doing a quick check via google. and btw are u sure this
regularity continues above the number 10 000 000.
nice regularity if so ...

by the way ... this almost constant time that you are talking about

is it not some function of the count of the digits of the number?
if so then it is a logN algorithm. which is not bad of course.

little joey · Post by **little joey** » Wed May 17, 2006 5:33 pm

Good point. But the regularity looks so regular, that it has to be true

. I have the feeling that it is not too hard to prove, although that can be deceptive, of course.

Yes, by almost constant I meant dependent on the number of digits. But my implementation is rather clumsy and does the same amount of work for all numbers, even if they are much smaller than 10^7.

temper_3243 · Post by **temper_3243** » Mon May 29, 2006 1:10 pm

for calculate function fun(a,b) we can do next:
precalculate array G[], where G = fun(0,i).
Than fun(a,b) = G - G[a-1], if a <= b.
If we see to this array we can do some conclusion about this numbers... For example G[27], G[35], G[99], G[143] we can evalute by next:

27 = 9 + 1 * 11 + 7;
than G[27] = 5 + 1 = 6;

35 = 9 + 2 * 11 + 4;
than G[35] = 5 + 2 = 7;

99 = 9 + 8 * 11 + 2;
than G[99] = 5 + 8 = 13;

143 = 9 + 3 * 11 + 1 * 101;
than G[143] = 5 + 3 + 1 * 10 = 18

I hope all is right ...

for all numbers from 1 to 10000001 I find out some rules that helps to evalute G without precalc in time near O(1).

But I cant to prove my algo by math

Why does the below code fail for numbers above 1002 . I mean i don't find the formula right. Can you please correct me.

Code: Select all

#include<cstdio>
using namespace std;

int ret(int n)
{
	int a1,a2,a3,a4,a5,a6,a,t;

	a=n-9;

	a6=a/1000001;
	t= a - a6*1000001;
	a5=  t/100001;
	t= a - a6*1000001  - a5*100001;
	a4= t/10001;
	t= a - a6*1000001  - a5*100001 - a4*10001; 
	a3=t/1001;
	t=a - a6*1000001  - a5*100001 - a4*10001 -a3*1001; 
	a2=t/101;
	t=a - a6*1000001  - a5*100001 - a4*10001 -a3*1001 -a2*101; 
	a1=t/11;

	printf("%d %d %d %d %d %d\n",a1,a2,a3,a4,a5,a6);

	return 5 + a1 + 10*a2 + 100*a3 + 1000*a4 + 10000*a5 + a6*100000;
	
}

int main()
{
	int n,k,b,z;

	scanf(" %d",&n);
	printf("%d\n",ret(n));

	return 0;
}

temper_3243 · Post by **temper_3243** » Tue May 30, 2006 10:30 pm

Can someone give more test cases. Can someone tell me where my code is wrong . Please help me .

Code: Select all


#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define mymax(a,b) ((a>b)?(a):(b))

int
ret (int n)
{
  int a1, a2, a3, a4, a5, a6, a, t;


	if(n<3)
		return 1;
	else if(n<5)
		return 2;
	else if(n<7)
		return 3;
	else if(n<9)
		return 4;
	else if(n<20)
		return 5;

  a = n - 9;

  a6 = a / 1000001;
  t = a - a6 * 1000001;
  a5 = t / 100001;
  t = a - a6 * 1000001 - a5 * 100001;
  a4 = t / 10001;
  t = a - a6 * 1000001 - a5 * 100001 - a4 * 10001;
  a3 = t / 1001;
  t = a - a6 * 1000001 - a5 * 100001 - a4 * 10001 - a3 * 1001;
  a2 = t / 101;
  t = a - a6 * 1000001 - a5 * 100001 - a4 * 10001 - a3 * 1001 - a2 * 101;
  a1 = t / 11;

  /* printf ("%d %d %d %d %d %d\n", a1, a2, a3, a4, a5, a6); */

  return 5 + a1 + 10 * a2 + 98 * a3 + 978 * a4 + 9778 * a5 + a6 * 97778;

}

int
sod (int n)
{
  int sum = 0;
  while (n)
    {
      sum += n % 10;
      n /= 10;
    }
  return sum;
}


int
isself (int k)
{
  int i;
  for (i = mymax (0, k - 72); i < k; i++)
    {
      if (i + sod (i) == k)
	return i;
    }
  return -1;
}

int
main ()
{
  int n, z, no, i, k, a, b;
  char *y, *str, *t;

  str = (char *) calloc (80, sizeof (char));
  t = str;
  fgets (str, 75, stdin);
  while ((y = strtok (str, " ")) != NULL)
    {
      no = strtoul (y, NULL, 10);
      str = NULL;
    }
  str = t;

  for (i = 0; i < no; i++)
    {
      str = t;
      fgets (str, 75, stdin);
      printf ("Case %d: ", i + 1);
      k = 0;
      while ((y = strtok (str, " ")) != NULL)
	{
	  if (k == 0)
	    a = strtoul (y, NULL, 10);
	  else
	    b = strtoul (y, NULL, 10);
	  k++;
	  str = NULL;
	}
      if (k == 1)
	printf ("%d\n", isself (a));
      else
	{
	  if (isself (a)==-1)
	    printf ("%d\n", ret (b) - ret (a) + 1);
	  else
	    printf ("%d\n", ret (b) - ret (a));
	}
    }

  return 0;
}

Martin Macko · Post by **Martin Macko** » Wed May 31, 2006 5:23 am

temper_3243 wrote:Can someone give more test cases. Can someone tell me where my code is wrong . Please help me .

Your solution's not working for

Code: Select all

3
1240026 1240027
1240026
1240027

The correct answer is

Code: Select all

Case 1: 0
Case 2: 1239987
Case 3: 1239992

emotional blind · Post by **emotional blind** » Thu Jun 08, 2006 9:28 pm

Nice Problem

Thanks Sohel
Now I lead the Function Overloading - ranklist
with 0.00.006

EDIT:Now : 0.00.004
So It is seen that time limit is not so harsh which was 1 sec in online contest!

StatujaLeha · Post by **StatujaLeha** » Fri Jul 21, 2006 11:51 am

Hi all! Please, give me some hint to avoid TLE. How I try to solve this problem now:
1. I found all numbers A for which there is number I such I + sod(I) == A. I remember it in bool IsSelfNumber[].
2. For numbers A < 5000001 i store in MyArr[A] number of numbers from punkt 1, which <= A.
3. I rewrite function fun(int a) so that it use IsSelfNumber[] and take at most 1000000 iteration to find answer.
Is there any other way to improve speed?

Programmer · Post by **Programmer** » Fri Sep 08, 2006 7:17 pm

Hello.
Can someone who get AC tell me answer of this test.
1
1 10000000
Thanks.

mamun · Post by **mamun** » Sat Sep 09, 2006 2:33 pm

Programmer wrote:Hello.
Can someone who get AC tell me answer of this test.
1
1 10000000
Thanks.

Case 1: 977787

jagadeesh · Post by **jagadeesh** » Sun Oct 22, 2006 9:34 pm

dears
i am new to this group
i happened to see this discussion
one of my student has derived a formulae for this
and that too at the age of 16
it was approved by cochim university of sceince and technology
and and he was congratulated by his highness the president of india
he has proved googol is not a self number
and the largest number he found at that time was named on his name and that was 10 *10^1000000
he has an immense intuition and that he will deliver whether a no is a self number or not in seconds
and if not he will say from which number it was generated
i like to discuss this matter in this group and to introduce the boy to this group
i am a mathematics teacher who was working in trk higher secondary school india
and now in mes indian school qatar
hope u all will reply and this boy will be an asset to this group
we can give a hand
being new i like to know how to discuss this matter in the group and to send messages
kindly inform me in jagadeeshsir@yahoo.com
thanking u
jagadeesh

SHAHADAT · Post by **SHAHADAT** » Thu Mar 22, 2007 8:09 pm

PLEASE CAN ANY ONE GIVE ME SOME I/O.
I'm GETTING WA

SHAHADAT · Post by **SHAHADAT** » Thu Mar 22, 2007 9:09 pm

AC.BUT almost 3.8 seconds.
Terrible

OJ Board

11032 - Function Overloading

thanks for the advice..

test cases please

Re: test cases please

selfnumbers

WA NEED I/O

Re: WA NEED I/O