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 :-)