p2195 Counting Zeroes (dhaka regionals)

vinay · 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

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

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

take a look at my code

Code: Select all

please help

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

vinay · 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

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

Maybe store primes as long longs?

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

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

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

vinay · 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???

vinay · 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

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

mrahman · 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