T23 - Editorial

general
,
1

PROBLEM LINK:

[Contest] T23

Author: Nandishwar Garg

DIFFICULTY:

SIMPLE

PROBLEM:

You are given an array of size N. You have to find every possible subset of the elements in array. Then we have to check 3 conditions on these subsets:

  1. It should not be empty.
  2. It should not have any element in subset which divide other elements present in subset except 1.
  3. It should not have duplicate elements.

If it satisfies all the conditions then print yes otherwise print no.

EXPLANATION:

Suppose the array elements are 1,2 and 3. The subsets of these elements are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

  1. None of these subsets are empty
  2. No element other than 1 is dividing another element
  3. No duplicate element is present.

So, you have to print yes.

Taking another example, the array elements are 2 and 4. The subsets of following elements are {2}, {4} and {2,4}.

  1. None of these subsets are empty
  2. In {2,4}, 2 is dividing 4 so it doesn’t satisfy the condition

Thus you have to print no as the output.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here

2

Atleast check the content before posting at the forum,

Editorial is 15 days late and the author’s solution link is pointing at some admin page.

plz fix the link and let us know.

3

Direct link to practice page

Note that the test set does not check that an input array consisting of only the value 1 should give an answer of YES. Any other single-value array should give NO.

This editorial doesn’t actually take the analysis of the problem any further than the problem statement.

As a hint: for a “good subset” to exist, there cannot be a common factor >1 to all elements of A. And if there is no such common factor, a version of A with duplicates removed(/ignored) will constitute a good subset.