Bài toán Nguồn: Tiếng Việt: Codeforces - Bản dễ Có thể giải với $O(n^2)$ Codeforces - Bản khó Cần giải bằng $O(n\log n)$ Tiếng Anh: Leetcode Cho một dãy số nguyên nums. Tìm độ dài của dãy con tăng đơn điệu dài nhất. Biết rằng dãy con tăng đơn điệu là 1 dãy $a_1,..,a_k$ thỏa mãn $$ \begin{align} &i_1 < i_2 < \dots < i_k,\\\ &nums[i_1] < nums[i_2] < \dots < nums[i_k] \end{align} $$ Ví dụ:...

Bài toán Nguồn: Codewars Đọc hiểu Theo Wikipedia : Bài toán xâu con chung dài nhất là bài toán tìm một xâu có độ dài lớn nhất và là xâu con của mọi xâu trong một tập hợp các xâu. Khác với chuỗi con, các phần tử của xâu con không nhất thiết phải liên tiếp nhau. Với 2 chuỗi được nhập vào, nhiệm vụ của bạn chính là tìm ra xâu con dài nhất của chúng....

Bài toán Nguồn: Codewars Đọc hiểu Có bao nhiêu cách phân tích số n thành tổng các số? Theo wikipedia: https://vi.wikipedia.org/wiki/Phân_hoạch_(lý_thuyết_số) Trong số học, sự phân tích một số nguyên dương n là cách viết số đó dưới dạng tổng của các số nguyên dương. Hai cách phân tích có các số hạng giống nhau được coi là một cách phân tích. Ví dụ: Input: 4 Output: 5 //4, 3+1, 2+2, 2+1+1, 1+1+1+1 Lời giải Bài toàn này có thể dùng phương pháp liệt kê để đếm nhưng mà như vậy rất là chậm khi $n$ là số lớn nên mình sẽ dùng quy hoạch động (Oω<)☆....

Bài toán Nguồn: Codeforces Đọc hiểu Tìm phần dư của số Fibonacci thứ $n$ ($n <= 10^{18}$) cho $10^9 + 7$. Như vậy, mình cần tìm $F_n$ trong dãy số được định nghĩa: $$ \begin{aligned} F_0 & = 0\\ F_1 & = 1\\ F_i & = F_{i-1} + F_{i-2} (i >= 2) \end{aligned} $$ Ví dụ: Input: 50 Output: 586268941 Lời giải Cách 1: Quy hoạch động Xem phương trình sai phân của dãy fibonacci là công thức truy hồi, mình có thể viết thành đoạn code sau:...

Bài toán Nguồn: Leetcode , Codewars Đọc hiểu: Bạn có một lượng đồng xu với các mệnh giá khác nhau và một tổng số tiền amount. Nhiệm vụ của bạn là tính xem có bao nhiêu cách khác nhau để đổi được số tiền với số xu đã cho. Số lượng xu không giới hạn. Ví dụ: Input: amount = 5, coins = {1,2,5} Output: 4 //{5, 2+2+1, 2+1+1+1, 1+1+1+1+1} Lời giải Với bài này mình sẽ lần lượt đi qua các giai đoạn của nó mà ở mỗi gia đoạn số xu của mình sẽ thay đổi dẫn đến sự thay đổi của kết quả bài toán....

Bài toán Nguồn: Leetcode Đọc hiểu Bạn có một lượng đồng xu có các mệnh giá khác nhau và tổng số tiền amount. Nhiệm vụ của bạn là tìm số xu ít cần ít nhất để tạo nên số tiền đó (không giới hạn số đồng xu). Nếu số tiền đó không thể tạo thành thì trả về -1. Ví dụ: Input: coins = {1,2,5}, amount = 11 Output: 3 //2 đồng 5 và 1 đồng 1 Input: coins = {2}, amount = 3 Output: -1 Lời giải Cách 1: Vét cạn bằng đệ qui Lấy ví dụ như trên, mình có amount là 11....

Sơ lược Phép thao tác trên bit Kí hiệu Mô tả AND & Cả hai bit là 1, trả về 1. Ngược lại trả về 0. OR \ Một trong hai bit là 1, trả về 1. Ngược lại trả về 0. XOR ^ Hai bit khác nhau trả về 1. Ngược lại trả về 0. NOT ~ Đảo bit, 0 thành 1, 1 thành 0. Dịch trái - Shift left << Dịch tất cả các bit sang trái....

Bài toán Nguồn: Codewars Cho một số $n$ được nhập vào, việc của tụi mình là phân tích giai thừa của nó ra thừa số nguyên tố. Ví dụ: Input: n = 12 Output: 2^10 * 3^5 * 5^2 * 7 * 11 Có 1 lưu ý nho nhỏ là giá trị của $n$ có thể lên tới 4000, tất nhiên, 4000! sẽ trở thành 1 con số không hề nhỏ, nó có hơn 12000 chữ số lận á!...

Bài toán Nguồn: Codewars Đọc hiểu Cho một số dương $n$ > 1. Phân tích $n$ ra tích các số nguyên tố theo dạng: ($p_1$**$n_1$)($p_2$**$n_2$)…($p_k$**$n_k$) Trong đó: a**b nghĩa là $a^b$ $p_i$ liệt kê theo thứ tự tăng dần Nếu $n_i$ = 1 thì không ghi ra Ví dụ: Input: n = 86240 Output: (2**5)(5)(7**2) Lời giải Để phân tích ra thừa số nguyên tố, mỉnh đem chia số đó cho ước nguyên tố nhỏ nhất của nó....

Bài toán Nguồn: Codeforces Đọc hiểu Một số được gọi là t-prime nếu nó có đúng 3 ước số dương. Một số nguyên dương sẽ có 2 ước số là 1 và chính nó. Ngoài ra, nếu số đó, tạm gọi là $x$, có thêm 1 ước số nhỏ hơn $\sqrt{x}$ thì chắc chắn nó sẽ có ước khác. Để $x$ có đúng 3 ước số thì ước số nhỏ hơn $\sqrt{x}$ của nó phải là 1 số nguyên tố....