Bài "New year and Ascent sequence" trên codeforces

[Circuit]

Link phần bài tập: Problem - 1284B - Codeforces

int main() {
    int n, ans;

    cin >> n;

    ans = 0;
    vector<int> Min, Max;

    for (int i = 0; i < n; i++) {
        int len, min_so_far, max_so_far;
        bool has_ascent = false;

        cin >> len;

        min_so_far = numeric_limits<int>::max();
        max_so_far = numeric_limits<int>::min();

        for (int j = 0; j < len; j++) {
            int x;

            cin >> x;

            if (min_so_far < x) has_ascent = true;

            min_so_far = min(x, min_so_far);
            max_so_far = max(x, max_so_far);
        }

        if (has_ascent)
            ans += 2 * n - 1;
        else {
            Max.push_back(max_so_far);
            Min.push_back(min_so_far);
        }
    }

    sort(Max.begin(), Max.end());

    for (int i = 0; i < (int)Min.size(); i++) {
        ans += Max.end() - upper_bound(Max.begin(), Max.end(), Min[i]);
    }

    cout << ans;
    return 0;
}

Ascent ở đây em xin tạm dịch là cặp tăng.
Ý tưởng của em trong bài này là xét các dãy đã có sẵn “cặp tăng”. Đối với các cặp này thì để nó trước hay sau dãy khác cũng đều cho ra dãy có “cặp tăng” nhưng mình phải bỏ ra trường hợp (dãy A, dãy A) vì đảo của nó bị trùng. Cho nên đối với dãy có sẵn “cặp tăng”, em += 2n - 1.

Còn đối với các cặp không có cặp tăng(dãy không tăng) thì em coi như ta có 2 vị trí TRƯỚC-SAU.

TRƯỚC thì xét min, SAU thì xét max của dãy.

Đầu tiên em sắp xếp mảng Max.

Ta có: nếu dãy ghép là A1 + A2 tồn tại cặp tăng thì ta phải có minA1 < maxA2. Do đó hướng làm của em là:

Xét mọi min của các dãy(tức là xét mọi trường hợp 1 dãy nào đó đứng trước), binary search giá trị min đó trên mảng Max để tìm số giá trị Max lớn hơn giá trị min đang xét.(tức là với dãy đó đứng trước thì các dãy phía sau em sẽ xét max để tìm dãy hợp lệ).

Cách xét như vậy thì với input:
10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100

Cho ra 74 trong khi đáp án là 72 . Không hiểu em đếm trùng ở đâu. Mong các anh giúp đỡ ạ!

[tntxtnt]

chắc trùng ở 2 dãy ascent này
20 73
62 24 39

mỗi dãy cộng với 2n-1 nghĩa là đếm 2 lần rồi :V
20 73 cho ra 2 dãy 20 73 62 24 39 và 62 24 39 20 73
62 24 39 lại cho ra 2 dãy 62 24 39 20 73 và 20 73 62 24 39 2 dãy nãy giống nhau

ờ ờm chắc lấy kết quả trừ số dãy ascent hay lấy 74-2 là được :V

[Circuit]

Thử rồi bạn ơi 🥲. Input thứ hai trong link sẽ fail. Với lại 20 73 20 73 vẫn chọn được theo đề bài.

[tntxtnt]

ờ nếu 3 dãy A B C là dãy ascent thì cộng 2n-1 nó tạo ra
AA AB AC BA CA
BB BA BC AB CB
CC CA CB AC BC
thì có tới 6 dãy trùng, vậy là phải trừ 6 với 3 dãy ascent :V
tìm công thức đi :V :V 4 dãy, 5 dãy, k dãy thì sao :V

có lẽ là trừ (k^2 - k)

k dãy ascent thì tạo ra 2k - 1 dãy, trừ 1 dãy XX còn 2k-2, nhân k lần là 2k^2 - 2k, trùng hết phân nửa thì chia đôi là ra số dãy bị trùng là k^2 - k