| Submit | All submissions | Best solutions | Back to list |
|
Problem hidden on 2014-01-01 08:39:11 by Mitch Schwartz
ERRORMIN - Error Minimization |
In this problem, you have to reverse an algorithm. The known algorithm takes inputs A and C, and produces output B. Your task will be to take A and B as inputs, and produce C.
The known algorithm can be expressed several ways:
As a mathematical expression: |
As a repeating pattern: B[0] = A[0] * C[0] B[1] = A[0] * C[1] + A[1] * C[0] B[2] = A[0] * C[2] + A[1] * C[1] + A[2] * C[0] B[3] = A[0] * C[3] + A[1] * C[2] + A[2] * C[1] + A[3] * C[0] B[4] = A[0] * C[4] + A[1] * C[3] + A[2] * C[2] + A[3] * C[1] + A[4] * C[0] B[5] = A[0] * C[5] + A[1] * C[4] + A[2] * C[3] + A[3] * C[2] + A[4] * C[1] + A[5] * C[0] ... |
As a program: for(int iB = 0; iB < len; iB++) {
for(int iC = 0; iC < len; iC++) {
B[iB + iC] += A[iB] * C[iC];
}
}
|
When you produce a solution (C), you can check your work by running the known algorithm on it, and the output value (B) will be called Bprime. If B equals Bprime, then your program is working.
However, errors will be introduced into B, such that it is impossible to produce a matching Bprime. In that case, your program must find the closest match. Here is the criteria for a success:
- When given perfect inputs, B must match Bprime exactly.
- The sum of the deltas between B and Bprime (sum(B[n] - Bprime[n])) must equal zero:
- The sum of the differences between B and Bprime (sum(abs(B[n] - Bprime[n]))) must be as low as possible:
Your score is the sum total of the errors between B and Bprime during it's test. The goal is to get as low a score as possible.
Notes:
- The lengths of arrays A, B and C are the same.
- The arrays are floating point numbers.
Input
Each request is sent in two lines; each of the values for A separated by spaces, and each of the values for B separated by spaces. More than one request will be made.
Output
Your program must output the value for C on one line, separated by spaces, in response to each pair of input lines.
Example
Input: 1 2 0 1 0 0 5 10 1 7 0 1 0 1 0 1 0 0 0 0 0 1 0 -1 0 0 0 1 0 1 0 0 0 0 0 0.5 0 1 0 0 Output: 5 0 1 0 0 0 0 0 0 0 0 0 0 0 0.75 0 0 0 0 0
All source code submitted for this problem must be free of intellectual property restrictions, and becomes the intellectual property of Michael Mudge.
The longest input array is no more than 50 entries.
| Added by: | Michael Mudge |
| Date: | 2008-01-13 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C CSHARP CPP C99 JAVA |
hide comments
|
2014-01-01 08:38:22 Mitch Schwartz
I feel it goes against the spirit of SPOJ to set a problem with the aim of taking legal ownership of contestants' ideas for personal gain. You may disagree, but I think it's not really that far off from writing e.g. "Any user wishing to submit to this problem must send $5 to [problem setter's email address], otherwise his submissions will be disqualified". This problem is now hidden. Last edit: 2014-01-01 09:16:50 |
|
|
2013-02-03 23:36:30 Mitch Schwartz
"All source code submitted for this problem must be free of intellectual property restrictions, and becomes the intellectual property of Michael Mudge." Should this be allowed on SPOJ? I haven't seen such a notice for any other problem. I guess it's part of why there are so few submissions. |
|
|
2012-03-09 14:16:01 Michael Mudge
Maximum array length is less than 50. "0 1 0 -2 0 2 0" probably IS a better answer than "0 0 0 0 0 0 0". The example output is not optimal. I didn't realize it at the time - I was impressed to see solutions with a better score than the example. |
|
|
2012-03-09 14:12:03 [[soup_boy]]
Specify array Length ! ! |
|
|
2012-03-09 14:12:03 Hagen von Eitzen
Why isn't "0 1 0 -2 0 2 0" a better answer than "0 0 0 0 0 0 0" for test case 2? Must we have all B[n]=0 for n > len? |
|
|
2012-03-09 14:12:03 Devil D
what is the maximum length if the values of the arrrays |
RSS