Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 有向グラフで優先度付きキューで探索

from heapq import heapify, heappop, heappush, heappushpop
from collections import Counter

INF = float('inf')

def dijkstra(s,n,g):
    seen = [False]*n
    cost = [INF]*n
    cost[s] = 0 #スタートはコスト0
    next_q = [(0,s)]
    heapify(next_q)
    while len(next_q)>0:
        c, i = heappop(next_q)
        if cost[i] < c:
            continue
        for nedge, ncost in g[i]:
            nc = cost[i]+ncost
            if cost[nedge]>nc:
                cost[nedge] = nc
                heappush(next_q,(nc, nedge))
    return cost

def main():
    N, X, Y = map(int, input().split())
    graph_F = [[] for _ in range(N)]
    #リストの作成
    for i in range(N-1):
        graph_F[i].append((i+1,1))
        graph_F[i+1].append((i,1))
    graph_F[X-1].append((Y-1,1))
    graph_F[Y-1].append((X-1,1))

    ret = []
    for s in range(N):
        ret += dijkstra(s,N,graph_F)
    ret = Counter(ret)
    for i in range(1,N):
        print(ret[i]//2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N - 1):
    G[i].append(i + 1)
    G[i + 1].append(i)
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)

L = [0] * N
for i in range(N - 1):
    dist = [N] * N
    dist[i] = 0
    Q = deque()
    Q.append(i)
    while len(Q) > 0:
        q = Q.popleft()
        for j in G[q]:
            if dist[j] != N:
                continue
            dist[j] = min(dist[q] + 1, dist[j])
            Q.append(j)
    for k in range(i, N):
        if dist[k] != N and dist[k] != 0:
            L[dist[k]] += 1
for i in range(1, N):
    print(L[i])

Submission status: Time Limit Exceeded

Solution code:
N ,X , Y = map(int,input().split())

def calc_dist(i,j):
  m1 = abs(i-j)
  m2 = abs(Y - i) + abs(X - j) + 1
  m3 = abs(X - i) + abs(Y - j) + 1
  return(min([m1 , m2 , m3]))
k = [0]*N
for i in range(N - 1):
  for j in range(N - 1 - i):
    d = calc_dist(i+1,i+j+2)
    k[d-1] += 1
for i in range(N-1):
  print(k[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

n, x, y = map(int, input().split())
x -= 1
y -= 1

ans = [0 for _ in range(n)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    def push(v, d): 
        if dist[v] != inf: return
        dist[v] = d 
        q.append(v)

    push(start, 0)
    while q:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0: push(v-1, d+1)
        if v+1 < n: push (v+1, d+1)
        if v==x: push(y, d+1)
        if v==y: push(x, d+1)
    
    for i in range(n):
        ans[dist[i]] += 1
    
for i in range(n):
    bfs(i)
for i in range(1, n): 
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[0]*N
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1 or j-i ==1:
            L[j-i]+=1
        elif i <= X-1 and j >= Y-1:
            L[1+abs(X-1-i)+abs(Y-1-j)]+=1
        elif i >= X-1 and i-(X-1) > (Y-1)-i:
            L[j-i]+=1
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L[min(L1,L2)]+=1

for i in range(1,N):
    print(L[i])

Submission status: Time Limit Exceeded

Solution code:
import collections

N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[]
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1:
            L.append(j-i)
        elif j-i == 1:
            L.append(1)
        elif i <= X-1 and j >= Y-1:
            L.append(1+abs(X-1-i)+abs(Y-1-j))
        elif i >= X-1 and i-(X-1) > (Y-1)-i:
            L.append(j-i)            
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L.append(min(L1,L2))

c=collections.Counter(L)

for i in range(1,N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
import collections

N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[]
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1:
            L.append(j-i)
        elif j-i == 1:
            L.append(1)
        elif i <= X-1 and j >= Y-1:
            L.append(1+abs(X-1-i)+abs(Y-1-j))
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L.append(min(L1,L2))

c=collections.Counter(L)

for i in range(1,N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
import collections

N,X,Y=map(int,input().split())
if X > Y:
    exc=X
    X=Y
    Y=exc
L=[]
for i in range(N-1):
    for j in range(i+1,N):
        if i >= Y-1 or j <= X-1:
            L.append(j-i)
        elif j-i == 1:
            L.append(1)
        else:
            L1=j-i
            L2=min(j-i,1+abs(X-1-i)+abs(Y-1-j))
            L.append(min(L1,L2))

c=collections.Counter(L)

for i in range(1,N):
    print(c[i])

Submission status: Time Limit Exceeded

Solution code:
def line(N, X, Y):
    X = X - 1
    Y = Y - 1

    queue = [(a, a + 1) for a in range(N - 1)]
    queue.append((X, Y))
    visited = set(queue)
    print(len(queue))

    for i in range(N - 2):
        new_queue = []

        def add_to_queue(x, y):
            if y == N or y < 0:
                return
            if x == N or x < 0:
                return
            if x == y:
                return

            if x > y:
                x, y = y, x

            t = (x, y)
            if t not in visited:
                new_queue.append(t)
                visited.add(t)

        for q in queue:
            add_to_queue(q[0], q[1] + 1)
            add_to_queue(q[0], q[1] - 1)
            add_to_queue(q[0] + 1, q[1])
            add_to_queue(q[0] - 1, q[1])

        print(len(new_queue))
        # print(f"{len(new_queue)} {new_queue}")
        queue = new_queue


N, X, Y = map(int, input().split())
line(N, X, Y)

# line(5, 2, 4)
# print()
# line(3, 1, 3)
# print()
# line(7, 3, 7)
# print()
# line(10, 4, 8)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
n, x, y = map(int, input().split())
inf = 10**10
dp = [[inf]*n for _ in range(n)]
dic = defaultdict(int)
pas = defaultdict(list)

    

for i in range(n):
    l=1
    dp[i][i] = 0
    if i==0 and x==1:
        queue = deque([1, y-1])
        dp[i][1]=1
        dp[i][y-1]=1
        dic[1]+=2
    elif i==0:
        queue = deque([1])
        dp[i][1]=1
        dic[1]+=1
    elif i==n-1 and y==n:
        queue = deque([n-2, x-1])
        dp[i][n-2]=1
        dp[i][x-1]=1
        dic[1]+=2
    elif i==n-1:
        queue = deque([n-2])
        dp[i][n-2]=1
        dic[1]+=1
    elif i==x-1:
        queue = deque([i-1, i+1, y-1])
        dp[i][i+1]=1
        dp[i][i-1]=1
        dp[i][y-1]=1
        dic[1]+=3
    elif i==y-1:
        queue = deque([i-1, i+1, x-1])
        dp[i][i+1]=1
        dp[i][i-1]=1
        dp[i][x-1]=1
        dic[1]+=3
    else:
        queue = deque([i-1, i+1])
        dp[i][i-1]=1
        dp[i][i+1]=1
        dic[1]+=2
    while queue:
        
        t = queue.popleft()
        #dic[]+=1
        if t == x-1 and dp[i][y-1]==inf:
            queue.append(y-1)
            dp[i][y-1]=dp[i][t]+1
            dic[dp[i][t]+1]+=1
        if t == y-1 and dp[i][x-1]==inf:
            queue.append(x-1)
            dp[i][x-1]=dp[i][t]+1
            dic[dp[i][t]+1]+=1
        if not t==0:
            if dp[i][t-1]==inf:
                queue.append(t-1)
                dp[i][t-1]=dp[i][t]+1
                dic[dp[i][t]+1]+=1
        if not t==n-1:
            if dp[i][t+1]==inf:
                queue.append(t+1)
                dp[i][t+1]=dp[i][t]+1
                dic[dp[i][t]+1]+=1

for i in range(1, n):
    print(dic[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = [int(x) for x in input().split()]

for k in range(1, n):
    ans = 0
    for i in range(1,n):
        for j in range(i+1, n+1):
            if min(abs(j-i), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x)) == k:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
for k in range(1,n):
  cnt=0
  for i in range(1,n):
    for j in range(i+1,n+1):
      d=min(abs(j-i),abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))
      if d==k:cnt+=1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def line(N, X, Y):
    X = X - 1
    Y = Y - 1

    queue = [(a, a) for a in range(N - 1)]
    visited = set()

    for i in range(N - 1):
        new_queue = []

        def add_to_queue(x, y):
            if y == N or y < 0:
                return
            if x == N or x < 0:
                return
            if x == y:
                return

            if x > y:
                x, y = y, x

            t = (x, y)
            if t not in visited:
                new_queue.append(t)
                visited.add(t)

        for q in queue:
            add_to_queue(q[0], q[1] + 1)
            add_to_queue(q[0], q[1] - 1)
            add_to_queue(q[0] + 1, q[1])
            add_to_queue(q[0] - 1, q[1])

            if q[1] == X:
                add_to_queue(q[0], Y)
            if q[1] == Y:
                add_to_queue(q[0], X)
            if q[0] == X:
                add_to_queue(Y, q[1])
            if q[0] == Y:
                add_to_queue(X, q[1])

        print(len(new_queue))
        # print(f"{len(new_queue)} {new_queue}")
        queue = new_queue


N, X, Y = map(int, input().split())
line(N, X, Y)

# line(5, 2, 4)
# print()
# line(3, 1, 3)
# print()
# line(7, 3, 7)
# print()
# line(10, 4, 8)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

anss = [0 for _ in range(n-1)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    for k in range(1, n): 
        cnt = 0 
        for i in range(n):
            if cnt > 3:
                break
            if dist[i]-dist[start] == k:
                anss[k-1] += 1
                cnt += 1
    
for i in range(n):
    bfs(i)
for i in range(n-1):
    print(anss[i]//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

anss = [0 for _ in range(n-1)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    for k in range(1, n): 
        for i in range(n):
            if dist[i]-dist[start] == k:
                anss[k-1] += 1
    
for i in range(n):
    bfs(i)
for i in range(n-1):
    print(anss[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X, Y = MAP()
dic = defaultdict(int)
for i in range(1, N+1):
    for j in range(1, N+1):
        tmp = min(abs(i - j), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(X-j))
        dic[tmp] += 1
for i in range(1, N):
    print(dic[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
c = []
for i in range(1,N):
  for j in range(i+1,N+1):
    x = abs(X-i)
    y = abs(Y-j)
    a = min(x+y+1,j-i)
    c.append(a)
for i in range(1,N):
  ans = c.count(i)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
d = Y-X
c = []
for i in range(1,N):
  for j in range(i+1,N+1):
    if i <= X and j >= Y:
      c.append(j-i-d+1)
    elif i>=X and j <= Y:
      a = min(j-i, i-X+1+Y-j)
      c.append(a)
    elif i<= X and j <= Y:
      a = min(X-i+1+Y-j,j-i)
      c.append(a)
    else:
      a = min(j-Y+1+i-X,j-i)
      c.append(a)
for i in range(1,N):
  ans = c.count(i)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y = map(int, input().split())
X-=1;Y-=1
d = [[] for _ in range(N)]
for i in range(N):
  if i == 0:
    d[i].append(i+1)
  elif i == N-1:
    d[i].append(i-1)
  else:
    d[i].append(i+1)
    d[i].append(i-1)
  if i == X:
    d[i].append(Y)
  elif i == Y:
    d[i].append(X)
#print(d)
INF = float("inf")
ans = [0 for _ in range(N)]
for i in range(N):
  reach = [INF for _ in range(N)]
  reach[i] = 0
  Q = deque([])
  Q.append(i)
  while Q:
    v = Q.popleft()
    for u in d[v]: #vから行ける地点を調べる。
      if reach[u] != INF:
        continue
      reach[u] = reach[v] + 1
      ans[reach[u]] += 1
      Q.append(u)

for i in range(1,N):
  temp = ans[i]//2
  print(temp)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,X,Y = map(int,input().split())
G = [[] for i in range(N+1)] 
for i in range(1,N+1):
  if i-1 >= 1:
    G[i].append(i-1)
  if i+1 <= N:
    G[i].append(i+1)

G[X].append(Y)
G[Y].append(X)

dl = [0]*(N+1)
def bfs(p):
  seen = [False]*(N+1)
  seen[p] = True
  dist = [0]*(N+1)
  d = deque([p])
  while len(d) > 0:
    v = d.popleft()
    for i in G[v]:
      if seen[i] == False:
        seen[i] = True
        dist[i] = dist[v]+1
        dl[dist[i]] += 1
        d.append(i)      


for i in range(1,N+1):
  bfs(i)

for i in range(1,N):
  print(dl[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
INF = 10 ** 9


N, X, Y = map(int, input().split())
X -= 1
Y -= 1

G = [[abs(i - j) for i in range(N)] for j in range(N)]
G[X][Y] = 1
G[Y][X] = 1

for i in range(N):
    for j in range(N):
        G[i][j] = min(G[i][j], G[i][X] + G[Y][j] + 1, G[i][Y] + G[X][j] + 1)

ans = [0] * (N)
for i in range(N - 1):
    for j in range(i + 1, N):
        ans[G[i][j]] += 1
    
print (*ans[1:], sep = '\n')
        
# print (*G, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
X,Y = X-1,Y-1
from collections import deque

DP = [[-1]*N for _ in range(N)]

ans = [0]*N

for i in range(N):
    for j in range(i+1,N):
        x = j - (i+1)
        y = j
        if j <= X or Y <= i:
            DP[i][j] = j - i
        elif i <= X and Y <= j:
            DP[i][j] = X-i + 1 + j-Y
        elif i <= X and j <= Y:
            DP[i][j] = min(j-i,X-i + 1 + Y-j)
        elif X <= i and j <= Y:
            DP[i][j] = min(j-i,i-X+1+Y-j)
        else:
            DP[i][j] = min(j-i,i-X+1+j-Y)
        ans[DP[i][j]] += 1

print(*ans[1:],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

n,x,y = map(int,input().split())
graph=[[] for _ in range(n)]

for i in range(1,n+1):
    if i!=x:
        if i == 1:
            graph[i-1].append(i+1)
        elif i == n:
            graph[i-1].append(i-1)
        else:
            graph[i-1].append(i-1)
            graph[i-1].append(i+1)
    else:
        graph[i-1].append(y)
        if i == 1:
            graph[i-1].append(i+1)
        elif i == n:
            graph[i-1].append(i-1)
        else:
            graph[i-1].append(i-1)
            graph[i-1].append(i+1)
k_dic=defaultdict(int)

for i in range(1,n):
    q = deque([[i]])
    prev = [0]*n
    prev[i-1] = 1
    dic=defaultdict(int)
    while q:
        now_l = q.popleft()
        tu = []
        for now in now_l:
            nex = graph[now-1]
            
            for ne in nex:
                if prev[ne-1] == 0:
                
                    tu.append(ne)
                    q.append(tu)
                    prev[ne-1] = 1
                    dic[ne] = dic[now]+1
                    if ne > i:
                        k_dic[dic[ne]] += 1

for i in range(1,n):
    print(k_dic[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import Counter
from collections import defaultdict
from collections import deque 
def main():
    N, X, Y = map(int, readline().split())
    to = [[] for _ in range(N)] 

    for i in range(N-1):
        to[i].append(i+1)
        to[i+1].append(i)
    to[X-1].append(Y-1)
    to[Y-1].append(X-1)
    INF = int(1e9)
    ans = defaultdict(int)
    for si in range(N):
        dq = deque()
        dq.append(si)
        dist = [INF for _ in range(N)]
        dist[si] = 0
        while len(dq)>0:
            v = dq.popleft()
            for nx in to[v]:
                if dist[nx] != INF:
                    continue
                dq.append(nx)
                dist[nx] = dist[v]+1
        for i in dist:
            ans[i] += 1
    
    for i in range(1, N):
        print(ans[i]//2)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

if __name__ == '__main__':

    n, x, y = map(int, input().split())

    ans = [0] * (n+1)

    g = [[i+1, i-1] for i in range(n+1)]
    g[0].clear()
    g[1].pop(1)
    g[n].pop(0)

    g[x].append(y)
    g[y].append(x)

    for i in range(1,n+1):
        q = deque()
        time = 0

        visit = [False] * (n+1)

        q.append((i, time))

        while(len(q) > 0):
            item = q.popleft()

            if visit[item[0]] == False:
                visit[item[0]] = True
                ans[item[1]] += 1
                for k in g[item[0]]:
                    q.append((k, item[1]+1))

    for i in range(1,n):
        print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


n,x,y = imap()
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        dist.append(min(abs(i-j), abs(i-x)+abs(j-y)+1, abs(i-y)+abs(j-x)+1))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:

import collections as col


n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,x,y = imap()
ans = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        ans.append(min(a,b,c))
    
cnt = col.Counter(ans)
for i in range(1,n): print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, x, y = map(int, input().split())

cnt = [0] * n
for i, j in combinations(range(n), 2):
    i, j = i + 1, j + 1
    dist = min(abs(j - i), abs(i - x) + abs(j - y) + 1,
               abs(i - y) + abs(j - x) + 1)
    cnt[dist] += 1

for i in range(1, n):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque 
def main():
    n,x,y=map(int,input().split())
    root=[[]for i in range(n)]
    for i in range(1,n):
        root[i-1].append(i)
        root[i].append(i-1)
    root[x-1].append(y-1)
    root[y-1].append(x-1)
    short=[0 for i in range(n)]
    dictlen={}
    for i in range(1,n):
        dictlen[i]=0
    for start in range(n):
        distance=[0]*n
        toVis=deque()
        checkVis=[-1 for i in range(n)]
        toVis.append(start)
        while len(toVis)>0:
            now=toVis.popleft()
            checkVis[now]=1
            for nex in root[now]:
                if checkVis[nex]==1:
                    continue
                toVis.append(nex)
                checkVis[nex]=1
                tonex=distance[now]+1
                distance[nex]=tonex
                dictlen[tonex]+=1
    #print(dictlen)
    for key in dictlen.keys():
        print(dictlen[key]//2)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())

r = [[] for i in range(n)]

for i in range(n):
    if i==0:
        r[i].append(i+1)
    elif i==n-1:
        r[i].append(n-2)
    else:
        r[i].append(i-1)
        r[i].append(i+1)

#x,yの間に道を追加
x,y = x-1,y-1

r[x].append(y)
r[y].append(x)

from collections import deque

q = deque([0])

dist = [-1]*n
dist[0]=0

ans=[]
for p in range(n):
    
    dist = [-1]*n
    dist[p]=0
    q = deque([p])

    while q:
        v = q.popleft()

        for j in r[v]:
            if dist[j]==-1:
                dist[j] = dist[v] + 1
                q.append(j)
    
    ans.append(dist)


d={}
for k in range(1,n+1):
    d[k]=0


for i in range(n):
    for j in range(i+1,n):
        d[ans[i][j]]+=1

for k in range(n-1):
    print(d[k+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def main():
    N, X, Y = list(map(int, input().split()))

    ans = Counter()

    E = [{i-1, i+1} for i in range(N)]
    E[0] = {1}
    E[N-1] = {N-2}
    E[X-1].add(Y-1)
    E[Y-1].add(X-1)

    for i in range(N):
        visited = [False] * N
        visited[i] = True

        q = E[i]
        c = 0
        while q:
            next_q = set()
            c += 1

            for v in q:
                if visited[v]: continue

                ans[c] += 1
                visited[v] = True
                next_q |= E[v]
            q = next_q

    for i in range(1, N):
        print(ans[i]//2)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def ispow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist():
    return list(map(int,input().split()))
######################################################################################################

N,X,Y=inputintlist()
X-=1
Y-=1
G=[[] for a in range(N)]
for a in range(N-1):
    G[a].append(a+1)
    G[a+1].append(a)
G[X].append(Y)
G[Y].append(X)
A=[]
for a in range(N):
    for b in range(a,N):
        d=b-a
        d=min(d,abs(a-X)+1+abs(b-Y))
        d=min(d,abs(a-Y)+1+abs(b-X))
        A.append(d)
for k in range(1,N):
    print(A.count(k))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
n, x, y = map(int, input().split())
edge = [[] for i in range(n)]

for i in range(n-1):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x-1].append(y-1)
edge[y-1].append(x-1)

def bfs(i):
    dq = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while dq:
        now = dq.popleft()
        d = dist[now]
        for e in edge[now]:
            if dist[e]==-1:
                dist[e] = d + 1
                dq.append(e)
    return dist

c = Counter()
for i in range(n):
    c = c + Counter(bfs(i))

for i in range(1, n):
    print(c[i]//2)