CHEALG - December Lunchtime 2019 Division 2

Link đề bài trên Codechef - bản tiếng Việt
Hướng dẫn giải + code mẫu

Happy coding!

codelearn.io - root (easy)

Link đề bài

Cho một số nguyên n. Mỗi lần bạn sẽ biến n thành tổng các chữ số của n. Hãy tìm n khi tổng của n chỉ còn lại 1 chữ số.

Input: số nguyên n (1 <= n <= 10^9)

Output: số nguyên n là kết quả thỏa yêu cầu đề bài.

Ví dụ:

Input:

12

Output:

3

Input:

99

Output:

9

Giải thích: 

• Ở ví dụ đầu:
• Lần 1: 1 + 2 = 3 (chỉ có 1 chữ số, in ra 3).
• Ở ví dụ sau:
• Lần 1: 9 + 9 = 18
• Lần 2: 1 + 8 = 9 (chỉ có 1 chữ số, in ra 9).

Solution: Đệ quy cơ bản + tách số.

Code C++:

December Challenge - Division 2

Link đề bài + hướng dẫn giải (Tiếng Anh)
Update đề bài WATSCORE bằng tiếng Việt

Happy coding!

MDL - Medel

Xem đề bài trên Codechef – bản tiếng Việt

Solution: Giả sử ta có dãy A như testcase số 2, A = {38, 9, 102, 10, 96, 7, 46, 28,  88, 13}.

1. Ta xóa 38, còn lại {9, 102, 10, 96, 7, 46, 28,  88, 13}
2. Ta xóa 10, còn lại {9, 102, 96, 7, 46, 28,  88, 13}
3. Ta xóa 96, còn lại {9, 102, 7, 46, 28,  88, 13}
4. Ta xóa 9, còn lại {102, 7, 46, 28,  88, 13}
5. Ta xóa 46, còn lại {102, 7, 28,  88, 13}
6. Ta xóa 28, còn lại {102, 7, 88, 13}
7. Ta xóa 88, còn lại {102, 7, 13}
8. Ta xóa 13, còn lại {102, 7} cũng là đáp án.

Bây giờ từ dãy A ban đầu, ta sắp xếp các phần tử theo thứ tự tăng dần:

A = {7, 9, 10, 13, 28, 38, 46, 88, 96, 102}

Dễ dàng nhận thấy đáp án chính là 2 phần tử A[0] và A[1]. Điều mà ta cần quan tâm tiếp theo là việc xuất kết quả dựa trên thứ tự xuất hiện của 2 phần tử, nếu A[0] xuất hiện trước thì in A[0] trước, ngược lại in A[1] trước. Việc này có thể dễ dàng xử lý bằng một vòng lặp chạy từ 0 đến N, nếu gặp A[0] trước thì A[0] xuất hiện trước, ngược lại thì A[1] là phần tử xuất hiện trước.

Code mẫu (C++):

HPYNOS - Happy Numbers I

Xem đề bài trên SPOJ

Quá trình "tách rời" một số nguyên được miêu tả là quá trình tính tổng bình phương các chữ số của nó lại với nhau. Ví dụ, kết quả của quá trình "tách rời" số 125 là (1^2 + 2^2 + 5^2) = 30. Một số N được gọi là con số vui vẻ, nếu sau nhiều quá trình "tách rời" liên tiếp kết quả đạt thu cuối cùng bằng 1. Nếu kết quả không thể bằng 1 sau nhiêu quá trình "tách rời" liên tiếp, thì N không phải là con số vui vẻ.

Yêu cầu: Viết chương trình nhập vào số nguyên N, xác định xem nó có phải con số vui vẻ hay không.

Ràng buộc:

1 <= N <= 2147483647 (2^31 - 1).

Input: một và chỉ một số nguyên N.

Output: một dòng duy nhất chứa số nguyên T là số lần biến đổi số N để kết luận xem nó có phải con số vui vẻ hay không. Nếu N không phải con số vui vẻ, in ra -1.

Ví dụ:

Input:

19

Output:

4

Giải thích:

1. 19 => 1^2 + 9^2 = 82
2. 82 => 8^2 + 2^2 = 68
3. 68 => 6^2 + 8^2 = 100
4. 100 => 1^2 + 0^2 + 0^2 = 1 (dừng)

Input: 

204

Output

-1

Giải thích:

1. 204 => 2^2 + 0^2 + 4^2 = 20
2. 20 => 2^2 +0^2 = 4
3. 4 => 4^2 = 16
4. 16 => 1^2 + 6^2 = 37
5. 37 => 3^2 + 7^2 = 58
6. 58 => 5^2 + 8^2 = 89
7. 89 => 8^2 + 9^2 = 145
8. 145 => 1^2 + 4^2 + 5^2 = 42
9. 42 => 4^2 + 2^2 = 20 (tiếp tục lặp lại từ bước 2).

Solution: Chú ý là 2^31-1 vẫn nằm trong phạm vi của integer, hơn nữa công việc của chúng ta là xử lý bình phương của các chữ số, không phải cả số hạng nên kiểu dữ liệu toàn bài sử dụng integer vẫn AC bình thường. Dùng một mảng lưu lại những số sau khi xử lý, dùng một thuật toán tìm kiếm hiệu quả. Cuối cùng là duyệt trâu qua từng số hạng đã xử lý để đưa ra kết quả đề bài.

Code mẫu (C++, sử dụng hàm tìm kiếm nhị phân dựng sẵn)

ADASTAIR - Ada and the Staircase

Xem đề bài trên Codechef - bản tiếng Việt

Solution: Bài này ta tìm khoảng cách giữa hai bậc thang gần nhau nhất, nếu khoảng cách lớn hơn K thì lấy khoảng cách này chia cho K sẽ tìm được số bậc thang cần chèn. Chú ý, nếu khoảng cách chia hết cho K thì sau khi chèn ta xóa đi một bậc.

Ví dụ: K = 2, 2 bậc thang gần nhau nhất là 2 và 6
Ta có khoảng cách = 6 - 2 = 4 > K, nếu lấy 4 / K = 4 / 2 = 2 tức là chèn tới 2 bậc. Tuy nhiên ta chỉ cần chèn 1 bậc (2 - 4 - 6).

Bậc thang đầu tiên có thể cao hơn K.

Code mẫu:

ALTARAY - Alternating subarray prefix

(Kể từ bài viết này, những đáp án - code mẫu mình sẽ đăng lên GitHub dưới dạng file zip kèm đề bài pdf).

Đọc đề bài trên Codechef - bản tiếng Việt

Link hướng dẫn giải - code mẫu

Happy coding!

ZOZ - Magic Elements

Đọc đề bài trên Codechef - bản tiếng Việt

Solution: Duyệt cơ bản. Gọi S là tổng các phần tử trong dãy. i là vị trí hợp lệ nếu A[i] + k > S - A[i].

Code mẫu (C++):

longestArrays - dãy con không giảm dài nhất

(codelearn.io - Training Easy)

Đề bài: Một dãy a được gọi là dãy không giảm nếu thỏa mãn: a[i] <= a[j] với mọi 0 <= i <  j < a.size().

Cho một mảng a gồm các số nguyên. In ra độ dài dãy con không giảm dài nhất của a.

Input: mảng a (0 < a.size() <= 10^6, a[i] <= 10^9.)
Output: Độ dài dãy con không giảm dài nhất của a.

Example:
Input: a = [3, 2, 2, 4, 6, 3].
Output: longestArrays(a) = 4.
Giải thích ví dụ: dãy con không giảm dài nhất của a trong ví dụ trên là [2, 2, 4, 6].

Chú ý: 
Ở đây ta phân biệt khái niệm dãy con tăng dài nhất và dãy con không giảm dài nhất. Hiểu đơn giản là trong dãy con tăng dài nhất thì các phần tử tăng dần từ trái qua phải và không có 2 phần tử nào trong dãy bằng nhau. 
Ở testcase mẫu, nếu yêu cầu đưa ra dãy con tăng dài nhất thì kết quả longestArrays(a) = 3, dãy con là [2, 4, 6]. Còn dãy con không giảm dài nhất theo yêu cầu của đề bài là [2, 2, 4, 6], có 2 phần tử đầu tiên trùng nhau.

Solution: Quy hoạch động cơ bản. Theo testcase mẫu thì dãy con này là dãy con liên tiếp. Gọi F[i] là độ dài dãy con tăng liên tiếp tại vị trí i, F[0] = 1 do tại vị trí 0 chỉ có 1 phần tử. Tại vị trí i, nếu a[i] >= a[i - 1] thì F[i] = F[i - 1] + 1 (độ dài dãy con tại vị trí trước đó tăng lên 1 đơn vị). Nếu không, F[i] = 1 tức là ta bắt đầu xét một dãy con mới tại vị trí i.

Công thức truy hồi:
F[0] = 1
F[i]  = max(F[i - 1] + 1, 1) nếu a[i] >= a[i - 1]

Kết quả sẽ là max(F[])

Code C++:

Compress the List (Codechef November Lunchtime 2019)

Vừa mới về quê được ít hôm thì cúm. Vừa đau mắt vừa hắt xì đau mũi nên đầu óc cũng không được tỉnh táo cho lắm. Lại thêm lúc đang giải bài thì nổi hứng úp mì tôm ăn, vừa ăn vừa ngẫm cho nên 1 tiếng chỉ AC được 1 bài, định làm sang bài 2 thấy còn có 8 phút nên thôi :(

Link bài trên Codechef - bản tiếng Việt

Solution: quy hoạch động. Đề nhìn có vẻ phức tạp nhưng chủ yếu là tìm các dãy con tăng liên tiếp trong dãy các phần tử cho trước, rồi in ra theo một format nhất định.

Gọi dãy ban đầu là dãy A, dãy đánh dấu là dãy B. Một phần tử A[i] được đánh dấu tương ứng B[i], nếu B[i] = 1 thì có 2 khả năng, hoặc là phần tử đó là biên (phần tử đầu hoặc cuối) của một dãy con tăng, hoặc phần tử đó là một phần tử đặc biệt đứng riêng 1 mình.

B[0] = 1

B[i] = B[i - 1] + 1 nếu A[i] - A[i - 1] = 1 (A[i] và A[i - 1] là 2 phần tử tăng liên tiếp).

B[i] = 1 nếu A[i] - A[i - 1] != 1 (A[i] và A[i - 1] không phải 2 phần tử tăng liên tiếp).

Đặc biết: B[N] = 1 nếu B[N] != 1 (*)

(*) Sở dĩ ta đánh dấu phần tử cuối cùng bằng 1:

• Giả sử tồn tại dãy con tăng liên tiếp A[x], A[x + 1], ... , A[N]. Khi đó A[N] là phần tử biên, nên đánh dấu B[N] = 1. 
• Giả sử phần tử A[N - 1] và A[N] là 2 phần tử của dãy con tăng. Khi đó theo đề bài ta không thể tính A[N - 1...N] là một dãy con. Do vậy đánh dấu B[N] = 1.
• Trường hợp cuối A[N] là phần tử riêng biệt. Đánh dấu B[N] = 1 là điều hiển nhiên.

Cuối cùng ta chỉ cần xử lý, in kết quả. Những số cần in sẽ được đánh dấu là 1, những số không in ra thì đã được đánh dấu khác 1.

Code mẫu (C++):

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)

CDRSANJ spoj

https://www.spoj.com/problems/CDRSANJ/

Khaled in HIT (Codechef October Lunchtime 2019)

Lunchtime đầu tiên tham dự mà solve được có 1 bài, cũng đăng lên cho có content. 

(Tất cả code mình đã đăng trên blog đều được host ở gist.github.com hoặc lưu trữ trên GitHub).

Đề bài trên Codechef - bản tiếng Việt

Solution: Trước tiên ta sắp xếp tăng dần số điểm của từng học sinh. Do tổng số học sinh là bội số của 4 nên ta có thể chia số học sinh vào 4 khoảng điểm. Đến đây chỉ cần kiểm tra điểm của học sinh cuối cùng một khoảng với điểm của học sinh đầu tiên khoảng tiếp theo, nếu bằng nhau thì không thể chia, ngược lại thì lấy điểm của học sinh đầu tiên khoảng tiếp theo làm mốc chia điểm.

Code mẫu (C++):

P166PROH - Round 6H - Số gần nguyên tố

https://spoj.com/PTIT/problems/P166PROH

Đề bài: Một số được gọi là số gần nguyên tố nếu nó chỉ có đúng hai ước số nguyên tố. Ví dụ: 26, 62. Hãy đếm số lượng các số gần nguyên tố không vượt quá $N$.

Input: Một số $N$ duy nhất ($1 \leq N \leq 3000$)

Output: Một số nguyên duy nhất là số lượng các số nguyên tố không vượt quá N.

Example:

Input:

11

Output:

2

Solution: Ở đây mình lạm dụng sàng Eratosthenes nên chưa biết duyệt trâu có AC hay không. Cơ bản là mình check số nguyên tố rồi check số nguyên tố đó có phải ước của một số hay không, nếu có thì số lượng ước + 1. Nếu số lượng ước = 2 $\rightarrow$ số đó là số gần nguyên tố.

Code:

NEARPRIME - Số nguyên tố gần nhất

Đề bài: Cho số nguyên N (1 <= N <= 2 * 10^6) nhập từ bàn phím. Hãy đưa ra số M là số nguyên tố gần với N nhất. Số nguyên tố gần với N được định nghĩa là một số nguyên tố mà khoảng cách từ N tới nó là nhỏ nhất. Nếu ta tìm được 2 số nguyên tố có cùng khoảng cách tới N, ưu tiên in ra màn hình số nhỏ hơn (codelearn.io - practice easy).

Testcase #1:

Input: 

51

Output: 

53

Testcase #2:

Input:

1000

Output:

997

Solution: Dựng sàng Eratosthenes, sau đó tìm số nguyên tố gần nhất bên trái và bên phải. Nếu khoảng cách đến số nguyên tố bên trái lớn hơn khoảng cách đến số bên phải thì in số bên phải ra, còn lại in số bên trái.

Code:

Shitpost đêm khuya #1

Mình vừa mất con domain free. Đồ free dùng thì không tiếc, chỉ tiếc vì cái domain đó là domain hack của tên mình (tranhoan.gq/uan). Đã mở support ticket trên Freenom để khiếu nại, nhưng pending cả tuần nay.

Thế là mình phải tìm một chỗ mới để shitpost, thứ nhất là không phải cái gì cũng post lên Facebook được, thứ hai là phải tập viết lách dần để sau này khỏi bị khớp. Thành ra phải tìm một domain mới, sau là để làm chỗ post mấy bài shitpost dạng này lên.

Cũng may là mình mới submit GitHub Student Developer pack cách đây mấy tháng. Trong Developer Pack có liên kết với name.com - chuyên cung cấp hosting và domain. Và mình được free một domain .codes, tận dụng luôn vậy.

Có cái domain xong, cái chất ngu của mình lại trỗi dậy. Mình quên mất là Blogger có cung cấp free SSL, thay vào đó mình lại trỏ domain về Cloudflare. Mất cả buổi chiều mới config lại được cái Blogger, tốn thời gian vl.

Cuối cùng, có blog, có domain rồi thì content lại không có. Ngồi vắt óc chỉ để viết mấy dòng thế này thôi cho đỡ trống. 

Ít thông tin thêm về GitHub Student Developer Pack:

+ Dành cho học sinh / sinh viên từ 13 tuổi trở lên.

+ Có tài khoản GitHub.

Cách apply: Vào đây, nhấn Get the pack.

GitHub sẽ yêu cầu bạn chụp ảnh thẻ sinh viên để xác nhận. Cứ chụp rồi confirm, GitHub sẽ xác nhận trong khoảng 13 ngày (của mình là đúng 13 ngày). 

Phúc lợi: xem tại đây

Happy coding!