Nevertheless, the problemsetter cgy4ever and the admins have once again prepared very nice problems for everybody to solve. The hardest problem was not solved by anybody: you want to define an associative (but not necessarily commutative or inversible) binary operation on N elements, and have already decided what should be the results of applying the operation when the first argument is some fixed element X and the second argument is any of the N elements. Is there a way to define the rest of the operation to make it associative?
I haven't solved this problem myself yet, so I will try to at least share my approach. Given a formal set of constraints, we should try to see what can we derive from those constraints. Since we know the result of X*Y for all Y, and know that the operation is associative, we can look at (X*X)*Y=X*(X*Y) and learn the result of (X*X)*Y for all Y. In the same manner, we know the result of the operation if the first argument is X*X*...*X. If the data filled so far already leads to a contradiction, or to a non-associativity, then there's no solution. But can you see what should we do if there's no contradiction?
If I were solving this problem myself during the round, I would probably try to add some heuristic to define the remaining elements of the multiplication matrix, then implement a random testcase generator and see where the solution fails, hoping to obtain some more intuition about the problem.
Thanks for reading, and check back next week!
If I were solving this problem myself during the round, I would probably try to add some heuristic to define the remaining elements of the multiplication matrix, then implement a random testcase generator and see where the solution fails, hoping to obtain some more intuition about the problem.
Thanks for reading, and check back next week!
0 komentar:
Post a Comment