MaximumNonAdj - Tổng không liên tục lớn nhất

(codelearn.io Advanced Algorithms - Dynamic Programming, problem 6)
Updated $\LaTeX$, 2022

Đề bài

Cho một mảng gồm các số nguyên. Hãy tìm tổng lớn nhất của tất cả các chuỗi con mà không có 2 phần tử nào đứng cạnh nhau trong chuỗi con đó.

Input: mảng số nguyên $arr$, $0 \leq |arr| \leq 10^6$.
Output: số nguyên là tổng lớn nhất thỏa yêu cầu đề bài.

Ví dụ

Input: $arr = [1, 4, 1]$
Output: $4$

Giải thích: Các chuỗi con mà không có $2$ phần tử nào đứng cạnh nhau là $\{1\}, \{4\}, \{1\}, \{1, 1\}$, trong đó chuỗi con có tổng lớn nhất là $\{4\}$.

Solution

Quy hoạch động

Ta chèn một số $0$ vào trước mảng cần xét. Theo ví dụ, mảng sau khi chèn số $0$ sẽ trở thành $arr = [0, 1, 4, 1]$. Gọi $F_i$ là tổng lớn nhất của chuỗi con có phần tử cuối ở vị trí $i$.

• $F_0 := 0$ do vị trí $0$ vừa chèn vào không tồn tại trong mảng ban đầu;
• $F_1$ là tổng lớn nhất của chuỗi con có phần tử cuối tại vị trí $1$. Tại vị trí $1$ chỉ có $1$ phần tử, nên nghiễm nhiên $F_1 := arr_1$. Tuy nhiên, ta phải xét $2$ trường hợp:
• $arr_1 \geq 0$. Khi đó nếu gán $F_1 := arr_1$ thì $F_1$ là một số dương, vẫn có thể là tổng lớn nhất của cả dãy số.
• $arr_1 < 0$. Khi đó $F_1 = arr_1$ thì $F_1$ là một số âm. Tại đây có thể gây bug, nếu $F_1$ cộng vào một số dương ở phía sau sẽ cho kết quả sai. Do đó nếu $arr_1$ âm thì ta lấy $F_1 := 0$, nếu có một số dương ở phía sau cộng vào sẽ không cho kết quả sai.

Công thức truy hồi:

$\left\{\begin{aligned}F_0 &:= 0 \\ F_1 &:= \max(arr_1, 0) \\ F_i &:= \max(arr_i + F_{i - 2}, F_{i - 1})\ (i \geq 2)\end{aligned}\right.$

Kết quả sẽ là $\max(F)$.

Note: bài này yếu không có trường hợp tất cả số trong dãy cho trước là số âm. Với trường hợp này, kết quả sẽ là $\max(arr)$.

Code C++:

Code Python:

November Challenge 2019 - Division 2

Lần này solve được 2 bài, đăng lên coi như có tí tiến bộ.

SC31 - bản tiếng Việt

HRDSEQ - bản tiếng Việt

Solution:

• SC31: Bài này liên quan tới cổng XOR. Duyệt xâu là ra.
• HRDSEQ: Bài này cách nhanh nhất vẫn là khởi tạo một dãy phù hợp với yêu cầu ban đầu, sau đó thực hiện truy vấn trên dãy. Ta dễ dàng thực hiện được điều này do giới hạn của dãy khá ngắn (128 phần tử). Chú ý đừng để cận của dãy quá sát với 128 sẽ chỉ AC 30%. Khởi tạo dư dư xíu tầm 130 - 150 phần tử là dư sức AC all test.

Code mẫu:

SC31 (C++):

HRDSEQ (C++):

spoj NUB4 - Prime Machine

Đề bài: Kiểm tra một số A có phải là số nguyên tố hay không. Một số được gọi là số nguyên tố khi nó chỉ có 2 ước duy nhất là 1 và chính nó, nói cách khác, số nguyên tố là số chỉ chia hết cho chính nó và 1.

Số 2 là số nguyên tố nhỏ nhất, nó chỉ chia hết cho chính nó và 1.

Input: Mỗi hàng sẽ chứa một số nguyên N (1 <= N <= 10^12). Chương trình sẽ kết thúc khi gặp một ký tự không phải số nguyên.

Output: YES nếu N là số nguyên tố, ngược lại in NO.

Phân tích: 
Trước hết, cận trên của N là 10^12. Nếu dùng Sàng Eratosthenes bình thường, ta phải tạo một mảng 10^12 phần tử rồi lưu giá trị của từng phần tử. Nếu dùng phương pháp ngây thơ (dumb algorithm to find prime numbers), duyệt từ 2 đến sqrt(N) thì trong trường hợp xấu nhất ta chỉ phải duyệt đến sqrt(10^12). Rõ ràng độ phức tạp về thời gian của Sàng Eratosthenes hơn hẳn phương pháp ngây thơ, tuy nhiên trong trường hợp này chúng ta cần một giải thuật hiệu quả hơn hẳn cả về không gian lẫn thời gian. Sàng Eratosthenes chiếm quá nhiều không gian, do vậy triển khai phương pháp ngây thơ sẽ có hiệu quả hơn.

Với những bài toán liên quan đến số nguyên tố, chúng ta chỉ áp dụng sàng Eratosthenes với những bài toán cần kiểm tra tính nguyên tố của nhiều số khác nhau, nhằm giải quyết 1 vấn đề lớn hơn (ex: tìm các số nguyên tố mà tổng của chúng bằng một số nguyên tố khác). Việc lạm dụng sàng Eratosthenes có thể dẫn đến việc chương trình của bạn hiệu quả trong việc truy xuất nhưng lãng phí thời gian trong quá trình khởi tạo bảng nguyên tố. 

Code:

*Dùng Sàng Eratosthenes: O(Nlog(logN)) cho việc khởi tạo, O(1) cho việc truy xuất.
*Dùng phương pháp "ngây thơ": O(sqrt(N)) cho toàn bộ quá trình.

Bài viết có tham khảo lời giải của anh Phạm Văn Lâm cho bài PRIME1 (SPOJ). Điểm chung của cả 2 bài này là dùng để kiểm tra số nguyên tố trong phạm vi rất lớn. Bạn đọc có thể tham khảo đề PRIME1 tương tự.

PAIRS1 - Count the pairs

[Tutorial] SPOJ

Đề bài: Cho N số nguyên (0 < N <= 10^5), tìm số lượng các cặp số nguyên chênh lệch nhau một lượng K. Tất cả số liệu đều nằm trong phạm vi 32bits integers.

(Giải thích: Giả sử ta có N số nguyên lần lượt là a[1], a[2], ..., a[N]. Gọi i, j là chỉ số của 2 số nguyên trong dãy a, i khác j. Nếu abs(a[i] - a[j]) = K thì a[i] và a[j] là một cặp số thỏa yêu cầu đề bài).

Input: 2 dòng: dòng đầu tiên là hai số nguyên N và K, dòng tiếp theo là N số nguyên cách nhau bởi một khoảng trắng, các số trong dãy là phân biệt (không có 2 số trùng nhau trong dãy).

Output: một số nguyên là tổng số cặp số chênh lệch một lượng K thỏa yêu cầu đề bài.

Ví dụ:
Input:
5 2
1 5 3 4 2
Output:
3
(Các cặp thỏa mãn yêu cầu: [0, 2], [1, 4], [3, 4]).

Input:
10 1  
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Output:
0
(Không có cặp nào thỏa yêu cầu của đề bài)

Solution: sorting + binary search.
Sử dụng ví dụ 1: dãy số a sau khi sắp xếp lại:
1 5 3 4 2 thành 1 2 3 4 5.
Với mỗi phần tử a[i] trong dãy a, ta tìm kiếm phần tử a[x] sao cho a[i] + k = a[x]. Nếu a[x] tồn tại thì a[i] và a[x] là một cặp thỏa yêu cầu đề bài.

Code mẫu (C++, sử dụng thư viện algorithm có sẵn hàm sort và binary_search)