BÀI 1: MUA QUÀ [BUYGIFT]

• Bài tập chỉ yêu cầu học sinh sử dụng tư duy toán học để tìm ra công thức:

  • Chuyển bài toán từ mua k bút chì được tặng 1 cái thành mua ~(k + 1)~ cái bút chì thì chỉ cần trả ~k \times p~ đồng và mua ~<~ ~(k + 1)~ cái bút chì thì phải trả nguyên số tiền

  ~\Rightarrow~ Số tiền phải trả bé nhất khi ta mua càng nhiều ~(k + 1)~ bút chì càng tốt, và khi không thể mua như thế nữa thì số bút chì còn lại cần mua ~<~ ~(k + 1)~

  ~\Rightarrow~ Công thức: res = ~ \lfloor\frac{n}{(k+1)}\rfloor \times k \times p + (n \mod (k+1))\times(p)~

  • Độ phức tạp: ~O(1)~

BÀI 2: TRÒ CHƠI XÓA SỐ [DELSO]

• Thuật trâu:
  • Duyệt từng đoạn ~[l, r]~ bằng 2 vòng for, rồi sau đó kiểm tra xem trong đoạn đó có tồn tại số ~1~ hay số ~n~ hay không, nếu không thì cập nhật lại đáp án bằng với lượng phần tử phải xóa đi để có được đoạn ~[l, r]~ (hay ~ =l + n - r + 1~)
  • Độ phức tạp: ~O(t \times n^3)~
• Cải tiến 1:
  • Nhận xét là có thể không cần kiểm tra xem đoạn ~[l, r]~ có tồn tại phần tử ~1~ hay ~n~ bằng 1 vòng for, mà chỉ cần kiểm tra xem chỉ số của phần tử ~1~ và ~n~ có nằm trong đoạn ~[l, r]~ hay không
  • Độ phức tạp: ~O(t \times n^2)~
  • Đối với các giới hạn như trong bài toán, làm đến đây là đã được điểm rồi. Thế nhưng, trong kỳ thi tp v1 thì sẽ không chỉ đơn giản thế này (nếu bài này có vào thì chắc chắn giới hạn của n sẽ là ~10^5~ hoặc ~10^6~). Do đó, học sinh vẫn cần biết cách xử lí bài toán trong các trường hợp n to.
• Cải tiến 2:
  • Nhận xét là không cần phải quan tâm đến tất cả các đoạn ~[l, r]~ mà chỉ cần quan tâm đến chỉ số của phần tử ~1~ và ~n~ (gọi lần lượt là ~p1~ và ~pn~). Không mất tính tổng quát, giả sử ~p1<=pn~, ta nhận thấy có 3 trường hợp cần xét đến:
    • Xóa hết các phần tử có chỉ số từ ~1~ đến ~p1~ và từ ~pn~ đến ~n~
    • Xóa hết các phần tử có chỉ số từ ~1~ đến ~pn~
    • Xóa hết các phần tử có chỉ số từ ~p1~ đến ~n~ và trong cả 3 trường hợp này, mảng nhận được sẽ không bao gồm phần tử ~1~ và ~n~ (lí do tại sao thì sẽ để bạn đọc tự nhận ra, gợi ý là có liên quan đến việc ~p1<=pn~) và lượng phần tử phải xóa đi sẽ là nhỏ nhất khi so sánh với tất cả các trường hợp khác. ~\Rightarrow~ Đáp án của bài toán sẽ là giá trị nhỏ nhất trong cả 3 trường hợp trên
  • Độ phức tạp: ~O(t \times n)~

BÀI 3: DI CHUYỂN [MOVETO]

• Thuật trâu:
  • Sử dụng thuật toán BFS nhưng thêm 1 trạng thái nữa là số phép màu đã sử dụng và mỗi phần tử ~d[i][j][k]~ sẽ có giá trị 0 và 1 tương ứng với việc Đức có thể đi từ ô ~(1,1)~ đến ô ~(i,j)~ sau khi sử dụng ~k~ phép màu hay không. Đề bài yêu cầu mỗi lần dùng phép màu là sẽ tác động lên cả 4 ô trong 1 hình vuông ~2\times 2~ kề cạnh với ô ~(i,j)~, do đó nên khi kích hoạt phép màu, ta phải cập nhật lại đường đi nhỏ nhất cho TẤT CẢ các ô trong TẤT CẢ các hình vuông kề cạnh với ô ~(i,j)~ (hình vuông không nhất thiết phải có độ lớn là ~2\times 2~). Lúc này, kết quả sẽ là giá trị ~k~ nhỏ nhất thỏa mãn ~d[N][M][k]=1~ (dữ liệu đảm bảo luôn luôn có số ~k <= N \times M~ thỏa mãn).
  • Độ phức tạp: ~O(N*M*N*M)~
• Cải tiến:
  • Sử dụng thuật toán BFS 0-1:
    • Ta tiến hành đánh trọng số để thay đổi bài toán: Mỗi cạnh nối ô ~(i,j)~ đến ô ~(u,v)~ sẽ có trọng số là 0 nếu không cần sử dụng phép màu cũng có thể di chuyển từ ô ~(i,j)~ đến ô ~(u,v)~. Ngược lại, nếu ô ~(u,v)~ là một vật cản, trọng số của cạnh nối 2 ô đó sẽ là 1. .
    • Sau khi đánh trọng số, bài toán sẽ chỉ đơn giản là sử dụng thêm thuật toán BFS 0-1 nếu như đề bài không yêu cầu là mỗi phép màu sẽ tác động lên tất cả các vật cản trong phạm vi ~2\times 2~ của ô ~(i,j)~, do đó khi sử dụng phép màu (đồng nghĩa với việc đi qua cạnh có trọng số là 1) thì ta sẽ phải cập nhật lại đường đi ngắn nhất cho TẤT CẢ các ô nằm trong TẤT CẢ các hình vuông ~2\times 2~ mà kề cạnh với ô ~(i,j)~ và chứa ô ~(u,v)~.
  • Độ phức tạp: ~O(N*M)~

BÀI 4: TRANG TRẠI [FARM]

• Thuật trâu:
  • Duyệt nhị phân toàn bộ đồ thị con của đồ thị gốc mà là cây và đếm số cây có trọng số nhỏ nhất rồi trả về kết quả.
  • Độ phức tạp: ~O(2^N + M)~
• Cải tiến:
  • Bài toán 1: tìm cây khung nhỏ nhất: Sử dụng thuật toán Kruskal
  • Bài toán 2: đếm số cây khung nhỏ nhất: Chia tập hợp ~M~ cạnh ra thành các block, mỗi block chứa các cạnh có cùng trọng số với nhau. Ta có hai nhận xét:
    • Theo thuật toán Kruskal, việc thêm cạnh giữa các block là độc lập với nhau (tức là việc thêm và bớt cạnh khỏi cây khung nhỏ nhất ở block này không gây ảnh hưởng đến việc thêm và bớt cạnh khỏi cây khung ở block khác), miễn là các block ở đằng trước nối được càng nhiều cạnh càng tốt là được.
    • Với mỗi block, số lượng cạnh tối đa có thể thêm vào theo thuật toán kruskal là không thay đổi (tức là số lượng cạnh có cùng 1 trọng số ~w~ bất kỳ trong mọi cây khung nhỏ nhất là ~const~).
    • Các block có độ lớn không quá 3 (vì theo đề bài, không có quá 3 cạnh có cùng 1 trọng số)

~\Rightarrow~ Sử dụng cách duyệt nhị phân ở thuật trâu, nhưng lần này chỉ giới hạn trong các block, mỗi lần duyệt nhị phân cần phải kiểm tra xem các cạnh đã duyệt thỏa mãn tiêu chí là số cạnh có thể thêm được vào cây khung là lớn nhất (theo thuật toán Kruskal). Nếu thỏa mãn thì sẽ cập nhật lại kết quả. Lưu ý là khi cập nhật, vì các block là độc lập với nhau nên kết quả sẽ lấy tích của tất cả các lần duyệt nhị phân thỏa mãn.

• Độ phức tạp: ~O(M*log(M)*2^3)~

BÀI 5: ĐẾ CHẾ [AOE]

• Sub 1: bài toán đơn giản là tìm dãy con tăng bắt đầu từ giá trị ~a_l~ trong đoạn ~[l,r]~. Vì giới hạn của subtask này là ~N,Q <= 5\times 10^3~ nên có thể code trâu là được
• Sub 2: sử dụng cấu trúc dữ liệu cây phân đoạn (segment tree) và xử lí truy vấn offline:
  • Tạo mảng ~lmax[]~ sao cho ~lmax_i~ thể hiện điểm trái nhất mà phần tử ~a_i~ là lớn nhất trong đoạn ~[lmax_i,i]~
  • Nhận xét: một đế chế ~a_i~ chỉ có thể ngự trị trong đoạn ~[l,r]~ khi mà đế chế nằm trong đoạn ~[l,r]~ và nó là phần tử lớn nhất trong đoạn ~[l,i]~, đồng nghĩa với việc ~lmax_i <= l~ và ~l<= i <=r~.

~\Rightarrow~ Tạo mảng ~b~ và một segment tree hoạt động trên mảng đó. Ta sẽ xử lí offline các truy vấn như sau: sort các truy vấn theo độ tăng của giá trị ~r~ và mỗi lần đến đế chế ~i~, cập nhật ~b[lmax_i]~++ và ~b[i+1]~--. Đáp án của mỗi truy vấn sẽ là ~\sum_{j=1}^{l} b_j~. Lí do vì sao cập nhật 2 phần tử ở mảng ~b~ như vậy sẽ để bạn đọc tự ngẫm nghĩ (gợi ý: liên quan đến ~lmax_i <= l~ và ~l<= i <=r~).

• Độ phức tạp: ~O(N\times log(N))~

Phương pháp khác: dùng binary lifting