|
|
back to boardNew problem is available to solve! 1399 "Economical Director" (-) Is it a joke? (+) "Your program will pass a test if it produces an answer that is no worse than the answer produced by the jury’s program for the same data"
Does it mean, that the author can not prove his solution? Or (more over!) he does not know correct solution, and the tests are generated by brute force... Clarification is required. Re: Is it a joke? (+) Yes, the hint is quite ambiguous and let's us understand that the author wants heuristic solutions.
So, I wonder, must our answer be optimal for an AC? Or just better then the author's solution? If they have not a solution, they cannot check whether it is optimal or not :) (-) Re: If they have not a solution, they cannot check whether it is optimal or not :) (-) Posted by it4.kp 3 Jan 2007 00:27 Why not?
For example, you have a value of some hash function crypt() (MD5 or smth) and the problem is to find a key such that crypt(key) is as close to the given value as possible. Then optimality checking is trivial but solution is very hard :) Re: Is it a joke? (+) Jury has not optimal solutions for tests. Answers for tests are outputs of jury's program that passes TL and ML. Validator checks the correctness of your output and compares it to the jury's answer. So your answer should be just better then the jury's one. "Better" or "not worse"? (+) The problem is really novel. If one cannot solve a problem, he may just add it to Timus, I will think about it ;)
Edited by author 03.01.2007 02:06 I tell about this very problem only (+) md5() is unidirectional, and this problem's effectiveness function is not. I think that to check the optimality is not easier than to find a solution (both problems seem to be NP, although I may be mistaken). Some words about this problem. The problem is obvious NP-hard, so to get optimal answers for all tests is not so easy. :) Try to create some heuristics. |
|
|
