Page 2 of 3

Posted: Mon May 15, 2006 5:11 am
by 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.

Posted: Mon May 15, 2006 6:59 am
by mamun
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?

well...

Posted: Mon May 15, 2006 9:30 am
by 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 :-)

Posted: Mon May 15, 2006 11:52 am
by 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. :P

Posted: Mon May 15, 2006 12:33 pm
by 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

Posted: Mon May 15, 2006 7:06 pm
by helloneo
never mind..

yes...

Posted: Mon May 15, 2006 7:28 pm
by Victor Barinov
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. :-)

Posted: Mon May 15, 2006 7:46 pm
by C
There are 2 self numbers in segments[108,110], and they are 108 and 110

I'm sorry...

Posted: Mon May 15, 2006 8:22 pm
by Victor Barinov
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...

Can anyone post test cases?

Posted: Tue May 16, 2006 2:44 pm
by a123123123888
I already WA many times :oops:
So I want to test where my code go wrong :)
Can anyone post test cases for me?

Posted: Tue May 16, 2006 4:08 pm
by 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

AC!

Posted: Tue May 16, 2006 5:39 pm
by a123123123888
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?

Re: AC!

Posted: Tue May 16, 2006 6:23 pm
by helloneo
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..

1 sec.. to harsh?

Posted: Wed May 17, 2006 8:46 am
by 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.

Re: 1 sec.. to harsh?

Posted: Wed May 17, 2006 9:03 am
by mamun
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?