[Python 3] Split the graph and separately count, graphically explained
Let\'s convert x and y to 0-indexed, and x < y.\n\nTrivial cases then are when x == y or x == y - 1, and no distances in the chain has changed. The answer is [(
Let\'s convert x and y to 0-indexed, and `x < y`.\n\nTrivial cases then are when `x == y` or `x == y - 1`, and no distances in the chain has changed. The answer is `[(n - 1) * 2, (n - 2) * 2, ..., 4, 2, 0]`.\n\nIf `x < y - 1`, example below, `n = 7, x = 2, y = 6` converts to 0-indexed `n = 7, x = 1, y = 6`. The new graph can be decomposed as the following\n\n![image.png](https://assets.leetcode.com/users/images/15c248cb-2c25-43b9-aecd-3ccb4c6e7c11_1705815584.3472571.png)\n\nFirst component is a new shorter chain, which is in fact the trivial case.\n\nSecond component is a circle. Pair count can be calculated as `[2 * t for i in range(m)]` where `t` is number of houses in the circle, and `m` is the half length of the circle, `ceil((y - x) / 2)`. Note to discount the `(x, y)` pair by the new road, which has been counted in the first component. Also note that when the circle has even number of nodes, the half length pairs are double counted as shown below, and we need to divide it by 2.\n \n![image.png](https://assets.leetcode.com/users/images/fcb6476c-7a3a-48d1-aeb5-5c0762ad34bc_1705816309.928046.png)\n\nNext, houses to the left of x, they can reach houses `x + 1` to `y - 1`. For `mid = (x + y) // 2`, the shortest path is to go through `x`, and for `mid + 1`, the shortest path is to go through the new road `x -> y -> y - 1 ... -> mid + 1`.\n\nEach houses `0` to `x - 1` will form `mid - x` pairs with the houses `x + 1` to `mid`. As we move 1 step toward x, distances of these pairs bulk decrease by 1. We use differential array to calculate their contirbutions, refer to `fun(x, m, padding)` for details. \n\n```\n                     x       mid\nE.g.          [0, 1, 2, 3, 4, 5   ]\n\n    distance:     1  2  3  4  5  6\ncount of pairs:\n0 to 3/4/5:       0  0  2  2  2\n1 to 3/4/5:       0  2  2  2  0\ndiff due to 0:    0  0  2  0  0  -2\ndiff due to 1:    0  2  0  0  -2\naccumulated diff: 0  2  4  4  2  0           \n```\n\nOne caveat is that when taking the new road to reach `mid + 1`, we need a padding of 1 in the differential array, same reason the `(x, y)` pair should not be counted again.\n\n```\n                    x        mid+1   y\nE.g.         [0, 1, 2       5, 6, 7, 8]\ndistance:  1  2  3  4  5  6\ncount of pairs:\n0 to 7/6:  0  0  0  2  2  0\n1 to 7/6:  0  0  2  2  0  0\ndiff by 0: 0  0  0  2  0  -2\ndiff by 1: 0  0  2  0  -2 0\nacc. diff: 0  0  2  4  2  0\n```\n\nFor houses to the right of y can be handled similarly, since they are like mirror relection of houses to the left of x.\n\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        def fun(x, m, padding):\n            res = [0] * (m + 1)\n            for i in range(x):\n                res[x + padding - i] += 2\n                res[m - i] -= 2\n            res = list(accumulate(res))\n            for i in range(m):\n                ans[i] += res[i]\n                    \n        x, y = min(x, y), max(x, y)\n        x -= 1\n        y -= 1\n        \n        if abs(x - y) > 1:\n            ans = [0] * n\n            # new road formed by connection x and y, bypassing x + 1 to y - 1\n            # the (x, y) pair by the new road is counted here\n            m = n - (y - x - 1)\n            res = [i * 2 for i in range(m)][::-1]\n            for i, v in enumerate(res):\n                ans[i] += v\n            # the circle x, x + 1, ..., y - 1, y back to x\n            # note 1: discount (x, y) pair by the new road\n            # note 2: if number of houses is odd in the circle, divide the count of\n            #         m - 1 roads by 2, since double counting\n            t = y - x + 1\n            m = ceil((y - x) / 2)\n            res = [2 * t for i in range(m)]\n            res[0] -= 2 # discount the additional road x, y, double counted\n            if (y - x) & 1:\n                res[-1] //= 2\n            for i, v in enumerate(res):\n                ans[i] += v\n            # \n            mid = (x + y) // 2\n            # node [0 to x - 1], going thru x, then to mid\n            fun(x, mid, 0)\n            # node [0 to x - 1], going thru x, then y, then back to mid + 1\n            if mid + 1 < y:\n                fun(x, x + 1 + y - (mid + 1), 1)\n            # node [n - 1 to y + 1], going thru y, then to mid + 1\n            fun(n - 1 - y, n - 1 - mid, 0)\n            # node [n - 1, to y + 1], oging thru y, then x, then forward to mid \n            if mid - 1 > x:\n                fun(n - 1 - y, n - y + mid - 1 - x, 1)\n            return ans\n        else:\n            # trival case, new road does not change distances\n            return [i * 2 for i in range(n)][::-1]\n```
['Python3']