Editorial for streak: Tung đồng xu

Hiểu bài toán

Bài toán yêu cầu tìm độ dài dải liên tiếp dài nhất của hai loại kết quả tung đồng xu: mặt ngửa (Heads) và mặt sấp (Tails). Với N lần tung (N ≤ 50), đầu vào là danh sách các chuỗi 'Heads' hoặc 'Tails', đầu ra là hai số nguyên: độ dài dải liên tiếp dài nhất của 'Heads' và độ dài dải liên tiếp dài nhất của 'Tails'. Ví dụ: Input 'Heads, Tails, Tails, Tails, Tails, Heads, Heads, Tails' cho Output '2 4' (2 mặt ngửa liên tiếp, 4 mặt sấp liên tiếp).

Các cách tiếp cận

Cách Duyệt và theo dõi (Tracking)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int curHeads = 0, curTails = 0;
    int maxHeads = 0, maxTails = 0;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        if (s == "Heads") {
            curHeads++;
            curTails = 0;
            maxHeads = max(maxHeads, curHeads);
        } else {
            curTails++;
            curHeads = 0;
            maxTails = max(maxTails, curTails);
        }
    }

    cout << maxHeads << " " << maxTails;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Phương pháp này sử dụng hai biến đếm curHeads và curTails để theo dõi độ dài dải liên tiếp hiện tại cho mỗi loại. Khi gặp 'Heads', tăng curHeads và reset curTails về 0 (và ngược lại). Đồng thời cập nhật biến lưu độ dài lớn nhất (maxHeads, maxTails) mỗi khi có thay đổi. Đây là cách tiếp cận trực quan và hiệu quả nhất.

Cách Theo dõi chung (Duyệt duy nhất)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    string prev = "";
    int streak = 0;
    int maxHeads = 0, maxTails = 0;

    for (int i = 0; i < n; i++) {
        cin >> s;
        if (s == prev) {
            streak++;
        } else {
            streak = 1;
            prev = s;
        }

        if (s == "Heads") 
            maxHeads = max(maxHeads, streak);
        else 
            maxTails = max(maxTails, streak);
    }

    cout << maxHeads << " " << maxTails;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Tiếp cận này chỉ sử dụng một biến streak để đếm độ dài dải liên tiếp hiện tại. Nếu kết quả hiện tại giống kết quả trước đó (prev), tăng streak. Ngược lại, reset streak về 1 và cập nhật prev. Sau đó so sánh streak với maxHeads hoặc maxTails tùy vào loại hiện tại. Cách này tổng quát hơn nhưng logic khó đọc hơn một chút so với cách đầu tiên.

Cách Quản lý biến rời rạc

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    ll n;
    cin >> n;

    ll h = 0, t = 0;     
    ll mh = 0, mt = 0; 

    for (ll i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "Heads") {
            h++;
            t = 0;
            mh = max(mh, h);
        } else {
            t++;
            h = 0;
            mt = max(mt, t);
        }
    }

    cout << mh << " " << mt;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là biến thể của Approach 1, sử dụng các tên biến ngắn hơn (h cho Heads, t cho Tails, mh và mt cho max). Logic xử lý hoàn toàn tương tự: tăng biến đếm tương ứng và reset biến còn lại về 0.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể giải quyết trong một lần duyệt (One-pass) với độ phức tạp thời gian O(N) và không gian O(1).
• Mấu chốt là việc xử lý việc chuyển đổi trạng thái: khi gặp một mặt đồng xu mới, dải liên tiếp của mặt cũ bị chấm dứt và dải mới bắt đầu.

Lỗi thường gặp

• Quên reset biến đếm của mặt đối diện (ví dụ: khi tăng biến Heads mà không reset biến Tails về 0).
• Quên cập nhật giá trị max (maxHeads hoặc maxTails) tại thời điểm cuối cùng của dải liên tiếp.