THECODE - Subset with all Digits
Given a list of n d-digit numbers, choose the smallest subset from the list that covers all the digits [0 - 9].
Input
First line contains a positive integer T representing number of test cases.
Next line contains two numbers n and d, where n is the size of the list and d is number of digits in each number.
Next n lines follow each containing a d digit number made from [0 - 9].
1 ≤ t ≤ 100
1 ≤ n ≤ 1000
1 ≤ d ≤ 1000
Output
Output the length of the smallest subset that covers all digits [0 - 9]. Return -1 if not possible.
Example
Input: 2 4 5 01234 56789 01456 13452 4 5 11234 56789 01456 13452 Output: 2 3
Explanation
Smallest set will be {01234, 56789}
Smallest set will be {11234, 56789, 01456}
hide comments
Rafail Loizou:
2023-08-21 19:58:20
@tech_addict Not to spoil anything but it would be good to add the DP tag. Many people search problems by their tags. If you think this spoils the answer then just delete my comments. IMO it doesn't that's why I wrote the comment. |
|
offamitkumar:
2020-06-24 14:41:17
is it possible that two numbers are same? |
|
ak18shay:
2019-08-24 16:14:00
any can you please give me few test cases? |
|
nadstratosfer:
2019-07-15 00:58:35
I don't know how to solve this optimally, but I've tried what I could and got AC. Thanks for setting the constraints that make it possible, will probably learn a lot from this. Appears to be a rare concept for a SPOJ problem to be based on.
|
Added by: | Kriti Joshi |
Date: | 2019-07-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |