DMOPC '14 Contest 3 P5 - Not Enough Servers!

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Amagi Brilliant Contests runs a business making and hosting contests on its online platform for competitive programmers who want to run their own contests.

On their most recent contest, submissions were queued for unreasonably long times. The investigation that followed concluded that ABC needs to acquire more servers for their next contest. However, since ABC is not doing so well, they have no money to buy new servers with. Instead, the management has decided to cut out some test cases from the problems.

Cutting out test cases is a process that needs to be handled with care. The process involves removing a subset of test cases from the original M cases of a problem (numbered from 1 to M). The test cases that are left have to satisfy three conditions:

  1. All users who would have gotten AC for all cases should still get AC for all cases with the new test cases.
  2. All users who would not have gotten AC for all cases should not get AC for all cases with the new test cases.
  3. There should be at least 1 test case.

Amagi Brilliant Contests has collected some data from N problem testers on a problem they're planning to use on their next contest. Each tester submitted exactly one submission, and the verdict for each test case of a submission will either be O for AC or X for anything other than AC. Amagi Brilliant Contests believes that the data from these submissions should represent real contestants to a reasonable degree.

You are the head of the quality assurance department at Amagi Brilliant Contests, and so you have been tasked with selecting a minimal sized set of test cases such that they satisfy the three conditions above.


There will be a number of subtasks for this problem:

Test Case BatchPoints (%)Constraints
1201 \le N \le 10
M = 3
2101 \le N \le 20
1 \le M \le 15
Additionally, each submission will have exactly 1 test case where it did not receive an AC verdict.
3101 \le N \le 15
1 \le M \le 15
4101 \le N \le 20
1 \le M \le 20
5151 \le N \le 20
1 \le M \le 35
6351 \le N \le 20
1 \le M \le 50

Input Specification

The first line of input will have N, M separated by a single space.

The next N lines will each contain the results of a single submission.

The i^{th} character (the first character has index 1) of each of these lines will be O if test case i received an AC verdict; otherwise it will be X. There are no spaces between the characters.

Output Specification

The first line of output should be the minimal number of test cases to keep in the final set of test cases, T.

The second line of output should consist of T space-separated pairwise distinct integers between 1 and M, inclusive, the set of test cases to keep in the final set of test cases. If there are multiple possible solutions, you may output any of those. The numbers of test cases to keep may be listed in any order.

Your score for a test case will be

  • 0, if your output is formatted incorrectly or the T is incorrect
  • 40% of the full marks, if the first line of output, T, is correct, but the rest of the output is either formatted incorrectly or incorrect
  • 100% of the full marks, if the first line of output, T, is correct and the second line of output is a correct final set of test cases

Sample Input 1

2 4

Sample Output 1


Explanation for Sample Output 1

Both submissions should not get AC, and test case 4 is successful in failing both submissions.

Sample Input 2

2 4

Sample Output 2


Explanation for Sample Output 2

Since the first submission should get AC and the second submission should not, choosing the first test case will pass the first submission and fail the second submission. Another valid solution is choosing the fourth test case.

Sample Input 3

3 4

Sample Output 3

2 4

Explanation for Sample Output 3

Choosing cases 1 and 2 is also a valid solution. (1, 2) and (2, 4) are the only two valid solutions.


There are no comments at the moment.