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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

thanks for the advice..

Post by sohel »

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

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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 »

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

test cases please

Post by temper_3243 »

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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: test cases please

Post by Martin Macko »

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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

Nice Problem :D
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
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha »

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
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

Post by Programmer »

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

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

jagadeesh
New poster
Posts: 3
Joined: Sun Oct 22, 2006 8:04 pm

selfnumbers

Post by jagadeesh »

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

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

WA NEED I/O

Post by SHAHADAT »

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

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Re: WA NEED I/O

Post by SHAHADAT »

AC.BUT almost 3.8 seconds.
Terrible :oops:

Post Reply

Return to “Volume 110 (11000-11099)”