---
# System prepended metadata

title: 'Orange lecture #1 - Book of Evil'

---

# 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
    ![](https://i.imgur.com/pRd5aBy.png)
    + 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
           ![](https://i.imgur.com/110SLWE.png)

           
        => 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

``` python
### 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)
    
    
```python 
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




```
    
    
    