Problem 1101. USC Fall 2012 ACM : Chemical Analysis

This Challenge is to solve Question D, Chemical Analysis, of the USC ACM Fall 2012 Contest.

Given an array M of Element Spectral signatures(m elements by n Spectra) and a Sample spectra of width n, determine the minimum number of elements that could generate the Sample's spectra.

Input: [ A, Sample ]

Output: min_elements;

The minimum number Components to create the Sample Spectra. If no combination exists then output 0.

The full USC data file

Input: [1 1 0 0;0 1 1 1;0 1 1 0;0 1 0 1], [1 1 0 1]

Output: 2 as [1 1 0 0] and [0 1 0 1] can create [1 1 0 1]

The Winning C solution is in the Test Suite to assist - not likely.