p2195 Counting Zeroes (dhaka regionals)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Fri Sep 29, 2006 7:05 am

Darko wrote:I don't think that is correct (the case for 20) - you get the correct answer, but you don't remove first and last - you just remove 1 as a divisor every time you count them (because 1=1^2=1^3...).
thanks Darko, now the idea is quite clear :D

seeing the above discussion , one of my assumption goes wrong...

I thought ppl who reply have actually the accepted code with them...

but seeing differnt idea i think either my asumption is wrong or the test data is weak..

the chances of the later being very very less :lol:
If I will myself do hashing, then who will do coding !!!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Fri Sep 29, 2006 7:36 am

n now i m frustrated ...
this tle is the worst thing i have ever seen as far as programming is cocerned.. :evil:


take a look at my code

Code: Select all

 
please help :cry:
Last edited by vinay on Sat Sep 30, 2006 2:20 am, edited 1 time in total.
If I will myself do hashing, then who will do coding !!!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Sep 29, 2006 4:40 pm

I think you have it there, so you should remove the code, but it times out because you check for the primality inside the loop. You don't need to do it because you should break out of the loop as soon as primes*primes > n. If n>1 at that point, it's prime.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sat Sep 30, 2006 2:22 am

still tle, don't know how to get rid of it....
can anyone tell which part is time consuming...

do i need to memoize some results???

Code: Select all


}        
Last edited by vinay on Sat Sep 30, 2006 6:22 am, edited 1 time in total.
If I will myself do hashing, then who will do coding !!!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Sep 30, 2006 2:42 am

Maybe store primes as long longs?

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sat Sep 30, 2006 6:13 am

Darko wrote:Maybe store primes as long longs?

that doesn't solve the problem....

does it differ from your code anywhere in terms of the ideas...
If I will myself do hashing, then who will do coding !!!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sat Sep 30, 2006 6:27 am

ohh its accepted ...

the only change i made was instead of doing

if (primes*primes >n)

i took the sqrt on n (whenever it changed) and change my if to

if (primes > sqr) ...

I think the cost of that multiplication was too high....

but that was difficult to guess...

its accepted in 6.2 seconds..


ok thanks Darko for your cooperation... :D
If I will myself do hashing, then who will do coding !!!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Sep 30, 2006 6:30 am

No, I had exactly the same thing (up to the language differences, I guess).

I said "store as long longs" because you had something like if(primes*primes < n) where primes is an int up to 3000000 and n is long long. I don't know what C++ does with those, maybe there is an overflow. Which could've occured somewhere else, too.

The only thing that is different is that I used arrays, but I guess vectors are almost the same thing?

Make some test cases and see where it spends most of the time. Try extreme values (both upper and lower bounds), that sort of thing.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sat Sep 30, 2006 6:35 am

sorry , changing primes to long long is also accepted...

so if i used long long its accepted in 6.023 sec...

using the above idea of sqrt (with or without long long for primes) is acc in 6.23...

what could be interpreted out of it??? :-?
If I will myself do hashing, then who will do coding !!!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sat Sep 30, 2006 6:45 am

of course the multiplication had overflow problems if primes was int type....

so all the time I got tle was bcoz of oreflow not inefficient algo :oops:

using sqr was also doing the same job of avoiding overflows....

if i m right if i say calculating sqrt is slower than multiplication ...

as here the multiplication is done lot more times than sqrt and still multipliaction is acc in 6.0 sec while sqrt in 6.23 sec 8)
If I will myself do hashing, then who will do coding !!!

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Fri Oct 13, 2006 2:20 pm

hi all

I also have solved the problem and timing at 5.855s. But I think the timing is poor. some author have timing less than 3s. What is the method if anyone can explain. Thanks in advance.

Sorry for my poor english
Practice Makes a man perfect

Post Reply

Return to “ACM ICPC Archive Board”