Does anyone think it is possible to meet the performance requirements with clojure? It seems not, given that no one has even come close. I have an algorithm that is O(nlogn) to initialize, and basically O(1) for each query and update. I know, technically it has to be at least O(logn) but the coefficient seems small enough that for the sizes here the performance is relatively constant across all the tests.

I agree with @paulpach... it's an interesting challenge to find the right algo and learn about "mutable" structures in clojure. Would be more interesting if it was known to be solvable!

Use Integer instead of Int to store lcm

The Electrolux EWMED70JIW has it. It's also a confirmed winner: this is the fourth year in a row Electrolux has won this award. Many customers prefer a pinnacle-loading speed queen consumer reports washing gadget, and GE's all-new GTW680BSJWS is the first-class you can buy.

Just completed this after around 2 weeks of attempts, I used @paulpach's hint and that jump-started me for sure, but, like many of you, I was still timing out.

Because there's so much going on behind the scenes in these functional languages (namely haskell as that's what I used), it's hard to tell what the actual slowing factor is, so to maybe help a few of you I'll give a tip.

The tip is: if you have a slow yet working solution following @paulpach's hint, then try and focus on simplifying your structures. Try and simplify things down until you have as much personal control as possible over operations on those structures. Optimizing the smaller operations as much as possible could mean the difference between 40 seconds and 4 seconds just by the fact that they're used so much during the longer test cases.

Hope this helps (and also hope this doesn't help too much that I spoiled it)

I enjoyed this challenge. It took me a few days to come up with the right algorithm. In the process I learned to use mutable arrays in haskell, I learned a lot about lcm, gcd and module.

For all of you struggling: YES there is a solution that does not timeout in haskell.

My first try was the intuitive one: put all the values in an array, in every step either update the array or walk the array accumulating the lcm. This algorithm is O(1) for updates and O(n) for queries (assuming O(1) for lcm which is not true). This algorithm times out in several test cases.

My second try was to factorize the numbers and calculate the lcm by combining factorized numbers. The basic algorithm of storing the numbers an an array and either update them or calculate lcm of the range is the same. This algorithm is not faster than the previous one.

However, and this is a big tip: there is a way to do updates in O(log(n)) and queries in O(log(n)).