Chung kết ACM/ICPC PTIT 2023

Vào ngày 24/09/2022, Học viện Công nghệ Bưu Chính Viễn Thông đã tổ chức kỳ thi chung kết ICPC PTIT 2022. Sự kiện này đã thu hút 41 đội xuất sắc từ hơn 180 đội tham gia (không tính miền Nam). Kỳ thi đã diễn ra tại sảnh A2 của Học viện. Trong kỳ thi năm 2023, có sự tham gia đáng kể của các sinh viên khoá D22 và E22 (năm nhất). Đây là năm thứ hai mình tham gia cuộc thi này, và từ kinh nghiệm năm ngoái, mình đã có một số kinh nghiệm nhất định :v

image 18 - quochung.cyou PTIT

Đội của chúng mình, có tên là “ProPTIT. Ba bà đi bán lợn con”, gồm ba thành viên: Nguyễn Quốc Hưng (E2105), Nguyễn Mai Phương (D21CN01) và Lê Trí Tâm (D21). Sau khi đứng top 20 trong gần cả cuộc thi, chúng mình đã lội ngược dòng vào 15 phút cuối để giải lên 5 bài và giành được top 4 chung cuộc.

Đề thi năm 2023 có nhiều thay đổi so với 2022, nhìn chung các bài năm nay có nhiều đổi mới, tập trung vào giải thuật nhiều hơn, độ khó cũng khó hơn hẳn năm ngoái. Chắc đây cũng là một phần lí do số sinh viên năm nhất vào chung kết khá ít, chỉ có khoảng 1-2 bài cơ bản và còn lại là các bài với các thuật toán kinh điển như Quy hoạch động, dijkstra, greedy.

Một vài hình ảnh đáng chú ý trong kì thi

Thầy Cường và thầy Sơn tại vòng loại kì thi
Đội hình CLB Lập Trình PTIT checkin vòng loại
image 21 - quochung.cyou PTIT
khu vực thi 2023 tại hội trường a2
image 23 - quochung.cyou PTIT
image 24 - quochung.cyou PTIT

High Cohesion (Tương đồng cao) và Loosely Coupled (Liên kết lỏng)

image 36 - quochung.cyou PTIT

Mở đầu

Có thể bạn đã được nghe về các thuật ngữ này từ các câu hỏi trong các buổi phỏng vấn, trong một bài đăng medium nào đó, trong một cuộc thảo luận của anh em trong giang hồ. Vậy chính xác các term như high cohesion, low cohesion, loosely coupled, highly coupled có nghĩa là gì?

Cohesion (Tương đồng – Gắn kết)

image 34 - quochung.cyou PTIT

In computer programmingcohesion refers to the degree to which the elements inside a module belong together.[1] In one sense, it is a measure of the strength of relationship between the methods and data of a class and some unifying purpose or concept served by that class. In another sense, it is a measure of the strength of relationship between the class’s methods and data themselves.

Cohesion is an ordinal type of measurement and is usually described as “high cohesion” or “low cohesion”. Modules with high cohesion tend to be preferable, because high cohesion is associated with several desirable traits of software including robustness, reliability, reusability, and understandability. In contrast, low cohesion is associated with undesirable traits such as being difficult to maintain, test, reuse, or even understand.

Cohesion is often contrasted with coupling. High cohesion often correlates with loose coupling, and vice versa.[2] The software metrics of coupling and cohesion were invented by Larry Constantine in the late 1960s as part of Structured Design, based on characteristics of “good” programming practices that reduced maintenance and modification costs. Structured Design, cohesion and coupling were published in the article Stevens, Myers & Constantine (1974)[3] and the book Yourdon & Constantine (1979);[1] the latter two subsequently became standard terms in software engineering

Wikipedia

image 35 - quochung.cyou PTIT

Bản dịch

  • Trong khoa học máy tính, cohesion (tính tương đồng) thường được nhắc tới như một góc độ đánh giá nào đó, về việc các phần tử trong 1 module “tương đồng” với nhau.
  • Thông thường có thể nhắc tới việc sự liên kết bền chặt giữa các hàm (function) và các biến (property) trong 1 class có sự liên kết với nhau
  • Thông thường sẽ có 2 định nghĩa chính là “high cohesion” (tương đồng cao) và “low cohesion” (tương đồng thấp).
  • High cohesion thường đi cùng với việc code chặt chẽ hơn, dễ tái sử dụng, dễ bảo trì và dễ hiểu.

Vậy có thể hiểu là, high cohesion thường được ám chỉ các hàm và các biến trong 1 class đều cùng phục vụ mục đích, hoặc được sử dụng cho một ý nghĩa gì đó có tính tương đồng cao với nhau.

  • Trong cuốn Clean Code của Uncle Bobs có viết:
  • “Một class chỉ nên có ít biến. Các hàm trong class đó nên tác động lên một hoặc nhiều các biến trên. Nếu các hàm trong 1 class càng dùng nhiều các biến có sẵn, thì class có tính tương đồng càng cao”
  • => Tức là một class được đánh giá là tương đồng cao nên chỉ làm các tác vụ bên trong class đó, phục vụ chung 1 mục đích.

Ví dụ:

  • Bạn có một nhân vật trong 1 con game của mình. Bạn có các code logic cho việc nhân vật di chuyển từ các nút bấm trên bàn phím, và một số code logic để hiển thị việc nhân vật di chuyển trên trục toạ độ trên màn hình (render hình ảnh)
  • Nếu toàn bộ code đều nằm trong 1 class, code của bạn có 1 số hàm xử lí toán học cho nhân vật di chuyển, lại có 1 số hàm, biến để render hiển thị lên. Rõ ràng chúng có tính tương đồng yếu. Một cách đơn giản để nhận biết, bạn có thể nhìn các tên biến, tên hàm xem chúng có liên quan đến tên class không
  • Ví dụ: class tên là “InvoiceManager” (Quản lý hoá đơn), nếu có 1 hàm nào đó tên là “InHoaDon” thì cũng k ổn lắm, nó nên nằm trong “Printer”, hay có 1 hàm nào đó là “GuiEmailHoaDon” (thì hàm đó cũng nên làm trong class nào đó tên là EmailManager, …)

Coupled/Coupling (Tính liên kết)

  • Thoạt nghe thì nó có vẻ là 1 thuật ngữ trái ngược với cohesion? Vậy High Cohesion (tương đồng cao) thì sẽ có Tightly Coupling (Liên kết chặt) ?
  • Ở trường hợp này thì không. Cohesion thường dùng để xem xét giữa các phần tử (hàm, biến) trong 1 module (class). Trong khi Couple thường dùng để đánh giá tính liên kết giữa nhiều module
image 37 - quochung.cyou PTIT
  • Liên kết lỏng cho rằng, giữa các module với nhau, chúng không nên biết quá nhiều về nhau (liên kết quá chặt chẽ), mà chỉ nên giao tiếp với nhau qua 1 số phương thức mang tính “khái quát” nhất định một cách lỏng lẻo (loosely coupled)
image 39 - quochung.cyou PTIT
  • Ví dụ: Chiếc mũ đang “liên kết lỏng lẻo” với người đàn ông. Bạn dễ dàng thêm hoặc bỏ cái mũ ra mà không phải thay đổi gì người đàn ông cả. Khi code bạn làm được như vậy, thì nó là liên kết lỏng lẻo (loosely coupled)
image 40 - quochung.cyou PTIT

Ví dụ:

  • Bạn đang có một class xử lí việc bán lẻ bánh ở cửa hàng của mình tên là “CuaHang”. Cửa hàng sẽ lấy bánh từ class “XuongBanh”. Ban đầu class của bạn chỉ cần cứ lấy bánh từ Xưởng rồi bán thôi, việc rất đơn giản
image 41 - quochung.cyou PTIT
  • Nhưng một ngày đẹp trời, bạn nhận ra khách có vẻ thích những chiếc bánh có một chút muối, rồi thì bánh có thêm chút trang trí. Dĩ nhiên việc thêm chút thứ gia vị này, bạn cần thêm một chút tiền vào giá hàng, bạn sửa code thành như sau:
image 42 - quochung.cyou PTIT
  • Bạn có thể thấy, điều này đáp ứng nhu cầu của bạn. Tuy nhiên bạn thấy rõ ràng lúc này class Banh và CuaHang đang gắn rất chặt với nhau. CuaHang can thiệp quá nhiều vào class Banh, và có những phương thức không phù hợp lắm. (CuaHang chỉ nên là bán hàng thôi, chỉ nên có giá tiền). Rõ ràng bạn có thể làm chúng liên kết lỏng hơn như sau:
image 43 - quochung.cyou PTIT
  • Rõ ràng, lúc này class CuaHang chỉ cần tập trung lấy bánh và sau đó tính ra tổng tiền. Không cần quan tâm giá từng loại bánh từ xưởng nữa, vì việc tính tiền giá trị 1 đơn hàng sẽ được thực hiện bởi 1 class khác. CuaHang chỉ cần biết tôi sẽ có được tổng tiền từ hàm này, chứ không cần biết chính xác các class kia sẽ cụ thể làm gì, tính cái gì nữa (liên kết lỏng)
  • Mở rộng hơn nữa, ví dụ một ngày bạn muốn bán kẹo thì sao? Bán gấu bông? … Nhu cầu thị trường luôn thay đổi, bạn luôn muốn giàu hơn và mở rộng hơn nữa, lúc này bạn lại nhận ra, class CuaHang đang phụ thuộc quá nhiều vào xưởng bánh, mà thực chất ta chỉ cần lấy ra danh sách sản phẩm từ 1 xưởng nào đó thôi, ta có thể sửa thành như sau:
image 44 - quochung.cyou PTIT
  • Ta tạo 1 interface VatPham luôn có 1 phương thức tinhTien(), sau này, ta có thể làm bánh, kẹo, trái cây, .. chỉ cần chúng implement interface VatPham, ta luôn đảm bảo ta có thể lấy giá tiền từ chúng, còn implemention thực tế chúng tính tiền thế nào là việc của class con đó.
  • Tương tự, ta có 1 interface XuongSanXuat luôn trả về các danh sách vật phẩm, chúng có thể là xưởng bánh trả về bánh, xưởng kẹo trả về kẹo
  • Cửa hàng bây giờ khi khởi tạo có thể truyền vào xưởng mà chúng sẽ nhận đồ để bán
  • Cuối cùng, chuỗi cửa hàng của ta với nhiều cửa hàng, có thể có cửa hàng bánh, cửa hàng kẹo, còn việc chúng tính tiền thế nào làm gì cũng không phải việc của class lớn nữa. Dự án đã lỏng lẻo hơn nhiều ban đầu, và dễ mở rộng hơn.

Tổng kết

  • Với các dự án lập trình, thông thường chúng ta nên nhắm tới việc đạt được cùng lúc 2 yếu tố: High Cohesion (tương đồng cao trong 1 class/module) và Loosely Coupled (liên kết lỏng giữa nhiều module)
  • Việc đạt được 2 yếu tố trên giúp code dễ mở rộng, dễ bảo trì, ta dễ dàng tìm được nguyên căn nơi tạo lỗi vì chúng không share chung các code nhỏ với nhau, nên lỗi chỉ nên từ 1 nguồn
  • Đây là 1 kĩ năng thiết yếu với lập trình viên cho các dự án ngày càng cần mở rộng
  • High Cohesion cũng khá tương đồng với SRP trong SOLID, bạn có thể tìm hiểu thêm về SOLID tại đây http://quochung.cyou/tim-hieu-solid-5-nguyen-tac-thiet-ke-huong-doi-tuong-bang-java/

Chung kết ACM/ICPC PTIT 2022

Vừa qua 09/10/2022 Học viện Công nghệ Bưu Chính Viễn Thông đã tổ chức kì thi chung kết ICPC PTIT 2022 với 33 đội (chưa kể miền Nam) tại sảnh A2 của Học Viện. Kì thi 2022 có sự góp mặt phần lớn của khoá sinh viên D21, E21 (Năm nhất), tuy rằng kết quả chung cuộc bị chênh lệch phần lớn bởi thời gian sub bài chứ không có nhiều khác biệt giữa các team top giữa, nhưng kì thi vẫn đã diễn ra vô cùng hấp dẫn và kịch tích

image - quochung.cyou PTIT
Banner ICPC PTIT 2022

Đội của mình “ProPTIT. GGWP” Gồm mình Nguyễn Quốc Hưng E2105, Nguyễn Mai Phương (D21CN01), Nguyễn Đăng Minh (E2101) đã cố gắng giành thứ hạng #8 với 6 bài, khá tiếc là cây toán của team – Mai Phương đã đưa 2 teammate vào hai bài khó nhất đề bằng câu “hai bài này có vẻ làm được này”, mà bỏ qua 1 câu toán khá vừa tầm đúng ra nên làm.

Một vài hình ảnh đáng chú ý trong kì thi

image 1 - quochung.cyou PTIT
Thầy Từ Minh Phương phát biểu khai mạc
image 2 - quochung.cyou PTIT
Ban tổ chức ICPC PTIT 2022
image 3 - quochung.cyou PTIT
Đội 812 – Đội vô địch cũng là team First Solve bài đầu tiên
308852668 519902050142483 6200032404820115480 n - quochung.cyou PTIT
Khu vực thi – Sảnh A2
310474281 519902076809147 5619913051196432147 n - quochung.cyou PTIT
Khu vực thi – Sảnh A2
311190978 519910133475008 26272425141169940 n - quochung.cyou PTIT
Các thầy cô ban tổ chức
image 6 - quochung.cyou PTIT
Lễ trao giải ICPC PTIT 2022 – Đội vô địch 812

Lễ trao giải cuộc thi: https://portal.ptit.edu.vn/le-trao-giai-cuoc-thi-lap-trinh-theo-chuan-quoc-te-icpc-icpc-ptit-2022/

Sắc màu ICPC PTIT 2022: https://www.facebook.com/media/set/?set=a.518458426953512&type=3