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.
