Chọn 3 thành phố để xây khách sạn sao cho khoảng cách của mỗi cặp đều bằng nhau?

#1

Chào mọi người, em đang gặp một bài toán trên hackerank về dạng graph. Sau một hồi suy nghĩ nhưng vẩn không tìm ra được cách giải nên em xin phép đăng lên đây để xin mọi người giúp đỡ? Bài toán như hình đính kèm ạ!

5
5514×784 57.4 KB
6
6514×835 55.6 KB
7
8
8480×754 34.3 KB
9
9505×758 40.2 KB

1 Like
#2

Do đề cho đồ thị đặc biệt: liên thông và có số cạnh = số đỉnh - 1 nên ta có này là 1 cái spanning tree.
Thì bây giờ bạn chỉ cần tính khoảng cách giữa tất cả các thành phố.
Sau đó, nếu có 1 thành phố i nào đó mà có khoảng cách bằng nhau tới k \ (k \ge 3) thành phố khác, thì ta có thể chọn ra 3 trong số k thành phố này.
Cuối cùng chắc là tính tổng tất cả các cách chọn với mọi thành phố i là xong.

4 Likes
#3

Bác có thể nói rõ hơn về cách tính khoảng cách giữa tất cả các thành phố và cách tính tổng các cách chọn k?

#4

Bài toán tính khoảng cách giữa các đỉnh trong đồ thị thì là bài toán cơ bản rồi. Không biết bạn gặp khó khăn gì với việc tính khoảng cách này?

Còn về việc tính tổng, lấy ví dụ n=6, roads=[[1,2], [2,5], [3,4], [4,5], [5,6], [6,7]]
Thì các đỉnh có các đỉnh sao thỏa điệu kiện có \ge 3 đỉnh cùng khoảng cách:

  • Đỉnh số 5, khoảng cách 2 tới các đỉnh: 2, 4, 6 => số cách chọn {3 \choose 3} = 1

  • Đỉnh số 5, khoảng cách 3 tới các đỉnh: 1, 3, 7 => số cách chọn {3 \choose 3} = 1

=> Tổng số cách chọn là 1+1=2

2 Likes
#5

Để tính khoảng cách các đỉnh thì mình dùng thuật toán floyd-warshall phải không bác?
Còn cái tính tổng số cách chọn thì theo cách bác thì em gặp 1 vấn đề. Đó là vd cho n = 5, roads = [[1,2],[1,3],[1,4],[1,5]] thì:

  • Từ đỉnh 1 tới các đỉnh còn lại đều có khoảng cách là 1 sẽ nên có 4C3 = 4 cách.
  • Nhưng khi xét các đỉnh còn lại vd như đỉnh 2 tới đỉnh 3, 4, 5 thì khoảng cách đều bằng 2. Như thế dẫn tới có thêm 4 cách nữa, là bị trùng -> có 8 cách!!!. Mà đáp án đúng chỉ có 4 cách.

Không biết bác có cách nào để loại bỏ đi việc bị trùng này không? Xin góp ý ạ!

2 Likes
#6

Ồ, đúng là chưa tính tới trường hợp bị lặp lại như vầy.

Ý tưởng ban đầu sẽ là nếu có đỉnh i cùng khoảng cách, thì đỉnh i này sẽ là trung tâm và các thành phố được chọn sẽ đi qua chỗ đỉnh i này.

Bây giờ, xét trường hợp đỉnh 2 tới đỉnh 3, 4, 5 như trong ví dụ: thì ta sẽ có các đường đi đều đi qua cả 2 đỉnh chung là 2 và 1 => có thể chọn 1 làm trung tâm cũng được, mà chọn 2 làm trung tâm cũng được => có thể loại trường hợp cùng khoảng cách nhưng lại có chung 1 đỉnh nào đó trên đường đi => cần phải lưu thêm cả đường đi và chỉ chọn đỉnh trung tâm khi các đường đi không có đỉnh nào chung khác đỉnh trung tâm.

3 Likes
#7

Để hiện thực được code theo hướng bác nói thì có vẻ khá là khó á bác. Mà việc tính khoảng cách đường đi bác dùng floyd-warshall phải không hay dùng thuật toán khác ạ? Thấy floyd-warshall O(n^3) hơi ngán, không biết có thuật toán nào tối ưu hơn không?

#8

Mình chưa thấy bài đồ thị nào mà code đơn giản cả, nhưng chung quy lại thì vẫn quay về mấy thao tác cơ bản (dù hiện thực hơi phức tạp) mà thôi.
Mình không rành đồ thị, nên bạn dùng thuật toán nào tìm được đường đi giữa mọi cặp đỉnh là được. Chứ giờ bạn có hỏi Floyd-Warshall là gì thì mình cũng biết dùng tay đi google thôi bạn à :smile:

1 Like
#9

Chào bạn,
Cho mình ngu chút là giới hạn của bài toán n <= 50. Sao không dùng 3 vòng for lồng nhau để xét 3 đỉnh bất kì nhỉ :v

Nếu mà O(n^3) không qua thì bạn thử dp:

  • f[i][j] là số đỉnh nằm trong cây con gốc i và khoảng cách đến i là j
  • g[i][j] là số đỉnh nằm ngoài cây con gốc i và khoảng cách đến i là j
    thì khi đó số đỉnh có khoảng cách j đến i là f[i][j] + g[i][j]

Độ phức tạp là O(n ^ 2)
Còn nếu chỉ cần lấy khoảng cách từ một số cặp đỉnh bất kì thì có thể dùng LCA. Với mỗi truy vấn mất O(log n).
Mà mình nghĩ O(n ^ 3) là đủ để qua bài toán rồi :((

2 Likes
#10

Thì thấy bác ghi đây là bài toán cơ bản nên nghĩ chắc bác có cách hay để tính hơn là dùng floyd-warshall :sweat_smile:

#11

Ờ nhở, một ý kiến hay á bác!!! :heart_eyes:

Còn cái này thì chưa rõ ý bác muốn nói về cái gì cả, chắc bác đang nói đến việc sử dụng quy hoạch động phải không? Bác có thể giải thích rõ hơn được không, em đang cần sự khai sáng :sweat_smile:

#12

Mình nói rõ ràng vậy mà ?
Còn giải thích thì bạn muốn giải thích ý phía trên hay ý phía dưới ?

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?