Count Number of Teams (LeetCode 1395)

Nguồn: LeetCode 1395 Độ khó: Trung bình Quy hoạch động Đếm Vét cạn

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

1395. Count Number of Teams – Đếm số đội (LeetCode, độ khó Medium)

Có $n$ người lính đứng thành một hàng. Mỗi người lính được gán một giá trị rating duy nhất (không trùng với ai khác).

Bạn phải lập một đội gồm 3 người lính trong số họ theo các quy tắc sau:

• Chọn 3 người lính có chỉ số $(i, j, k)$ với rating lần lượt là $($rating[i], rating[j], rating[k]$)$.
• Một đội là hợp lệ nếu: $($rating[i] $\lt$ rating[j] $\lt$ rating[k]$)$ hoặc $($rating[i] $\gt$ rating[j] $\gt$ rating[k]$)$, trong đó $0 \le i \lt j \lt k \lt n$.

Hãy trả về số đội bạn có thể lập được thỏa các điều kiện trên. (Một người lính có thể thuộc nhiều đội khác nhau.)

Ràng buộc:

• $n ==$ rating.length
• $3 \le n \le 1000$
• $1 \le$ rating[i] $\le 10^5$
• Tất cả các số trong rating đều khác nhau.

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm numTeams trong class Solution. Để chạy được như một chương trình bình thường (và dùng được khung chạy tay bên dưới), mình đặt thêm định dạng:

• Dữ liệu vào: dòng đầu là số nguyên $n$, dòng thứ hai gồm $n$ số nguyên rating[0], rating[1], ..., rating[n-1].
• Kết quả: một số nguyên là số đội hợp lệ.

Giải thích ví dụ của đề:

• Ví dụ 1: lập được 3 đội thỏa điều kiện: $(2, 3, 4)$, $(5, 4, 1)$, $(5, 3, 1)$.
• Ví dụ 2: không lập được đội nào thỏa điều kiện.
• Ví dụ 3: mảng tăng dần nên chọn 3 người bất kỳ đều được: $\binom{4}{3} = 4$ đội.

1395. Count Number of Teams (LeetCode, Medium)

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
• A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

• n == rating.length
• 3 <= n <= 1000
• 1 <= rating[i] <= 10^5
• All the integers in rating are unique.

Ví dụ 1 – LeetCode

Input: rating = [2,5,3,4,1]
Output: 3

Ví dụ 1 – stdin / stdout

5
2 5 3 4 1
---
3

Ví dụ 2 – LeetCode

Input: rating = [2,1,3]
Output: 0

Ví dụ 2 – stdin / stdout

3
2 1 3
---
0

Ví dụ 3 – LeetCode

Input: rating = [1,2,3,4]
Output: 4

Ví dụ 3 – stdin / stdout

4
1 2 3 4
---
4

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Tóm tắt đề bài: cho một mảng rating gồm các số khác nhau. Đếm số bộ 3 chỉ số $(i, j, k)$ sao cho:

• $i \lt j \lt k$;
• rating[i] < rating[j] < rating[k] (tăng chặt) hoặc rating[i] > rating[j] > rating[k] (giảm chặt).

Với ví dụ 1, mảng $[2, 5, 3, 4, 1]$: bộ tăng duy nhất là $(2, 3, 4)$ (chỉ số $0, 2, 3$); các bộ giảm là $(5, 4, 1)$ (chỉ số $1, 3, 4$) và $(5, 3, 1)$ (chỉ số $1, 2, 4$). Tổng cộng $3$ đội. Các bạn để ý: các số trong bộ phải giữ đúng thứ tự xuất hiện trong mảng, không được tự sắp xếp lại nhé.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn 3 vòng lặp · O(N³)Cách 2Quy hoạch động · O(N²)

Cách 1Vét cạn mọi bộ ba – O(N³)

Làm theo đúng đề: 3 vòng lặp lồng nhau chọn $i \lt j \lt k$, bộ nào tăng chặt hoặc giảm chặt thì đếm. Cách này để các bạn có cái so sánh và kiểm tra đáp án thôi nhé.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = (int) rating.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (rating[i] < rating[j] && rating[j] < rating[k]) {
                        ans++;
                    }
                    if (rating[i] > rating[j] && rating[j] > rating[k]) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> rating(n);
    for (int i = 0; i < n; i++) cin >> rating[i];
    Solution sol;
    cout << sol.numTeams(rating);
    return 0;
}

import sys
from typing import List

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if rating[i] < rating[j] < rating[k]:
                        ans += 1
                    if rating[i] > rating[j] > rating[k]:
                        ans += 1
        return ans

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    rating = list(map(int, data[1:1 + n]))
    print(Solution().numTeams(rating))

if __name__ == "__main__":
    main()

C++▶ Chạy tay từng dòng codeCách 1: thử mọi bộ i < j < k, đếm bộ tăng chặt hoặc giảm chặt.

Dữ liệu vào (stdin) – sửa thoải mái5 2 5 3 4 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4class Solution {

5public:

6 int numTeams(vector<int>& rating) {

7 int n = (int) rating.size();

8 int ans = 0;

9 for (int i = 0; i < n; i++) {

10 for (int j = i + 1; j < n; j++) {

11 for (int k = j + 1; k < n; k++) {

12 if (rating[i] < rating[j] && rating[j] < rating[k]) {

13 ans++;

14 }

15 if (rating[i] > rating[j] && rating[j] > rating[k]) {

16 ans++;

17 }

18 }

19 }

20 }

21 return ans;

22 }

23};

24

25int main() {

26 int n;

27 cin >> n;

28 vector<int> rating(n);

29 for (int i = 0; i < n; i++) cin >> rating[i];

30 Solution sol;

31 cout << sol.numTeams(rating);

32 return 0;

33}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$ ngoài mảng đầu vào.
• Thời gian: số bộ $(i, j, k)$ là $\binom{n}{3} \approx \dfrac{n^3}{6}$, với $n = 1000$ là khoảng $1.66 \cdot 10^8$ lần kiểm tra ⇒ $O(N^3)$.

Không gian$O(1)$

Thời gian$O(N^3)$

Chạy được nhưng chậm

Bản C++ với $n = 1000$ vẫn chạy được vì phép so sánh rất nhẹ, nhưng $1.66 \cdot 10^8$ phép thì đã sát ngưỡng; bản Python thì chạy rất lâu. Ta cần cách tốt hơn.

Cách 2Quy hoạch động – O(N²)

Trước hết, ta nhận xét như sau:

Nhận xét: chỉ cần giải bài "tăng"

Nếu ta giải được bài toán đếm số bộ $(i, j, k)$ sao cho rating[i] < rating[j] < rating[k], thì với bài toán đếm số bộ rating[i] > rating[j] > rating[k], ta chỉ cần đảo ngược mảng rating lại và thực hiện y như cách giải bài toán đầu tiên là xong (một bộ giảm khi đọc từ trái sang chính là một bộ tăng khi đọc từ phải sang). Do đó bây giờ ta chỉ cần ưu tiên giải bài toán đếm bộ tăng.

Ta có thể xem bài toán đếm bộ tăng là: ta chọn lần lượt 1 giá trị, rồi 2 giá trị, rồi 3 giá trị, trong đó giá trị sau phải lớn hơn giá trị trước và vị trí của giá trị sau cũng phải lớn hơn vị trí của giá trị trước.

Định nghĩa trạng thái

Đánh số các phần tử từ $1$: phần tử thứ $x$ là rating[x - 1]. Gọi dp[x][j] là số cách chọn ra $j$ số (tăng dần, đúng thứ tự vị trí) mà số được chọn thứ $j$ chính là phần tử thứ $x$.

• Khởi tạo dp[0][0] = 1: "chưa chọn số nào" là một trạng thái xuất phát ảo ở vị trí $0$.
• Chuyển trạng thái: phần tử $x$ làm số thứ $j$ được nếu trước đó có phần tử $i \lt x$ làm số thứ $j - 1$ với rating[i-1] < rating[x-1] (hoặc $i = 0$ là trạng thái xuất phát), nên dp[x][j] = Σ dp[i][j-1] với các $i$ thỏa điều kiện.
• Kết quả: tổng các dp[x][3] với $x = 1..n$.

Trong code, mình cài đặt theo kiểu "đẩy" (thay vì "kéo"): duyệt từng trạng thái dp[i][j] đã tính xong, rồi cộng nó sang mọi dp[x][j + 1] với $x \gt i$ mà phần tử $x$ lớn hơn phần tử $i$. Hai kiểu này cho cùng kết quả, kiểu đẩy có lợi là trạng thái nào bằng $0$ thì continue bỏ qua luôn. Vì $i$ duyệt tăng dần nên khi tới dp[i][j] thì mọi $i' \lt i$ đã đẩy vào nó xong rồi.

Minh hoạ: bảng dp được "đẩy" như thế nào

Em nhập mảng rồi bấm Tiếp. Mỗi bước là một ô nguồn dp[i][j] (vàng) đẩy giá trị sang cột $j + 1$ của các vị trí $x \gt i$: ô xanh là được cộng (phần tử $x$ lớn hơn phần tử $i$), ô đỏ là bỏ qua. Làm xong lượt "tăng" thì đảo mảng, làm lại lượt thứ hai cho bộ "giảm".

rating

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé (phần main đọc stdin là mình thêm vào để chạy trên máy, nộp LeetCode thì chỉ cần phần dp + class Solution):

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

int dp[1005][4];

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = (int) rating.size();
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (dp[i][j] == 0) {
                    continue;
                }
                for (int x = i + 1; x <= n; x++) {
                    if (i == 0) {
                        dp[x][j + 1] += dp[i][j];
                    }
                    if (i != 0 && rating[i - 1] < rating[x - 1]) {
                        dp[x][j + 1] += dp[i][j];
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            ans += dp[i][3];
        }
        reverse(rating.begin(), rating.end());
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (dp[i][j] == 0) {
                    continue;
                }
                for (int x = i + 1; x <= n; x++) {
                    if (i == 0) {
                        dp[x][j + 1] += dp[i][j];
                    }
                    if (i != 0 && rating[i - 1] < rating[x - 1]) {
                        dp[x][j + 1] += dp[i][j];
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            ans += dp[i][3];
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> rating(n);
    for (int i = 0; i < n; i++) cin >> rating[i];
    Solution sol;
    cout << sol.numTeams(rating);
    return 0;
}

import sys
from typing import List

class Solution:
    def count_increasing(self, rating: List[int]) -> int:
        n = len(rating)
        dp = [[0] * 4 for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(n):
            for j in range(3):
                if dp[i][j] == 0:
                    continue
                for x in range(i + 1, n + 1):
                    if i == 0:
                        dp[x][j + 1] += dp[i][j]
                    if i != 0 and rating[i - 1] < rating[x - 1]:
                        dp[x][j + 1] += dp[i][j]
        return sum(dp[i][3] for i in range(1, n + 1))

    def numTeams(self, rating: List[int]) -> int:
        ans = self.count_increasing(rating)
        ans += self.count_increasing(rating[::-1])
        return ans

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    rating = list(map(int, data[1:1 + n]))
    print(Solution().numTeams(rating))

if __name__ == "__main__":
    main()

C++▶ Chạy tay từng dòng codeCách 2: QHĐ dp[x][j] kiểu đẩy, làm 2 lượt (mảng gốc và mảng đảo ngược).

Dữ liệu vào (stdin) – sửa thoải mái5 2 5 3 4 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int dp[1005][4];

5

6class Solution {

7public:

8 int numTeams(vector<int>& rating) {

9 int n = (int) rating.size();

10 memset(dp, 0, sizeof(dp));

11 dp[0][0] = 1;

12 int ans = 0;

13 for (int i = 0; i < n; i++) {

14 for (int j = 0; j < 3; j++) {

15 if (dp[i][j] == 0) {

16 continue;

17 }

18 for (int x = i + 1; x <= n; x++) {

19 if (i == 0) {

20 dp[x][j + 1] += dp[i][j];

21 }

22 if (i != 0 && rating[i - 1] < rating[x - 1]) {

23 dp[x][j + 1] += dp[i][j];

24 }

25 }

26 }

27 }

28 for (int i = 1; i <= n; i++) {

29 ans += dp[i][3];

30 }

31 reverse(rating.begin(), rating.end());

32 memset(dp, 0, sizeof(dp));

33 dp[0][0] = 1;

34 for (int i = 0; i < n; i++) {

35 for (int j = 0; j < 3; j++) {

36 if (dp[i][j] == 0) {

37 continue;

38 }

39 for (int x = i + 1; x <= n; x++) {

40 if (i == 0) {

41 dp[x][j + 1] += dp[i][j];

42 }

43 if (i != 0 && rating[i - 1] < rating[x - 1]) {

44 dp[x][j + 1] += dp[i][j];

45 }

46 }

47 }

48 }

49 for (int i = 1; i <= n; i++) {

50 ans += dp[i][3];

51 }

52 return ans;

53 }

54};

55

56int main() {

57 int n;

58 cin >> n;

59 vector<int> rating(n);

60 for (int i = 0; i < n; i++) cin >> rating[i];

61 Solution sol;

62 cout << sol.numTeams(rating);

63 return 0;

64}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: bảng dp kích thước $(n + 1) \times 4$ ⇒ $O(N)$.
• Thời gian: mỗi lượt có $n \times 3$ trạng thái, mỗi trạng thái đẩy sang tối đa $n$ vị trí ⇒ $O(3 \cdot N^2)$, làm 2 lượt vẫn là $O(N^2)$. Với $n = 1000$ chỉ khoảng $6 \cdot 10^6$ phép tính.

Không gian$O(N)$

Thời gian$O(N^2)$

Muốn nhanh hơn nữa?

Bài này có thể tối ưu xuống còn $O(N \log N)$ bằng cách dùng cây Fenwick (Fenwick tree) để lưu tổng các giá trị dp theo giá trị rating. Tuy nhiên cách này phức tạp và không hợp lắm với các bạn chưa biết nhiều thuật toán hay cấu trúc dữ liệu nâng cao, nên mình không trình bày ở đây. Với $n \le 1000$ thì $O(N^2)$ là quá đủ rồi.

Lưu ý nhỏ về kiểu int

Đáp án lớn nhất là khi mảng tăng (hoặc giảm) hoàn toàn: $\binom{1000}{3} = 166\,167\,000$, vẫn nằm trong int nên dùng int như code trên là an toàn.

Ghi chú của mình: code C++ và Python của cả 2 cách (chạy với stdin như định dạng mình đặt ở phần đề) đã được kiểm tra với 3 ví dụ của đề và 400 bộ test ngẫu nhiên nhỏ (rating khác nhau), so với nhau – khớp hết. Với $n = 1000$: Cách 1 (C++) khoảng 0.35 giây còn bản Python mất gần 30 giây; Cách 2 (C++) chưa tới 0.01 giây, bản Python khoảng 0.4 giây. Mảng tăng dần $n = 1000$ cho đáp án $166167000$ đúng bằng $\binom{1000}{3}$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇