# Orange lecture #1 - Book of Evil

### 1, Đề bài
- n khu chỗ ở, n - 1 đường đi 2 chiều kết nối tất cả khu này -> cây vô hướng
- Book of Evil có phạm phi phá huỷ là d, các node bị ảnh hưởng là p[1], p[2], ..., p[m] -> tìm tất cả vị trí có khả năng đặt Book of Evil

### 2, Ý tưởng
#### a) Bruteforce
- for u = 1 -> n: bfs(u)
// check dist(u, p[1]) <= d && ... dist(u, p[m]) <= d ???

#### b) AC Solution
- Nhận xét:
+ Tìm cặp **(s = p[i], p[j] = r)** xa nhau nhất trong số các node bị ảnh hưởng
+ Ta có mệnh đề tương đương: Book of Evil gây ảnh hưởng tới cả 2 node này <=> Book Of Evil gây ảnh hưởng tới tất cả p[i]

`Nếu dist(x, s) <= d && dist(x, r) <= d => dist(x, p[k]) <= d với mọi k`

Chứng minh: Giả sử dist(x,s) <= d && dist(x,r) <= d với s và r là hai đỉnh xa nhau nhất trong số các node bị ảnh hưởng bởi BoE.

+ TH1: x nằm trên đường đi từ s <-> r.
Nếu tồn tại một đỉnh p[k] mà dist(x, p[k]) > d thì dist(p[k], r) = dist(x, p[k]) + dist(x, r) > d + dist(x,r) >= dist(s, x) + dist(x,r) = dist(s,r) => (p[k], r) mới là cặp đỉnh bị ảnh hưởng nằm cách xa nhau nhất chứ không phải (s,r)
=> Mâu thuẫn
+ TH2: x không nằm trên đường đi từ s <-> r
Chứng minh tương tự

- Thuật toán:
+ B1: Tìm cặp đỉnh xa nhau nhất s, r
- Chọn 1 đỉnh p[j] bất kì -> tìm đỉnh bị ảnh hưởng cách xa p[j] nhất (q)
-> q là s (một đỉnh của cặp đỉnh bị ảnh hưởng cách xa nhau nhất)

Chứng minh:
Giả sử q không phải là s: Chia 2 trường hợp
- s,r đi qua p[j] -> mâu thuẫn
- s,r không đi qua p[j] -> mâu thuẫn

=> q chính là s

- Từ s tìm đỉnh bị ảnh hưởng xa nhất -> r

+ B2: Tìm tất cả các đỉnh có khoảng cách <= d đến hai đỉnh s,r -> Kết quả bài toán

3, Psedocode

### Step 1: find a pair of two affected nodes (s,r) with longest distance

distPM = bfs(p[m]) # return the distance array containing distance of each node from p[m]

s = -1 # find the farthest affected node from p[m]
for i = 1 -> m:
  if (s < 0 || distPM[s] < distPM[p[i]]):
    s = p[i]

distS = bfs(s) # bfs from s
r = -1 # r = the farthest affected node from s 
for i = 1 -> m:
  if(r < 0 || distS[r] < distS[p[i]]):
    r = p[i]

### Step 2: Count the number of nodes which may contain the Book of Evil
distR = bfs(r) # bfs from r

result = 0 # count the number of nodes whose distances to both s & r not exceed d
for i = 1 -> n:
  if(distS[i] <= d and distR[i] <= d):
    result += 1

print(result)

4, Complexity

=> O(N)

function BookOfEvil(n, d, m, p, graph):
    count = 0  # initialize the count of settlements that may contain the Book
    for i = 1 to n:
             distances = BFS(i, d, graph) # run BFS to visit all nodes with distance to i less than or equal to d
            ok = true
            for j = 1 m:
               if(distances[p[j]] == +oo): # not reached
                   ok = false; break
            if(ok): count += 1
    return count  # return the count of settlements that may contain the Book