Collision means nothing
This problem has a trick. I could not do it during contest but later realized the trick.\n\n- The fact that the robots change directions at collision means noth
This problem has a trick. I could not do it during contest but later realized the trick.\n\n- The fact that the robots change directions at collision means nothing. We can just consider they switched IDs because at the end we really only care about the positions of the robots as a whole. We do not really care about *where robot number so and so is*. What this means is that we can solve the problem as if each robot is on its own track and the solution will still work. Here is an example. Consider the problem: `nums = [-2,0,2], s = "RLL", d = 3`. Then, with the robots changing directions, we have at the end `[-3,-1,1]` and without changing directions we will have `[1,-3,-1]`. Realize that both of these will give the same answer. \n\n- The second problem is how to calculate the sum of absolute differences in $O(n)$ time. We can sort the final array and then use a heuristic to find answer. Consider the final positions sorted array is `[a,b,c,d,e]`. Then we need to do `(4-0)e + (3-1)d + (2-2)c + (1-3)b + (0-4)a`. This is essentially `nums[i] * (i - (n-1-i))` which we can sum for all `i` to get the answer. \n\n- The third and final trick is that `int` does not work because of overflow issues. Use `long long` and even then you will need to apply `mod` at each step to get AC.\n\n\n```\nint sumDistance(vector<int>& nums, string s, int d) \n{\n    int n=nums.size(), mod=1e9+7;;\n    long long res = 0;\n    unordered_map<char,int> dirs {{\'L\',-1}, {\'R\',1}};\n    for (int i=0; i<n; i++) nums[i] += dirs[s[i]] * d;\n    sort(nums.begin(),nums.end());\n    for(int i=0; i<n; i++) \n    {\n        res += (long long)nums[i] * (2*i+1-n);\n        res %= mod;\n    }\n    return res;\n}\n```\n\nTC: $O(n\\log(n))$ because sorting is involved.
['Math', 'Simulation', 'C++']