11032 - Function Overloading

[trulo17]

i first got ac using as much as ten million sod functions(precalculating part) so maybe you are answering querys in a very slow way(for example when you read 2 values, doing a linear search is a really bad idea).Read post aboves to get an idea of what to do in each case.

[mamun]

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?

Seems you've improved your sod() calculation and hence runtime. But you might be interested to know my method.
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.

Wow, AC in 0.010 sec

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?

I think that we can find out formula or not complicated rule for function fun(0,a).

Can you explain what do you mean?

[Victor Barinov]

Can you explain what do you mean?

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

[mamun]

Nice explanation Victor Barinov.

So no precalculation. No formula for self numbers but for frequency of them.

OK. Let me find the rules for that.

[lonelyone]

but how about 1017
G(1017) = 9 + 9*11 + 9*101
but 1017 is not a self-number
so it should not be counted..

anyone could explain this ?
thanks a lot

[helloneo]

never mind..

[Victor Barinov]

but how about 1017
G(1017) = 9 + 9*11 + 9*101
but 1017 is not a self-number
so it should not be counted..

anyone could explain this ?
thanks a lot

There are no self numbers in segments:

[108, 110]
[1006, 1021]
[10004, 10032]
etc.

[C]

There are 2 self numbers in segments[108,110], and they are 108 and 110

[Victor Barinov]

There are 2 self numbers in segments[108,110], and they are 108 and 110

You are right! I missprinted:

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

[a123123123888]

I already WA many times
So I want to test where my code go wrong
Can anyone post test cases for me?

[Sedefcho]

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 self-number"

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

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

Actually the non-self-numbers 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 self-number
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

[a123123123888]

Actually the non-self-numbers 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.

Thank you for your hint!
I got AC.
But it used about 6.7sec...
Is there a faster method easy to understand?

[helloneo]

But it used about 6.7sec...
Is there a faster method easy to understand?

Sure it is..
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..

[sohel]

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 non-self numbers.

If you generate all the self numbers using brute-force, 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.

[mamun]

The gaps between consecutive 'self numbers' are from the set { 2, 11, 15, 28, 41, 54 } ... and the gaps are periodic.

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?