Bài toán dãy con tăng gần nhất
algorithm
30
White

kiennt viết ngày 13/10/2016

Bài toán dãy con tăng lớn nhất

Cho một dãy N số nguyên A0, A1, ... An. Một dãy con X0, X1, ... Xk là dãy con tăng của A nếu
X0 < X1 < X2 < ... < Xk và A[X0] < A[X1] < ... < A[Xk].
Bài toán là bạn cần đưa ra độ dài lớn nhất của các dãy con tăng của A

Bài toán này là bài toán rất phổ biến trong tin học, tôi đề nghị trước khi đọc phần dưới, các bạn hãy làm thử và kiểm tra cài đặt của mình

Bài viết này sẽ trình bày một số điều tôi học được khi giải bài toán này.

Giải quyết bằng Quy hoạch động:

Nếu gọi M[i] là độ dài lớn nhất của các dãy con tăng trong khoảng từ từ A[0] đến A[i] mà các dãy con này sẽ kết thúc bằng phần tử A[i]. Nếu M được định nghĩa như trên, kết quả bài toán sẽ là max(M[i] với i từ 0 -> N)

Ta có công thức tính M[i] truy hồi như sau

M[i] = max(M[j] với j từ 0 -> (i - 1) mà A[j] < A[i]) + 1            (1)

Từ công thức này, có thể dễ dàng thấy độ phức tạp để tính M[i] là O(i), nên độ phức tạp của bài toán sẽ là O(N ^ 2)

Tối ưu bằng tìm kiếm nhị phân

Với N đủ lớn (khoảng 10^6), thì thuật toán O(N^2) không chạy được, nên chúng ta cần thiết kế thuật toán tốt hơn, cỡ O(NlogN) (tôi không biết liệu có thuật toán nào O(N) để giải bài này không, nếu bạn biết làm ơn chỉ giúp tôi với)

Bản chất của công thức (1) là chúng ta cần tìm chỉ số j < i sao cho A[j] < A[i] và M[j] là cực đại.
Tức là với mỗi i, cần tìm cặp (A[j], M[j]) sao cho A[j] < A[i] và M[j] là cực đại.
Đến đây tôi nghĩ tới việc sử dung tìm kiếm nhị phân trên một dãy tăng, bằng cách sắp xếp cặp (A[i], M[i]) theo một thứ tự nào đó, để sau khi có được dãy với N phần tử, tôi có thể dễ dàng thêm phần từ thứ N + 1 bằng chia nhị phân

Giờ công việc sẽ làm tìm các điều kiện cho thuật toán sắp xếp.

  1. Để ý là, phần tử (N + 1) được chèn vào giữa dãy, thì chúng ta sẽ tốn chi phí để move các phần tử lớn hơn, hoặc nhỏ hơn (N + 1) lên/xuống 1 vị trí. Lúc đó thuật toán chèn sẽ có độ phức tạp là O(N).
    Thế nên, để thuật toán có độ phức tạp O(1), chúng ta nên tìm cách để chèn phần tử (N + 1) vào đầu hoặc cuối dãy
    Đây là một chi tiết rất quan trọng tôi sử dụng để có thể tìm ra hướng giải.

  2. Từ nhận xét 1, tôi đi tìm 2 thuộc tính luôn tăng gắn với A[i], một thuộc tính để làm index của dãy, một thuộc tính để làm value của dãy. Thuộc tính làm index cần có tính chất mỗi lần tăng chỉ tăng nhiều nhất là 1 (để chúng ta có thể chèn thêm vào cuối dãy)

Thuộc tính index chính là độ dài của dãy tăng dài nhất trong khoảng từ 0 -> i. Thuộc tính giá trị chính là giá trị của một phần tử A[j] mà M[j] = i. Để các giá trị luôn tăng, nếu có 2 phần tử của A có cùng giá trị M, ta sẽ chọn phần tử nhỏ hơn.

Hay nói cách khác, ta sẽ xây dựng một dãy m mà phần tử thứ i của m là phần tử X nhỏ nhất trong A, sao cho độ dài của dãy con dài nhất của A kết thúc tại X, sẽ có độ dài là i + 1.

Tới đây, tôi có thể cài đặt bài toán như sau

def find_position(a, value):
    if not a or value > a[-1]:
        return -1

    l, h = 0, len(a) - 1
    while l < h:
        mid = (l + h) // 2
        if a[mid] < value <= a[mid + 1]:
            return mid + 1
        elif a[mid] >= value:
            h = mid
        else:
            l = mid + 1
    return l


def solution(A):
    size = len(A)
    m = []

    for i in xrange(0, size):
        pos = find_position(m, A[i])
        if pos == -1:
            m.append(A[i])
        else:
            m[pos] = min(m[pos], A[i])

    return len(m)

Thuật toán này có độ phức tạp khi chạy là O(NlogN), và độ phức tạp về không gian lưu trữ là O(N).

Đối với tôi, điểm quan trong nhất để có thể nghĩ ra cách cài đặt này đó:

  1. để cài đặt thuật toán tìm kiếm O(logN), chúng ta nên tìm cách thiết kế dãy sao cho chúng ta chỉ cần chèn phần tử vào đầu hoặc cuối dãy.
  2. dãy đầu vào, có 2 thuộc tính (A, B), và chúng ta muốn cực đại/cực tiểu một thuộc tính

Mở rộng

Bài toán trên có rất nhiều mở rộng, một trong những mở rộng đầu tiên đó là:

Đếm số lượng dãy con tăng nhỏ nhất

Thay vì tìm dãy con dài nhất, tìm số lượng các dãy con tăng nhỏ nhất, sao cho các dãy con tăng là riêng biệt nhau.

VD: dãy 1, 20, 30, 2, 3, 4, 5, 6, 90, 70, 30, 40 có thể chia thành 3 dãy

1, 20, 30, 90
2, 3, 4, 5, 6, 70
30, 40

Số lượng nhỏ nhất các dãy con tăng là 3

Để làm bài này, ta sẽ xây dựng một dãy con m, trong đó m[i] là giá trị lớn thứ i trong các gía trị lớn nhất của các dãy con tăng của A. Dãy m[i] là dãy giảm dần. Độ dài của m chính là số lượng nhỏ nhất của các dãy

Bài toán sắp xếp búp bê Nga
(http://poj.org/problem?id=3636)

Nếu coi dãy con tăng là một dãy của các cặp (A, B) với A là giá trị, B là index của A trong dãy, thì ta sẽ có bài toán búp bê Nga. Cách giải giống như cách giải bài đếm số lượng dãy con tăng nhỏ nhất.

def could_eat(d1, d2):
    return d1[0] > d2[0] and d1[1] > d2[1]


def find_position(a, value, l, h):
    if h < 0 or not could_eat(value, a[h]):
        return -1

    while l < h:
        mid = (l + h) // 2
        could_eat_current = could_eat(value, a[mid])
        could_eat_next = could_eat(value, a[mid + 1])
        if not could_eat_current and could_eat_next:
            return mid + 1
        elif could_eat_current:
            h = mid
        else:
            l = mid + 1
    return l


def solution(A):
    size = len(A)
    # sort A with w increase, and h decrease
    A.sort(key=lambda (w, h): (w, -h))

    m = [-1] * size
    msize = -1
    for i in xrange(0, size):
        pos = find_position(m, A[i], 0, msize)
        if pos == -1:
            msize += 1
            m[msize] = A[i]
        else:
            m[pos] = max(m[pos], A[i])

    return msize + 1

if __name__ == '__main__':
    cases = int(input())
    for i in xrange(cases):
        n = input()
        nums = raw_input().split()
        A = []
        for i in xrange(n):
            A.append((int(nums[i * 2]), int(nums[i * 2 + 1])))
        print solution(A)


import unittest

class TestSolution(unittest.TestCase):
    def test_solution(self):
        self.assertEquals(
            1, solution([(20, 30), (40, 50), (30, 40)]))
        self.assertEquals(
            2, solution([(20, 30), (10, 10), (30, 20), (40, 50)]))
        self.assertEquals(
            3, solution([(10, 30), (20, 20), (30, 10)]))
        self.assertEquals(
            2, solution([(10, 10), (20, 30), (40, 50), (39, 51)]))
        self.assertEquals(
            3,
            solution([
                (10, 10), (10, 30), (10, 10), (20, 30), (20, 30),
                (40, 50), (39, 51), (30, 50)]))
Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

kiennt

29 bài viết.
230 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
82 18
Mọi chuyện bắt đầu từ nắm 2013 trong quá trình xây dựng chức năng login với Facebook, tôi đã tìm ra một cách để tấn công vào các hệ thống login với...
kiennt viết gần 2 năm trước
82 18
White
26 5
1. Đặt vấn đề Một trong các vấn đề của một hệ thống backend là bài toán điều phối request tới các nguồn dữ liệu. Xét bài toán với một hệ thống bl...
kiennt viết hơn 1 năm trước
26 5
White
22 4
Mở đầu Tôi đang học về (Link) (Link) (hệ thống phân tán). Đây là một lĩnh vực rất hay và khó (đối với tôi). Phần lớn các hệ thống máy tính hiện na...
kiennt viết hơn 1 năm trước
22 4
Bài viết liên quan
White
41 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 2 tháng trước
41 7
White
2 0
What is competitive programming? Sites like CodeForces, TopCoder, HackerRank, CodeChef,... ACMICPC, Olympiad in Informatics (for high school stude...
Nguyễn Lê Vũ Long viết 7 tháng trước
2 0
White
71 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết hơn 1 năm trước
71 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
29 bài viết.
230 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!