11087 - Divisibility Testing

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

11087 - Divisibility Testing

Post by Martin Macko »

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

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

thanks

Hurricane_NET
New poster
Posts: 1
Joined: Wed Jun 21, 2006 10:17 am

Post by Hurricane_NET »

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

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan »

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

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

Post by Sumon »

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.
Change your view,your life will be changed.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

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

Thanks

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

can u pls describe ur algo a little bit.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

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

Post by vinay »

some hints please....... :cry: :oops:
If I will myself do hashing, then who will do coding !!!

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi »

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

Post Reply

Return to “Volume 110 (11000-11099)”