Lot of maths and accumulated arrays | python
Intuition\nThe problem has only one cycle, so I thought about dividing the line of houses into three groups: the ones inside the cycle, the ones to the left, an
# Intuition\nThe problem has only one cycle, so I thought about dividing the line of houses into three groups: the ones inside the cycle, the ones to the left, and the ones to the right.\n\nWith this in mind, the next step was to derive all the formulas to calculate the distances. A lot of math is coming!\n\n# Approach\n\nLet\'s divide the houses into three groups:\n- Group $C$: the houses between $x$ and $y$ (we\'ll assume $x < y$ for simplicity).\n- Group $L$: the houses before $x$.\n- Group $R$: the houses after $y$.\n\nNow, we need to calculate the distances between any pair, but with three groups, we need the distances between:\n- All pairs inside Group $C$.\n- All pairs inside Group $L$.\n- All pairs inside Group $R$.\n- All houses in $L$ to all houses in $R$.\n- All houses in $L$ to all houses in $C$.\n- All houses in $R$ to all houses in $C$.\n\nOf course, it seems like a lot of work, and indeed it is, but actually, there are only 4 calculations to do because some of those cases are equivalent with other parameters. So, let\'s work on those calculations.\n\n# All distances inside a cycle\n\nFirst, all the distances inside a cycle. For that, we can test on paper and observe the pattern. For example, for an arbitrary start node in a cycle of length $6$, we have the following distances: \n\n$1, 2, 3, 3, 2, 1$\n\nThis is in the case of an even length of the cycle; otherwise, it will be (for example, for a length of $5$):\n\n$1, 2, 3, 2, 1$\n\nBut getting all the distances is not exactly useful; instead, we need the frequency of the distances, which can be seen as (1-indexed):\n\n$2, 2, 2$ and $2, 2, 1$. This pattern is the same for every length just depending of the parity and the number of different distances is $\\lfloor\\frac{LenC+1}{2}\\rfloor$.\n\n$[2,2,2,2,\\dots 1/2]$\nAnd since we have $LenC$ nodes inside a cycle we just multiply the frequency array by $LenC$ this because all the nodes are equivalent then the final frecuency array seems like.\n\n$[2\\times LenC,2\\times LenC,2\\times LenC,2\\times LenC,\\dots 1/2 \\times LenC]$\n# All distances inside $L$ or $R$\n\nThis is easier and can be observed with a few tests on paper. It just a line without cycles and the answer will be (as a frequency array):\n\n$[L-1, L-2, L-3, L-4, \\dots]$\n\n# All distances between $L/R$ and $C$\n\nThis case might seem hard, but actually, we can use the same approach as the case inside the cycle. Just add $1, 2, 3, \\dots, L/R$ extra steps to reach $x$ or $y$ in the case of $R$ and then use the calculations for all distances inside the cycle and seems like .\n\n$1, 2, 2, 2, 2, 2, \\dots 1$ for the case of cycle of length even\n$1,2,2,2,2,2,2 \\dots 2$ in odd cycle. \n\nYou can see that apart from the first $1$, it is the same case as inside a cycle for just one node, just moved to the right. We add a distance of length $1$ for the case $a \\rightarrow x$, where $a$ is the rightmost house in $L$ or the closest to $x$.\n\n\nBut since we have $L$ or $R$ elements to pair, we need to move the window to the right to take in mind the steps to reach $x/y$ for example for the second closer to $x/y$ the frequency array will be: \n$[0 , 1,2,2,2,2\\dots 1/2]$\nThen for the third closer. \n$[0,0,1,2,2,2,2\\dots,1/2]$\n$\\vdots$\n\n\n# All distances between L and R\n\nThis case is also straightforward. We omit the cycle and take two steps more, or one in the case of $x == y$. We calculate the frequency array for each element in $L$ from the closest to $x$ to the farthest. For example, for the closest element to $x$, the frequency array looks like:\n\n$[0, 0, 1, 1, 1, 1, 1, 1, \\dots, 0]$\n\nThe number of ones is equal to the length of $R$ and starts at $1$ or $2$ depending on whether $x == y$. \n\nThe last array is for the closest house to $x$. Then we need to do the same for the second, third, until the $L$-th closest to $x$:\n\n$[0, 0, 0, 1, 1, 1, 1, \\dots, 0]$\n\n$[0, 0, 0, 0, 1, 1, 1, \\dots, 0]$\n\n$\\vdots$\n\n\nFinally, we need to keep in mind that the solution is about testing and identifying the patterns for each case. However, since we need the frequency of all distances, updating the answer for each case and for each element inside each group is not possible. Instead, we need to use accumulated arrays and the +1/-1 trick to update the answer efficiently and avoid TLE.\n\n\n# Complexity\n- Time complexity:\n$O(n)$\n\n\n# Code\n```python\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        if x>y: \n            (x,y) = (y,x)\n            \n        def insideCycle(lenCycle):\n            frequencies = [0]*n\n            for i in range((lenCycle-1)//2): \n                frequencies[i]+=2*lenCycle\n                \n            if lenC&1==0: \n                frequencies[(lenCycle-1)//2]+=lenCycle\n\n            return frequencies\n            \n        def insideLR(length):\n            frequencies = [0]*(n*2)\n\n            for i in range(length-1):\n                frequencies[i]+=(length-1-i) * 2\n            return frequencies[:n]\n            \n        def LRtoCycle(lengthSegment,lengthCycle):\n            frequencies = [0]*(n*2)\n            for i in range(lengthSegment):\n                frequencies[i+1]+=4\n                if lengthCycle%2==0: \n                    frequencies[i+(lengthCycle//2)]-=4\n                    frequencies[i+(lengthCycle//2)]+=2 \n                    frequencies[i+1+(lengthCycle//2)]-=2 \n                    \n                else:\n                    frequencies[i+1+(lengthCycle//2)]-=4\n\n                frequencies[i]+=2\n                frequencies[i+1]-=2\n\n            return list(accumulate(frequencies))[:n]\n\n\n        def LtoR(lengthL,lengthR):\n            frequencies = [0]*(n*2)\n            for i in range(lengthL):\n                if x== y: \n                    frequencies[i+1]+=2\n                    frequencies[i+1+lengthR]-=2 \n\n                else: \n                    frequencies[i+2]+=2\n                    frequencies[i+2+lengthR]-=2 \n\n            return list(accumulate(frequencies))[:n]\n        \n        lenC = y-x + 1\n        L = x-1\n        R = (n-y)\n        \n        ans = [0]*n\n        ans = list(map(add, ans, insideCycle(lenC)))\n        ans = list(map(add, ans, insideLR(L)))\n        ans = list(map(add, ans, insideLR(R)))\n        ans = list(map(add, ans, LRtoCycle(L,lenC)))\n        ans = list(map(add, ans, LRtoCycle(R,lenC)))\n        ans = list(map(add, ans, LtoR(L,R)))\n        return ans\n            \n            \n            \n```
['Python3']