Integer Combinations Of Vectors

All submissions for this problem are available.
You are given a collection of n integervalued vectors v_{1}, v_{2}, ..., v_{n} (i.e. integer arrays) of some fixed dimension. An integer combination of these vectors is a vector of the form v = c_{1}v_{1} + ... + c_{n}v_{n} where each c_{i} is an integer. Here, the j'th component v[j] is precisely c[1]v_{1}[j] + ... + c[n]v_{n}[j].
Define the length of a vector x = (x[1], x[2], ..., x[n]) to be the square root of x[1]*x[1] + x[2]*x[2] + ... + x[n]*x[n]. Your task is to find a short integer combination of vectors v_{1}, ..., v_{n} whose length is nonzero.
Input
The first line contains a single integer T ≤ 30 indicating the number of test cases to follow. Each test case begins with two integers n and d, both between 1 and 100, where n is the number of vectors in the test case and d is their common dimension.
Then n lines follow, each containing d integers. The j'th number on the i'th line is the j'th component of vector v_{i} (i.e. v_{i}[j]). Every such integer is between 100 and 100 (inclusive). None of the input vectors will be a zero vector. This means that for each i, at least one j is such that v_{i}[j] ≠ 0.
Test cases are separated by a single blank line including a blank line preceding the first test case.
Output
For each test case, you are to output a single line consisting of n integers where the i'th integer is the value of the coefficient c[i] in some integer combination of the input vectors. The value must satisfy 100 ≤ c[i] ≤ 100.
Furthermore, the integer combination of the input vectors using these coefficients must produce a nonzero vector. That is, the vector must have positive length.
Example
Input: 2 2 1 14 35 4 5 1 4 1 2 5 1 2 3 4 5 0 1 2 3 7 1 2 3 4 5 Output: 3 1 1 0 1 0
Scoring
The score for a test case is the length of the integer combination as given by the output coefficients divided by the length of the shortest input vector. The total score for the entire data set is simply the sum of the scores of the individual test cases.
Example
The integer combination represented by the output in the first test case is 3*(14) + 1*(35) = (7). The length of the vector (7) is simply 7. The length of the shortest vector in the input is 14 so the score for this case is 0.5.
The integer combination represented by the output for the second test case is 1*(1,4,1,2,5) + 1*(0,1,2,3,7) = (1,3,1,1,2). The length of this is the square root of 1*1 + 3*3 + 1*1 + 1*1 + 2*2 = 16, so the length is 4. The shortest vector in the input is the first one having length equal to the square root of 1*1 + 4*4 + 1*1 + 2*2 + 5*5 = 47 which is roughly 6.855. Thus, the score for the second case is 4/6.855 = 0.5835.
Input Distribution
Some of the test data is randomly generated by simply selecting values for the components of the vectors uniformly at random in the range 100 to 100 and keeping the vector if it is nonzero.
Other test data is generated by generating n1 of the vectors as above, computing a random integer combination of these vectors and then creating the final vector so that subtracting it from the random integer combination results in a very short vector. This final vector may be any of the n vectors in the input.
Author:  friggstad 
Tester:  anshuman_singh 
Editorial  http://discuss.codechef.com/problems/INTCOMB 
Tags  challenge friggstad oct10 
Date Added:  8092010 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 