Toy cũng xài heap push ra push vào edge case tùm lum vì ko prove được là nó đúng đme đọc đề cứ đẩy vào heapq xog đẩy và pop ra xog thằng bn bảo dùng gready là xong đúng k nhanh nhạy cứ thích brute force
fence có mấy thằng bạn uy tín thế 
bn em toàn mấy đứa dân cày thuật mà thím tối rủ nhau ngồi làm contest , h vẫn đang ngồi chữa đềToy cũng xài heap push ra push vào edge case tùm lum vì ko prove được là nó đúng đm
thiệt rầu
public class Solution {
public int[] CountOfPairs(int n, int x, int y) {
int tmp1 = x;
int tmp2 = y;
x = Math.Min(tmp1, tmp2);
y = Math.Max(tmp1, tmp2);
x--;y--;
int[] array = new int[n];
for(int i = 0;i<n;i++) {
for(int j = i + 1; j< n;j++) {
int step = j - i;
// out side
if(j <= x) {
array[step - 1]+=2;
continue;
}
if(i>=y) {
array[step - 1]+=2;
continue;
}
// inside
if(i>=x && j <=y) {
step = Math.Min(j - i, i - x + y - j + 1);
array[step - 1] +=2;
continue;
}
if(i <= x && j >= y) {
step = Math.Min(j - i, x - i + j - y + 1);
array[step - 1] +=2;
continue;
}
if(i <= x && j <=y) {
step = x - i + Math.Min(j - x, 1 + y - j);
array[step - 1] += 2;
continue;
}
step = j - y + Math.Min(y - i, i - x + 1);
array[step - 1] += 2;
}
}
return array;
}
}
Mình cũng vậy làm bài 3 lại dễ hơn bài 2 sub phát ăn luôn
{
int[] re = new int[n];
if (x > y) {
int tmp = x;
x = y;
y = tmp;
}
for (int i = 1; i < n; ++i) {
for (int j = i+1; j <= n; ++j) {
int l1 = j-i;
int l2 = Math.abs(x-i) + Math.abs(y-j) + 1;
re[Math.min(l1, l2)-1] += 2;
}
}
return re;
}
bài đấy chia từng th, a ms làm đc left->right. Còn th ở giữa đi sang 2 bên ko nghĩ đcBài 4 nghĩ hơn 1 tiếng mà lại sai, ý tưởng là update theo range, 1 là dùng fenwick tree, 2 là dùng trick update theo range của prefix sum
hướng anh làm có vẻ ổn hơnbài đấy chia từng th, a ms làm đc left->right. Còn th ở giữa đi sang 2 bên ko nghĩ đc
, em làm theo kiểu cố định L xong xét R >= y với R < y mà sai
bài 2 thường brute force thôi, đôi khi nghĩ nhiều lại làm phức tạp hoá. Như e tính khoảng cách giữa 2 thành phố bất kỳ. cách hơi ngu nhưng vẫn pass
Thật nếu nghĩ là xài graph thì dùng floyd warshall tìm khoảng cách giữa tất cả các điểm rồi đưa nó vô kết quả là xong rồi. Mà cứ ngồi tìm cách greedy tào lao không
My fence giải thích mình cái này thử vớibài 2 của mìnhJava:{ int[] re = new int[n]; if (x > y) { int tmp = x; x = y; y = tmp; } for (int i = 1; i < n; ++i) { for (int j = i+1; j <= n; ++j) { int l1 = j-i; int l2 = Math.abs(x-i) + Math.abs(y-j) + 1; re[Math.min(l1, l2)-1] += 2; } } return re; }
class Solution:
def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
x -=1
y -=1
ans = [0]*n
for start in range(n):
visited = set()
visited.add(start)
queue = deque()
queue.append((start, 0))
while queue:
item, distance = queue.popleft()
if distance > 0:
ans[distance - 1] += 1
neighbors = [item - 1, item + 1]
if item == x:
neighbors.append(y)
if item == y:
neighbors.append(x)
for next in neighbors:
if 0 <= next < n and not next in visited:
queue.append((next, distance + 1))
visited.add(next)
return anscách của mình brute force tù túng ấy màThật nếu nghĩ là xài graph thì dùng floyd warshall tìm khoảng cách giữa tất cả các điểm rồi đưa nó vô kết quả là xong rồi. Mà cứ ngồi tìm cách greedy tào lao không
My fence giải thích mình cái này thử với
, với 2 thành phố i, j thì tính input size nhỏ nên vẫn pass, chứ input size lớn thì cook luôn 
