let us assume.. a,b,c are relative primes to each other and d,e,f are also relative primes to each other.
what happens in that case ? On Tue, Apr 3, 2012 at 5:23 PM, Renato Parente <[email protected]> wrote: > (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. > -- 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.
