Bài viết gốc: How to Find a Solution - đăng bởi Dumitru trên Topcoder
Với nhiều bài toán trên topcoder (TC), lời giải có thể được tìm ra ngay sau một nốt nhạc. Điều này có được là do những nét tương đồng giữa những bài toán có lời giải giống nhau. Những nét tương đồng này chính là những gợi ý tuyệt vời cho những coder kinh nghiệm để có thể nhận định được lời giải bài toán. Mục tiêu chính của bài viết này là hướng dẫn để các bạn cũng có thể nhận định được chúng.
Hầu hết các trường hợp, những bài toán này thường chỉ yêu cầu bạn thực hiện từng bước một với những công việc rất đơn giản. Giới hạn thì không quá lớn cũng không quá nhỏ. Và những bài này thường là bài đầu tiên (bài dễ nhất) trong TC SRM. Chúng thường để kiểm tra xem bạn code nhanh và chính xác như nào, và không yêu cầu kiến thức về thuật toán.
Hầu hết các bài toàn sẽ yêu cầu bạn mô phỏng tất cả các bước được nêu ra trong đề.
BusinessTasks - SRM 236 Div 1:
Có nhiệm vụ được liệt kê dưới dạng 1 vòng tròn, nhiệm vụ đầu tiên kề với nhiệm vụ cuối cùng. Cho một số . Bắt đầu từ nhiệm vụ đầu tiên, di chuyển theo chiều kim đồng hồ (từ thứ 1 đến thứ 2 rồi tiếp tục như vậy) và đồng thời đếm từ 1 đến . Vừa di chuyển vừa đếm, khi đếm đến n, bỏ nhiệm vụ hiện tại ra khỏi danh sách và đếm từ nhiệm vụ tiếp theo. Lặp lại thủ tục này cho đến khi chỉ còn 1 nhiệm vụ. Tìm nhiệm vụ đó.
Với bài này chỉ là vấn đề của code, không có thuật toán gì đặc biệt - thực hiện từng bước một cho đến khi chỉ còn lại một nhiệm vụ. Những loại bài toán này thường có nhỏ, vậy nên không cần phải quan tâm đến trường hợp lớn. Cần nhớ rằng trong topcoder thì 100 triệu phép tính vẫn có thể chạy được.
Có một số bài yêu cầu bạn phải tìm kiếm
TallPeople - SRM 208 Div 1:
Có một nhóm người được xếp thành một ma trận , hàng, cột. Nhiệm vụ của bạn là trả về 2 số - Số thứ nhất là chiều cao của người cao nhất trong những người thấp nhất ở mỗi hàng, số thứ hai là chiều cao của người thấp nhất trong những người cao nhất ở mỗi cột.
Như bạn có thể thấy, đây là một bài toán tìm kiếm rất đơn giản. Bạn chỉ cần theo các bước được mô tả trong đề và tìm ra 2 giá trị yêu cầu. Những bài TC khác có thể yêu cầu sắp xếp các bộ theo quy luật nào đó. Bạn có thể làm với thuật toán sort hoặc sử dụng các thư viên có sẵn.
Ví dụ khác:
MedalTable - SRM 209 Div 1
Những bài sử dụng BFS thường yêu cầu tìm số bước ít nhất (hoặc đường đi ngắn nhất) từ điểm đầu đến điểm cuối. Bên cạnh đó, đường đi giữa 2 điểm bất kì thường có chung trọng số (và thường là 1). Phổ biến nhất là dạng bài cho bảng , có những ô đi qua được và những ô không đi qua được. Bảng này có thể là mê cung, sơ đồ, các thành phố hoặc các thứ các thứ tương đương. Có thể nói đây là những bài toàn BFS kinh điển (classic). Bởi vì độ phức tạp của BFS là tuyến tính trong hầu hết các trường hợp ( hoặc ), giới hạn của (hoặc ) có thể lớn, lên tới 1 triệu.
SmartWordToy - SRM 233 Div 1:
Cho một từ gồm 4 chữ cái Latin in thường. Với một lần click bạn có thể đổi bất kì chữ nào thành chữ cái trước hoặc sau nó trong bảng chữ cái (ví dụ 'c' có thể thành 'b' hoặc 'd'). Bảng chữ cái sẽ theo chu kì vòng lặp, tức là 'a' có thể thành 'z' và 'z' có thể thành 'a'.Cho một tập các rằng buộc, mỗi rằng buộc sẽ là tập các từ bị cấm. Một rằng buộc bao gồm 4 xâu kí tự. Một từ gọi là bị cấm nếu mỗi chữ cái của nó đều xuất hiện trong chính ràng buộc ở vị trí đó, i.e. chữ đầu tiên ở trong xâu đầu tiên, chữ thứ 2 trong xâu thứ 2, ... Ví dụ, có rằng buộc sau "lf a tc e" thì các từ sau bị cấm "late", "fate", "lace" và "face".
Bạn cần phải tìm số lần bấm nút ít nhất để từ ban đầu biến thành từ đích mà không đi qua từ cấm, hoặc trả về -1 nếu không thể biến được.
Hints:
Mọi thứ đều chỉ ra rằng bài này cần giải bằng BFS. Những điều tương tự như trên sẽ thường thấy trong các bài BFS. Bây giờ, chúng ta cùng xem một BFS bài khá thú vị.
CaptureThemAll - SRM 207 Div 2 (3rd problem):
Harry đang chơi cờ vua. Anh có một quân mã, còn đối thủ là Joe có 1 quân hậu và 1 quân xe. Hãy tìm số bước nhỏ nhất quân mã phải đi để ăn được cả hậu và xe.
Hints: Mới đầu, có vẻ như bài này là 1 bài quy hoạch động hoặc backtrack. Nhưng nếu để ý kĩ đề bài, ta sẽ có những nhận xét sau:
Với những thông tin trên, ta có thể dễ dàng giải được bằng BFS. Đừng bối rối nếu những điểm liên thông là những ô không kề nhau. Hãy nghĩ mỗi ô là một điểm trên đồ thị hay một trạng thái hay bất cứ cái gì bạn muốn.
Chú ý rằng phần lớn những gợi ý về thuật giải BFS là chi phí bằng 1 cho mỗi bước.
Bạn có thể luyện tập thêm về BFS bằng những ví dụ sau:
Ví dụ khác:
RevolvingDoors - SRM 233 Div 1
WalkingHome - SRM 222 Div 1
TurntableService - SRM 219 Div 1
Thỉnh thoảng bạn sẽ gặp phải bài toán cần tới Loang, một kĩ thuật sử dụng BFS để tìm tất cả các điểm có thể đi tới. Điểm khác biệt giữa Loang so với những bài BFS ở trên là bạn không phải tìm chi phí nhỏ nhất.
Ví dụ, có một mê cung, ô 1 là không đi được và 0 là đi được. Ban cần phải tìm tất cả các ô mà có thể đi đến từ ô góc trái trên. Bài này chỉ cần lấy ra một đỉnh đã thăm, nhét tất cả các đỉnh chưa thăm mà kề với đỉnh hiện tại vào queue rồi tiếp tục làm như vậy cho đến khi queue rỗng. Lưu ý rằng nếu số đỉnh lớn, cài đặt bằng DFS (Depth First Search) sẽ có thể bị tràn stack do đệ quy quá sâu và compile code không tăng kích thước stack (xem thêm giải thích ở đây). Tốt hơn hết là nên dùng BFS. Đây là một bài ví dụ:
grafixMask - SRM 211 Div 1:
Cho một bitmap . Có một tập hình chữ nhật bao phủ bitmap này (các góc của chúng có tọa độ nguyên). Bạn cần phải tìm ra tất cả các vùng liên tiếp không bị phủ và kích thước của chúng.
Hints:
Những dấu hiệu trên cho thấy bài này cần phải sử dụng Loang
Hai kĩ thuật này được gộp chung vào một loại vì chúng khá giống nhau. Quay lui là kĩ thuật nâng cao và tối ưu hơn so với duyệt trâu. Nó thường sử dụng đệ quy và áp dụng cho những bài có giới hạn nhỏ
Đối với những bài duyệt trâu thì giới hạn thường bé. Duyệt trâu bản chất đúng như cái tên của nó, là duyệt hết tất cả các trường hợp và chọn ra cái tốt nhất. Nó rất dễ xây dựng và cài đặt.
GeneralChess - SRM 197 Div 1:
Cho một số quân mã (nhiều nhất là 8) cùng với vị trí của chúng . Bạn cần phải tìm các vị trí để đặt thêm một quân mã mà nó có thể ăn được tất cả các quân đã cho.
Hints:
Giới hạn , trong bài trên không quan trọng, bạn chỉ cần thử các vị trí có thể ăn một quân mã và đối với từng vị trí thì xét xem nó có ăn được các quân còn lại không.
Một ví dụ khác:
LargestCircle - SRM 212 Div 2 (3rd problem):
Cho một lưới vuông với một số ô đã bị đánh dấu. Tìm đường tròn lớn nhất không đi qua các ô đã bị đánh dấu và có tâm nằm trên điểm giao của lưới ô vuông (bán kính là số nguyên). Trả lại bán kính của đường tròn.Kích thước lớn nhất của lưới là 50
Hints: Tại mỗi điểm giao bạn thử từng bán kính một sao cho thỏa mãn đề bài. Rồi chọn ra bán kính lớn nhất trong số chúng.
Phân tích độ phức tạp: Có nhiều nhất là ô, bán kính là một số nguyên với max là 25 và bạn cần kiểm tra các điểm trên thuộc đường tròn trong một thời gian tuyến tính. Tổng độ phức tạp sẽ rất bé và bạn có thể yên tâm duyệt trâu.
Ví dụ khác:
Cafeteria – SRM 229 Div 1
WordFind – SRM 232 Div 1
Kĩ thuật này thường được sử dụng với những bài có giới hạn nhỏ. Các dạng quay lui mà bạn có thể gặp phải là tìm:
BridgeCrossing – SRM 146 Div 2 (3rd problem):
Có một nhóm người cần sang cầu. Tuy nhiên, do cầu quá cũ, nên một lần chỉ được tối đa 2 người qua cầu. Trời thì tối, chỉ có một cái đèn pin. Hai người cùng đi qua cầu thì thời gian của hai người sẽ là thời gian của người chậm hơn. Do không thể ném đèn pin từ bên này sang bên kia, nên một người sẽ phải quay lại rồi đi với một người khác. Hỏi thời gian ít nhất để tất cả cùng qua cầu.Có nhiều nhất là 6 người.
Hints:
Ta sẽ bắt đầu bằng việc đưa 2 người bất kì qua cầu rồi tiếp tục đưa những người còn lại sang. Người quay lại sẽ là người nhanh nhất. So sánh và tìm ra phương án tốn ít thời gian nhất. Mặc dù còn có một thuật giải khác cho bài này nhưng với giới hạn bé như vậy thì chúng ta không cần thiết phải quan tâm.
MNS – SRM 148 Div 1:
Cho 9 số nguyên trong khoảng từ 0 đến 9. Một ô vuông thần kì là ô vuông mà các số được sắp xếp sao cho tổng mỗi hàng và mỗi cột đều bằng nhau. Tính số cách khác nhau để sắp xêp dãy số đã cho thành một ô vuông thần kì. Hai cách sắp xếp khác nhau nếu chúng khác nhau ở ít nhất 1 vị trí.
Hints: Do chỉ có 9 số nên hoàn toàn có thể sinh ra hết các cách sắp xếp của chúng. Liệt kê các hoán vị của 9 số, đồng thời lưu lại một danh sách các cách sắp xếp khác nhau đã có để kiểm tra.
Ví dụ khác:
WeirdRooks – SRM 234 Div 1
Để giải quyết cũng như nhìn ra dạng bài này thì chủ yếu dựa vào kinh nghiệm. Thường thì giới hạn trong các bài QHĐ không lớn cũng không nhỏ, độ phức tạp thường là , , ... Nếu như giới hạn quá nhỏ (với TC thì thường ) thì thường không phải là DP. Trong QHĐ thì các bài toán lớn sẽ được chia thành các bài toán nhỏ hơn và tính dựa vào chúng. Để hiểu hơn về QHĐ, bạn có thể tham khảo bài này.
Thử phân tích một ví dụ đơn giản:
Cho N đồng xu với giá trị của chúng(, , ..., ) và một số S. Tìm số đồng xu nhỏ nhất mà tổng giá trị của chúng bằng S (bạn có thể dùng một đồng nhiều lần) hoặc thông báo không có cách nào như vậy.
và
Hints:
Tất cả những tính chất trên cho thấy đây là một bài QHĐ.
ZigZag – 2003 TCCC Semifinals 3:
Một dãy số được gọi là zig-zag nếu các hiệu giữa những liền nhau là một dãy đan dấu (luân phiên âm dương âm dương ...). Dãy có ít hơn 2 số là 1 dãy zig-zag. Cho một dãy số tìm dãy con zig-zag dài nhất. Một dãy con thu được bằng cách xóa bỏ một số số trong dãy ban đầu (hoặc không xóa). Giới hạn
Hints:
Như vậy, bài này cũng có những dâu hiệu giống với bài trên và những bài QHĐ khác. Phần khó nhất là xác định được bài đưa ra là QHĐ bằng những dấu hiệu trên. Sau đó bước tiếp theo chỉ là xây dựng thuật toán và cài đặt.
Ví dụ khác:
ChessMetric – 2003 TCCC Round 4
AvoidRoads – 2003 TCO Semifinals 4
FlowerGarden – 2004 TCCC Round 1
BadNeighbors – 2004 TCCC Round 4
Cũng không dễ để có thể xác định được một bài toán sử dụng Luồng. Tuy nhiên, một số dấu hiệu sau có thể giúp bạn:
Ví dụ
Cho một danh sách các ống nước, mỗi ống chỉ cho một lượng nước nhất định được đi qua. Các ông được nối với nhau.Tìm lượng nước lớn nhất có thể chảy được từ điểm đầu đến điểm cuối trong một đơn vị thời gian.
Dễ dàng thấy được lượng nước ở mỗi ống là trọng số các cạnh, khớp nối các ống là các đỉnh trong đồ thị. Bạn phải tìm lượng nước lớn nhất chảy từ đỉnh bắt đầu đến đỉnh kết thúc.
Dạng bài này thường cho 2 tập và các quy tắc, bạn phải sử dụng các quy tắc này để ghép càng nhiều càng tốt các phần tử ở tập với các phần tử ở tập .
Parking – SRM 236 Div 1:
Cho cái xe và chỗ đỗ xe trên một cái bảng hình chữ nhật, trong đó có một số ô không đi qua được. Bạn cần tìm một cách để đưa tất cả các xe vào điểm đỗ xe, sao cho số lớn nhất trong các khoảng cách từ một xe đến chỗ đỗ của nó là nhỏ nhất có thể. Một điểm đỗ xe chỉ cho phép một xe đỗ.
Hints: Nhận xét bài này, ta thấy có 2 tập: xe và điểm đỗ xe, chúng ta cần thực hiện ghép mỗi xe với một điểm đỗ tương ứng. Tồn tại một cạnh giữa 1 xe và 1 điểm đỗ nếu có đường đi giữa chúng và trọng số của cạnh này là đường đi ngắn nhất giữa 2 điểm này. Bước tiếp theo là chia nhị phân khoảng cách dài nhất: ở mỗi bước, xóa đi các cạnh có độ dài lớn hơn ; nếu vẫn có thể ghép tất cả các xe vào điểm đỗ thì chọn một giá trị nhỏ hơn; ngược lại thì chọn một giá trị lớn hơn. Khi đã chia nhị phân xong, giá trị nhỏ nhất sẽ là kết quả cần tìm.
Dấu hiệu nhận biết:
Ví dụ:
Mixture – SRM 231 Div 1:
Bạn đang muốn làm ra một hỗn hợp từ các hợp chất khác nhau, mỗi hợp chất cần phải đúng liều lượng. Bởi vì các hợp chất đôi khi không được bán riêng, mà bạn phải mua các hỗn hợp có sẵn mà chứa chúng. Mỗi hỗn hợp lại có một lượng nhất định của mỗi hợp chất cấu thành. Bạn không cần phải mua toàn bộ hỗn hợp mà có thể mua những hợp chất bạn cần với liều lượng tùy chọn. Nhiệm vụ của bạn là tìm ra cách tiêu ít tiền nhất đề có thể tạo ra được hỗn hợp mong muốn.
Hints:
Những tính chất trên giống hệt với dấu hiệu nhận biết của dạng Linear Programming.
Đây là 1 kĩ thuật nâng cao, bạn có thể tham khảo thêm ở:
Để có thể tìm ra được lời giải cho một bài toán bạn cần phải làm nhiều bài tập để luyện khả năng nhận định bài toán cũng như tăng thêm kinh nghiệm. Ngoài ra, còn rất nhiều dạng bài khác mà trong phạm vi bài viết này không thể bao phủ hết được.