Re: [algogeeks] spoj problem EASYMATH

[Wladimir Tavares]

Using KISS :)
http://en.wikipedia.org/wiki/KISS_principle

Ps: is not an offensive message


Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*




On Fri, Sep 28, 2012 at 6:17 PM, icy`  wrote:

> why not just brute force this?  one little array contains [a, (a+d),
> (a+2d), (a+3d), (a+4d) ], which is then filtered so that none of those are
> multiples of another.
>
> Then set a count variable to m-n+1.  Check all numbers in range against
> your little array, decrementing count and breaking out if a divisible num
> is found.  In Ruby, screenshot so that syntax highlighting remains.
>  (comments start with #  )
>
> [image: Inline image 1]
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

<>

Re: [algogeeks] spoj problem EASYMATH

[icy`]

why not just brute force this?  one little array contains [a, (a+d),
(a+2d), (a+3d), (a+4d) ], which is then filtered so that none of those are
multiples of another.

Then set a count variable to m-n+1.  Check all numbers in range against
your little array, decrementing count and breaking out if a divisible num
is found.  In Ruby, screenshot so that syntax highlighting remains.
 (comments start with #  )

[image: Inline image 1]

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

<>

Re: [algogeeks] spoj problem EASYMATH

[atul anand]

@Wladimir : you have to use  formula given in below link

http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

On Fri, Sep 28, 2012 at 12:26 AM, Wladimir Tavares wrote:

> what happens when a = 3, d = 5
> a, a + d, d +2, a +3 d = 3,8,13,18?
>
> Wladimir Araujo Tavares
> *Federal University of Ceará 
> Homepage  | 
> Maratona|
> *
>
>
>
>
>
> On Thu, Sep 27, 2012 at 8:57 AM, atul anand wrote:
>
>> @ashish : here is the generalized equation
>> http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
>>
>> note : you need to take LCM of a,a+d,a+2d etc etcwhenever you are
>> dividing to find count
>>
>> On Thu, Sep 27, 2012 at 2:55 AM, ashish pant wrote:
>>
>>> thanks for your reply.. actually i was thinking the same thing.. but I
>>> am facing problems in finding the unique multiples  of a+3d and a+4d as
>>> applying inclusion exclusion principle in this way is getting too difficult
>>> due to large no of factors to be added and subtracted.. is der any other
>>> approach or any way to simplify the process..
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[Wladimir Tavares]

what happens when a = 3, d = 5
a, a + d, d +2, a +3 d = 3,8,13,18?

Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*




On Thu, Sep 27, 2012 at 8:57 AM, atul anand  wrote:

> @ashish : here is the generalized equation
> http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
>
> note : you need to take LCM of a,a+d,a+2d etc etcwhenever you are
> dividing to find count
>
> On Thu, Sep 27, 2012 at 2:55 AM, ashish pant  wrote:
>
>> thanks for your reply.. actually i was thinking the same thing.. but I am
>> facing problems in finding the unique multiples  of a+3d and a+4d as
>> applying inclusion exclusion principle in this way is getting too difficult
>> due to large no of factors to be added and subtracted.. is der any other
>> approach or any way to simplify the process..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[atul anand]

@ashish : here is the generalized equation
http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

note : you need to take LCM of a,a+d,a+2d etc etcwhenever you are
dividing to find count

On Thu, Sep 27, 2012 at 2:55 AM, ashish pant  wrote:

> thanks for your reply.. actually i was thinking the same thing.. but I am
> facing problems in finding the unique multiples  of a+3d and a+4d as
> applying inclusion exclusion principle in this way is getting too difficult
> due to large no of factors to be added and subtracted.. is der any other
> approach or any way to simplify the process..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[ashish pant]

thanks for your reply.. actually i was thinking the same thing.. but I am
facing problems in finding the unique multiples  of a+3d and a+4d as
applying inclusion exclusion principle in this way is getting too difficult
due to large no of factors to be added and subtracted.. is der any other
approach or any way to simplify the process..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[atul anand]

EXAMPLE 1)

1 10 2 2

a,d=2
a,a+d,a+2d,a+3d,a+4d are all multiple of 2 , so basically you need to
count elements which are multiple of 2 and then subtract from the 1-10
range(inclusive)

number of elements multiple of of 2 = (m/2) = 10/2 = 5
range = ( m - n) + 1 = 10

number of elements not multiple of 2 = range -  5 = 10 - 5 = 5(ans)

EXAMPLE 2)

20 100 3 3

a,d=3

same as above case a,a+d,a+2d,a+3d,a+4d all are multiple of 3

number of elements multiple of of 3(1..to..100) = (m/2) = 100/3 = 33
now 33 includes elements which lies b/w 1-19 , but we dont want those count
so remove those count..

number of elements multiple of of 3(1..to..19) =(n-1)/2 = (19/2) = 6
desired count lies b/w range (20-100) = 33 - 6 = 27
range = ( m - n) + 1 = 81

number of elements not multiple of 3 = range -  27 = 81 - 27 = 54 (ans)

so we just applying general formula :-
n(A U B) =n(A) + n(B) - n(A intersection B)

but in above 2 examples both a and d were same or could be multiple of
each otherthis is a simple scenario .

EXAMPLE 3)

20 100 2 3
suppose a = 2 , d = 3
now i am considering only a and a+d ...just to give you the idea..
so we need to find elments b/w 20-100 not divisible by 2 and 5.

using same method as above :-
elements divisible by 2 = 41
elements divisible by 5 = 17
total elements = 41 + 17 = 58

but some number are include twice in 58 number which are multiple
of both 2 and 5 i.e once by calculating counts for 2 and another while
calculating count for 5.
eg 10 = 5 x 2 , 20 = 4 x 5...etc..

so now we want to remove these double inclusion i.e calculating n(A
intersecting B).

which is nothing but same as counting elements divisible by ( a X a+d
) i.e 2 X 5 =10
by same method :-

elements divisible by 10 = 9
correct count of elements in range (20-100) = 58 - 9 = 49

number of elements not multiple of 2 or 5 = 81 - 49 = 32 (ANS)

now i hope you got the idea

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[gaurav yadav]

an idea of the approach would be enough.. plz help..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] spoj problem EASYMATH

[gaurav yadav]

help needed in spoj problem EASYMATH .. i 
thought about inclusion exclusion principle but unable to get to a 
solution.. plz help..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/Zm2bwN2FHRQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[shady]

dont post codes, ask whether your algorithm is correct or not.

On Sun, Jun 24, 2012 at 8:29 PM, Hassan Monfared wrote:

> use " return (a/gcd(a,b)*b instead "
>
>
> On Sun, Jun 24, 2012 at 7:10 PM, Sourabh Singh 
> wrote:
>
>> please suggest something  :
>>
>> Problem :
>> http://www.spoj.pl/problems/EASYMATH/
>>
>> C++ code :
>> http://ideone.com/r2OSb
>> was getting wrong ans due to over flow i think in LCM() for big prime's i
>> guess.
>> thin tried in python .
>>
>> Now getting NZEC for python code which mean's high level or recurrsion
>> some where preventing
>> normal termination .
>> but where ??
>>
>> Python code:
>> http://ideone.com/KDPPJ
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] spoj problem EASYMATH

[Hassan Monfared]

use " return (a/gcd(a,b)*b instead "

On Sun, Jun 24, 2012 at 7:10 PM, Sourabh Singh wrote:

> please suggest something  :
>
> Problem :
> http://www.spoj.pl/problems/EASYMATH/
>
> C++ code :
> http://ideone.com/r2OSb
> was getting wrong ans due to over flow i think in LCM() for big prime's i
> guess.
> thin tried in python .
>
> Now getting NZEC for python code which mean's high level or recurrsion
> some where preventing
> normal termination .
> but where ??
>
> Python code:
> http://ideone.com/KDPPJ
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] spoj problem EASYMATH

[Sourabh Singh]

please suggest something  :

Problem :
http://www.spoj.pl/problems/EASYMATH/

C++ code :
http://ideone.com/r2OSb
was getting wrong ans due to over flow i think in LCM() for big prime's i guess.
thin tried in python .

Now getting NZEC for python code which mean's high level or recurrsion
some where preventing
normal termination .
but where ??

Python code:
http://ideone.com/KDPPJ

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.