[Java/C++/Python] Burning Points
Intuition\nFor each start point i where 1 < i < n,\nit will spread in 2 directions.\nThen there will be 2 points at the same time, with same distance to i\n\nTh
# **Intuition**\nFor each start point `i` where `1 < i < n`,\nit will spread in 2 directions.\nThen there will be 2 points at the same time, with same distance to `i`\n\nThe idea is to count the spreading points.\nYou can imagine the graph is a connnected rope,\nand we burn at the point of `i`,\nwe count how many points are burning.\n<br>\n\n# **Explanation**\n`A[t]` means at `time = t`,\nthe diff change of burning point is `A[t]`.\n\nInitially, it starts to burn on the left and on the right:\nWhen it reach 1, deadend then stop.\nWhen it reach n, deadend then stop.\nWhen reach `x`, it split one more from `x` to `y`\nWhen reach `y`, it split one more from `y` to `x`\nWhen go from `x` to `y` then go to the middle, it will stop in middle.\nWhen go from `y` to `x` then go to the middle, it will stop in middle.\n\nIn the end,\nwe aacumulate the prefix sum,\nthen we have the result to return.\n<br>\n\n# **Complexity**\nTime `O(n)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public long[] countOfPairs(int n, int x, int y) {\n        if (x > y) {\n            int t = x; x = y; y = t;\n        }\n        long[] A = new long[n];\n        for (int i = 1; i <= n; ++i) {\n            A[0] += 2;                                             // go left and right\n            A[Math.min(i - 1, Math.abs(i - y) + x)]--;             // reach 1 then stop\n            A[Math.min(n - i, Math.abs(i - x) + 1 + n - y)]--;     // reach n then stop\n            A[Math.min(Math.abs(i - x), Math.abs(y - i) + 1)]++;   // reach x then split\n            A[Math.min(Math.abs(i - x) + 1, Math.abs(y - i))]++;   // reach y then split\n            int r = Math.max(x - i, 0) + Math.max(i - y, 0);\n            A[r + (y - x + 0) / 2]--;                              // i -> x -> y <- x\n            A[r + (y - x + 1) / 2]--;                              // i -> y -> x <- y\n        }\n        for (int i = 1; i < n; ++i)\n            A[i] += A[i - 1];\n        return A;\n    }\n```\n\n**C++**\n```cpp\n    vector<long long> countOfPairs(int n, int x, int y) {\n        if (x > y) swap(x, y);\n        vector<long long> A(n);\n        for (int i = 1; i <= n; ++i) {\n            A[0] += 2;                               // go left and right\n            A[min(i - 1, abs(i - y) + x)]--;         // reach 1 then stop\n            A[min(n - i, abs(i - x) + 1 + n - y)]--; // reach n then stop\n            A[min(abs(i - x), abs(y - i) + 1)]++;    // reach x then split\n            A[min(abs(i - x) + 1, abs(y - i))]++;    // reach y then split\n            int r = max(x - i, 0) + max(i - y, 0);\n            A[r + (y - x + 0) / 2]--;                // i -> x -> y <- x\n            A[r + (y - x + 1) / 2]--;                // i -> y -> x <- y\n        }\n        for (int i = 1; i < n; ++i)\n            A[i] += A[i - 1];\n        return A;\n    }\n```\n\n**Python**\n```py\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        x, y = min(x, y), max(x, y)\n        A = [0] * n\n        for i in range(1, n + 1):\n            A[0] += 2 \t\t\t\t\t\t\t\t\t# go left and right\n            A[min(i - 1, abs(i - y) + x)] -= 1 \t\t\t# reach 1 then stop\n            A[min(n - i, abs(i - x) + 1 + n - y)] -= 1 \t# reach n then stop\n            A[min(abs(i - x), abs(y - i) + 1)] += 1 \t# reach x then split\n            A[min(abs(i - x) + 1, abs(y - i))] += 1 \t# reach y then split\n            r = max(x - i, 0) + max(i - y, 0)\n            A[r + (y - x + 0) // 2] -= 1 \t\t\t\t# i -> x -> y <- x\n            A[r + (y - x + 1) // 2] -= 1 \t\t\t\t# i -> y -> x <- y\n        return list(accumulate(A))\n```\n
['C', 'Python', 'Java']