C++ | Detailed explanation | Line Sweep | Clean Code | Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nUnderstanding the problem, we can conclude that there will be one cycle. If the cycle w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUnderstanding the problem, we can conclude that there will be one cycle. If the cycle was not there, we can solve the problem easily with a formula, but cycle will affect distance between many pair of house. Lets divide the problem in subproblems and solve them individually, eventually merge them.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will divide the houses into three groups (let $$x$$ < $$y$$):\n- $$Group Cycle$$: the houses between $$x$$ and $$y$$ \n- $$Group Left$$: the houses before house $$x$$\n- $$Group Right$$: the houses after house $$y$$\n\nNow, our problem reduces to calculate distances between:\n- $$T1$$ - All pairs in $$GroupCycle$$\n- $$T2$$ - All pairs in $$GroupLeft$$\n- $$T3$$ - All pairs in $$GroupRight$$\n- $$T4$$ - All house in $$GroupLeft$$ to all houses in $$GroupCycle$$\n- $$T5$$ - All house in $$GroupRight$$ to all houses in $$GroupCycle$$\n- $$T6$$ - All house in $$GroupLeft$$ to all houses in $$GroupRight$$\n\nAt the end, we will multiply the answer with $$2$$, as the a pair will contribute to our final answer two times, one with being $$(house1, house2)$$ and other with $$(house2, house1)$$.\n\n## Calculating answer for a Straight Line\n\n$$GroupLeft$$ and $$GroupRight$$ can be considered as a straight line. It can be observed that if number of houses in the line (length of the line) is $$L$$, then pairs with:\n\n> length $$i$$ will be $$L - i$$\n\nSo, contributions of $$T2$$ and $$T3$$ can be easily calculated by this observation.\n\n## Calculating answer for a Cycle\n\n$$GroupCycle$$ is a cycle. Lets see how will we calculate answer for it. Let say number of houses in cycle (length of cycle) is $$L$$. The observation for a cycle is:\n\n> A pair of house having distance $$i$$ will also have a path of streets with distance $$L - i$$. As we need to take the minimum distance between houses, we will take the smaller one. This indicates that we don\'t need to find pairs with distance greater than $$L$$ / $$2$$. \n\nNow we can easily derive the formula from observation for few smaller values of $$L$$. \n\n> ### $$L$$ is odd\n> - Pairs with distance $$d$$ ($$d$$ <= $$L$$ / $$2$$) will be $$L$$. Yes, you read it right, all the distances will apprear exactly $$L$$ times.\n\n> ### $$L$$ is even\n> - Pairs with distance $$d$$ ($$d$$ < $$L$$ / $$2$$) will be $$L$$.\n> - Pairs with distance $$d$$ ($$d$$ = $$L$$ / $$2$$) will be $$L$$ / $$2$$. \nBecause the pair will repeat here. We will multiple whole answer by two at the end, so no need to count two times here.\n\nSo, these observations will help to find answer contribution of $$T1$$.\n\n## Calculating answer for a Straight Line and a Cycle\n\nHere we will see how to calculate answer for $$T4$$ and $$T5$$. We will use a concept of **Line Sweep** to calculate our answers in this section. Considering length of line to be $$L$$ and length of cycle to be $$C$$. Let say the point of contact between Stright line and Cycle is $$x$$. \n\nKey Observations are : \n\n> - For each house in Straight Line we will calculate number of pairs with other house in cycle. \n> - $$2$$ house in cycle will give same length for a house in line, as we can go either way from $$x$$ in the cycle.\n\n> For each house in the line with distance $$d$$ to $$x$$:\n>> Minimum contribution to answer, $$MN$$: $$d$$\n>> Maximum contribution to answer, $$MX$$: $$d$$ + $$C$$ / $$2$$\n\nWe will add contribution of $$2$$ for each length above. We can use line sweep from $$MN$$ to $$MX$$ and calculate the contributions for each house in Stright Line.\n\n**NOTE**: When $$C$$ is even, we need to add its contribution as $$1$$ for the house at maximum distance in cycle. As no other house in cycle will have same distance as this house.\n\nSo, contributions of $$T4$$ and $$T5$$ can be easily calculated by this observation.\n \n## Calculating answer for Two Stright Lines\n\nHere we will see how to calculate the contribution of pairs with all house in $$GroupLeft$$ to all houses in $$GroupRight$$. Again, we will use the concept of **Line Sweep** to solve this sub problem. Let say the lines are $$L1$$ and $$L2$$.\n\nFor each house in $$L1$$ we will see its contribution to the answer:\n> - $$MN$$: pair with minimum distance having this house from $$L1$$. \n> - $$MX$$: pair with maximum distance having this house from $$L1$$.\n\nWe can use line sweep from $$MN$$ to $$MX$$ and calculate the contributions for each pair. So, this gives us the contribution of $$T6$$.\n\n## Calculating final answer\n\nWe will just add contributions of $$T1$$, $$T2$$, $$T3$$, $$T4$$, $$T5$$ and $$T6$$. Don\'t forget to multiply final answer by $$2$$. \n\n# Complexity\n- Time complexity: $$O(n)$$\n\n<!-- - Space complexity: -->\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n> **Upvote if you find the solution easy to understand!**\n> **Suggestions and improvements are appreciated.**\n\n# Code\n```\ntypedef long long ll;\n\nclass Solution {\npublic:\n    vector<ll> lineAndCycle(ll n, ll lineLen, ll cycleLen) {\n        vector<ll> res(n);\n\n        for (ll d = 1; d <= lineLen; d++) {\n            ll mn = d + 1;\n            ll mx = d + (cycleLen / 2);\n            res[mn - 1] += 2;\n            res[mx - 1] -= 2;\n        }\n\n        ll mn = cycleLen / 2 + 1;\n        ll mx = cycleLen / 2 + lineLen;\n\n        ll add = (cycleLen & 1 ? 2 : 1);\n\n        res[mn - 1] += add;\n        if (mx < n) res[mx] -= add;\n\n        for (ll i = 1; i < n; i++)\n            res[i] += res[i - 1];\n\n        for (ll len = 1; len <= lineLen; len++)\n            res[len - 1]++;\n\n        return res;\n    }\n\n    vector<ll> lineAnswer(ll n, ll lineLen) {\n        vector<ll> res(n);\n\n        for (ll len = 1, add = lineLen - 1; len < lineLen; len++, add--)\n            res[len - 1] += add;\n\n        return res;\n    }\n\n    vector<ll> cycleAnswer(ll n, ll cycleLen) {\n        vector<ll> res(n);\n\n        for (ll len = 1; len < cycleLen / 2; len++)\n            res[len - 1] += cycleLen;\n        \n        if (cycleLen & 1) {\n            int len = cycleLen / 2;\n            if (len - 1 >= 0)\n                res[len - 1] += cycleLen;\n        } else {\n            int len = cycleLen / 2;\n            if (len - 1 >= 0)\n                res[len - 1] += (cycleLen / 2);  \n        }\n\n        return res;\n    }\n\n    vector<ll> twoLineAnswer(ll n, ll lineLen1, ll lineLen2, ll x, ll y) {\n        vector<ll> res(n);\n\n        if (lineLen1 > lineLen2) swap(lineLen1, lineLen2);\n        ll plus = (x != y ? 1 : 0);\n        \n        for (ll i = 0; i < lineLen1; i++) {\n            ll mn = i + plus + 2;\n            ll mx = i + plus + 1 + lineLen2;\n            \n            res[mn - 1]++;\n            if (mx < n) res[mx]--;\n        }\n\n        for (int i = 1; i < n; i++)\n            res[i] += res[i - 1];\n\n        return res;\n    }\n    \n    vector<long long> countOfPairs(int n, int x, int y) {\n        vector<ll> res(n);\n        if (x > y) swap(x, y);\n        \n        ll lineLen1 = x - 1;\n        ll lineLen2 = n - y;\n        ll cycleLen = y - x + 1;\n        ll finalLen = lineLen1 + lineLen2 + 2;\n        \n        auto line1ans = lineAnswer(n, lineLen1);\n        auto line2ans = lineAnswer(n, lineLen2);\n        auto cycleAns = cycleAnswer(n, cycleLen);       \n        auto l1c = lineAndCycle(n, lineLen1, cycleLen);\n        auto l2c = lineAndCycle(n, lineLen2, cycleLen);\n        auto l1l2 = twoLineAnswer(n, lineLen1, lineLen2, x, y);\n        \n        for (int i = 0; i < n; i++) {\n            res[i] += line1ans[i];\n            res[i] += line2ans[i];\n            res[i] += cycleAns[i];\n            res[i] += l1c[i];\n            res[i] += l2c[i];\n            res[i] += l1l2[i];\n            res[i] *= 2;\n        }\n\n        return res;\n    }\n};\n```
['Math', 'Line Sweep', 'Counting', 'C++']