An associative week

TopCoder SRM 662 took place this week (problems, results, top 5 on the left). With just under 600 competitors, this was the lowest attendance for a TopCoder SRM since SRM 307 which happened more than nine years ago. Of course, the starting time at 3am in Europe and 4am in Russia wasn't exactly helpful.

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!