Types of programming contest problems

There are 16 types of programming contest problems (according to USACO)

• Dynamic Programming
• Greedy
• Complete Search
• Flood Fill
• Shortest Path
• Recursive Search Techniques
• Minimum Spanning Tree
• Knapsack
• Computational Geometry
• Network Flow
• Eulerian Path
• Two-Dimensional Convex Hull
• BigNums
• Heuristic Search
• Approximate Search
• Ad Hoc Problems

[Kĩ năng coding]Một kĩ thuật tính tổng tích lũy đơn giản mà hiệu quả

Ngày hôm nay là một ngày đẹp trời ! Mình đã được truyền đạt lại một kĩ thuật khá đơn giản nhưng rất hiệu quả để tính tổng tích lũy. Kĩ thuật này đối với mình thì rất là xa lạ, nhưng thật ra nó khá phổ biến đối với những học sinh chuyên Tin ở những nơi khác. Kệ, học được bao nhiêu tốt bấy nhiêu ^.^

Vấn đề đặt ra như sau: Cho một dãy số a[1..n] và danh sách m lệnh có dạng (x, y, k) - tăng tất cả các phần tử a[x..y] lên k đơn vị (k có thể là số âm, 0 hoặc dương). Yêu cầu in ra dãy a[1..n] sau m lệnh đó.

Trước giờ mình chỉ nghĩ tới việc sử dụng Brute-Force: "Với từng lệnh, xét từng phần tử thuộc đoạn a[x..y] rồi đem cộng với k" mà thôi (Độ phức tạp O(n²)), hoặc cùng lắm, dùng cây chứa khoảng với độ phức tạp O(nlogn) là nhanh lắm rồi. Bởi thế, tri thức mới này làm cho mình có phần sốc khi thực sự hiểu ra, và đương nhiên, rất vui ^.^

Kĩ thuật này như sau: Xét từng lệnh trong m lệnh đó, giả sử đang xét tới lệnh (i, j, t), ta sẽ gán lại các giá trị a[i] và a[j + 1] như sau:

a[i] := a[i] + k; a[j + 1] := a[j + 1] - k;

Sau đó, ta chỉ cần:

for i := 2 to n do a[i] := a[i - 1] + a[i];

Thì dãy a[1..n] cuối cùng sẽ là dãy kết quả cần tìm !! Thời gian chính xác là O(2m + n) !!

Lí giải tại sao, ta chỉ cần chú ý rằng các lệnh (x, y, k) là riêng biệt, tức là thứ tự thực hiện các lệnh không ảnh hưởng gì tới kết quả, và với mỗi đoạn (i, j), bởi vì phần tử đầu tiên (a[i]) được cộng thêm t, do đó trong bước cộng dồn vào các phần tử sau, đương nhiên các phần tử phía sau đều được cộng thêm một lượng là t (đúng!), còn tới phần tử a[j + 1] vì đã trừ mất t rồi, nên cộng t vào sẽ không thay đổi nữa, do đó, làm theo các bước trên rõ ràng sẽ cho ta kết quả.

Và tới giờ này mình vẫn luôn cố gắng tìm được một con đường để giúp cái đầu mình thông minh hơn. Tại sao mình chưa bao giờ từng nghĩ ra điều này nhỉ ? Tại vì trong đầu mình luôn luôn thường trực một tư tưởng sắt thép rằng: "Vấn đề này không thể giải quyết trong thời gian tuyến tính được đâu, quá rõ ràng mà!" ... và giờ niềm tin này đã nát vụn. Bởi thế, mình (và mong các bạn, những ai cũng giống mình lúc này) sẽ luôn luôn thay đổi cách suy nghĩ để tìm tới những điều tốt đẹp hơn. "Không đúng đâu, chưa tối ưu đâu, có thể nhanh hơn nữa, có thể tốt hơn nữa" ! ^.^

Chúc vui vẻ ^.^

[VNOI]NKINV

Bài viết này bàn về một hướng suy nghĩ giải quyết bài NKINV.

Chú ý: Để nắm được toàn bộ tư tưởng bài viết, mình đề nghị các bạn (nếu chưa từng) đọc qua nội dung kiến thức về một kiểu cấu trúc dữ liệu đặc biệt nổi tiếng, đó là Binary Indexed Tree (BIT). Thuật toán chính giới thiệu trong bài này sử dụng cấu trúc dữ liệu đó. Lưu ý rằng mình sẽ không nói đến hoạt động của BIT như thế nào mà vấn đề chính đề cập tới chính là làm thế nào xuất hiện ý tưởng sử dụng BIT.

Đề bài:

Cho một dãy số a₁.. a_N. Một nghịch thế là một cặp số u, v sao cho u < v và a_u > a_v. Nhiệm vụ của bạn là đếm số nghịch thế.

Dữ liệu

• Dòng đầu ghi số nguyên dương N.
• N dòng sau mỗi dòng ghi một số a_i ( 1 ≤ i ≤ N ).

Kết quả

Ghi trên một dòng số M duy nhất là số nghịch thế.

Giới hạn

• 1 ≤ N ≤ 60000
• 1 ≤ a_i ≤ 60000

Ví dụ

Dữ liệu:
3
3
1
2

Kết quả
2

Thuật toán đơn giản nhất cho bài này đó là Brute-Force: kiểm tra tất cả các cặp (u, v) (u < v) nếu a_u > a_v thì tăng biến kết quả lên 1.

result := 0;
    for i := 1 to n - 1 do
        for j := i + 1 to n do
            if a[i] > a[j] then result := result + 1;

Thuật toán này tuy rất đơn giản nhưng độ phức tạp quá lớn (cỡ O(n²)), không thể chạy với N ≤ 60000 trong 1s được. Do đó ta sẽ đi tìm thuật toán khác với độ phức tạp nhỏ hơn để giải bài này.

Đã tới giờ tưởng tượng ! Hãy thử tưởng tượng, bằng cách nào đó bạn có được một dãy số b[x] với b[x] chính là số số lớn hơn x (x = a[i] nào đó) trong dãy a, xét từ phần tử thứ nhất đến phần tử x đang xét. Bạn hiểu ý chỗ này chứ ? Tức là giả sử bạn đang xét đến phần tử mang giá trị x nào đó trong dãy a, bạn sẽ có một số b[x] là số số lớn hơn x trong dãy a[1..j] (j là vị trí của phần tử x trong a). Để ý rằng dãy b sẽ thay đổi theo thời gian và hơn nữa, các phần tử của b cũng như số phần tử của b sẽ không vượt quá 60000 (vì 1 ≤ a_i ≤ 60000)

Vậy khi có dãy b, ta sẽ làm gì ? Khi có dãy b, ta sẽ chỉ đơn giản là cộng b[x] vào result, bởi vì phần tử hiện tại là x và ta biết có b[x] số nằm trước x trong dãy a và lớn hơn x, do đó kết quả thực sự sẽ tăng thêm b[x] cặp nghịch thế nữa. Do đó vấn đề của chúng ta hiện tại chính là tính được b[x] mà thôi. Ta sẽ lần lượt xét các phương án từ cơ bản đến phức tạp hơn dưới đây.

Phương án thứ nhất mà ai cũng nghĩ ra, đó chính là duyệt toàn bộ các phần tử nằm trước x trong a (giả sử vị trí của x là j, thì toàn bộ các phần tử 1..j - 1 sẽ được xét đến) và với mỗi cặp nghịch thế tìm được, ta sẽ tăng 1 vào b[x]. Cách này chẳng khá khẩm gì hơn thuật toán Brute-Force, thậm chí còn tệ hơn vì sử dụng đến hai mảng a, b. Do đó, ta loại cách này.

Phương án thứ hai, ta thử xây dựng một bảng tần số g, trong đó g[x] là số lần xuất hiện của phần tử x trong dãy a[1..j - 1]. Khi đó, b[x] := Σ g[x + 1..60000] (ở đây 60000 chính là giá trị tối đa của a[i], không phải giá trị lớn nhất của n-số phần tử). Việc xây dựng bảng tần số g chỉ mất O(1) cho mỗi số x, tức là O(n) xét toàn tập dữ liệu. Vì vậy, vấn đề cuối cùng của chúng ta là tính các tổng b[1..60000] mà thôi. Yêu cầu này gợi ý chúng ta đến việc sử dụng cấu trúc dữ liệu BIT (tức là IT và RMQ đều được) để xây dựng và lưu trữ dãy b trong thời gian O(mlogn).

Mình xin được nêu một số gợi ý để sử dụng BIT (ý kiến cá nhân): Nếu bài toán xuất hiện yêu cầu xử lí các khoảng số  và tính các tổng liên tiếp của dãy số (bảng số, khối số, ...) thì có thể nghĩ tới dùng BIT để xử lí (điều này chỉ là một suy nghĩ của người mới biết tới BIT được 2 ngày, chưa phải chân lí).

Vậy quay lại với bài toán. Ta thấy trong tài liệu BIT (mình đã đặt link ở đầu bài), mỗi phần tử tree[i] sẽ lưu tổng của một đoạn nằm phía trước (bao gồm cả phần tử a[i]) của phần tử a[i] mà trong bài này lại yêu cầu tính tổng phía sau. Vậy thì hoặc là ta đảo cả mảng tree lại, hoặc là ta "lật" phần mà tree[i] quản lí lại, tức là tree[i] sẽ không quản lí nửa phía trước mà là nửa phía sau của đoạn đó (bạn nên xem hình sẽ rõ hơn).

Trong tài liệu:

Còn đối với chúng ta, ta sẽ quan tâm tới cây BIT có dạng như sau:

Chú ý rằng các số liệu trong hình là không liên quan tới bài toán, các bạn chỉ cần để ý tới các thanh dọc là được rồi. Một lưu ý nhỏ là phần tử lớn nhất (maxnum, trong hình là 16) thì không có giá trị nào lớn hơn nữa, do đó tree[16] là không cần thiết phải lưu, ta ngầm định nó bằng 0.

Như vậy, sử dụng cấu trúc BIT, ta sẽ giải bài tập này trong thời gian ngắn hơn thuật toán Brute-Force. Có thể rút xuống còn sử dụng một mảng tree[1..n] mà thôi. Code bên dưới dùng mảng ff[1..n] thay vì mảng tree[1..n].

Code:


Lưu ý: dữ liệu vào định dạng như trong đề bài, lưu trong file VNOI_NKINV.INP để chạy.