Hiểu bài toán

Bài toán yêu cầu đếm số lần doanh thu của Thor tăng và giảm giữa các tháng liên tiếp. Cụ thể, với danh sách doanh thu của n tháng, ta cần đếm:

• Số lần doanh thu tăng: khi doanh thu tháng sau lớn hơn doanh thu tháng trước.
• Số lần doanh thu giảm: khi doanh thu tháng sau nhỏ hơn doanh thu tháng trước. Nếu doanh thu không thay đổi (bằng nhau), không được tính là tăng hay giảm.

Ví dụ: [10, 5, 20, 20, 4, 5, 2, 25, 1]

• Tăng: 10->20, 4->5, 2->25 (tổng 3 lần) nhưng theo hint thì increase là 2 lần (10->20, 20->25? Wait, hint says: 10->20->25 is 2 increases. This implies we count 'upward movements' as segments, not individual adjacent pairs. Wait, re-reading hint: 'tăng 2 lần: 10 -> 20 -> 25'. This means 10->20 (1 lần) và 20->25 (1 lần) tổng 2. Wait, in the sequence 10, 5, 20, 20, 4, 5, 2, 25, 1: Adjacent pairs increasing: (10,5) no, (5,20) yes, (20,20) no, (20,4) no, (4,5) yes, (5,2) no, (2,25) yes. That's 3 increases. BUT the hint says output is '2 4'. And the hint explanation says: 'tăng 2 lần: 10 -> 20 -> 25'. This implies the problem asks for the number of 'peaks' or 'increasing sequences' or perhaps strictly strictly strictly... Ah, looking at the code solutions provided:

Solution 1: if (x > k) { t++; k = x; } if (x < q) { g++; q = x; } Here k tracks the maximum seen so far, q tracks the minimum seen so far. Wait, this logic counts: Increase: Whenever current value > previous maximum. This counts the number of 'new records' (strictly increasing peaks). Decrease: Whenever current value < previous minimum. This counts the number of 'new lows'.

Let's trace with input: 10, 5, 20, 20, 4, 5, 2, 25, 1 k=-inf, q=+inf 10: >k -> t=1, k=10. g=1, q=10. (Wait, code initializes k=x; q=x on first, so loop starts from 1).

Let's trace Solution 1 logic carefully: k is max, q is min. Init: i=0, x=10. k=10, q=10. i=1, x=5. 5 > 10? No. 5 < 10? Yes. g++ (g=1), q=5. i=2, x=20. 20 > 10? Yes. t++ (t=1), k=20. 20 < 5? No. i=3, x=20. 20 > 20? No. 20 < 5? No. i=4, x=4. 4 > 20? No. 4 < 5? Yes. g++ (g=2), q=4. i=5, x=5. 5 > 20? No. 5 < 4? No. i=6, x=2. 2 > 20? No. 2 < 4? Yes. g++ (g=3), q=2. i=7, x=25. 25 > 20? Yes. t++ (t=2), k=25. 25 < 2? No. i=8, x=1. 1 > 25? No. 1 < 2? Yes. g++ (g=4), q=1.

Result: t=2, g=4. Matches sample output.

So the problem definition is NOT adjacent changes. It is:

• Count how many times the revenue reaches a NEW ALL-TIME HIGH (strictly greater than any previous month).
• Count how many times the revenue reaches a NEW ALL-TIME LOW (strictly lower than any previous month).

Wait, the hint says: 'tăng 2 lần: 10 -> 20 -> 25'. This confirms it counts the number of times a new maximum is reached. Decreases: '10 -> 5 -> 4 -> 2 -> 1'. This counts the number of times a new minimum is reached.

Constraint: 1 < n < 1000. Values up to 10^8.

This is a classic 'Record Breaking' problem.

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

Cách Duyệt đơn giản theo định nghĩa (Tìm max/min mới)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];

    int increases = 0;
    int decreases = 0;

    // Biến lưu giá trị cao nhất và thấp nhất đã thấy tính đến thời điểm hiện tại
    int max_so_far = a[0];
    int min_so_far = a[0];

    // Bắt đầu từ phần tử thứ 2 (tháng thứ 2)
    for(int i=1; i<n; i++) {
        // Nếu tháng này cao hơn tất cả các tháng trước đó => Tăng
        if(a[i] > max_so_far) {
            increases++;
            max_so_far = a[i]; // Cập nhật giá trị cao nhất
        }
        // Nếu tháng này thấp hơn tất cả các tháng trước đó => Giảm
        else if(a[i] < min_so_far) {
            decreases++;
            min_so_far = a[i]; // Cập nhật giá trị thấp nhất
        }
    }

    cout << increases << " " << decreases << endl;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n) (to store array, can be O(1) if reading on the fly)

Cách tiếp cận này dựa trên việc hiểu chính xác định nghĩa của 'tăng' và 'giảm' trong bài toán (theo như các giải pháp đã cho và gợi ý).

• Ta duyệt qua danh sách doanh thu.
• Giữ hai biến: max_so_far (giá trị cao nhất đã gặp) và min_so_far (giá trị thấp nhất đã gặp).
• Khởi tạo chúng bằng giá trị tháng đầu tiên.
• Với mỗi tháng tiếp theo:
  • Nếu doanh thu > max_so_far: Đây là một lần 'tăng' mới (đạt đỉnh cao mới). Tăng biến đếm và cập nhật max_so_far.
  • Nếu doanh thu < min_so_far: Đây là một lần 'giảm' mới (đáy thấp mới). Tăng biến đếm và cập nhật min_so_far.
  • Nếu nằm giữa, không làm gì.
• Độ phức tạp thời gian là O(n) do duyệt một lần. Không gian O(n) nếu lưu mảng, hoặc O(1) nếu nhập liệu trực tiếp.

Cách Tối ưu không gian (Xử lý trực tiếp)

#include <iostream>
using namespace std;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    int increases = 0;
    int decreases = 0;
    int max_so_far, min_so_far;

    // Đọc tháng đầu tiên và khởi tạo biến theo dõi
    int current_month;
    cin >> current_month;
    max_so_far = current_month;
    min_so_far = current_month;

    // Duyệt các tháng còn lại
    for(int i = 1; i < n; i++) {
        cin >> current_month;

        if (current_month > max_so_far) {
            increases++;
            max_so_far = current_month;
        } else if (current_month < min_so_far) {
            decreases++;
            min_so_far = current_month;
        }
    }

    cout << increases << " " << decreases;

    return 0;
}

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

Đây là phiên bản tối ưu hóa của phương pháp đầu tiên.

• Thay vì lưu trữ toàn bộ danh sách n tháng vào mảng (tốn O(n) bộ nhớ), ta chỉ cần xử lý dữ liệu khi đọc vào.
• Biến current_month lưu giá trị của tháng đang xét.
• Hai biến max_so_far và min_so_far vẫn được sử dụng để theo dõi kỷ lục.
• Sử dụng ios_base::sync_with_stdio(false); cin.tie(0); để tăng tốc độ nhập xuất, hữu ích trong lập trình thi đấu.
• Phương pháp này giải quyết bài toán một cách trực tiếp và hiệu kiệm bộ nhớ nhất.

Cách Tối ưu Logic (Code ngắn)

#include <iostream>
using namespace std;

int main() {
    int n, x, k, q, t = 0, g = 0; 
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x;
        if (i == 0){
            k = x; q = x; 
        } else {
            if (x > k){
                t++; k = x; 
            } 
            if (x < q){
                g++; q = x; 
            } 
        } 
    } 
    cout << t << " " << g; 
}

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

Đây là cách viết c cực kỳ ngắn gọn và hiệu quả của Logic 'Tìm max/min mới'.

• Sử dụng biến k để lưu giá trị lớn nhất (key max) và q để lưu giá trị nhỏ nhất (key min).
• t đếm số lần tăng, g đếm số lần giảm.
• Trong vòng lặp:
  • i == 0: Gán k và q bằng giá trị đầu tiên.
  • i > 0:
    • Nếu x > k: Tăng t và cập nhật k = x.
    • Nếu x < q: Tăng g và cập nhật q = x.
• Lưu ý: Sử dụng hai câu lệnh if riêng biệt (không else if) là an toàn và đúng đắn trong trường hợp hiếm hoi giá trị nhập vào có thể cùng lúc phá kỷ lục cả tăng và giảm (ví dụ nếu k và q chưa được cập nhật đúng cách, nhưng với logic này thì k và q luôn là min/max của các phần tử trước đó, nên một số không thể cùng lúc lớn hơn max và nhỏ hơn min của quá khứ được). Tuy nhiên, trong ngữ cảnh bài này (duyệt tuần tự), việc dùng if riêng biệt hoặc else if đều cho kết quả chính xác như nhau vì x không thể vừa lớn hơn max cũ vừa nhỏ hơn min cũ được. Code này là tối ưu nhất về mặt viết code.

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

Bài học kinh nghiệm

• Bài toán không yêu cầu đếm số lượng các cặp tháng liên tiếp thay đổi (tăng/giảm), mà yêu cầu đếm số lần doanh thu đạt mức cao/thấp mới so với toàn bộ quá khứ.
• Cần phân biệt rõ giữa 'trend' (xu hướng) và 'record breaking' (phá kỷ lục). Dựa vào sample và code accepted, bài này là 'Record Breaking'.
• Có thể giải quyết bài toán chỉ với 3 biến (current, max, min) mà không cần lưu mảng, đạt độ phức tạp không gian O(1).

Lỗi thường gặp

• Lầm tưởng bài toán yêu cầu đếm số lần doanh thu tăng/giảm giữa các tháng liền kề (adjacent comparison). Ví dụ: 10 -> 5 -> 20 sẽ đếm 1 tăng (5->20), 1 giảm (10->5). Nhưng đáp án đúng với logic bài là 1 tăng (20 vượt 10), 1 giảm (5 vượt 10 theo chiều giảm).
• Quên xử lý trường hợp n=1 (nếu có). Tuy đề bài n>1 nhưng code nên vững.
• Sử dụng else if một cách sai lầm nếu logic tính toán có thể cho phép một phần tử cùng lúc là max mới và min mới (trong các bài toán khác, ví dụ tính range). Ở bài này, nếu chỉ dùng else if với logic max và min độc lập thì an toàn. Tuy nhiên, nếu viết code phức tạp hơn (vd: update max rồi dùng max đó để so sánh min) thì có thể sai.