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.
