Tài liệu Thuật toán qui hoạch động

 có được tư duy sắc sảo nên đã mất thời gian xử lý việc này – trong khi chỉ cần có một cách tổ chức dữ liệu “hai vòng” thì việc xử lý này không còn nữa. Cách tổ chức đó như sau: Bạn khai báo xâu S chứa chuỗi hạt rộng lên đến 250 ký tự. Cho chuỗi hạt “dài gấp đôi”, nghĩa là giả sử S có chiều dài d, cho S thành chiều dài 2d mà S[d+i] = S[i] (i=1..d), khi đó có thể tưởng tượng chuỗi hạt được đánh chỉ số giả đến 2 lần:
Khi cần kiểm tra nửa chuỗi hạt từ S[10] đến S[3] bạn khỏi lo phải tăng hay giảm chỉ số mà cứ đi từ S[10] đến S[15] là được. Lợi ích của phép “gấp đôi” là như thế. Để rõ hơn về các giải thuật thú vị như thế này mời bạn tìm đọc cuốn “Bắn tàu trên biển” - TS Nguyễn Xuân Huy (có thể liên hệ qua tòa soạn để có cuốn sách này). 
Bài 2. Bộ chuyển hướng Đề bài toán có vẻ phức tạp nhưng thực chất chỉ là việc thử chọn đặt các phần tử vào các vị trí khác nhau rồi tiến hành “bắn tia lade” xem kết quả thế nào. Việc phức tạp nhất ở việc “bắn tia lade”, tùy vào giá trị của mảng thiết bị mà tia lade chuyển sang các vị trí khác nhau – việc này chỉ đơn giản là các phép kiểm tra. Bạn chỉ cần tỉnh táo xem xét các vị trí biên là bài toán trở thành hoàn hảo. Với tư duy của các bạn bảng B, bài toán có vẻ phức tạp, để những bài toán như thế này trở nên đơn giản các bạn hãy áp dụng phương pháp mô hình hóa bài toán thành lược đồ các đầu vào và yêu cầu đầu ra dạng “Tin học” – nghĩa là bài toán cho các số nào, cho mảng gì, quan hệ với nhau ra sao, ta cần đưa ra số nào, theo quy luật nào,… từ đó giải quyết bài toán trên các “đối tượng Tin học” sẽ dễ dàng hơn. 
BẢNG C Bài 1. Tập bắn Ta mô hình hoá bài toán thành một bài toán đơn giản đối với ma trận 2 chiều như sau: Xây dựng một ma trận hai chiều A[1..6,1..6], mỗi hàng i của ma trận gồm 6 phần tử thể hiện 6 bia của người thứ i bắn, do mỗi người chỉ bắn vào một bia nên A[i,j] chỉ có giá trị là 0 (bắn trượt) hoặc 1 (bắn trúng). Đây chính là ma trận thể hiện một khả năng có thể xảy ra mà người Huấn luận viên dự đoán, và theo đề bài bạn phải xuất ra ma trận này nếu chỉ có một khả năng duy nhất. Gọi số phát trúng của 6 người là T[1..6], số phát trúng trên 6 bia là B[1..6]. Nhận xét: T chính là ma trận thể hiện tổng các hàng của A. B là ma trận thể hiện tổng các cột của A.
Đề bài đã cho mảng T và mảng B, nhiệm của bạn là tìm số ma trận A như vậy, nếu chỉ có 1 ma trận duy nhất thì cho biết mảng A đó. Thuật toán đệ quy là thuật toán áp dụng tốt ở bài toán này để thử và tìm ra ma trận A, với nhánh cận hợp lý nhờ 2 mảng T và B sẽ làm cho đệ quy dễ dàng và nhẹ nhàng hơn. Chẳng hạn khi thử chọn đến phần tử A[i,j] (bằng 0 hoặc 1) bạn kiểm tra tổng hàng và tổng cột trước nó đã bằng T[i] hay B[j] chưa, nếu đã bằng, đương nhiên A[i,j] và các phần tử “sau” hay “dưới” nó đều bằng 0. Với tư tưởng như vậy bạn có thể viết chương trình thực hiện dễ dàng. 
Bài 2. Robot Kích thước của bài toán khá lớn nên bạn nào sử dụng Đệ quy, Quay lui nói chung đều không đạt. Bạn nào sử dụng phương pháp Duyệt theo chiều rộng (Breadth First Search - BFS) cổ điển không có cải biến – nghĩa là làm khá giống như bài toán “Mã đi tuần trên bàn cờ vua” cũng không đạt, nhưng nhiều bạn đã sử dụng cách này. Xét test sau đây: 
Nếu sử dụng BFS cổ điển sẽ tìm ra lối đi đến ô (2,2) là (1,1) → (1,2) → (2,2) và hết năng lượng buộc phải sang (2,3) sau đó sang (3,3) và không tìm được đường đi. Tuy nhiên có một cách đi khác đến ô (2,2) là: (1,1) → (1,2) → (1,3) → (2,3) → (2,2) mà vẫn còn năng lượng là 1, tiếp tục đi về đích theo đường: (2,2) → (3,2) → (4,2) → (5,2) → (5,3). Như vậy để đi đến (2,2) phương pháp BFS nguyên bản không đảm bảo tối ưu, từ đó cho thấy đó là phương pháp không đúng đắn khi giải bài toán này. Đề giải bài toán này bạn có thể sử dụng phương pháp quy hoạch động, hoặc áp dụng thuật toán tìm đường đi ngắn nhất trên một đồ thị giả một cách khéo léo theo kiểu thuật toán Dijkstra. Dù là sử dụng cách nào thì thực chất cũng là việc Loang (tức là duyệt theo chiều rộng) và thay đổi các giá trị tối ưu tại các ô đã đi đến theo quy tắc sau đây: Những ô nằm sau ô nạp năng lượng trên hành trình của Robot là những ô có thể đánh dấu việc tối ưu để không cho Robot quay lại ô đó, những ô không nằm sau ô nạp năng lượng nhưng nằm sau ô đã đánh dấu tối ưu thì cũng được đánh dấu tối ưu. Từ đó bạn có thể hình dung ra một giải thuật, có thể nói là tựa như BFS, tựa như Dijkstra, tựa như Quy hoạch động… - như thế không có nghĩa là quá khó, đó đơn giản là giải thuật dựa trên tư tưởng đã nói ở trên và áp dụng với một cấu trúc dữ liệu hợp lý là bài toán được giải quyết trọn vẹn. Trên số tháng sau sẽ đăng chi tiết về giải thuật “lai tạo” này và chương trình thực hiện bài toán. 
Một số ý kiến về đề thi năm nay - Bạn Trần Lê Quân (Đoàn Đồng Tháp, bảng A): Đề thi với học sinh tiểu học như vậy là khó, kiến thức quá rộng, có những “thứ” chưa được nghe đến bao giờ. - Nguyễn Thị Thùy Linh (Đoàn Nghệ An, bảng B): Đề khó hơn mọi năm (năm nay bạn đã thi Toàn quốc lần thứ 2), phần trắc nghiệm có nhiều câu hỏi hay. - Xa Thành Nam (Đoàn Hòa Bình, bảng B): Đề khó, đặc biệt là bài 2 rất khó. - Đỗ Văn Trung (Đoàn Ninh Bình, bảng C): Nhìn chung đề thi ở mức độ tương đối, không khó và cũng không dễ, cả hai bài đều sử dụng giải thuật quay lui, bài Robot bạn chưa làm được một số trường hợp. Phần thi trắc nghiệm vừa phải. - Trần Thiện Khiêm (Đoàn Quảng Trị, bảng C): Đề tương đối khó, bài “Tập bắn” chỉ làm được một trường hợp. - Võ Thị Thùy Linh (Đoàn Hòa Bình, bảng C): Đề thi khó hơn năm ngoái (năm nay bạn đã thi Toàn quốc lần thứ 2) khiến bạn chỉ làm được một nửa. Bài Robot khó hơn bài “Tập bắn”. - Huỳnh Ngọc Ân (Đoàn BCVT, bảng C): Bạn cho rằng bài tập bắn rắc rối, đề thi vừa với bạn nhưng khó hơn một chút thì hay hơn, thời gian làm bài không thừa nên test chưa kỹ. Bạn Ân thi Tin Học trẻ không chuyên lần này là lần thứ 4 với thành tích khá cao. - Chú Đạo (Đoàn Bến Tre - 2 thí sinh bảng A và C): Các em đều cho rằng đề thi khó, phần trắc nghiệm kiến thức quá rộng. - Phụ huynh bạn Linh (Đoàn Nghệ An): Các cháu nói đề thi quá rộng so với chương trình học và khả năng tự học của các cháu, nhiều kiến thức chưa được phổ cập rộng.BBT tạp chí đã có cơ hội gặp gỡ, trò chuuyện và tặng tạp chí cho các bạn học sinh, các thầy cô, phụ huynh,… trong thời gian diễn ra hội thi. Các bạn học sinh từ khắp mọi miền tổ quốc bạn nào cũng sáng sủa thông minh, rất xứng đáng đại diện cho Đoàn, cho Tỉnh mình. Trên đây chỉ là một trong số ít ý kiến mà BBT được nghe, có thể thấy sơ bộ Đề thi là khá khó và rắc rối. Phần thi trắc nghiệm có kiến thức rộng khiến rất nhiều bạn phải “trả lời ngẫu nhiên” hay “đoán mò”! Tuy nhiên, rõ ràng là do tư duy phân tích của các bạn có khác nhau (và sự thực là cũng chưa tốt) nên có bạn thấy bài “Tập bắn” quá khó, có bạn lại thấy bài Robot quá khó (bảng C) còn bài kia thì dễ (!). Nếu phân tích đề như Olypiad đã làm thì bài nào cũng đơn giản cả phải không các bạn? Chúc các bạn thành công hơn nữa ở các kỳ thi sau! 
Các kỳ thi Tin học trên thế giới
Ngô Minh Đức
* Quốc tế Ngoài kỳ thi IOI nổi tiếng nhất thế giới mà trong số tháng 9/2005 này tạp chí đã đăng tin chi tiết còn có: ACM International Collegiate Programming Contest – ICPC 
ACM International Collegiate Programming Contest (info.acm.org/contest) được tổ chức hằng năm bởi tổ chức ACM (info.acm.org), là một kì thi có uy tín dành cho sinh viên các trường đại học diễn ra lần đầu tiên vào năm 1970. Trong vòng 5 giờ, mỗi đội dùng một máy tính để giải các bài toán tin học. Một đội được phép nộp một bài toán nhiều lần. Bài nộp trong khi thi và sẽ được chấm ngay; tuy nhiên bài nộp sai sẽ bị trừ điểm. Hơn 60 đội sẽ tham dự kì thi chung kết ICPC World Finals, thông thường được tổ chức vào tháng 2, 3 hoặc đầu tháng 4 hằng năm. Để dành được quyền tham dự kì thi chung kết, các đội phải trải qua vòng loại khu vực (regional contests) chia làm hơn 25 khu vực trên khắp thế giới. Trước đó, thông thường còn có các kì tuyển chọn nội bộ (local contests) để chọn ra các đội tham dự vòng loại khu vực. 
Internet Problem Solving Contest – IPSC 
IPSC (ipsc.ksp.sk) là kì thi lập trình đồng đội trên internet. Mục đích của cuộc thi là để so sánh khả năng giải toán tin học của mọi người trên khắp thế giới, tạo ra một sân chơi vui vẻ, bổ ích. Hàng năm có hàng trăm đội tham gia. 
* Khu vực Balkan Olympiad on Informatics – BOI 
Kì thi BOI - Olympic tin học khu vực Balkan ( là một kì thi lập trình cho học sinh, sinh vịn các nước khu vực Balkan (bao gồm Albenia, Bulgaria, Cyprus, FYROM, Hy Lạp, Romania, Thổ Nhĩ Kỳ, Nam Tư). BOI lần đầu tiên tổ chức tại Romania:  BOI gần nhất là lần thứ 13 tại Bulagria:  Thông tin chung về các kì thi BOI:  
Baltic Olympiad in Informatics – BOI 
Một kì thi nổi tiếng khác là Olympic tin học khu vực Baltic (cũng gọi tắt là BOI) được mô phỏng theo Olympic tin học quốc tế IOI. Các nước tham dự trong kì thi này bao gồm Estonia, Phần Lan, Latvia, Lithuania, Ba Lan và Thụy Điển BOI gần nhất là lần thứ 11 tại Lithuania:  
Central-European Olympiad in Informatics – CEOI 
Olympic tin học khu vực Trung Âu, gọi tắt là CEOI ( được tổ chức bởi Bộ Văn Hóa, Giáo Dục hoặc các tổ chức tương đương của một trong tám nước khu vực Trung Âu. Theo điều lệ đã được chấp nhận bởi những người khởi xướng CEOI ( các đội của tám nước Ăo, Croatia, Cộng Hòa Séc, Hungary, Ba Lan, Romania, Cộng Hòa Slovak và Slovenia sẽ được mời tham dự với tư cách chính thức. Ngoài ra, nước chủ nhà có thể mời thêm các đội khác với tư cách khách mời. CEOI2005 tổ chức tại Sárospatak, Hungary (28/7 – 5/8/2005):  
* Quốc gia Hầu như các nước đều có kì thi Olympic Tin học Quốc Gia để tuyển chọn học sinh tham dự kì thi tin học quốc tế IOI. Xin giới thiệu website về kỳ thi này của một số quốc gia: Croatia:  Ba Lan:  Anh:  Mỹ:  Singapore:  Để biết được đầy đủ chi tiết hơn về những kì thi tin học trên thế giới, mời các bạn truy cập website:  và  Hầu hết website của những kì thi đều có lưu giữ lại đề bài, lời giải và bộ test; là những phương tiện rất tốt để chúng ta có thể luyện tập kỹ năng giải bài toán tin học.