Ball Bearing Collisions - A proposed New Problem
Back to General discussions forum
This problem is about keeping track of a very large number of collisions.
Thank you Clive, as it happens, it looks "not very complicated" at first... Let us some time to dive and see... :)
UPD: wow, I've done it - but it took more time and thinking - the puzzle is funny for it allows several approaches and the first I come upon was very good except it didn't allow calculating collisions!
Slightly longer code but it is possible to calculate results for all bearings in O(n) overall.
My first attempt was O(n*log(n)) and calculating positions/directions for all, but I failed to come up with idea how
to calculate collision count :(
Yes, the idea for positions comes quickly but the collision count approach is not as obvious or intuitive (at least to me).
I assume your O(n*log(n)) comes from sorting, but we all hopefully learnt here on CodeAbbey about the merge routine
from mergesort which allows O(n) for this problem.