Interesting problem at work.

Revision en2, by Sazzon, 2017-01-17 04:04:58

Hi!

An interesting problem appeared at work today. I've managed to reduce the problem into what seems to be a solvable problem. Here it is:

Given an resultant array A of C elements and a list of N arrays, also with C elements. Is there a way to sum a subset of the N given arrays such that every element in the i-th position is summed with the element on the i-th position of the other array and result in the given array A? Let me give you an example:

C = 3

N = 6

A = {2,1,1}

N arrays:

1 = {1,0,1} 2 = {1,1,0} 3 = {1,0,1} 4 = {1,0,0} 5 = {0,1,1} 6 = {0,1,0}

The best answer is both 1 and 2 or 2 and 3. If we sum 1,0,1 + 1,1,0 = 2,1,1 or 1,1,0 + 1,0,1 = 2,1,1.

Have you ever came across a problem like this ? Is there any problem here in codeforces which has the same solution or editorial ? Do you know any technique that maybe useful for this purpose. If you have any input, please feel more than welcome to share.

Thank you in advance :-)

Tags subset sum

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Sazzon 2017-01-17 04:04:58 3 Tiny change: 'result in in the gi' -> 'result in the gi'
en1 English Sazzon 2017-01-17 04:04:08 1034 Initial revision (published)