thanks a lot mat to many kudos to u ); On Sat, Apr 9, 2011 at 4:18 PM, Luke Pebody <[email protected]> wrote:
> See http://code.google.com/codejam/contest/dashboard?c=635101#s=a&a=2 > > On Sat, Apr 9, 2011 at 11:37 AM, Luke Pebody <[email protected]> > wrote: > > I have put a sample first effort of coding this at > http://ideone.com/Uu7ru . > > > > The central idea is that in order for a set of k elements to be pure > > for n, the initial sequence up to and including k must be pure for k. > > Therefore, if we know how many sets of any given size are pure for k, > > we can work out how many sets of k elements are pure for n. > > > > The programme here is extremely inefficient: it calculates the value > > of f(3,2) many many times. However, it is fast enough for the small > > case: http://ideone.com/acRHe. > > > > However, the large case needs something smarter: http://ideone.com/UyEnJ > > > > More to follow... > > > > On Sat, Apr 9, 2011 at 11:01 AM, Luke Pebody <[email protected]> > wrote: > >> Let us try and work out what the pure sets for 2-6 are: > >> > >> 2. In order for a subset of {2} to be pure for 2, 2 must be in the set. > Thus > >> the only pure set is {2}. This is pure for 2 because the index of 2 is > 1. > >> > >> 3. In order for a subset of {2,3} to be pure for 3, 3 must be in the > set. > >> The only possibilities are {3} and {2,3}. {3} is pure for 3 because the > >> index of 3 is 1. {2,3} is pure for 3 because the index of 3 is 2 and the > >> index of 2 is 1. > >> > >> 4. In order for a subset of {2,3,4} to be pure for 4, 4 must be in the > set. > >> The only possibilities are {4}, {2,4}, {3,4} and {2,3,4}. {4} is pure > for 4 > >> because the index of 4 is 1. {2,4} is pure for 4 because the index of 4 > is 2 > >> and the index of 2 is 1. {3,4} is NOT pure for 4, because the index of 4 > is > >> 2 which is not in the set. Finally {2,3,4} is pure for 4 because the > index > >> of 4 is 3, the index of 3 is 2 and the index of 2 is 1. Thus the pure > sets > >> are {4}, {2,4} and {2,3,4}. > >> > >> 5. In order for a subset of {2,3,4,5} to be pure for 5, 5 must be in the > >> set. Let us split into separate cases depending on the size of the set > >> (1-4). > >> > >> The only subset of {2,3,4,5} of size 1 that contains 5 is {5}. This is > pure > >> for 5, because the index of 5 is 1. > >> > >> In any subset of {2,3,4,5} of size 2 containing 5, the index of 5 is 2. > Thus > >> if the set is pure, it must also contain 2, and hence must be {2,5}. > This is > >> pure for 5 because the index of 5 is 2 and the index of 2 is 1. > >> > >> In any subset of {2,3,4,5} of size 3 containing 5, the index of 5 is 3. > Thus > >> if the set is pure, it must also contain 3, and hence must be {2,3,5} or > >> {3,4,5}. These are both pure for 5: in {2,3,5} the index of 5 is 3, the > >> index of 3 is 2 and the index of 2 is 1, whereas in {3,4,5}, the index > of 5 > >> is 3 and the index of 3 is 1. > >> > >> Finally the only subset of {2,3,4,5} of size 4 is {2,3,4,5} which is > pure > >> for 5. > >> > >> Thus the pure subsets of {2,3,4,5} are {5}, {2,5}, {2,3,5}, {3,4,5} and > >> {2,3,4,5}. > >> > >> 6. Once again the set must contain 6 and be of size 1-5. > >> > >> If size 1, the set must be {6}, which is pure. > >> > >> If size 2, the set must also contain 2 and therefore must be {2,6}, > which is > >> pure. > >> > >> If size 3, the set must also contain 3 and therefore must be {2,3,6}, > >> {3,4,6} or {3,5,6} which are all pure. > >> > >> If size 4, the set must also contain 4. Furthermore the intersection of > the > >> set with {2,3,4} must be pure for 4, and hence must be either {4}, {2,4} > or > >> {2,3,4}. Since the set is a subset of {2,3,4,5,6} containing 4 and 6 > with 4 > >> elements, it must be {3,4,5,6}, {2,4,5,6} or {2,3,4,6}. {3,4,5,6} is not > >> pure for 4, and hence is not pure for 6. The others are pure. > >> > >> Finally, if size 5, the set must be {2,3,4,5,6}. > >> > >> Thus there are 8 pure sets, {6}, {2,6}, {2,3,6}, {3,4,6}, {3,5,6}, > >> {2,4,5,6}, {2,3,4,6} or {2,3,4,5,6}. > >> > >> More to follow... > >> > >> > >> On 9 Apr 2011 09:02, "Cody" <[email protected]> wrote: > >>> Respected Members, > >>> > >>> Hey can any one give me an example how do we get 6 for 8 and for 25 > >>> can any one just explain me it in small if possible. > >>> > >>> http://code.google.com/codejam/contest/dashboard?c=635101#s=p2 > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "google-codejam" 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-codejam" 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 ,Prajay -- You received this message because you are subscribed to the Google Groups "google-codejam" 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.
