Houses, streets, minimal paths
Intuition\nFirst intuition was to solve the problem with graphs and depth first search with some optimizations like ending recursion when minimum was found. The
# Intuition\nFirst intuition was to solve the problem with graphs and depth first search with some optimizations like ending recursion when minimum was found. Then we can precompute a triangle of the matrix of pairs, also skipping diagonal. Then just aggregate pairs by length of path. I implemented it very quickly but it did not pass the timing on the last test case. Solution is attached to the notes.\n\n# Approach\nHad to hardcode all possible scenarios of x-y edge relative to positions of i and j. Then it is possible to calculate optimal route for each scenario. This is only possible, because problem states that houses are linked one to the next. I dont like this solution, graph solution is more generic. This solution can be further optimized for speed, if the mess of if conditions is collapsed into fewer branches.\n\n# Complexity\n- Time complexity:\n$$O((n^2 - n)/2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution(object):\n    def countOfPairs(self, n, x, y):\n        # graph implementation did not finish in time on the test 879 out of 880\n        # I am assuming nobody is interested in graps, we want pure math solution\n\n        if n < 2 or n > 100:\n            raise ValueError(\'constraint violation\')\n\n        if x > y:\n            t = x\n            x = y\n            y = t\n\n        if x < 1 or y > n:\n            raise ValueError(\'constraint violation\')\n\n        precomp_k = {i: 0 for i in range(1, n + 1)}\n        for i in range(1, n + 1):\n            for j in range(i + 1, n + 1):\n                # the problem that we are trying to solve defines self cyclic edges as having lenth = 0 \n                \n                if i < x and j < y: #\n                    if x != y:\n                        if j > x:\n                            m1 = (x - i) + (j - x)\n                            m2 = (x - i) + 1 + (y - j)\n                            m = min(m1, m2)\n                        else:\n                            m = j - i\n                    else:\n                        m = j - i\n                elif i < x and j > y: #\n                    if x != y:\n                        m = (x - i) + 1 + (j - y)\n                    else:\n                        m = j - i\n                elif i < x and j == y: #\n                    if x != y:\n                        m = (x - i) + 1\n                    else:\n                        m = j - i\n                # --------\n                elif i > x and j < y: #\n                    if x != y:\n                        m1 = j - i\n                        m2 = (i - x) + 1 + (y - j)\n                        m = min(m1, m2)\n                    else:\n                        m = j - i\n                elif i > x and j > y:  #\n                    if x != y:\n                        if i < y:\n                            m1 = j - i\n                            m2 = (i - x) + 1 + (j - y)\n                            m = min(m1, m2)\n                        else:\n                            m = j - i\n                    else:\n                        m = j - i\n                elif i > x and j == y: #\n                    if x != y:\n                        m1 = j - i\n                        m2 = (i - x) + 1\n                        m = min(m1, m2)\n                    else:\n                        m = j - i\n                # --------\n                elif i == x and j < y: #\n                    if x != y:\n                        m1 = j - i\n                        m2 = 1 + (y - j)\n                        m = min(m1, m2)\n                    else:\n                        m = j - i\n                elif i == x and j > y: #\n                    if x != y:\n                        m = 1 + (j - y)\n                    else:\n                        m = j - i\n                elif i == x and j == y: #\n                    if x != y: \n                        m = 1\n                    else:\n                        m = 0  \n                else:\n                    # accodring to ask each house is linked to the next\n                    # you can calculate distance between by substracting house numbers\n                    m = j - i\n\n                #if m == 4:\n                #    print(i, j, x, y, m)\n\n                #if m == 101:\n                #    print(n, x, y)\n\n                if m > 0:\n                    #if m in precomp_k:\n                    precomp_k[m] += 1\n                    precomp_k[m] += 1\n\n        #print(precomp_k)\n        \n        # if we are on higher python - we dont need to sort our dict\n        #precomp_k = [(k, len(v)) for k, v in precomp_k.items()]\n        #precomp_k = sorted(precomp_k, key=lambda x: x[1])\n        #precomp_k = [i[1] for i in precomp_k]\n\n        # skip sorting to save time, enable if required\n        #precomp_k = [len(v) for k, v in precomp_k.items()]\n\n        precomp_k = list(precomp_k.values())\n        \n        #print(precomp_k)\n\n        return precomp_k\n\n```
['Python']