11087 - Divisibility Testing

Martin Macko · Post by **Martin Macko** » Sat Sep 09, 2006 8:34 pm

To help people who have troubles with this problem, note, that the answer doesn't have to fit to 32bit integer (as the answer may be as big as 10^5*(10^5-1)/2). My other bug was, that at first I didn't realise that -7%4=-3 a not 1.

Adrian Kuegel · Post by **Adrian Kuegel** » Sat Sep 09, 2006 8:47 pm

It seems there is no input where the output doesn't fit in a 32 bit integer.
At least under the assumption that you got accepted with long long. I got accepted with int.

Martin Macko · Post by **Martin Macko** » Sat Sep 09, 2006 8:55 pm

Adrian Kuegel wrote:It seems there is no input where the output doesn't fit in a 32 bit integer.
At least under the assumption that you got accepted with long long. I got accepted with int.

Well, I've corrected both bugs at once, so possibly there are be no such inputs in the judge. Anyway, the constraints allow such inputs.

Hisoka · Post by **Hisoka** » Sun Sep 10, 2006 3:54 am

why n lg n algo get TLE > 10 s ? since T < 100 and n < 100001 ?

thanks

Hurricane_NET · Post by **Hurricane_NET** » Sun Sep 10, 2006 4:51 am

A program with complexity O(NlogN) and a relatively small constant factor will run well within the time limit...

sakhassan · Post by **sakhassan** » Sun Sep 10, 2006 7:38 am

Can neone give me some test cases which r critical ??

Sumon · Post by **Sumon** » Sun Sep 10, 2006 8:01 am

Hisoka wrote:why n lg n algo get TLE > 10 s ? since T < 100 and n < 100001 ?

thanks

Your program's worst case complexity = T*nlgn*C = 100*(lg100000)*100000*C=1.7*10^8*C,where C is cost of unit operation in each iteration. If this C is larger then there is no way of running within the time limit. I think this problem is not solvable with nlogn algo. I got accepted it with 2*n+K,where K is a small number and it took 7.141 Sec. So, you can compare your's complexity with mine to get the concept about the time required by your algo.

Hisoka · Post by **Hisoka** » Sun Sep 10, 2006 1:41 pm

Ouu, ic ... You can doing 2 N + K algo without sorting before ...

Thanks

sunny · Post by **sunny** » Sun Sep 10, 2006 3:23 pm

can u pls describe ur algo a little bit.

Martin Macko · Post by **Martin Macko** » Sun Sep 10, 2006 3:25 pm

Hisoka wrote:Ouu, ic ... You can doing 2 N + K algo without sorting before ...

Thanks

My algo sorts the numbers at the beginning and runs in about 8.7s.

little joey · Post by **little joey** » Sun Sep 10, 2006 4:22 pm

The real time bottle-neck is not the sorting of the input, but the reading of it in the first place.
My first attempt, using scanf() to read the input and using qsort() to sort it, took 5.5 seconds to read and 4.0 seconds to sort all of the judge input.

I feel sorry for Darko and all others that try to solve this problem in Java...

sclo · Post by **sclo** » Mon Sep 11, 2006 2:36 am

The only reason for sorting is to identify the duplicates, there are ways to do it without sorting.

vinay · Post by **vinay** » Mon Sep 11, 2006 2:04 pm

some hints please.......

Hadi · Post by **Hadi** » Mon Sep 11, 2006 5:24 pm

Only thing other than sorting that comes to my mind is Hashing. But I get WA with hashing. (I cannot use perfect hashing, i.e. a + 10000000 because I get TLE) , so I use a % some_prime_less_than_8000000).

Any suggestions?

sclo · Post by **sclo** » Tue Sep 12, 2006 12:18 am

hashing with a prime less than 10^6, with linked list resolving the collisions should work fine.