C++ solution based on lee215's (with comments)
Lee\'s original solution is absolutely brilliant.\nMy solution is a much longer version for his (for my own understanding), I have added comments for explanatio
Lee\'s original [solution](https://leetcode.com/problems/count-the-number-of-houses-at-a-certain-distance-ii/discuss/4601078/JavaC%2B%2BPython-Burning-Points) is absolutely brilliant.\nMy solution is a much longer version for his (for my own understanding), I have added comments for explanation for others like me who took a long time to understand lee\'s solution\n```\nclass Solution {\npublic:\n  /*\n  Let us initially light a flame at every point i\n  At time t, each flame has travelled a distance (t + 1) from its initial point\n\n  Let there be an array A such that at time t, A[t] is the number of points newly \n  reached by all the flames at time t\n  */\n  vector<long long> countOfPairs(int n, int x, int y) {\n    // Trivial case of x == y. Lee\'s solution doesn\'t need to this separately:)\n    if (x == y) {\n      vector<long long> result(n, 0);\n      for (int i = 0; i < n; ++i) {\n        result[i] = 2 * (n - i - 1);\n      }\n      return result;\n    }\n    \n    if (x > y) swap(x, y);\n    vector<long long> pairsWithDist(n + 1, 0); // 1-indexed for readability.\n    int mid = (x + y) / 2;\n    for (int i = 1; i <= n; ++i) {\n      /*\n      We start with d = 1 and realize the fact that every flame spreads to its \n      neighbors first and every point except for the end points has two neighbors\n      so we must do A[1 - 1 = 0] += 2.\n      */\n      pairsWithDist[1] += 2;\n      \n      /*\n      Whenever the flame reaches x or y, the flame branches into two so we do \n      A[dist(i, x)] += 1 and A[dist(i, y)] += 1.\n      */\n      if (i < mid) {\n        // Reaches x directly.\n        pairsWithDist[abs(i - x) + 1]++;\n        // Reaches y via x.\n        pairsWithDist[abs(i - x) + 2]++;\n      } else if (i > mid) {\n        // Reaches y directly.\n        pairsWithDist[abs(i - y) + 1]++;\n        // Reaches x via y.\n        pairsWithDist[abs(i - y) + 2]++;\n      } else {\n        // Reaches x directly.\n        pairsWithDist[abs(i - x) + 1]++;\n        // Reaches y directly.\n        pairsWithDist[abs(i - y) + 1]++;\n      }\n    }\n    \n    /*\n    Now every flame that reaches a distance of d at time t, must have also reached a \n    distance of d - 1 at time t - 1\n    We can define A[-1] = 0 and d = 1 at t = 0\n    A[t] += A[t - 1]\n    */\n    for (int d = 1; d <= n; ++d) {\n      pairsWithDist[d] += pairsWithDist[d - 1];\n    }\n    \n    /*\n    Let us define some dead ends for the flame after which the flame doesn\'t spread \n    further: 1, n and the mid point of x and y (this midpoint is where flame from the\n    same point "collides" with itself which means that all the shortest paths from\n    point i have been covered)\n    */\n    vector<long long> deductions(n + 1, 0); // 1-indexed for readability.\n    for (int i = 1; i <= n; ++i) {\n      if (i <= mid) {\n        // Dead end when reaching 1 directly.\n        deductions[(i - 1) + 1]++;\n      } else {\n        // Dead end when reaching 1 through y.\n        deductions[(abs(i - y) + 1 + (x - 1)) + 1]++;\n      }\n      if (i >= mid) {\n        // Dead end when reaching n directly.\n        deductions[(n - i) + 1]++;\n      } else {\n        // Dead end when reaching n  through x.\n        deductions[(abs(i - x) + 1 + (n - y)) + 1]++;\n      }\n      \n      /*\n      The part between x and y can be imagined to be a ring. You can at max go\n      (ringLen / 2) in one direction and ((ringLen - 1) / 2) in the other (doesn\'t \n      matter clockwise or anti-clockwise).\n      Convince yourself that this would be the case in both cases:\n      even and odd ring length\n      */\n      int ringLen = (y - x) + 1;\n      if (i <= x) {\n        // Clockwise path entering at x.\n        deductions[((x - i) + (ringLen / 2)) + 1]++;\n        // Anti-clockwise path entering at x.\n        deductions[((x - i) + ((ringLen - 1) / 2)) + 1]++;\n      }\n      if (i > x && i < y) {\n        // Clockwise path starting with i itself.\n        deductions[(ringLen / 2) + 1]++;\n        // Anti-clockwise path starting with i itself.\n        deductions[((ringLen - 1) / 2) + 1]++;\n      }\n      if (i >= y) {\n        // Clockwise path entering at y.\n        deductions[((i - y) + (ringLen / 2)) + 1]++;\n        // Anti-clockwise path entering at y.\n        deductions[((i - y) + ((ringLen - 1) / 2)) + 1]++;\n      }\n    }\n    // Accumulate the deductions as well\n    // (since the additions were accumulated for all subsequent distances as well).\n    for (int d = 1; d <= n; ++d) {\n      deductions[d] += deductions[d - 1];\n    }\n    \n    vector<long long> result(n);\n    for (int i = 0; i < n; ++i) {\n      // Apply the deductions due to the midpoints.\n      result[i] = pairsWithDist[i + 1] - deductions[i + 1];\n    }\n    return result;\n  }\n};\n```
[]