Tap here to switch tabs
Problem
Submissions

Problem: Count the Number of Houses at a Certain Distance II

Try to solve the Count the Number of Houses at a Certain Distance II problem.

Statement

You are given three integers n, x, and y.

There are n houses numbered from 11 to n located along a street. For every ii from 11 to n −1- 1, house ii is connected to house i+1i + 1 by a bidirectional street. In addition, an extra bidirectional street connects house x and house y.

Return an array result of length n where result[k - 1] represents the total number of pairs of houses (house1,house2)(house_1, house_2) such that the minimum number of streets needed to travel between house1house_1 and house2house_2 is exactly kk, for each kk from 11 to n.

Note: A pair of houses (house1,house2)(house_1, house_2) must consist of distinct houses, and the pair is ordered, which means (house1,house2)(house_1, house_2) and (house2,house1)(house_2, house_1) are counted as distinct pairs.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 1≤1 \leq x, y ≤\leq n

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count the Number of Houses at a Certain Distance II

Try to solve the Count the Number of Houses at a Certain Distance II problem.

Statement

You are given three integers n, x, and y.

There are n houses numbered from 11 to n located along a street. For every ii from 11 to n −1- 1, house ii is connected to house i+1i + 1 by a bidirectional street. In addition, an extra bidirectional street connects house x and house y.

Return an array result of length n where result[k - 1] represents the total number of pairs of houses (house1,house2)(house_1, house_2) such that the minimum number of streets needed to travel between house1house_1 and house2house_2 is exactly kk, for each kk from 11 to n.

Note: A pair of houses (house1,house2)(house_1, house_2) must consist of distinct houses, and the pair is ordered, which means (house1,house2)(house_1, house_2) and (house2,house1)(house_2, house_1) are counted as distinct pairs.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 1≤1 \leq x, y ≤\leq n