I-love-this-problem feel.
Intuition\n\nFirst time I was reading a part of the description about collisions, I thought to myself: "the collisions must be intuitive and there is no point i
# Intuition\n\nFirst time I was reading a part of the description about collisions, I thought to myself: "the collisions must be intuitive and there is no point in paying atention to them." \n\nInitially I thought that the right path is to notice, that before the collision there is one robot moving right and one robot moving left, and after collision the same is true. So that is an invariant and we are asked to find the sum of pairs and maybe this sum is going to be liniar with time as a parameter. `sum_of_dist=sum_of_dist(t)=const_0+const_1*t`. This way of thinking was not a path to accepted. And I was able to solve the problem only after returning to it in a few days. The key is collisions. \n\nThe phisics looks the same if there is no collisions and robots move through each other. I love this problem because it is very strange and gives me opportunity to think about _many things_. So what we have here is that one, let call it math formula, descript two different visual models. (the author) start with one visual model (from the nature) and ends up with formal description. (the reader) start with formal description and ends up with the other visual model that helps him to solve the problem. In some way movement is more abstract then identity of robots.\n\n# Approach\nImplementing is an easy part. Some people solved it in an algebraic manner: when all points are sorted, what is contribution of j? `(p[j]-p[j-1])+(p[j]-p[j-2])..`. And we can rearenge addends. My implementation is different: how often the length of segment `[p[j],p[j+1]]` is added in the total sum. This lenght will be added if we take left point of segment $$\\le$$`j` and right point of segment $$\\ge$$`j+1`. The combinations of that is $$(j+1)*(n-(j+1))$$ (\'choose left side\' multiply \'choose right side\'). \n\n# Complexity\n- Time complexity: $$O(n\\cdot log(n))$$ for sorting\n\n- Space complexity: $$O(n)$$ for vector of long long. By the way, do we need to use long long in problem where the final answer is taken by modulo? I mean the addition in \'machine\' is implemented in a way that max_int is followed by min_int, that is numbers are in cycle. So going out of range of int type might not lead to a wrong answer? \n\n# Code\n```\ntypedef long long i64;\nconstexpr i64 md{1000000007};\nclass Solution {\npublic:\n    int sumDistance(vector<int>& nums, string s, int d) {\n        vector<i64> a(nums.begin(), nums.end());\n        for(int i{}; auto& a : a)\n            a += (((s[i++]==\'R\')<<1)-1)*d;\n        sort(a.begin(), a.end());\n        d = {};\n        for(int i{}, n_minus_one{(int)a.size()-1}, r{n_minus_one}; i<n_minus_one; ++i, --r)\n            d = (d + (a[i+1]-a[i]) * (i+1) % md * (r)) % md;\n        return d ;\n    }\n};\n```
['C++']