Giải quyết bài toán Nhị phân Lẻ Tối đa và Xung đột Thời gian trong Perl Weekly Challenge 367

Giải quyết bài toán Nhị phân Lẻ Tối đa và Xung đột Thời gian trong Perl Weekly Challenge 367

Perl Weekly Challenge 367 mang đến hai bài toán thú vị xoay quanh thao tác chuỗi bit và xử lý logic khoảng thời gian. Chúng ta sẽ cùng đi sâu vào cách giải quyết Maximum Odd Binary (Số nhị phân lẻ tối đa) và Conflict Events (Sự kiện xung đột) dưới góc độ thuật toán và hiệu năng.

Phần 1: Số Nhị phân Lẻ Tối đa (Maximum Odd Binary)

Đề bài

Cho một chuỗi nhị phân chứa ít nhất một ký tự '1'. Nhiệm vụ của bạn là viết script sắp xếp lại các bit sao cho tạo ra số nhị phân lẻ lớn nhất có thể. Chuỗi kết quả được phép có các số 0 đứng đầu.

Phân tích thuật toán

Để tạo ra một số nhị phân lớn nhất, tất cả các bit '1' phải được dồn sang phía bên trái (các vị trí có trọng số cao nhất). Để đảm bảo số đó là lẻ, bit tận cùng (bên phải nhất) phải là '1'.

Do đó, cấu trúc kết quả mong muốn sẽ là: một nhóm các bit '1', tiếp theo là nhóm các bit '0', và cuối cùng là duy nhất một bit '1' làm đuôi. Bài toán trở thành việc tách và sắp xếp lại các bit này.

Các phương án giải quyết

1. Sắp xếp (Sorting)

Phương pháp đơn giản nhất là sắp xếp chuỗi theo thứ tự giảm dần để đưa tất cả '1' lên đầu, sau đó lấy bit '1' đầu tiên chuyển xuống cuối cùng.

sub mobSort($str)
{
    my @bits = sort { $b cmp $a } split(//, $str);
    push @bits, shift @bits;
    return join("", @bits);
}

• Ưu điểm: Dễ hiểu, trực quan.
• Nhược điểm: Độ phức tạp là $O(n \log n)$, chậm hơn các phương pháp khác.

2. Tách chuỗi (Splitting)

Thay vì sắp xếp, ta có thể tách chuỗi thành hai nhóm: nhóm bit '0' và nhóm bit '1'. Sau đó, ta chèn nhóm '0' vào giữa chuỗi '1' (trừ bit cuối cùng).

sub mobSplit($str)
{
    my @bit = ( "", "" );
    $bit[$_] .= $_ for split //, $str;

    substr($bit[1], -1, 0, $bit[0]);
    return $bit[1];
}

3. Đếm (Counting)

Đây là phương pháp tối ưu nhất vì chỉ cần đếm số lượng bit '0' và '1', sau đó tái tạo chuỗi mà không cần thao tác sắp xếp phức tạp.

sub mobCount($str)
{
    my $n = length($str);
    my $zero = ($str =~ tr/0/0/);

    return ("1" x ($n-$zero-1)) . ("0" x $zero) . ("1");
}

• Logic: Chuỗi kết quả gồm (số lượng 1 trừ 1) cái '1', nối tiếp bằng toàn bộ số '0', và kết thúc bằng một cái '1'.

So sánh hiệu năng (Benchmark)

Kết quả đo hiệu năng cho thấy phương pháp đếm vượt trội hơn hẳn:

• Sorting: 128,205 lượt/giây (chậm nhất)
• Splitting: 178,571 lượt/giây
• Counting: 2,500,000 lượt/giây (nhanh hơn tới 1850% so với sắp xếp)

Phần 2: Sự kiện Xung đột (Conflict Events)

Đề bài

Cho thời gian bắt đầu và kết thúc của hai sự kiện. Hãy xác định xem是否存在 sự xung đột (giao nhau) giữa hai sự kiện đó. Lưu ý: giao nhau phải là khoảng không rỗng, nếu một sự kiện kết thúc đúng lúc sự kiện kia bắt đầu thì không được tính là xung đột.

Phân tích vấn đề

Đây là bài toán kinh điển về việc kiểm tra sự giao nhau của hai khoảng (range overlap). Tuy nhiên, thách thức nằm ở việc xử lý định dạng thời gian dạng chuỗi ("HH:MM") và trường hợp khoảng thời gian vượt qua nửa đêm (ví dụ: từ 23:30 đến 00:30).

Giải pháp bao gồm các bước:

1. Chuyển đổi thời gian chuỗi thành số phút trong ngày.
2. Xử lý trường hợp vượt qua nửa đêm bằng toán tử modulo.
3. Kiểm tra xem hai khoảng thời gian có giao nhau không.

Triển khai chi tiết

Bước 1: Chuyển đổi thời gian

Hàm toMinute chuyển đổi định dạng "HH:MM" thành số nguyên đại diện cho phút.

sub toMinute($hhmm)
{
    my ($h, $m) = split(":", $hhmm);
    my $minute = $m + 60 * $h;
    return $minute;
}

Bước 2: Xác định khoảng thời gian

Hàm toRange tính toán khoảng thời gian sự kiện. Để xử lý việc qua nửa đêm, ta sử dụng modulo 1440 (số phút trong một ngày). Nếu thời gian bắt đầu lớn hơn thời gian kết thúc (qua ngày), phép tính modulo sẽ tự động điều chỉnh độ dài.

sub toRange($minBeg, $minEnd)
{
    my $duration = ($minEnd - $minBeg) % 1440;
    return [ $minEnd - $duration, $minEnd ];
}

Bước 3: Kiểm tra sự chồng lấn

Hai khoảng $[s1, e1]$ và $[s2, e2]$ giao nhau khi và chỉ khi $s1 < e2$ và $s2 < e1$.

sub isOverlap($range1, $range2)
{
    use enum qw( BEG=0 END=1 );
    return $range1->[END] > $range2->[BEG]
        && $range1->[BEG] < $range2->[END];
}

Hàm tổng hợp

Cuối cùng, ta ghép các hàm con lại để giải quyết bài toán hoàn chỉnh.

sub isConflict($event1, $event2)
{
    return isOverlap(toRange( map { toMinute($_) } $event1->@* ),
                     toRange( map { toMinute($_) } $event2->@* ) );
}

Qua hai bài toán này, chúng ta thấy rõ tầm quan trọng của việc chọn thuật toán phù hợp (từ Sorting sang Counting) và cách xử lý các trường hợp đặc biệt trong logic thời gian một cách tối giản và chính xác.