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.
