#2 - "Mình đã quá lạc hậu rồi ư?"

Trước khi tham gia ban truyền thông, tôi được Kiên giao phụ trách đội bài tập. Nhiệm vụ của tôi là phân chia công việc, kiểm tra lại bài tập và bộ test mà các tình nguyện viên gửi lên, hoặc đôi khi là ra đề nếu có thời gian. Thường thì song song với việc bắt lỗi trong đề bài, tôi cũng thử giải chúng để đánh giá độ khó của bài tập.

Có một lần tình nguyện viên gửi lên cho tôi bài tập này (mà sau đó đã trở thành bài CITY trong Free Contest 65), đại ý như sau:

"Cho một đồ thị có hướng n đỉnh, m cạnh. Có q truy vấn thuộc 2 loại, loại thứ nhất yêu cầu thêm 1 đỉnh mới và 1 cạnh có hướng mới nối từ nó đến một đỉnh đã có hoặc ngược lại, loại thứ hai hỏi xem có đường đi từ đỉnh x đến đỉnh y hay không.

n,m ≤ 50000, q ≤ 100000, dữ liệu đảm bảo tổng số đỉnh sau khi thêm không vượt quá 50000."

Link đề và bộ test: codecard.cf/problem/FC65CIT

Có thể nhận thấy rằng nếu đỉnh x không có đường đi đến đỉnh y thì dù có thực hiện bao nhiêu truy vấn loại một, đỉnh x vẫn không đến được y. Vì thế ta có thể dựng một đồ thị mới bằng cách làm tất cả các truy vấn loại một với đồ thị ban đầu, sau đó ta thực hiện lần lượt các truy vấn loại hai trên đồ thị mới đó.

Vấn đề ở đây là thuật toán trên có độ phức tạp O(n.m), tương đương = 2.5 tỷ, về lý thuyết không thể qua nổi giới hạn thời gian 1 hoặc 2 giây.

Tôi nằm nghĩ cách tối ưu sao cho nó thành O(n+m) cũng mất kha khá thời gian. Bạn có thể tạm dừng đọc và nghĩ thử một cách tối ưu về O(n+m) nếu cảm thấy có hứng thú.

…

Nếu không thể tìm ra được cách thì xin mời bạn đọc tiếp.

- "Bài CITY độ phức tạp bao nhiêu hả mọi người?" - tôi hỏi

- "" - một tình nguyện viên đáp

- "Nhưng mà 50000 thì sao qua được?" - tôi ngạc nhiên

- "bitset"

- "Hả???"

- "Bài này trên Hackerrank đó anh."

Tôi tự hỏi: “Phải chăng mình giờ đây đã quá lạc hậu?”

Lùi lại thời gian 2, 3 năm trước thì bitset vẫn chưa phải là một công cụ quá phổ biến. Nó là một kiểu dữ liệu trong ngôn ngữ C++ cho phép thực hiện các thao tác trên bit với nhiều ưu điểm về tốc độ và thời gian. Thường thì với một bài tập, người ra đề sẽ cố gắng điều chỉnh giới hạn sao cho phù hợp với một giới hạn thời gian cho trước để tránh phải dùng những cách tối ưu nhỏ lẻ như dùng bitset. Nhưng điều đấy không có nghĩa bitset là một thứ không cần thiết.

Với bài CITY, ta dùng bitset để lưu lại một dãy n bit cho mỗi đỉnh i, bit thứ j bằng 1 nghĩa là có đường đi từ đỉnh i đến đỉnh j. Để tính các dãy bitset này trước hết ta tạo các thành phần liên thông mạnh và quy hoạch động trên các thành phần liên thông mạnh đó theo thứ tự topo ngược.

Độ phức tạp về căn bản vẫn là O(n.m), nhưng bitset cho phép bạn thực hiện các thao tác AND, OR, XOR, NOT, SHIFT,... như với số nguyên thông thường, cộng thêm ưu thế tiết kiệm bộ nhớ (ngoại trừ điểm yếu bộ nhớ tĩnh) và đặc biệt là chạy nhanh, đã giải quyết được vấn đề lớn nhất của bài tập này.

…

Một ví dụ khác là bài BINARY của Free Contest 66, nội dung khá ngắn gọn như sau:

“Cho một dãy nhị phân a gồm N bit và một dãy nhị phân b gồm M bit. Bạn phải tính giá trị của biểu thức sau đây:

Giới hạn 1 ≤ M ≤ N ≤ 100000”

Link đề và bộ test: codecard.cf/problem/FC66BIN

Câu hỏi thứ nhất, liệu bitset có áp dụng được cho bài này không? Câu trả lời là bạn cứ cài thử đi rồi sẽ biết. Với test max của bài này, bitset tiêu tốn ít nhất 3 giây nếu dịch có -O2.

Câu hỏi thứ hai, liệu có cách nào để độ phức tạp là O(N) hay O(N.logN) hay không? Câu trả lời là tôi không biết, bạn có thể giúp tôi được không?

Thực ra thì mục đích của tôi đưa bài này vào kì thi là để tìm kiếm một lời giải triệt để từ cộng đồng Free Contest.

Mọi thứ có vẻ không được khả quan cho lắm. Cho đến hết 2 giờ đồng hồ đầu tiên của Free Contest 66 không ai có một lời giải thật sự hiệu quả. Nhưng rồi (như một thói quen)...

Thanks SLoW MoTIoN for your very creative solution!

Bạn trẻ này chắc không xa lạ gì với cộng đồng Free Contest, mặc dù tôi cũng không thực sự biết cậu ta là ai. SLoW MoTIoN không tạo ra lời giải O(N) hay O(N.logN). Tạo hai mảng f[N][60] và g[M][60], trong đó:

Gọi h(x) là số bit 1 của số x. Trong C++ hàm h(x) có thể được tính trong O(1) bằng lệnh __builtin_popcount(x).

Với mọi 1 i N-M+1 ta có:

(& là toán tử AND)

Như vậy với mỗi vị trí 1 i N-M+1, để tính được tổng trên ta mất M/60 bước. Tổng cộng độ phức tạp là:

theo bất đẳng thức Cauchy, vừa đủ để vượt qua giới hạn thời gian 1 giây.

...

Kiểu tối ưu này hình như là một đặc sản của Hackerrank thì phải?

"Cho dãy a gồm N số nguyên. Tìm số nguyên dương x sao cho:

1, Với mọi 1 ≤ i ≤ N,

2, Số bit 1 của x là nhỏ nhất.

3, Nếu có nhiều số x thỏa mãn, chọn số nhỏ nhất

Giới hạn: "

Bài gốc: The best mask - World Code Sprint 11 - 2017 - Hackerrank

Ta tìm tất cả các số thỏa mãn điều kiện 1 và chọn số thích hợp nhất trong số đó để thỏa mãn điều kiện 2 và 3. Một số x thỏa mãn điều kiện 1 khi và chỉ khi không tồn tại i mà ailà một dãy bit con của x. Từ đó ta dựng hàm:

dp(x) = 1 (nếu tồn tại ailà dãy bit con của x) hoặc 0 (nếu ngược lại)

Mỗi hàm dp(x) có thể tính trong O(26), mà 1 ≤ x ≤

nên tổng cộng thời gian để dựng hàm dp là , hơi lớn so với giới hạn thời gian cho phép.

Một cách để giảm độ phức tạp là tạo 1 hàm m(k) bằng 1 số nguyên dương 32 bit để tính gộp các giá trị dp(32k), dp(32k+1),…, dp(32k+31). Cách tính hàm m(k) mời các bạn đọc trên trang solution của bài tập này tại Hackerrank. Độ phức tạp cuối cùng sẽ là O(26.

/32).

Một bài tập luyện thêm cho tư tưởng này là bài NONZERO của Free Contest 61. Đề bài, bộ test và lời giải có tại: codecard.cf/problem/FC61NON. Rất khuyến khích các bạn làm thử.

…

Mặc dù không phải là một fan của tối ưu nhỏ lẻ, nhưng tôi không phủ nhận tầm quan trọng của tư tưởng này. Trong rất nhiều trường hợp, tối ưu nhỏ lẻ là một cách tinh tế để giảm thời gian chạy. Nếu nhìn rộng ra, bạn sẽ thấy khá nhiều những ví dụ tương tự khác. Chẳng hạn Merge Sort ra đời năm 1945 với độ phức tạp O(N.logN), và O(N.logN) cũng là độ phức tạp tối ưu của các thuật toán sắp xếp so sánh trực tiếp hai phần tử với nhau, nhưng người ta vẫn nghiên cứu để cho ra đời Quick Sort năm 1961 và Heap Sort năm 1964, chính vì trong những điều kiện khác nhau các thuật toán sẽ có ưu điểm và nhược điểm khác nhau, từ đó xem xét sử dụng cho hợp lý.

Tư duy của thuật toán giúp cho suy nghĩ trở nên linh hoạt, thiên biến vạn hóa nhưng cũng không làm mất đi tính hệ thống của toán học. Ở kì sau, chúng ta sẽ bàn về một chủ đề cũng thiên biến vạn hóa không kém kì này. Mời các bạn đón đọc, và đừng quên để lại bình luận của mình về {Kí ức thuật toán} trên trang facebook Kc97ble - Free Contest. Hẹn gặp lại!

TĨNH LẶNG

Số tiếp theo: {Kí ức thuật toán #3} Cắn test để làm gì?

Page updated

Google Sites

Report abuse