thanks mate On Apr 9, 3:48 pm, Luke Pebody <[email protected]> wrote: > Seehttp://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 athttp://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.
