# Lời giải bài Period

## Tác giả: Phạm Quang Minh, I2023

## 1. Tóm tắt đề
Cho dãy $a$ có $n$ $(1 \le n \le 5*10^6)$ phần tử và hệ số $k$ $(1 \le k \le 10^9)$, hãy tìm vị trí $i$ xuất phát sao cho giá trị $a_p + dist(i,p) \times k$ tối đa là bé nhất, với $dist(i,p)$ được định nghĩa là là khoảng cách từ $i$ đến $p$ theo chiều kim đồng hồ.

## 2. Thuật toán ngây thơ

- Ta có duyệt với mọi vị trí xuất phát $i$ và tìm giá trị $a_p + dist(i,p) * k$ tối đa của vị trí này bằng cách duyệt từng phần tử trong mảng $a$. Từ đó ta có thể so sánh để tìm được vị trí xuất phát $i$ tạo ra giá trị $a_p + dist(i,p) * k$ tối đa bé nhất.
- Độ phức tạp: $O(n^2)$

## 3. Cải tiến
- Với mọi mọi vị trí xuất phát $i$, thay vì ta duyệt mọi phần tử trong mảng $a$, ta có thể tiền xử lí giá trị này bằng cách lưu 2 mảng tiền tố và hậu tố, mảng hậu tố tương đương với việc đi từ vị trí $i$ tới $n$ và mảng tiền tố tương đương với việc đi từ $1$ tới $i-1$.
- Ta định nghĩa mảng tiền tố là $pre$ được tính theo công thức $pre_i = max(pre_{i-1}, a_i + i * k)$ $(1 \leq i \leq n)$
- Ta định nghĩa mảng hậu tố là $suf$ được tính theo công thức $suf_i = max(suf_{i+1}, a_i + i * k)$ $(1 \leq i \leq n)$
- Khi đó với mỗi vị trí $i$, ta có thể tìm được giá trị $a_p + dist(i,p) \times k$ tối đa bằng công thức $max(suf_i - (i-1) \times k, pre_{i-1} + (n-i+1) \times k)$ $(1 \leq i \leq n)$. Từ đó ta có thể so sánh để tìm được vị trí xuất phát $i$ tạo ra giá trị $a_p + dist(i,p) * k$ tối đa bé nhất.

### Độ phức tạp: $O(n)$

### Code mẫu: [Link](https://ideone.com/4Tv1Rg)
### Tag: Prefix sum