(Sorry for the quite long e-mail)
You can try to think about Venn's Diagram
http://en.wikipedia.org/wiki/Venn_diagram
In a nutshell, for this case, realize 6 circles,
one that includes all numbers divided by 'a',
other that includes all numbers divided by 'b',
and so on, ending with the circle that includes
all numbers divided by 'f'. Now, visualize you
can have intersection between these circles,
these ones inform you which elements are
divisible by both of these circles, e.g. the
intersection of the first and the second circles
informs us which numbers are divided by both
'a' and 'b'. Let's assume, for simplicity, that all
of these numbers are relative prime.
Let's see now the subset corresponding to the
intersection of the first, second and fourth
circles. They'll inform us which numbers are
divided by 'a', 'b' and 'd', simultaneously.
Notice this subset is also included at the
intersection of ('a', 'b'), of ('a', 'd') and ('b', 'd')
subsets. Since they've been counted three times
and we only need one, we naturally subtract
two time the number of elements in the subset
('a', 'b', 'd').
In the end (I swear this'll look painful, but it'll
make some sense), let's see now the subset
corresponding to the 'a', 'b', 'd' and 'e' circles.
Naturally they'll inform which numbers are
divided by all of these 4 numbers. Notice that
the ('a', 'b', 'd', 'e') subset will appear in other
subsets, such as ('a', 'b', 'd'), ('a', 'b', 'e'),
('a', 'd', 'e') and ('b', 'd', 'e') subsets, which have
been subtracted (from previous steps).
You'll need to notice that you had subtracted it
4 times, 3 of those which have been
unnecessary subtractions, so you'll need to add
them back again, multiplied by three. You'll do
that again for subsets which include 5 circles and 6.
This is called Inclusion-Exclusion principle, it's
more explained online (a start up:
http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle ).
Well, for this problem, since you want all numbers less than k which
represent this is the same thing as wanting all numbers less or equal
to (k-1), and it's quite easy to know how many elements are in the
subset of each, for instance, of subset ('a', 'b'), the number of
elements inside of it is (k-1)/(a*b).
For this problem there are only two more issues to be
pointed out. First, it's natural that there aren't relative primes in
these sets. To solve that out, instead of the simple product of numbers,
you'll need to find the least common multiple of the numbers of each
subset (it's pretty easy to code this). Second, when you apply this
principle, realize if I have numbers of a single 'partition'
(either numbers only from ('a', 'b', 'c') or ('d', 'e', 'f')), I do not
need to
consider them at all, simply ignore it and go for the next step.
Having any doubts, please don't hesitate of asking or
looking at other sites :)
On 3 April 2012 05:18, vivek dhiman <[email protected]> wrote:
> Than you Igor.
> But can you explain the last addition..
>
>
>
> On Tue, Apr 3, 2012 at 12:09 AM, Igor Naverniouk <[email protected]>wrote:
>
>> Inclusion-Exclusion principle.
>>
>> Add all the numbers that are divisible by
>> - a and d
>> - a and e
>> - a and f
>> - b and d
>> - ...
>> - c and f
>>
>> Subtract all the numbers that are divisible by
>> - a, b and d
>> - a, c and d
>> - b, c and d
>> - ...
>> - c, e and f
>>
>> Add back all the numbers that are divisible by
>> - a, b, c and d
>> - ...
>> - c, d, e and f.
>>
>> ...
>>
>> igor
>>
>> On 2 April 2012 11:36, vivek dhiman <[email protected]> wrote:
>>
>>> Hi all smart people.
>>>
>>> if there are two set of numbers (both sets are of size 3)
>>> (a,b,c) and (d,e,f)
>>>
>>> given a number k, how will you count all numbers(n) < k that are
>>> divisible by both x and y
>>> where x is any number from set (a,b,c)
>>> and y is any number from set (d,e,f)
>>>
>>> remember you should take care of repetitions..
>>>
>>> Thing is I am doing this using sets and iterators which is taking much
>>> more time ..suggest some better approach ..
>>> No need to write code... just the approach..
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Google Code Jam" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/google-code?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Google Code Jam" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/google-code?hl=en.
>>
>
>
>
> --
> Regards
> Vivek Dhiman
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
