Tại sao Python phù hợp cho Competitive Coding

Lập trình thi đấu (competitive programming) là viết code sử dụng thuật toán hiệu quả với cấu trúc dữ liệu phù hợp. Chúng kiểm tra kỹ năng lập trình viên ở nhiều cấp độ.

Với thuật toán và cấu trúc dữ liệu, bạn phải giải quyết bài toán giả định bằng các logic khác nhau. Không chỉ giải quyết mà còn phải tìm giải pháp cực kỳ hiệu quả về độ phức tạp thời gian và không gian.

Ví dụ bài toán

Cho chuỗi s độ dài n chỉ chứa chữ cái Latinh thường. Substring là dãy con liên tiếp. Tính số cách xóa đúng một substring sao cho các ký tự còn lại đều giống nhau (số ký tự khác nhau bằng 0 hoặc 1). Đảm bảo có ít nhất hai ký tự khác nhau trong s. Có thể xóa toàn bộ chuỗi và phải xóa ít nhất một ký tự.

Có thể dùng bất kỳ ngôn ngữ nào. Vậy tại sao chọn Python?

Tốc độ viết code (Speed)

Python giúp giảm đáng kể thời gian viết code, thay vào đó tập trung suy nghĩ logic. Trong thi đấu, thời gian là yếu tố then chốt. "Tốc độ" ở đây là tốc độ viết giải pháp, không phải tốc độ chạy của ngôn ngữ.

Thư viện phong phú (Huge variety of libraries)

Python đi kèm nhiều thư viện chuẩn, rất hữu ích cho competitive programming.

i. Common inbuilt functions

• Python cung cấp nhiều hàm phổ biến: count, min, max, sorted... Giúp bỏ qua việc viết code cho các thủ tục tầm thường. Hàm Python dùng thuật toán tốt nhất. Ví dụ: sorted() dùng Timsort - stable sort, worst-case O(nlogn), best-case O(1).

#abs() print(abs(-7))
#max() print(max(2, 13, 4, 20))
#memoryview() print(memoryview(bytes(9)))
#object() o = object(); print(type(o))
#pow() print(pow(2,6))
#reversed a = reversed([3, 13, 2, 1]); print(a)
#sorted() print(sorted([9, 2, 4, 13, 7]))
#sum() print(sum([2, 9, 12, 19]))
# type() print(type([])) print(type({}))
#zip() print(set(zip([1,2],[3,4,5])))

ii. List Comprehensions

• Python có list comprehension tuyệt vời. Viết code 5-20 dòng chỉ trong 1 dòng. Có thể lồng vòng lặp và điều kiện.

# Duyệt chuỗi dùng List Comprehension
l_string = [letter for letter in 'Tutorialspoint']
print(l_string)
# List Comprehension vs Lambda
l_lambda = list(map(lambda x: x, 'Tutorialspoint'))
print(l_lambda)

['T', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't']
['T', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't']

iii. Standard library (Lợi thế lớn)

• Python có thư viện chuẩn rất mở rộng, cung cấp nhiều tiện ích. Các thư viện đi kèm nhiều cấu trúc dữ liệu loại bỏ việc triển khai thủ công, và itertools là phần quan trọng.
• Ví dụ: tạo tất cả permutation của list và lưu vào list khác, dùng list comprehension + permutation từ itertools.

Python Standard Library

iv. Đa dạng cấu trúc dữ liệu

• Python cung cấp nhiều cấu trúc dữ liệu: dictionary, sets, tuple, list... đi kèm gói chuẩn.

v. Dễ sử dụng (Ease of use)

Cú pháp Python đọc như pseudocode, rất dễ và nhanh.

>>> print("hello world!")
hello world!
>>> sum([3, 4, 3,5])
15
>>> max(3, 4, 5, 13,2)
13
>>> min(3, 4, 5, 13, 2)
2