Integer Combinations Of Vectors
All submissions for this problem are available.
You are given a collection of n integer-valued vectors v1, v2, ..., vn (i.e. integer arrays) of some fixed dimension. An integer combination of these vectors is a vector of the form v = c1v1 + ... + cnvn where each ci is an integer. Here, the j'th component v[j] is precisely cv1[j] + ... + c[n]vn[j].
Define the length of a vector x = (x, x, ..., x[n]) to be the square root of x*x + x*x + ... + x[n]*x[n]. Your task is to find a short integer combination of vectors v1, ..., vn whose length is non-zero.
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 vi (i.e. vi[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 vi[j] ≠ 0.
Test cases are separated by a single blank line including a blank line preceding the first test case.
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 non-zero vector. That is, the vector must have positive length.
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
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.
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.
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 non-zero.
Other test data is generated by generating n-1 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.
|Tags||challenge friggstad oct10|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.