11032  Function Overloading
Moderator: Board moderators
Seems you've improved your sod() calculation and hence runtime. But you might be interested to know my method.trulo17 wrote:any hints for avoiding sod(),but still in a precalculating approach?mamun wrote:Try to get rid of function, sod(). It's all divisions and consumes a lot of time.
Precalculate the values of sod(i) in an array sod[] using some nested loops. For example, you know the value of sod[1]. The same value applies for sod[10]. Just increment 1 successively for sod[11] to sod[19]. Similarly sod[100] and sod[101] to sod[109] and so on. There is no division or mod operation. Hence fast. I cut down 3 sec. of my time with this method.
Congratulations! That's really a great performance. Your memory needed is also very low. Didn't you use any array or is it the problem with judge system?Victor Barinov wrote:Wow, AC in 0.010 sec
Can you explain what do you mean?Victor Barinov wrote:I think that we can find out formula or not complicated rule for function fun(0,a).

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
well...
for calculate function fun(a,b) we can do next:Can you explain what do you mean?
precalculate array G[], where G = fun(0,i).
Than fun(a,b) = G  G[a1], 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

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
yes...
There are no self numbers in segments:lonelyone wrote:but how about 1017
G(1017) = 9 + 9*11 + 9*101
but 1017 is not a selfnumber
so it should not be counted..
anyone could explain this ?
thanks a lot
[108, 110]
[1006, 1021]
[10004, 10032]
etc.

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
I'm sorry...
You are right! I missprinted:C wrote:There are 2 self numbers in segments[108,110], and they are 108 and 110
there are no self numbers in intervals
(108, 110)
(1006, 1021)
(10004, 10032)
etc.
and 108, 110, 1006, 1021, 10004, 10032 are self numbers.
sorry...

 New poster
 Posts: 7
 Joined: Fri Mar 31, 2006 1:22 pm
Can anyone post test cases?
I already WA many times
So I want to test where my code go wrong
Can anyone post test cases for me?
So I want to test where my code go wrong
Can anyone post test cases for me?
Hi all + Victor,
The formula I have cited some days ago states that
"each self number has this form"
BUT it does state that
"each number generated by this formula is a selfnumber"
So if I follow Victor's ideas correctly I think the way
you generate the G function is incorrect. I am not 100% sure though.
To be more precise I will say that by using the formula:
where Ai are decimal digits you can generate exactly
1,000,000 numbers which are less than or equal to:
M = 9 + 9*11 + 9*101 + 9*1001 + 9*10001 + 9*100001 + 9*1000001
But they are not all selfnumbers.
Actually the nonselfnumbers generated by this formula
are about 20 000 only. Which is only about 2% of all
numbers generated by that formula. But still their existence
makes the problem harder.
Do you make this assumption that each such number is selfnumber
or am I misunderstanding something?
I used a precalculation technique + some small optimization
for SOD and I got ACC with a modest time of 0.9 secs and
not so modest memory of 14 MB.
Regards
Peter
The formula I have cited some days ago states that
"each self number has this form"
BUT it does state that
"each number generated by this formula is a selfnumber"
So if I follow Victor's ideas correctly I think the way
you generate the G function is incorrect. I am not 100% sure though.
To be more precise I will say that by using the formula:
Code: Select all
N = 9 + A1*11 + A2*101 + A3*1001 + A4*10001 + A5*100001 + A6*1000001
1,000,000 numbers which are less than or equal to:
M = 9 + 9*11 + 9*101 + 9*1001 + 9*10001 + 9*100001 + 9*1000001
But they are not all selfnumbers.
Actually the nonselfnumbers generated by this formula
are about 20 000 only. Which is only about 2% of all
numbers generated by that formula. But still their existence
makes the problem harder.
Do you make this assumption that each such number is selfnumber
or am I misunderstanding something?
I used a precalculation technique + some small optimization
for SOD and I got ACC with a modest time of 0.9 secs and
not so modest memory of 14 MB.
Regards
Peter

 New poster
 Posts: 7
 Joined: Fri Mar 31, 2006 1:22 pm
AC!
Thank you for your hint!Sedefcho wrote: Actually the nonselfnumbers generated by this formula
are about 20 000 only. Which is only about 2% of all
numbers generated by that formula. But still their existence
makes the problem harder.
I got AC.
But it used about 6.7sec...
Is there a faster method easy to understand?
Re: AC!
Sure it is..a123123123888 wrote: But it used about 6.7sec...
Is there a faster method easy to understand?
It's already up there..
See trulo17's posts..
I think it's the easiest method..
I got AC with that under 3 sec, still slow though..
1 sec.. to harsh?
A lot of you are saying that the time limit of 1 sec was a little too harsh..
.. actually my soln took a time of 0.064 seconds and thought 1 sec should be enough. Actually, I was looking for a solution that does not require the assistance of SOD(). I myself wrote a soln using sod() and that took around 3 seconds. But i was unaware of the optimized version of calculating sod(), through which many passed the time limit.
My method was to insert all the 'self numbers' in an array.. my function makes sure it goes to the immediate next self number, and thus i don't have to worry about rejecting the nonself numbers.
If you generate all the self numbers using bruteforce, you will find some sort of pattern. The gaps between consecutive 'self numbers' are from the set { 2, 11, 15, 28, 41, 54 } ... and the gaps are periodic.
.. actually my soln took a time of 0.064 seconds and thought 1 sec should be enough. Actually, I was looking for a solution that does not require the assistance of SOD(). I myself wrote a soln using sod() and that took around 3 seconds. But i was unaware of the optimized version of calculating sod(), through which many passed the time limit.
My method was to insert all the 'self numbers' in an array.. my function makes sure it goes to the immediate next self number, and thus i don't have to worry about rejecting the nonself numbers.
If you generate all the self numbers using bruteforce, you will find some sort of pattern. The gaps between consecutive 'self numbers' are from the set { 2, 11, 15, 28, 41, 54 } ... and the gaps are periodic.
Re: 1 sec.. to harsh?
The gaps are not that periodic unless I misunderstood you.sohel wrote:The gaps between consecutive 'self numbers' are from the set { 2, 11, 15, 28, 41, 54 } ... and the gaps are periodic.
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?