Moderator: Board moderators

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
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
Contact:
trulo17 wrote:
mamun wrote: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.
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...

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
Contact:
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
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
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
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...

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

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?

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

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

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.
I got AC.
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!

a123123123888 wrote: But it used about 6.7sec...
Is there a faster method easy to understand?
Sure it is..
See trulo17's posts..
I think it's the easiest method..
I got AC with that under 3 sec, still slow though..

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

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