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

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Mon May 15, 2006 5:11 am

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Mon May 15, 2006 6:59 am

trulo17 wrote:
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?
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.
Victor Barinov wrote: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?
Victor Barinov wrote: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
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

well...

Post by Victor Barinov » Mon May 15, 2006 9:30 am

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Mon May 15, 2006 11:52 am

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

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Mon May 15, 2006 12:33 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon May 15, 2006 7:06 pm

never mind..
Last edited by helloneo on Tue May 16, 2006 8:35 am, edited 1 time in total.

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

yes...

Post by Victor Barinov » Mon May 15, 2006 7:28 pm

lonelyone wrote: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
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » Mon May 15, 2006 7:46 pm

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

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

I'm sorry...

Post by Victor Barinov » Mon May 15, 2006 8:22 pm

C wrote: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
New poster
Posts: 7
Joined: Fri Mar 31, 2006 1:22 pm

Can anyone post test cases?

Post by a123123123888 » Tue May 16, 2006 2:44 pm

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

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

Post by Sedefcho » Tue May 16, 2006 4:08 pm

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
New poster
Posts: 7
Joined: Fri Mar 31, 2006 1:22 pm

AC!

Post by a123123123888 » Tue May 16, 2006 5:39 pm

Sedefcho wrote: 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: AC!

Post by helloneo » Tue May 16, 2006 6:23 pm

a123123123888 wrote: 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..

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

1 sec.. to harsh?

Post by sohel » Wed May 17, 2006 8:46 am

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Re: 1 sec.. to harsh?

Post by mamun » Wed May 17, 2006 9:03 am

sohel wrote: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?

Post Reply

Return to “Volume 110 (11000-11099)”