Bàn tròn IOI 2015

Kỳ thi IOI 2015 đã kết thúc, kết quả chính thức chắc sẽ có trong hôm nay hoặc ngày mai, mình mở topic này để các bạn cùng tham gia bàn luận về kỳ thi cũng như solution các bài trong kỳ thi này.

Link đề:

Ngày 1:

http://olympiads.kz/ioi2015/day1/boxes/en-VNM.VNM.pdf

http://olympiads.kz/ioi2015/day1/scales/en-VNM.VNM.pdf

http://olympiads.kz/ioi2015/day1/teams/en-VNM.VNM.pdf

Ngày 2:

http://olympiads.kz/ioi2015/day2/horses/en-VNM.VNM.pdf

http://olympiads.kz/ioi2015/day2/sorting/en-VNM.VNM.pdf

http://olympiads.kz/ioi2015/day2/towns/en-VNM.VNM.pdf

Tin học trẻ quốc gia 2015

Thay mặt ban thư kí admin vnoi (thực ra có mỗi mình em nhưng các bác cứ để e atsm tí :D ), chúc mọi người ngày mai bình tĩnh tự tin và đạt kết quả tốt nhất, nhưng cao vừa vừa thôi cho đội e còn giải nữa :v :v

PS: bác nào rảnh lên 903 ae "xã giao" tí 

IOI 2015 - Ngày 2

10 giờ sáng ngày mai, ngày 2 của IOI 2015 sẽ diễn ra. Xin mời quý vị và các bạn cùng tham gia buổi bình luận trước trận thi. Sau ngày thi 1, đội tuyển Việt Nam đã dành được những lợi thế nhất định. Đây là kết quả của ngày 1:

 

Phạm Văn Hạnh              : Rank 10   | 249.02 điểm

Phan Đức Nhật Minh       : Rank 27   | 205.42 điểm

Nguyễn Việt Dũng          : Rank 71   | 179.45 điểm

Nguyễn Tiến Trung Kiên : Rank 122 | 114.45 điểm

 

Theo tôi, kết quả ngày 1 chưa thực sự phản ánh đúng thực lực của đội tuyển Việt Nam. Các code thủ Việt Nam có vẻ chưa thực sự bung hết sức mình mà mới chỉ chơi thăm dò để đối thủ chủ quan. Có lẽ khác biệt sẽ nằm ở ngày 2, tất cả đều đang nhắm đến ngôi vô địch, hoặc ít ra cũng là huy chương vàng. Chúng ta hãy cùng hy vọng đẳng cấp và tinh thần chiến đấu của đội tuyển Việt Nam sẽ được thể hiện vào ngày 2. Diễn biến chi tiết của ngày 2 sẽ được cập nhật trong topic này, các bạn có thể vào bình loạn, chém gió cũng như gửi những lời chúc tốt đẹp nhất đến đội tuyển Việt Nam.

Rank: http://scoreboard.ioinformatics.org/Ranking.html

Đề bài: http://ioi2015.kz/content/view/1/271

Dừng tính điểm / submit qua VNOI

Trong thời gian này, việc tính điểm & submit gặp nhiều sự cố, nên bọn mình đã phải tắt phần tính điểm để sửa lỗi. Vì vậy trong thời gian này các bài nộp qua VNOI và xếp hạng VOJ sẽ không được cập nhật.

Bọn mình sẽ cố gắng sửa sớm trong 1-2 tuần tới. Rất mong các bạn thông cảm.

Discuss đề thi IOI 2015

Như tít ạ, em thấy các bác chém gió bảng rank ghê quá nên cũng xin mạn phép mở topic chém gió lời giải ở đây :3

Em xin mở hàng luôn bằng sol bài 1 (hi vọng là đúng) của em:

*Nhận xét 1 (khá hiển nhiên): Nếu tại một thời điểm nào đó ta về 0 để lấy đồ mà trong kho còn >= K món đồ thì ta nên lấy đủ K món (và đương nhiên phát lượng đồ tối đa có thể).

*Nhận xét 2: Ta không nên đi đủ một vòng tròn quá 1 lần.

- Chứng minh: giả sử ta đi nhiều hơn 1 vòng tròn. Xét 2 lần đi bất kì. Trong 2 lần đó, ta sẽ chuyển không nhiều hơn 2 * K món đồ. Ta có thể tối ưu cách đi này bằng cách: đi theo chiều bất kì, đến khi gặp và phát đủ K món thì quay về, sau đó đi theo chiều ngược lại, phát quà cho những thằng còn lại (<= K thằng). Tổng độ dài quãng đường sẽ không lớn hơn 2 * L, tốt hơn cách đi trước.

Như vậy ta chỉ cần xét 2 trường hợp: không đi hết vòng tròn nào và đi hết 1 vòng tròn. Trước hết chia những thằng trên vòng tròn thành 2 tập trái và phải, tùy theo đi từ 0 theo hướng nào đến nó gần hơn.

*TH1: Ta sẽ đến phát quà cho 2 thằng xa 0 nhất của mỗi tập. Trên đường đi ta sẽ phát hết quà cho nó và  K - 1 thằng trước nó. Do đó tiếp theo ta sẽ phát quà cho các thằng xa 0 thứ K, 2 * K, ... của mỗi tập cho đến khi hết hàng. Vì mảng được sort rồi nên trường hợp này chạy hết O (N / K).

*TH2: Để ý rằng ta có thể đi hết vòng tròn ngay từ đầu, và ta nên chọn một đoạn liên tiếp K thằng để phát quà (và hiển nhiên, mỗi tập nên có ít nhất 1 thằng được phát). Sau đó ta tham theo chiến thuật trên. Để đơn giản, ta lưu lại S[r] là tổng đường đi các thằng nằm ở vị trí q * K + r (0 < r < K), và M[r] là thằng xa 0 nhất. Đáp số là min 2 * { S[r] - M[r] } + L.

Mong các bác vào góp cho xôm ạ :3

IOI 2015 - ngày 1

IOI 2015 - ngày 1 sẽ diễn ra vào 10h sáng ngày mai ở Kazakhstan. Đội tuyển chúng ta năm nay gồm 4 bạn:

4 bạn đều học Tổng hợp <3

Nghe nói sẽ có bảng rank online, nhưng giờ chưa có link (bao giờ mình có link sẽ update vào đây).

Các bạn có thể vào đây chém gió, cổ vũ đội tuyển chúng ta, dự đoán kết quả... nhé :v

Mình dự đoán 1 vàng 3 bạc :D

Thay mặt admin VNOI chúc các bạn dành thắng lợi lớn trong kỳ thi ngày mai.

UPD: Link rank --> http://scoreboard.ioinformatics.org/Ranking.html

VNOI Marathon Round 1 - Thảo luận

Ban tổ chức chưa muốn công bố lời giải của các bài ngay vì muốn khuyến khích các bạn trao đổi và học tập lẫn nhau. Đó là cách rất nhanh và hiệu quả để các bạn biết cách làm các bài. Các bạn không làm được bài đừng ngần ngại hỏi, và các bạn làm được bài cũng chớ quên chia sẻ nhé :) 

Mời các bạn thảo luận về lời giải của các bài tập trong vòng vừa rồi :)

Interval Tree trên tập đoạn thẳng

Interval Tree trên tập đoạn thẳng

Xét bài toán sau:

Cho một tập hợp chứa các đường thẳng có dạng ax + b, mỗi đường thẳng được biểu diễn bằng một cặp số (a, b). Cần thực hiện hai truy vấn:

  1. Thêm một đường thẳng vào tập hợp.

  2. Trả lời xem tại hoành độ q, điểm nào thuộc ít nhất một đường thẳng trong tập có tung độ lớn nhất. Nói cách khác, đường thẳng (a, b) nào có aq + b lớn nhất.

Để giải bài toán này, hai cách phổ biến là ứng dụng bao lồi và sử dụng cây Interval Tree lưu đoạn thẳng. Sau đây là những ưu điểm và nhược điểm của IT đoạn thẳng so với bao lồi.

Ưu điểm:

  1. Ứng dụng được với đoạn thẳng chứ không chỉ đường thẳng. Đây là ưu điểm lớn nhất của IT đoạn thẳng so với bao lồi, khi tập hợp cần xử lí là tập đoạn thẳng chứ không phải đường thẳng (tức là đường thẳng ax + b chỉ tồn tại khi x thuộc một khoảng (l, h) nhất định), bao lồi sẽ không thể làm được.

  2. Thực hiện truy vấn thêm đường thẳng (đoạn thẳng) một cách dễ dàng. Bao lồi gặp nhược điểm lớn khi thêm đường thẳng mà hệ số góc a không tăng dần hoặc giảm dần. Mặc dù không phải là không thể làm được, nhưng bao lồi khi đó phải biểu diễn bằng cấu trúc khác không phải stack, gây khó khăn lớn khi code.

  3. Dễ code. Chính vì hai ưu điểm ở trên, IT đoạn thẳng rất tổng quát và không cần phải xét trường hợp phụ thuộc vào bài toán như bao lồi. Đa số các bài toán, phần Update và Query của IT đoạn thẳng gần như giống hệt nhau. Phần thân chương trình cũng rất ngắn gọn.

Nhược điểm:

  1. Phụ thuộc vào kích thước hoành độ x. Vì IT đoạn thẳng xử lí trên khoảng của hoành độ, với bài toán mà truy vấn x lớn hoặc x không phải số nguyên không thể biểu diễn bằng IT bình thường. Có thể thay thế bằng rời rạc hóa truy vấn hoặc IT động, nhưng so với bao lồi đây là một nhược điểm đáng kể khi bao lồi hoàn toàn không phụ thuộc vào x.

  2. Bộ nhớ và thời gian lớn. Lưu một cây IT chứa hai số nguyên a, b tốn bộ nhớ hơn nhiều so với stack bao lồi. Xử lí trên cây IT cũng chậm hơn chặt nhị phân trên bao lồi. Về độ phức tạp, có thể so sánh qua bảng sau:

*Lưu ý: Ở đây ta giả sử các đường thẳng thêm vào có hệ số a tăng dần hoặc giảm dần, bao lồi được biểu diễn bằng stack.

Tóm lại, so với cách ứng dụng bao lồi, sử dụng IT đoạn thẳng là một phương pháp tổng quát hơn nhưng chậm và tốn nhiều bộ nhớ hơn. Sau đây là những phân tích cơ bản về thuật toán.

 

Ý tưởng:

Xây dựng một cây Interval Tree để quản lí tập các đoạn thẳng, mỗi nút của cây quản lí một khoảng trên trục hoành. Thông tin lưu ở mỗi nút trên cây sẽ là đoạn thẳng đặc trưng cho khoảng nó quản lí. Đoạn thẳng này phải phủ kín khoảng, tức là đoạn ax + b có khoảng x bao lấy khoảng do nút quản lí (nếu là đường thẳng thì luôn phủ kín khoảng do nút quản lí). Đoạn thẳng được lưu trong nút phải cao hơn tất cả các đoạn khác tại một vị trí nào đó thuộc khoảng (nếu không thì không cần quan tâm đến đoạn đó). Ý nghĩa của việc lưu này là với một truy vấn q bất kì, đoạn aq + b cao nhất sẽ được lưu trong một nút nào đó của cây IT quản lí khoảng chứa q. Cách lưu đoạn thẳng này khá trừu trượng, nếu bạn đọc phần này chưa hiểu, nên bỏ qua để xem cách Query và Update trên cây rồi đọc lại phần này sau.

Như vậy, thông tin lưu trên cây IT sẽ được biểu diễn bằng một mảng line, line là một cặp số (a, b) biểu diễn đường thẳng.

line it[MAXX * 4]; // MAXX là giới hạn trục hoành

Ngoài ra, có thể thêm một vài mảng phụ cần thiết cho IT như low, high, leaf, ...

Ta định nghĩa hàm Get(line d, int x) cho biết tung độ của điểm thuộc đường thẳng d tại hoành độ x.

int Get(line d, int x)
{
    return d.a * x + d.b;
}

Query:

Ta sẽ trả lời cho truy vấn q, xem tại hoành độ x =  q, tìm tung độ cao nhất của một điểm thuộc một đoạn trong tập. Như đã nói ở trên, IT lưu các đoạn thẳng đảm bảo trong các nút cây quản lí khoảng chứa q có một nút lưu đoạn thẳng đạt tung độ cao nhất (làm thế nào để được như vậy thì xem phần Update). Vậy ở đây, muốn trả lời cho truy vấn q, ta đi từ gốc xuống nút lá quản lí điểm q, trên đường đi cập nhật đáp số bằng tung độ cao nhất tại điểm q của đoạn thẳng do nút đó quản lí.

int Query(int node, int pos)
{
    if(low[node] > pos || high[node] < pos)
    {
        return -oo;
    }
    res = Get(it[node], pos);
    if(low[node] == high[node])
    {
        return res;
    }
    res = max(res, Query(node * 2, pos));
    res = max(res, Query(node * 2 + 1, pos));
    return res;
}

Độ phức tạp: O(log(MAXX))

Update:

Thêm một đoạn thẳng vào tập hợp, ta phải thay đổi những nút trên cây IT quản lí khoảng ứng với đoạn thẳng đó. Việc đầu tiên, giống như Update trên cây IT cơ bản, ta phải chia đoạn cần Update ra thành những khoảng IT.

void Update(int node, int l, int h, line val)
{
    if(low[node] > h || high[node] < l)
    {
        return;
    }
    if(low[node] >= l && high[node] <= h)
    {
        // Do something
        return;
    }
    Update(node * 2, l, h, val);
    Update(node * 2 + 1, l, h, val);
}

Độ phức tạp của phần chia khoảng này là: O(log(MAXX)), giống như IT cơ bản. Nếu đoạn cần Update là đường thẳng (l = low[1], h = high[1]) thì không mất thời gian chia khoảng, độ phức tạp chỉ là O(1).

Bây giờ việc phải làm là điền vào chỗ “// Do Something”. Ta có một đường thẳng val và đường thẳng it[node], cả hai đều chỉ được xét trong khoảng từ low[node] đến high[node]. Lấy mid là điểm giữa của khoảng (mid = (low[node] + high[node]) / 2). Ta sẽ thay đổi nút it[node] và cả các con của nó. Có 6 trường hợp có thể xảy ra:

  1. it[node] hoàn toàn nằm trên val. Trường hợp này ta chỉ bỏ qua mà không làm gì, vì val chắc chắn không bao giờ đạt max trong khoảng low[node] đến high[node].

    if(Get(it[node], low[node]) >= Get(val, low[node]) && Get(it[node], high[node]) >= Get(val, high[node]))
    {
        return;
    }
    

     

  2. it[node] hoàn toàn nằm dưới val. Trường hợp này ta gán it[node] bằng val, it[node] cũ không còn giá trị khi tìm max.

    if(Get(it[node], low[node]) <= Get(val, low[node]) && Get(it[node], high[node]) <= Get(val, high[node]))
    {
        it[node] = val;
        return;
    }
    

     

  3. Nửa bên trái của it[node] hoàn toàn nằm trên nửa bên trái của val. Vậy val chắc chắn không bao giờ đạt max tại nửa trái của khoảng node, ta giữ lại it[node] tại node và down val xuống con phải (node * 2 + 1).

    if(Get(it[node], low[node]) >= Get(val, low[node]) && Get(it[node], mid) >= Get(val, mid))
    {
        Update(node * 2 + 1, l, h, val);
        return;
    }

     

  4. Nửa bên trái của it[node] hoàn toàn nằm dưới nửa bên trái của val. Tương tự như trên, ta down it[node] xuống con phải của node và cập nhật it[node] bằng val.

    if(Get(it[node], low[node]) <= Get(val, low[node]) && Get(it[node], mid) <= Get(val, mid))
    {
        Update(node * 2 + 1, l, h, it[node]);
        it[node] = val;
        return;
    }

     

  5. Nửa bên phải của it[node] hoàn toàn nằm trên nửa bên phải của val.

    if(Get(it[node], mid + 1) >= Get(val, mid + 1) && Get(it[node], high[node]) >= Get(val, high[node]))
    {
        Update(node * 2, l, h, val);
        return;
    }

     

  6. Nửa bên phải của it[node] hoàn toàn nằm dưới nửa bên phải của val.

    if(Get(it[node], mid + 1) <= Get(val, mid + 1) && Get(it[node], high[node]) <= Get(val, high[node]))
    {
        Update(node * 2, l, h, it[node]);
        it[node] = val;
        return;
    }

     

Sau khi xét xong 6 trường hợp ở trên, ta đã xử lí xong việc Update đoạn val trong một khoảng low[node], high[node]. Độ phức tạp của thao tác này là O(log(MAXX)), vì có thể phải đi từ node cho đến lá. Có thể thấy, cây IT có đầy đủ thông tin về đoạn thằng đạt max tại một hoành độ nhất định, vì ta chỉ loại những đoạn thẳng mà hoàn toàn không còn giá trị (trường hợp 1 và trường hợp 2), còn những đoạn thẳng vẫn có thể đạt max tại một vị trí nào đấy luôn được bảo tồn.

Độ phức tạp: O(log2(MAXX)). O(log(MAXX)) khi chia khoảng, O(log(MAXX)) khi Update trên một khoảng. Nếu Update đường thẳng thì không mất thời gian chia khoảng, độ phức tạp tổng cộng là O(log(MAXX)).

Mở rộng:

Query và Update ở trên là những thao tác cơ bản nhất của IT đoạn thẳng. Ngoài ra, có thể có thêm nhiều thông tin phụ đính kèm với đoạn thẳng, tùy thuộc vào đề bài toán.

Có nhiều cách để biểu diễn đoạn thẳng trong cây IT ngoài ax + b. Ví dụ, có thể biểu diễn đoạn thẳng bằng cách lưu tọa độ 2 điểm đầu mút của đoạn. Tùy vào đề bài toán mà có cách biểu diễn hợp lí nhất.

Ứng dụng:

Bài toán tìm max, min của ax + b thường đi kèm với thuật toán quy hoạch động, chẳng hạn như bài toán quy hoạch động có công thức f[i] = max(a[j] * x[i] + b[j] + c), ta cần tìm j < i sao cho hàm đó đạt max. Bao lồi cũng là phương pháp thường được sử dụng trong bài toán này. Hạn chế của bao lồi là a[j] phải tăng dần hoặc giảm dần (nếu không sẽ phải sử dụng cấu trúc khác stack để biểu diễn bao lồi, code rất khó khăn). Hạn chế của IT đoạn thẳng là x[i] phải nguyên và nhỏ để có thể biểu diễn trên IT (nếu không sẽ phải sử dụng IT động hoặc rời rạc hóa).

Ngoài ra, có một số bài toán yêu cầu tìm max, min trên tập đoạn thẳng. Đây là những bài toán IT đoạn thẳng gần như là cách làm duy nhất.

Nguồn bài: https://langocthuyan.wordpress.com/2014/08/12/ki-thuat-su-dung-deque-stack-2-dau-tim-minmax-tren-doan-tinh-tien/ của YÊN VŨ 

Kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến xuất hiện nhiều trong các bài tập tin học, thông thường để cải tiến chương trình, làm giảm độ phức tạp. Chúng ta sẽ tìm hiểu kĩ thuật này qua một vài ví dụ cụ thể và xem xét khả năng mở rộng ứng dụng của nó trong các bài toán khác.

 

1. Bài toán đơn giản

Dạng bài: Cho dãy số nguyên không âm A có n phần tử (n <= 10^6). Tìm L, R là 2 dãy số được hình thành từ A như sau:

  • 1 <= L[i] <= i <= R[i] <= n
  • A[i] = min{A[L[i]], A[L[i]+1]…, A[R[i]]}
  • Số lượng phần tử của A trong đoạn [L[i], R[i]] dài nhất

Yêu cầu: Xuất ra 2 dãy L, R.

Bài tập trên cho thấy rõ công việc của kĩ thuật này: Với mỗi phần tử i của A, tìm đoạn [l, r] dài nhất sao cho i ∈ [l,r] và A[i] = min{A[l],…,A[r]}. Với n nhỏ (n <= 10^3 chẳng hạn) ta có thể giải quyết bằng cách: với mỗi i, ta kiểm tra các phần tử xung quanh i để mở rộng phạm vi l, r, cụ thể:

for (int i = 1; i <= n; ++i){
   L[i] = i;
   while (L[i] > 0 && a[i] <= a[L[i]]) --L[i];
   ++L[i];
   R[i] = i;
   while (R[i] < n && a[i] <= a[R[i]]) ++R[i];
   --R[i];
}

Nhận xét:

  • L[i] – 1 bằng 0 hoặc là số lớn nhất mà L[i] – 1< i và A[L[i] – 1] < A[i] (1)
  • R[i] + 1  bằng n+1 hoặc là số nhỏ nhất mà R[i] + 1 > i và A[R[i] + 1] < A[i] (2)

Từ nhận xét này, ta xây dựng Deque bằng cách “lọc” lại dãy như sau: trong quá trình duyệt dãy A, luôn đưa i vào cuối Deque hiện tại, nhưng loại bỏ hết tất cả các vị trí j đã được đưa vào trong Deque mà A[j] >= A[i]. Như vậy, tại mọi thời điểm I, ta luôn có danh sách các vị trí trên Deque tạo thành dãy các số tăng dần trên A.

Ví dụ: A: 1 3 5 4 2 8 Deque và giá trị tương ứng trên A

i = 1: Deque: 1                                                 A: 1
i = 2: Deque: 1 2                                               A: 1 3
i = 3: Deque: 1 2 3                                             A: 1 3 5
i = 4: Deque: 1 2 4                                             A: 1 3 4
i = 5: Deque: 1 5                                               A: 1 2
i = 6: Deque: 1 5 6                                             A: 1 2 8

for (int i = 1; i <= n; ++i){
   while (top > 0 && a[D[top]] >= a[i]) --top;  //cap nhat Deque
   D[++top] = i; //dua i vao cuoi Deque
}

Theo cách hoạt động của Deque, ta có: Giả sử tại bước i, đã xác định được i ở vị trí top trong Deque. Khi đó: L[i] = Deque[top – 1] + 1

Chứng minh:

Từ (1) ta có A[L[i] – 1] < A[i], nên L[i] – 1 không bị loại khỏi Deque trong quá trình cập nhật lại Deque. Mặc khác, cũng từ (1) ta có L[i] – 1 lớn nhất, mọi số j ∈ [L[i], i – 1] đều đã bị loại khỏi Deque do A[j] >= A[i], nên L[i] – 1 sẽ đứng liền sát i trong Deque. Ta đưa i vào vị trí cuối (top) của Deque, nên L[i] – 1 chính bằng Deque[top – 1], hay L[i] = Deque[top – 1] + 1.

Vậy, ta xác định được L của một phần tử bất kì ngay khi đưa phần tử đó vào Deque.

Bên cạnh đó, gọi t là vị trí các phần tử của A bị loại khỏi Deque trong quá trình cập nhật Deque. t bị loại khỏi Deque tại thời điểm i, chứng tỏ i là số đầu tiên xuất hiện trong Deque mà A[i] < A[t] (vì nếu tồn tại một số k thỏa t < k < i mà A[k] < A[t] thì t đã bị loại tại thời điểm k). Từ (2) ta suy ra R[t] + 1 chính là i, hay: R[t] = i – 1;

Vậy, ta xác định được R của một phần tử bất kì khi loại phần tử đó ra khỏi Deque.

D[0] = 0;
for (int i = 1; i <= n; ++i){
    while (top > 0 && a[D[top]] >= a[i])
         R[D[top--]] = i – 1;
    L[i] = D[top] + 1;
    D[++top] = i;
}
while (top > 0) R[D[top--]] = n;

Độ phức tạp của đoạn chương trình trên có thể đánh giá như sau: Với mỗi số ∈ dãy A ta chỉ đưa vào Deque 1 lần duy nhất và cũng chỉ lấy ra khỏi Deque 1 lần duy nhất. Do vậy chi phí thực hiện chỉ khoảng 2*n, hay độ phức tạp chương trình là O(n).

2.  Áp dụng

Chúng ta xem các bài tập sau đây:

Áp dụng 1http://vnoi.info/problems/show/KAGAIN/

Tóm tắt đề: Cho dãy A gồm n phần tử.  Ta chọn các đoạn liên tiếp [i, j] bất kì. “Sức mạnh” của đoạn [i, j] được định nghĩa như sau: SM[i, j] = (j – i + 1) * min{A[i],…, A[j]}. Yêu cầu: Cho biết SM lớn nhất có thể trong dãy A.

Giải: Để tìm kết quả, ta xét tất cả n trường hợp có A[k] chính bằng số người của đại đội ít nhất. “Sức mạnh” lớn nhất tại trường hợp k khi có dãy chọn dài nhất. Xây dựng mảng L, R và kiểm tra (R[i] – L[i]+1) * A[i] để tìm kết quả.

Bài tập tương tựhttp://vnoi.info/problems/show/MINK

Áp dụng 2http://vnoi.info/problems/show/QBRECT/

Tóm tắt đề: Cho bảng số {0, 1} kích thước m x n. Tìm diện tích hình chữ nhật lớn nhất chỉ gồm các số 1 có cạnh song song với bảng.

Giải: Trên dòng k, ta xét đoạn các cột [i, j] gồm các số 1 liên tiếp. Xét mỗi cột t ∈ [i, j], ta gọi H[t] = số dòng của đoạn liên tiếp dài nhất chỉ có số 1 kết thúc tại dòng k.

 Screenshot 2014-08-12 08.28.33

Khi đó: Hình chữ nhật có thể tạo bởi đoạn [i,j] chính là hình có cạnh dài (j – i +1) và chiều cao bằng min{H[t]}. Diện tích hình chữ nhật này là (j – i + 1) * min{H[t]}.

Với mỗi dòng trên hình chữ nhật, ta làm tương tự bài KAGAIN: xét hết tất cả m trường hợp có H[t] là min, tìm đoạn [i, j] dài nhất để có được hình chữ nhật lớn nhất. Để tiện tính toán, ta chuẩn bị trước H[t], thay vì là mảng một chiều ứng với cột t và tính lại với mỗi dòng k, ta mở rộng lưu trữ H[k][t] với ý nghĩa tương tự. Tính bảng H bằng quy hoạch động đơn giản: H[k][t] = 0 nếu A[k][t] = 0, ngược lại H[k][t] = H[k – 1][t] + 1. Việc chuẩn bị bảng H cũng như tìm hình chữ nhật là O(n^2), nên ta giải quyết bài tập này với O(n^2)

Bài tập tương tự:

Một vài bài tập khác sử dụng Kĩ thuật tịnh tiến Deque

VNOI Marathon Round 1!

Chào các bạn,

Như đã thông báo ở đây, T7 tuần này sẽ diễn ra VNOI Marathon vòng 1.

Hè đã đến, và đây là thời gian tuyệt vời nhất để các bạn cày bài và tăng trình độ vì không phải vướng víu công việc ở trường. VNOI Marathon, bắt đầu từ năm 2008, được lập ra với mục tiêu giúp các bạn học được kiến thức mới. Vì vậy bọn mình để thời gian thi 12h khá dài, để các bạn có thể chày cối cả ngày và phát minh ra những ý tưởng kỳ diệu.

Những điều bạn nên biết trước khi thi:

  • Bạn chỉ cần có account VOJ là có thể thi
  • Bạn đọc đề và submit ở đây. Khi kỳ thi bắt đầu, đề bài sẽ tự động xuất hiện.
  • Trong quá trình thi, bài của bạn chỉ được chấm với test ví dụ. Đối với 1 số bài đặc biệt bạn được chấm nhiều test hơn, thì sẽ được nói cụ thể rõ ràng trong đề bài.
  • Bạn được nộp bài nhiều lần, kết quả cao nhất sẽ được tính là kết quả cuối.
  • Nếu bài của bạn chạy trên máy đúng, mà nộp lên không hiểu sao sai, thì bạn có thể submit thử ở ideone, nhưng chú ý là bạn cần đặt chế độ private, nếu không các thí sinh khác có thể tình cờ và bất ngờ đọc được code của bạn. Trong trường hợp 2 bài thí sinh giống nhau, bọn mình có quyền chấm thành 0 điểm mà không nhất thiết phải giải thích thêm.
  • Trong quá trình thi, nếu có thắc mắc gì, các bạn có thể đặt câu hỏi ở đây. Bọn mình sẽ cố gắng giải đáp thắc mắc trong thời gian sớm nhất có thể.
  • Trong trường hợp đề bài / việc chấm bài có vấn đề, các thông báo sẽ được đăng ở đây. Vì vậy các bạn nên thỉnh thoảng quay lại kiểm tra topic này.

Muốn bùng cháy,

VNOI Admin team.

 

UPDATE#1: Link đề bài

UPDATE#2: Tạm thời trình chấm bài VMCUT đang bị sai và sẽ được sửa trong thời gian sớm nhất. Các bài nộp của các bạn sẽ được rejudge sau khi trình chấm được sửa xong.

UPDATE#3: Hiện tại trình chấm bài VMCUT đã chính xác. Các bài đã được rejudge

UPDATE#4: Đề bài VMSALARY bị viết sai. Đề đã được sửa lại:

"Nếu nhân viên x là cấp trên trực tiếp của nhân viên y và nhân viên y là cấp trên của nhân viên z thì x là cấp trên (nhưng không trực tiếp) của nhân viên z."

UPDATE#5: 3 bài VMSALARY, VMDAOBIT và VMPIZZA đã được chấm xong. Bài VMCUT do có 1 chút sự cố kĩ thuật nên sẽ được chấm sau. Dự kiến bài VMCUT sẽ được chấm xong trong 1-2h nữa.

UPDATE#6: Mình đang rejudge lại bài VMPIZZA do có 2 test yếu. Nếu các bạn 100 điểm thì khả năng cao là sẽ không bị ảnh hưởng gì. Bài VMCUT mình đang rejudge lại từ đầu do rejudge sai khiến các bạn bị 0

UPDATE#7: Mình đã add 3 bài VMPIZZA, VMSALARY, VMDAOBIT lên VOJ. Bài VMCUT sẽ được up lên sau.

UPDATE#8: Bảng rank đã có ở đây. Với những bạn nộp nhiều lần, kết quả cao nhất sẽ được tính.

Codeforces Round #313

Vào 21:00 tối nay 22/07/2015 Codeforces Round #313 sẽ diễn ra.

Thời gian kết thúc đăng ký: 20:55

Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

Heavy-light decomposition

Heavy-light decomposition (HLD) là kĩ thuật phân tách một cây thành nhiều chuỗi đỉnh (chain) rời nhau. Sau đó, chúng ta có thể áp dụng các cấu trúc dữ liệu như Interval Tree hay Binary-Indexed Tree lên những chuỗi này để có thể cập nhật dữ liệu hoặc trả lời các truy vấn trên một đường đi giữa 2 đỉnh trong cây.

Thuật toán phân tách cây

Trước hết, chúng ta có các định nghĩa như sau:

  • Đỉnh con đặc biệt (heavy vertex): Trong số những đỉnh con của một đỉnh u không phải là lá, đỉnh đặc biệt v là gốc của cây con có kích thước lớn nhất.
  • Cạnh đặc biệt (heavy edge): Là cạnh nối giữa u và v.
  • Những đỉnh con còn lại của u gọi là đỉnh thường (light vertex) và những cạnh nối giữa u đến các đỉnh đó gọi là cạnh thường (light edge).

Dễ thấy là với mỗi đỉnh không phải là lá đều có thể chọn được đúng một cạnh và một đỉnh con đặc biệt của nó. Để tạo các chuỗi đỉnh, chúng ta làm như sau: bắt đầu từ đỉnh gốc, di chuyển xuống đỉnh con đặc biệt của nó và tiếp tục di chuyển xuống các đỉnh con tiếp theo đến khi gặp đỉnh lá thì kết thúc. Đường đi từ đỉnh gốc đến đỉnh lá này tạo thành một chuỗi đỉnh. Chúng ta lại lặp lại thao tác này với các đỉnh còn lại đến khi tất cả các đỉnh đều thuộc đúng một chuỗi nào đó.

Để cho dễ hiểu, chúng ta có ví dụ sau:

Từ đỉnh 1 di chuyển xuống đỉnh 2. Đỉnh đặc biệt của đỉnh 1 là đỉnh 2 vì cây con có đỉnh 2 làm gốc có kích thước lớn nhất.

 

 

Từ đỉnh 2 di chuyển xuống đỉnh 4 vì cây con có gốc là đỉnh 4 có kích thước lớn nhất.

 

 

  

Từ đỉnh 4 di chuyển xuống đỉnh số 7. Tại đây 2 cây con có gốc là đỉnh 7 và đỉnh 5 đều có kích thước như nhau nên ta có thể chọn bất kì đỉnh nào.

 

 

Tiếp tục thực hiện cho đến khi gặp đỉnh lá. Như vậy là chúng ta đã có được một chuỗi đỉnh.

 

 

Chúng ta bắt đầu chuỗi mới ở một đỉnh gần nhất và lặp lại quá trình trên.

 

 

Cuối cùng chúng ta sẽ có một tập các chuỗi đỉnh rời nhau. Những cạnh được tô màu là cạnh đặc biệt và cạnh không được tô màu là cạnh thường.

 

// nChain chuỗi hiện tại. Sau khi kết thúc việc phân tách thì đây sẽ là tổng số chuỗi.
// chainHead[c] đỉnh đầu của chuỗi c
// chainInd[u] chuỗi mà đỉnh u nằm trong.

void hld(int u) {

    // Nếu chuỗi hiện tại chưa có đỉnh đầu (đỉnh gần gốc nhất) thì đặt u làm đỉnh đầu của nó.
	if (chainHead[nChain] == 0) chainHead[nChain] = u;

    // Gán chuỗi hiện tại cho u
	chainInd[u] = nChain;

    // Giải thích bên dưới
	posInBase[u] = ++nBase;

    // Biến lưu đỉnh con đặc biệt của u
	int mxVtx = -1;

    // Tìm đỉnh con đặc biệt trong số những đỉnh con của u
	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];
		if (v != parent[u]) {
			if (mxVtx == -1 || nChild[v] > nChild[mxVtx]) {
				mxVtx = v;
			}
		}	
	}

    // Nếu tìm ra đỉnh con đặc biệt (u không phải là đỉnh lá) thì di chuyển đến đỉnh đó
	if (mxVtx > -1)
		hld(mxVtx);

    // Sau khi đi hết một chuỗi thì tăng nChain lên và bắt đầu một chuỗi mới
	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];
		if (v != parent[u] && v != mxVtx) {
			nChain++;
			hld(v);
		}
	}
}

Để có thể tiếp tục, chúng ta cần biết ít nhất các thông tin sau:

  • Với một chuỗi, đỉnh đầu (đỉnh gần đỉnh gốc nhất) của nó là đỉnh nào.
  • Với một đỉnh, chuỗi mà nó nằm trong là chuỗi nào.
  • Ngoài ra chúng ta còn có mảng posInBase[]. Đây là mảng lưu lại vị trí của các đỉnh sau khi chúng ta "trải" các chuỗi trên lên một đường thẳng. Điều này sẽ giúp cho việc cài đặt các cấu trúc dữ liệu như Interval Tree hoặc Binary Indexed Tree một cách gọn gàng hơn.

Giả sử với hình trên thì posInBase[7] = 4; posInBase[14] = 8 ...

Cập nhật và truy vấn một đường đi trên cây

Thay vì cập nhật hoặc truy vấn một đường đi từ đỉnh u đến đỉnh v trên cây, chúng ta có thể thực hiện các thao tác này trên 2 đường đi từ u đến lca(u, v) và từ v đến lca(u, v) (lca là hàm tìm cha chung gần nhất của 2 đỉnh).

Giả sử chúng ta cần cập nhật đường đi từ u đến lca(u, v) (gọi tắt là a). Nếu a và u không cùng một chuỗi, chúng ta thực hiện thao tác cập nhật lên đường đi từ đỉnh u đến đỉnh đầu của chuỗi hiện tại. Sau đó cho u nhảy lên đỉnh cha của đỉnh đầu này rồi lặp lại thao tác cập nhật. Đến khi u và a nằm trên cùng một chuỗi, chúng ta chỉ cần cập nhật đoạn từ u đến a và kết thúc. Thao tác truy vấn được thực hiện tương tự.

Ví dụ:

Chúng ta cần thực hiện cập nhật trên đường đi từ u = 16 đến a = 1.

Gọi hàm update interval tree cho đoạn từ đỉnh 8 đến đỉnh 16.

 

 

Nhảy lên đỉnh cha của đỉnh đầu của chuỗi hiện tại. Lúc này u = 11.

 

 

Gọi hàm update interval tree cho đoạn từ đỉnh 11 đến đỉnh 5.

 

 

Nhảy lên đỉnh cha của đỉnh đầu của chuỗi hiện tại. Lúc này u = 4.

 

 

Gọi hàm update interval tree cho đoạn từ đỉnh 4 đến đỉnh 1 và kết thúc.

 

void update(int u, int a) {
    // uchain chuỗi hiện tại của u 
    // achain chuỗi của a
     int uchain = chainInd[u], achain = chainInd[a];

     while (1) {
        // Nếu u và a cùng nằm trên một chuỗi thì update đoạn từ u đến a và kết thúc.
          if (uchain == achain) {
               updateIntervalTree(..., posInBase[a], posInBase[u], ...);
               break;
          }
        // Nếu u và a không nằm trên cùng một chuỗi thì update đoạn từ u đến đỉnh đầu của chuỗi hiện tại.
          updateIntervalTree(..., posInBase[chainHead[uchain]], posInBase[u], ...);

        // Nhảy lên đỉnh cha của đỉnh đầu hiện tại.
          u = parent[chainHead[uchain]];
          uchain = chainInd[u];
     }
}

Độ phức tạp

Với một cây có n đỉnh, khi đi từ đỉnh gốc đến một đỉnh lá bằng một đường đi bất kì thì số lần chúng ta phải nhảy chuỗi sẽ không vượt quá log(n). Để chứng minh điều này, chúng ta có thể thấy rằng, khi nhảy từ một đỉnh bất kì đến đỉnh con thường của nó thông qua cạnh thường thì số lượng đỉnh con có thể đi được sẽ giảm đi xuống còn tối đa một nửa so với ban đầu (nếu số đỉnh con còn lại nhiều hơn một nửa số đỉnh ban đầu thì đỉnh chúng ta nhảy tới đã là đỉnh con đặc biệt). Và nếu chúng ta tiếp tục nhảy qua nhiều chuỗi mới thì số lượng đỉnh sẽ giảm theo bội của 2. Bên cạnh đó, chúng ta sử dụng cấu trúc dữ liệu đặc biệt cho việc cập nhật hoặc truy vấn thông tin các đỉnh trong cùng một chuỗi nên độ phức tạp của thao tác này cũng là O(log(n)).

Như vậy độ phức tạp của một thao tác cập nhật hoặc truy vấn một đường đi trên cây sẽ là O(log(n)).

Bài tập áp dụng

QTREE

QTREE3

QTREEX

EpicTree

Tham khảo

http://wcipeg.com/wiki/Heavy-light_decomposition

http://blog.anudeep2011.com/heavy-light-decomposition/

 

Chuỗi ký tự trong C++

KIỂU CHUỖI CỦA C VÀ HẠN CHẾ
Khi mới học C, chắc các bạn đều rất bối rối khi làm việc với xâu ký tự, việc sử dụng con trỏ lưu xâu ký tự rất phức tạp, dễ gây lỗi khiến nhiều người cho rằng nó không bằng xâu ký tự trong Pascal.
Các chương trình C++ có thể sử dụng chuỗi theo cách thức cũ của Ngôn ngữ C: mảng các ký tự kết thúc bởi ký tự mã ASCII là 0 (ký tự ‘\0’) cùng với các hàm thư viện khai báo trong <string.h> . Có nhiều bất tiện khi dùng theo cách thức này:

  • Người lập trình phải chủ động kiểm soát bộ nhớ cấp phát cho chuỗi ký tự. Nói chung là phải am hiểu và rất thông thạo về kỹ thuật dùng bộ nhớ và con trỏ thì chương trình mới tránh được các lỗi về kỹ thuật;
  • Không thể gán giá trị hay sử dụng phép toán + (ghép chuỗi) và các phép toán so sánh như: > (lớn hơn), < (nhỏ hơn),… mà phải gọi các hàm thư viện trong <string.h>;
  • Nếu dùng kỹ thuật cấp phát động thì phải quản lý việc cấp thêm bộ nhớ khi chuỗi dãn ra (chẳng hạn do ghép chuỗi) và phải hủy bộ nhớ (khi không dùng nữa) để tránh việc cạn kiệt bộ nhớ của máy tính trong trường hợp có nhiều chương trình hoạt động đồng thời.

1. KIỄU CHUỖI STRING TRONG THƯ VIỆN STL CỦA C++
Thư viện chuẩn STL (Standard Template Library) cung cấp kiểu string (xâu ký tự), giúp các bạn tránh khỏi hoàn toàn các phiền phức nêu trên.Các chỉ thị #include cần khai báo để sử dụng string :

#include <string>
using std::string;
//using namespace std;

2. CÁC PHƯƠNG THỨC, PHÉP TOÁN TIỆN ÍCH CỦA KIỂU STRING
Kiểu string của STL hỗ trợ các nhóm phương thức và phép toán tiện ích sau đây.
a) Các phép toán và phương thức cơ bản

  • Các toán tử +, += dùng để ghép hai chuỗi và cũng để ghép một ký tự vào chuỗi;
  • Các phép so sánh theo thứ tự từ điển: == (bằng nhau), != (khác nhau), > (lớn hơn), >= (lớn hơn hay bằng), < (nhỏ hơn), <= (nhỏ hơn hay bằng);
  • Phương thức length( ) và phép lấy chỉ số [ ] để duyệt từng ký tự của chuỗi: nếu s là biến kiểu string thì s[i] là ký tự thứ i của s với 0 ≤ i <s.length( );
  • Phép gán (=) dùng để gán biến kiểu string bằng một chuỗi, hoặc bằng string khác, chẳng hạn: string s=”ABCDEF”; hay s1=s2; mà không cần copy xâu.
  • Những constructor thường sử dụng nhất:
string();
string(const char *str);
string(const string & str);

 

  •  Có thể dùng toán tử << với cout để xuất một chuỗi ra màn hình hoặc dùng toán tử >> với cin để nhập một chuỗi ký tự đến khi gặp một khoảng trống thì dừng.
char st[]=“ABCDEF”;
string s;
s=“XYZ”;
cout << s << endl;
s=st;
cout << s.length() << “ : ” << s << endl;
//…

 

  • Một vấn đề thường nảy sinh trong các ứng dụng có sử dụng C-string: một C-String chưa khởi tạo cần được gán NULL. Tuy nhiên, rất nhiều hàm thư viện của C-String sẽ gặp sự cố trong thời gian chạy khi gặp đối tượng CString là NULL. Chẳng hạn, lệnh
char* x = NULL;
cout << strlen(x);

 

được một số trình biên dịch chấp nhận, nhưng với nhiều hiện thực khác của thư viện C-String, thì gặp lỗi trong thời gian chạy. string không gặp vấn đề này, ta hoàn toàn có thể cho 1 xâu là rỗng mà không gặp bất cứ lỗi nào: string s="";

  • String thực chất là một vector<char> có bổ sung thêm một số phương thức và thuộc tính, do đó, nó có toàn bộ các tính chất của 1 vector, vd hàm size(), push_back(), toán tử [] …
  • Phương thức Mô tả
    • v.size(): Số lượng phần tử
    • v.empty (): Trả về 1 nếu chuỗi rỗng, 0 nếu ngược lại.
    • v.max_size(): Trả về số lượng phần tử tối đa đã được cấp phát
    • v1 == v2: Trả về 1 nếu hai chuỗi giống nhau
    • v1 != v2: Trả về 1 nếu hai chuỗi khác nhau
    • v.begin(): Trả về iterator đầu tiên của chuỗi
    • v.end(): Trả về iterator lặp cuối cùng của chuỗi
    • v.front(): Trả về tham chiếu đến phần tử đầu tiên của chuỗi
    • v.back(): Trả về tham chiếu đến phần tử cuối cùng của chuỗi
    • v1.swap(v2): Hoán đổi 2 chuỗi với nhau (giống việc hoán đổi giá trị của 2 biến)
#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
int main()
{
    string s = "Hello string"; // Khai báo biến kiểu string
    cout << "Noi dung string: " << s << endl; // In nôi dung string ra màn h.nh
    cout << "Chieu dai cua string: " << s.size() << endl;
    // Chiều dài
    cout << "Ky tu 0: " << s[0] << endl; // In ký tự đầu tiên của xâu
    cout << "Ky tu 1: " << s[1] << endl; // In ký tự thứ 2
    cout << "Ky tu 2: " << s[2] << endl; // In ký tự thứ 3
    getchar();
    return 0;
}


Nhập một string: istream& getline ( istream& in, string& str, char delimiter = ‘\n’);
Đọc 1 dòng văn bản từ đối tượng nhập (istream) in (có thể là file hay đối tượng chuẩn cin) từng ký tự đến khi ký tự delimiter được nhập vào ( mặc định là \n )

(thường được dùng thay cho cin >> khi nhập chuỗi có ký tự space).Có thể dùng kết hợp với toán tử >>

// getline with strings
#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string str;
    short age;
    cout << "Please enter full name and age"<< endl;
    getline( cin, str) >> age;
    cout << "Thank you " << str << "!\n";
    return 0;
}


b) Các phương thức chèn, xóa, lấy chuỗi con:
Phương thức substr(int pos, int nchar) trích ra chuỗi con của một chuỗi cho trước, ví dụ str.substr(2,4) trả về chuỗi con gồm 4 ký tự của chuỗi str kể từ ký tự ở vị trí thứ 2 (ký tự đầu tiên của chuỗi ở vị trí 0).

//get substring
#include <iostream>
#include <string>
#include <conio.h>
using namespace std;
int main ()
{
    string s="ConCho chay qua rao";
    cout << s.substr(2,4) << endl;
    // cout << new string(str.begin()+2, str.begin()+2+4);
    getchar();
    return 0;
}

 

  • Phương thức insert( ) chèn thêm ký tự hay chuỗi vào một vị trí nào đó của chuỗi str cho trước. Có nhiều cách dùng phương thức này:
    • str.insert(int pos, char* s; chèn s (mảng ký tự kết thúc ‘\0’) vào vị trí pos của str;
    • str.insert(int pos, string s); chèn chuỗi s (kiểu string) vào vị trí pos của chuỗi str;
    • str.insert(int pos, int n, int ch); chèn n lần ký tự ch vào vị trí pos của chuỗi str;
// inserting into a string
#include <iostream>
#include <string>
#include <conio.h>
using namespace std;
int main ()
{
    string str="day la .. xau thu";
    string istr = "them";
    str.insert(8, istr);
    cout << str << endl;
    getchar();
    return 0;
}

 

  • Phương thức str.erase(int pos, int n) xóa n ký tự của chuỗi str kể từ vị trí pos; nếu không quy định giá trị n thì tất cả các ký tự của str từ vị trí pos trở đi sẽ bị xóa
// erase from a string
#include <iostream>
#include <string>
#include <conio.h>
using namespace std;
int main ()
{
    string str="day cung la xau thu";
    str.erase(0, 3); // " cung la xau thu"
    cout << str << endl;
    str.erase(6, 2);
    cout << str << endl; // " cung xau thu"
    getchar();
    return 0;
}


c) So sánh
Bạn có thể đơn giản là sử dụng những toán tử quan hệ ( ==, !=, <, <=, >= ) được định nghĩa sẵn. Tuy nhiên, nếu muốn so sánh một phần của một chuỗi thì sẽ cần sử dụng phương thức compare():
int compare ( const string& str ) const;
int compare ( const char* s ) const;
int compare ( size_t pos1, size_t n1, const string& str ) const;
int compare ( size_t pos1, size_t n1, const char* s) const;
int compare ( size_t pos1, size_t n1, const string& str, size_t pos2, size_t n2 ) const;
int compare ( size_t pos1, size_t n1, const char* s, size_t n2) const;
Hàm trả về 0 khi hai chuỗi bằng nhau và lớn hơn hoặc nhỏ hơn 0 cho trường hợp khác
Ví dụ:

// comparing apples with apples
#include <iostream>
#include <string>
using namespace std;
int main ()
{
    string str1 ("green apple");
    string str2 ("red apple");
    if (str1.compare(str2) != 0)
    cout << str1 << " is not " << str2 << "\n";
    if (str1.compare(6,5,"apple") == 0)
    cout << "still, " << str1 << " is an apple\n";
    if (str2.compare(str2.size()-5,5,"apple") == 0)
    cout << "and " << str2 << " is also an apple\n";
    if (str1.compare(6,5,str2,4,5) == 0)
    cout << "therefore, both are apples\n";
    return 0;
}


d) Các phương thức tìm kiếm và thay thế
- Phương thức find( ) tìm kiếm xem một ký tự hay một chuỗi nào đó có xuất hiện trong một chuỗi str cho trước hay không. Có nhiều cách dùng phương thức này:
str.find(int ch, int pos = 0); tìm ký tự ch kể từ vị trí pos đến cuối chuỗi str
str.find(char *s, int pos = 0); tìm s (mảng ký tự kết thúc ‘\0’) kể từ vị trí pos đến cuối
str.find(string& s, int pos = 0); tìm chuỗi s kể từ vị trí pos đến cuối chuỗi.
Nếu không quy định giá trị pos thì hiểu mặc nhiên là 0; nếu tìm có thì phương thức trả về vị trí xuất hiện đầu tiên, ngược lại trả về giá trị -1.

//find substring
#include <iostream>
#include <string>
#include <conio.h>
using namespace std;
int main ()
{
    string str="ConCho chay qua rao";
    cout << str.find("chay") << endl; // 7
    cout << (int)str.find("Chay") << endl; // -1
    getchar();
    return 0;
}
Hàm tìm kiếm ngược (rfind)
//find from back
#include <iostream>
#include <string>
#include <conio.h>
using namespace std;
int main ()
{
    string str="ConCho chay qua chay qua rao";
    cout << str.find("chay") << endl; // 7
    cout << (int)str.rfind("chay") << endl; // 16
    getchar();
    return 0;
}


- Phương thức replace( ) thay thế một đoạn con trong chuỗi str cho trước (đoạn con kể từ một vị trí pos và đếm tới nchar ký tự ký tự về phía cuối chuỗi) bởi một chuỗi s nào đó, hoặc bởi n ký tự ch nào đó. Có nhiều cách dùng, thứ tự tham số như sau:
str.replace(int pos, int nchar, char *s);
str.replace(int pos, int nchar, string s);
str.replace(int pos, int nchar, int n, int ch);
 

string str="con cho la con cho con. Con meo ko phai la con cho";
str.replace(4, 3, "CHO"); // "con CHO la con cho con. Con meo ko phai la con cho";
cout << str << endl;
getchar();


e) Tách xâu
Trong việc xử lý xâu ký tự, không thể thiếu được các thao tác tách xâu ký tự thành nhiều xâu ký tự con thông qua các ký tự ngăn cách. Các hàm này có sẵn trong các ngôn ngữ khác như Visual Basic,Java, hay thậm chí là trong
<string.h> (không phải <string>) Với STL, các bạn có thể dễ dàng tự xây dựng một hàm với chức năng tương tự:
 

string S = "Xin chao tat ca cac ban"; // Khởi tạo giá trị của xâu
string::iterator t, t2; // Các biến lặp
vector<string> split; // Mảng các xâu (lưu kết quả tách)

for (t=S.begin(); t<S.end();)
{
    // Lặp từ vị trí bắt đầu
    t2=find(t, S.end(), ' '); // TÌm ký tự space ' ' đầu tiên
    // kể từ vị trí t
    if (t!=t2) split.push_back(string(t, t2)); // Lấy xâu ký tự giữa 2 vị trí
    t = t2+1; // Chuyển sang vị trí sau
}
for (int i=0; i<splitìsize(); i++)
cout << split[i] << endl; // In mảng các xâu ký tự
getchar();


Output:
Xin
chao
tat
ca
cac
ban
Đoạn chương tr.nh sử dụng các kỹ thuật sau

  • Phương thức find(vị_trí_đầu, vị_trí_cuối, ký_tự_tìm) dùng để tìm vị trí đầu tiên của ký_tự_tìm bắt đầu từ vị_trí_đầu. Hàm này trả về vị trí của ký tự tìm được (nếu tìm thấy) hoặc vị_trí_cuối (nếu không tìm thấy)
  • string có thể khởi tạo từ một đoạn ký tự con của một xâu ký tự khác với cú pháp string(vị_trí_đầu, vị_trí_cuối)
  • Đoạn chương tr.nh thực hiện tách các xâu ký tự kể cả trong trường hợp có nhiều ký tự space nằm liên tiếp nhau. Một cách đơn giản hơn là bạn có thể gọi hàm strtok() trong string.h để làm việc này, nhưng không may là hàm này thao tác trên char* chứ không phải string. Hàm thành viên c_str() sẽ giúp bạn chuyển từ string thành dạng const charT* c_str ( ) const;

Hàm này cũng tự động sinh ra ký tự null chèn vào cuối xâu.
Từ prototype ta cũng thấy được hàm trả về một hằng chuỗi, điều này đồng nghĩa với việc ta không thể thay đổi chuỗi trả về.
Gọi phương thức c_str();
string s = "some_string";
cout << s.c_str() << endl;
cout << strlen(s.c_str()) << endl;
Sau đây là ví dụ bên trên được viết lại dùng hàm thành viên c_str() và các hàm trong <string.h>

// strings vs c-strings
#include <iostream>
#include <string.h>
#include <string>
using std::string;
int main ()
{
    char * cstr, *p;
    string str ("Xin chao tat ca cac ban");
    cstr = new char [str.size()+1];
    strcpy (cstr, str.c_str());
    // cstr là 1 bản sao c-string của str
    p=strtok (cstr," ");
    while (p!=NULL)
    {
        cout << p << endl;
        p=strtok(NULL," ");
    }
    delete[] cstr;
    return 0;
}


Output:
Xin
chao
tat
ca
cac
ban
f) Chuyển đổi hàng loạt với transform
OutputIterator transform( InputIterator first,
InputIterator last,
OutputIterator result,
UnaryOperation unary_op );

#include <cctype> // for toupper
#include <string>
#include <algorithm> //for transform
using namespace std;
char alphabet(char c)
{
    static char ch = 'a';
    return ch++;
}
int main()
{
    string s("this is a lower case string");
    transform(s.begin(), s.end(), s.begin(), toupper);
    cout << s << endl;
    transform(s.begin(), s.end(), s.begin(), alphabet);
    cout << s;
    return 0;
}


g) Một số phương thức khác
Còn nhiều phương thức tiện ích khác như: append(), rfind(), find_first_not_of(), find_last_not_of(), swap(). Cách dùng các hàm này đều được trình bày trong hệ thống hướng dẫn (help) của các môi trường có hỗ trợ STL (trong VC++ là MSDN). Ngoài ra các phương thức như find_first_of() tương tự như find(), find_last_of() tương tự như rfind()
Nguồn: Không rõ.

 

Tổng kết 2 tuần ra mắt VNOI

Vậy là VNOI mới đã ra mắt các bạn được 2 tuần. Với hầu hết team admin bọn mình, đây là lần đầu bọn mình ra mắt 1 trang web có người dùng. Cá nhân mình thì trước khi làm VNOI mình cũng biết sơ sơ về lý thuyết làm web, nhưng kinh nghiệm thực tế thì cũng chưa có :D, nên vô cùng háo hức & lo lắng, như đang chăm sóc đứa con đầu lòng của mình vậy :v

1 chút tổng kết trong thời gian qua:

  • Sau 2 tuần, chúng ta có gần 450 user, hơn 250 bạn đã kết nối account VOJ.
  • Số lượt submit lên VOJ qua VNOI là chưa đến 400. Mình biết là hiện tại có rất nhiều lỗi khi submit qua VNOI như ko submit đc, submit đc nhưng ko đc chấm, kết quả chấm bị sai so với VOJ. Bọn mình đang cố gắng khắc phục những lỗi này. Hiện tại theo mình biết thì các bạn đã có thể submit bình thường. Nếu bạn nào vẫn còn bị lỗi thì hãy nói cho bọn mình ngay ở đây.
  • Số bài post trên VNOI chỉ hơn 300, trong đó chắc hầu hết là của admin :D 1 phần cũng có thể do bọn mình ko thân thiện lắm, ví dụ như ở đây. Mình hi vọng là các bạn dần dần sẽ bớt ngại, bớt sợ admin và nói nhiều hơn :D Các bạn nói ngây thơ hoặc linh tinh cũng đc, cơ mà cứ tự nhiên nói cho có không khí :)). Nếu các bạn để ý thì giờ nếu bị trừ cũng không ảnh hưởng gì (hiện tại, đóng góp không bị giảm và bạn còn có thể tự cộng cho chính mình nếu cảm thấy mình nói quá hay).
  • Hiện tại đã có hơn 20 bài viết trong Thư viện, và mình hi vọng con số đó sẽ còn tăng lên nhiều.
    • Rất cảm ơn 2 bạn ttdpro98 và only_love97 đã đóng góp rất nhiều bài viết cho Thư viện VNOI :D
  • Thỉnh thoảng server vẫn bị không vào được và hiện lỗi 500, 502. Thông thường là do bọn mình đang cập nhật tính năng mới cho VNOI, hoặc đang phải sửa sự cố khẩn cấp nào đó. Nếu gặp trường hợp này các bạn có thể quay lại trong 10' hoặc 15' sau, lúc đó hi vọng bọn mình đã kịp thời sửa :D
  • 1 vài tính năng mới:
    • Hình quả chuông bên góc phải trên: mỗi lần có người trả lời bài viết của bạn, bạn sẽ nhận được thông báo (hi vọng các bạn post bài nhiều hơn để test tính năng này :)))
    • Ở phần danh sách bài tập, đã có đánh dấu xanh với những bài bạn đã làm được.
  • 1 vài tính năng sắp ra mắt:
    • Màu user ở bảng rank, forum (hiện tại đã có ở bài viết trên trang chủ :D)
    • Ẩn các bài đã làm ở danh sách bài tập
    • [Hot] Xem chi tiết kết quả chấm bài VOJ (test nào AC, test nào WA, test nào TLE...). Dự kiến tính năng này sẽ ra mắt trong vòng 1 - 2 tháng nữa. Để bọn mình có thể test tính năng này khi ra mắt, hi vọng các bạn tích cực nộp bài qua VNOI hơn :p
  • Hôm mới ra mắt, forum có bị darksabers hack (post vài nghìn bài trong khoảng thời gian ngắn). Hiện bạn ý đã vào team admin và giúp bọn mình hoàn thiện trang web hơn :). Team làm web VNOI từ đầu đến giờ gồm có mình, iamquang95, khoaplt, tmbaodarksabers, net12k44, quochuu_96, infrmtcs và Hoàng Yến. Tuy nhiên hiện giờ có 1 số bạn đã không làm tiếp nữa, và mình đang tuyển thêm người mới. Nếu bạn nào muốn gia nhập team thì có thể nói với mình, nếu bạn không biết code web thì mình có thể dạy từ đầu.

Nếu có phát hiện bug, các bạn có thể trả lời vào ngay trong topic này hoặc ở đây :D

Rất cảm ơn các bạn,

RR

VNOI Marathon 2015

                                                       

 

      Xin chào tất cả các VNOIers, chắc hẳn các bạn đã rất ngóng chờ kỳ thi VNOI Marathon 2015 (VM15) trong dịp hè này. Hôm nay mình xin đưa những thông tin nóng hổi nhất về kỳ thi VM15 cho tất cả các bạn.

        VNOI Marathon là một cuộc thi lập trình hàng năm do ban quản trị diễn đàn VNOI tổ chức. VNOI Marathon được khai sinh với hy vọng tạo ra một sân chơi mới mẻ, lành mạnh và bổ ích cho các bạn học sinh, sinh viên đam mê lập trình. VNOI Marathon giúp các bạn tìm tòi, khám phá những kiến thức mới cũng như góp phần tăng thêm nhiềm đam mê với bộ môn Tin học. Đề thi được tuyển chọn từ nguồn bài của các bạn học sinh có thành tích cao trong các kì thi quốc gia và quốc tế và của các thầy cô giáo nổi tiếng trong lĩnh vực Tin học.

        Kỳ thi VNOI Marathon 2015 sẽ bao gồm 4 vòng thi

  • 3 vòng đầu, mỗi vòng sẽ có 3 bài: 2 bài P (có thuật giải tối ưu) và 1 bài NP (không có thuật giải tối ưu). Trong thời gian thi, 2 bài P bạn sẽ được chấm test ví dụ, bài NP bạn sẽ được chấm 10 tests trong bộ test chính thức của kỳ thi. 3 vòng đầu sẽ diễn ra trong vòng 12 tiếng: 9:00 sáng đến 9:00 tối.
  • Vòng cuối là vòng đặc biệt, bao gồm 4 bài tập, thời gian và format đề thi sẽ được thông báo sau để tăng tính hấp dẫn cho kỳ thi.

        Thời gian cụ thể từng vòng thi 

  • Vòng 1 diễn ra vào thứ 7 ngày 25/7
  • Vòng 2 diễn ra vào thứ 7 ngày 8/8
  • Vòng 3 diễn ra vào thứ 7 ngày 15/8
  • Vòng 4 diễn ra vào thứ 7 ngày 22/8

        Và tất nhiên, kỳ thi nào cũng sẽ có giải thưởng, VM15 cũng vậy, rất nhiều giải thưởng hấp dẫn đang chờ đón các coders. Chi tiết về phần thưởng sẽ được các admins thông báo sau. 

        Các ngôn ngữ cho phép: FPC, C, C++, Java, ... (tùy tuộc từng bài cụ thể)

        Các bạn hãy share post này cho các bạn của bạn biết và cùng tham gia kỳ thi VNOI Marathon 2015 nhé <3

 

                                                                                                                                                      14/07/2015

                                                                                                                                                    Admins Team

 

I. Dãy con đơn điệu dài nhất

1. Mô hình

  • Cho dãy A1,A2,..An. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.
  • Đặc trưng:
    • Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử A trong dãy, khác với các bài toán của mô hình 4 (đặc trưng là bài toán đổi tiền), các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị.
    •  Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu.
  • Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài: Tam giác bao nhau.

2. Công thức QHĐ

  • Hàm mục tiêu : f = độ dài dãy con.
  • Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi Li là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ A1 đến Ai phần tử  cuối cùng là Ai
  • Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
  • Ta có công thức QHĐ để tính Li như sau:
    • L1 = 1. (Hiển nhiên)
    • Li = max(1, Lj+1 với mọi phần tử j: 0<j<i và Aj≤A)
  • Tính Li : phần tử đang được xét là Ai .Ta tìm đến phần tử Aj <Acó Lj lớn nhất. Khi đó nếu bổ sung ai vào sau dãy con ...Aj ta sẽ được dãy con tăng dần dài nhất xét từ A1...Ai

3. Cài đặt

  • Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau:
  • for i:= 1 to n do 
       begin
    
             L[i]:=1;
    
             for j:=1 to i–1 do
    
                  if (A[j]<=A[i]) and (L[i]<L[j]+1) then L[i]:=L[j]+1;
    
       end;

Như vậy chi phí không gian của bài toán là O(n), chi phí thời gian là O(n2). Có một phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời gian là O(nlogn)

4. Một số bài toán khác

Bài toán dãy con đơn điệu tăng dài nhất có biến thể đơn giản nhất là bài toán dãy con đơn điệu giảm dài nhất, tuy nhiên chúng ta có thể coi chúng như là một. Sau đây là một số bài toán khác.

  • Bố trí phòng họp( mất tính thứ tự so với dãy ban đầu)
    • Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm Ai  và kết thúc ở thời điểm Bi. Do chỉ có một phòng hội thảo nên 2 cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được nhiều cuộc họp nhất.
    • Hướng dẫn: Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc Bi. Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j<i và Bj<=Ai. Yêu cầu bố trí được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất thoả mãn điều kiện trên.
  • Cho thuê máy
    • Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ai      đến bi và trả tiền thuê là ci. Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).
    • Hướng dẫn: Tương tự như bài toán bố trí phòng họp, nếu sắp xếp các đơn đặt hàng theo thời điểm kết thúc, ta sẽ đưa được về bài toán tìm dãy con có tổng lớn nhất. Bài toán này là biến thể của bài toán tìm dãy con tăng dài nhất, ta có thể cài đặt bằng đoạn chương trình như sau:
    • for i:=1 to n do 
        begin
      
                L[i]:=C[i];
      
                for j:=1 to i–1 do
      
                     if (B[j]<=A[i]) and (L[i]<L[j]+C[i]) then L[i]:=L[j]+C[i];
      
        end;
  • Dãy tam giác bao nhau
    • Cho n tam giác trên mặt phẳng. Tam giác i bao tam giác j nếu 3 đỉnh của tam giác j đều nằm trong tam giác i (có thể nằm trên cạnh). Hãy tìm dãy tam giác bao nhau có nhiều tam giác nhất.
    • Hướng dẫn: Sắp xếp các tam giác tăng dần về diện tích. Khi đó tam giác i sẽ bao tam giác j nếu j<i và 3 đỉnh của j nằm trong i. Từ đó có thể đưa về bài toán tìm dãy “tăng” dài nhất.
    • Việc kiểm tra điểm M có nằm trong tam giác ABC không có thể dựa trên phương pháp tính diện tích: điểm M nằm trong nếu SABC = SABM + SACM + SBCM
    • Bài toán có một số biến thể khác như tìm dãy hình tam giác, hình chữ nhật… bao nhau có tổng diện tích lớn nhất.
  • Dãy đổi dấu
    • Cho dãy A1, A2,…AN. Hãy tìm dãy con đổi dấu dài nhất của dãy đó. Dãy con con đổi dấu Ai1,Ai2,…Aik phải thoả mãn các điều kiện sau:
      • Ai1<Ai2>Ai3<… hoặc Ai1>Ai2<Ai3>…
      • Các chỉ số phải cách nhau ít nhất L: i2–i1≥L, i3–i2≥L….
      • Chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |Ai1–Ai2|≤U, |Ai2–Ai3|≤U…
    • Hướng dẫn: Gọi Li là số phần tử của dãy con đổi dấu có phần tử cuối cùng là Ai và phần tử cuối cùng lớn hơn phần tử đứng trước. Tương tự, Pi là số phần tử của dãy con đổi dấu có phần tử cuối cùng là Ai và phần tử cuối cùng nhỏ hơn phần tử đứng trước.
    • Ta dễ dàng suy ra:
      • Li = max(1, P+ 1): j ≤ i–L và Ai–U ≤ A< Ai.
      • Pi = max(1, Lj + 1): j ≤ i–L và A< A≤ Ai+U.
  • Dãy số WAVIO:
    • Dãy số Wavio là dãy số nguyên thỏa mãn các tính chất : các phần tử đầu sắp xếp thành 1 dãy tăng dần đến 1 phần tử đỉnh sau đó giảm dần. Ví dụ dãy số 1 2 3 4 5 2 1 là 1 dãy Wavio độ dài 7. Cho 1 dãy gồm N số nguyên, hãy chỉ ra một dãy con Wavio có đọ dài lớn nhất trích ra từ dãy đó.
    • Hướng dẫn: L1i là mảng ghi độ dài lớn nhất của 1 dãy con tăng dần trích ra từ dãy N phần tử kể từ phần tử 1 đến phần tử ai. L2i : mảng ghi độ dài lớn nhất của dãy con giảm dần trích ra từ dãy N phần tử kể từ phần tử AN đến Ai. Ta tìm phần tử j trong 2 mảng L1, L2 thỏa mãn L1j+L2j lớn nhất.
  • Tháp Babilon ( Tính chất duy nhất của các phần tử trong phương án tối ưu bị vi phạm)
  • Xếp các khối đá :
    • Cho N khối đá (N≤5000) Các khối đá đều có dạng hình hộp chữ nhật và được đặc trưng bới 3 kích thước: dài, rộng, cao. Một cách xây dựng tháp là một cách đặt một số các khối đá trong các khối đá đã cho chồng lên nhau theo quy tắc:
      • Chiều cao mỗi khối đá là kích thước nhỏ nhất trong 3 kích thước.
      • Các mép của khối đá được đặt song song với nhau sao cho không có phần nào của khối trên nằm chìa ra ngoài khối dưới.
    • Hãy chỉ ra cách để xây dựng được một cái tháp sao cho số khối đá được dùng là nhiều nhất.
    • Hãy chỉ ra cách để xây dựng được một cái tháp sao cho chiều cao của cái tháp là cao nhất
    • Dữ liệu vào TOWER.INP có cấu trúc như sau :
      • Dòng đầu là số N.
      • N dòng sau dòng i ghi 3 số nguyên ≤ 255 là 3 kích thước của khối đá i .
    • Dữ liệu ra : TOWER1.OUT, TOWER2.OUT ghi theo quy cách :
      •  Dòng đầu ghi số các khối đá được chọn theo thứ tự dùng để xây tháp từ chân lên đỉnh.
      • Các dòng sau ghi các khối được chọn, mỗi khối đá ghi 4 số T, D, R, C trong đó T là số thứ tự của mỗi khối đá. D, R, C là kích thước của khối đá tương ứng.

II. Vali (B)

1. Mô hình

  • Có n đồ vật, vật thứ i có trọng lượng Ai và giá trị Bi. Hãy chọn ra một số các đồ vật, mỗi vật một cái để xếp vào 1 vali có trọng lượng tối đa W sao cho tổng giá trị của vali là lớn nhất.

2. Công thức

  • Hàm mục tiêu : f: tổng giá trị của vali.
  • Nhận xét : giá trị của vali phụ thuộc vào 2 yếu tố: có bao nhiêu vật đang được xét và trọng lượng của các vật. Do đó bảng phương án sẽ là bảng 2 chiều.
    • L[i,j] : tổng giá trị lớn nhất của vali khi xét từ vật 1..vật i và trọng lượng của vali chưa vượt quá j. Chú ý rằng khi xét đến L[i,j] thì các giá trị trên bảng phương án đều đã được tối ưu.
  • Tính L[i,j] : vật đang xét là ai  với trọng lượng của vali không được quá j. Có 2 khả năng xảy ra :
    • Nếu chọn aiđưa vào vali, trọng lượng vali trước đó phải   ≤ j-a[i]. Vì mỗi vật chỉ được chọn 1 lần nên giá trị lớn nhất của vali lúc đó là L[ i-1,j-Ai ]+ Bi
    • Nếu không chọn Ai, trọng lượng của vali là như cũ (như lúc trước khi chọn ai ): L[i-1,j]. Tóm lại ta có L[i,j]=max( L[i-1,j- Ai ] + Bi, L[i-1,j] ).

3. Cài đặt

For i:=1 to n do

    For j:=1 to W do

          If   b[i]<=j then L[i,j]:=max(L[ i-1,j-A[i] ] + B[i], L[i-1,j])

          else L[i,j]:=L[i-1,j];

4. Một số bài toán khác

  • Dãy con có tổng bằng S:
    • Cho dãy A1,A2,..AN. Tìm một dãy con của dãy đó có tổng bằng S.
    • Hướng dẫn
      • Đặt L[i,t]=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử A1,A2,..Ai. Ngược lại thì L[i,t]=0. Nếu L[n,S]=1 thì đáp án của bài toán trên là “có”.
      • Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1.
    • Cài đặt
      • Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và được tính như sau:
      • L[t]:=0; L[0]:=1;
        
        for i := 1 to n do
        
            for t := S downto a[i] do
        
                  if (L[t]=0) and (L[t–a[i]]=1) then L[t]:=1;
      • Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(nm), với m là tổng của n số. Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.
  • Chia kẹo
    • Cho n gói kẹo, gói thứ i có ai viên. Hãy chia các gói thành 2 phần sao cho chênh lệch giữa 2 phần là ít nhất.
    • Hướng dẫn: Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn:
      • S≤T/2.
      • Có một dãy con của dãy a có tổng bằng S.
      • Khi đó sẽ có cách chia với chênh lệch 2 phần là T–2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại.
  • Market (Olympic Balkan 2000)
    • Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là ai, đem bán ngoài chợ. Ở chợ cá, người ta không mua cá theo từng con mà mua theo một lượng nào đó. Chẳng hạn 3 kg, 5kg…
    • Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6 kg sẽ phải lấy con cá thứ 2 và và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể mua lượng 8 kg. Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?
    • Hướng dẫn: Thực chất bài toán là tìm các số S mà có một dãy con của dãy a có tổng bằng S. Ta có thể dùng phương pháp đánh dấu của bài chia kẹo ở trên rồi đếm các giá trị t mà L[t]=1.
  • Điền dấu
    • Cho n số tự nhiên A1,A2, ...,AN. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu "?": A1?A2?...?AN. Cho trước số nguyên S, có cách nào thay các dấu "?" bằng dấu + hay dấu − để được một biểu thức số học cho giá trị là S không?
      • Hướng dẫn: Đặt L[i,t]=1 nếu có thể điền dấu vào i số đầu tiên và cho kết quả bằng t. Ta có công thức sau để tính L:
        • L[ 1,a[1] ] =1.
        • L[i,t]=1 nếu L[i–1,t+a[i] ]=1 hoặc L[ i–1,t–a[i] ]=1.
        • Nếu L[n,S]]=1 thì câu trả lời của bài toán là có. Khi cài đặt, có thể dùng một mảng 2 chiều (lưu toàn bộ bảng phương án) hoặc 2 mảng một chiều (để lưu dòng i và dòng i–1). Chú ý là chỉ số theo t của các mảng phải có cả phần âm (tức là từ –T đến T, với T là tổng của n số), vì trong bài này chúng ta dùng cả dấu – nên có thể tạo ra các tổng âm.
      • Bài này có một biến thể là đặt dấu sao cho kết quả là một số chia hết cho k. Ta có thuật giải tương tự bài toán trên bằng cách thay các phép cộng, trừ bằng các phép cộng và trừ theo môđun k và dùng mảng đánh dấu với các giá trị từ 0 đến k–1 (là các số dư có thể có khi chia cho k). Đáp số của bài toán là L[n,0].
  • Expression (ACM 10690)
    • Cho n số nguyên. Hãy chia chúng thành 2 nhóm sao cho tích của tổng 2 nhóm là lớn nhất.
    • Hướng dẫn: Gọi T là tổng n số nguyên đó. Giả sử ta chia dãy thành 2 nhóm, gọi S là tổng của một nhóm, tổng nhóm còn lại là T–S và tích của tổng 2 nhóm là S*(T–S). Bằng phương pháp đánh dấu ta xác định được mọi số S là tổng của một nhóm (như bài Market) và tìm số S sao cho S*(T–S) đạt max.

III. Biến đổi xâu:

1. Mô hình

  • Cho 2 xâu X,F. Xâu nguồn có n kí tự X1X2...Xn , xâu đích có m kí tự F1F2...Fm .Có 3 phép biến đổi :
    • Chèn 1 kí tự vào sau kí tự thứ i :I i C
    • Thay thế kí tự ở vị trí thứ i bằng kí tự C : R i C.
    • Xoá kí tự ở vị trí thứ i. D i
  • Hãy tìm số ít nhất các phép biến đổi để biến xâu X thành xâu F.
  • Hướng dẫn:
    • Hàm mục tiêu : f: số phép biến đổi.
    • Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang xét của xâu F. Do vậy để cài đặt cho bang phương án ta sẽ dùng mảng 2 chiều
    • Gọi L[i,j] là số phép biến đổi ít nhất để biến xâu Xi gồm i kí tự phần đầu của X ( Xi=X[1..i] ) thành xâu Fj gồm j kí tự phần đầu của F( Fj =F[1..j]). Dễ thấy F[0,j]=j và F[i,0]=i.
    • Có 2 trường hợp xảy ra: Nếu X[i]=F[j] :
      • X1X2...Xi-1      Xi
      • F1F2...Fj-1       Xi 
      • thì ta chỉ phải biến đổi xâu Xi-1 thành xâu Yj-1. Do đó F[i,j]=F[i-1,j-1].
    • Ngược lại, ta có 3 cách biến đổi:
      •  ​​ Xoá kí tự  Xi:             
        • X1X2...Xi-1      Xi
        • F1F2...Fj-1      Fj
        • Xâu Xi-1 thành Fj. Khi đó F[i,j]=F[i-1,j]+1.(Cộng 1 là do ta đã dùng 1 phép xóa)
      • Thay thế Xi bởi Fj :        
        • X1X2...Xi-1        Fj
        • F1F2...Fj-1         Fj
        • Xâu Xi-1 thành Fj-1. Khi đó F[i,j]=F[i-1,j-1]+1.
      • Chèn Fj vào Xi:               
        • X1X2...Xi-1      Fj
        • F1F2...Fj-1       Fj
    • Xâu X(i) thành Y(j-1). Khi đó F(i,j)=F(i,j-1)+1. Tổng kết lại, ta có công thức QHĐ:
      • F[0,j]=j
      • F[i,0]=i
      • F[i,j] =F[i−1,j−1] nếu Xi = Yj.
      • F[i,j] = min( F[i−1,j] , F[i,j−1] , F[i−1,j−1] )+1 nếu Xi≠Xj.
  • Bài này ta có thể tiết kiệm biến hơn bằng cách dùng 2 mảng 1 chiều tính lẫn nhau và một mảng đánh dấu 2 chiều để truy vết.

4. Một số bài toán khác

  • Xâu con chung dài nhất
    • Cho 2 xâu X,Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất.
    • Công thức QHĐ
      • Gọi L[i,j] là độ dài xâu con chung dài nhất của xâu Xi gồm i kí tự phần đầu của X ( Xi=X[1..i] ) và xâu Yj gồm j kí tự phần đầu của Y ( Yj =Y[1..j] ). Ta có công thức quy hoạch động như sau:
        • L[0,j]=L[i,0]=0.
        • L[i,j] = L[i−1,j−1]+1 nếu Xi = Yj.
        • L[i,j] = max( L(i−1,j), L[i,j−1] ) nếu Xi≠Yj.
    • Cài đặt
      • Bảng phương án là một mảng 2 chiều L[0..m,0..n] để lưu các giá trị của hàm QHĐ L[i,j].
      • Đoạn chương trình cài đặt công thức QHĐ trên như sau:
        • for i:=0 to m do L[i,0]:=0; 
          
          for j:=0 to n do L[0,j]:=0; 
          
          
          for i:=1 to m do
          
              for j:=1 to n do
          
                     if X[i]=Y[j] then L[i,j]:=L[i–1,j–1]+1
          
                     else L[i,j]:=max(L[i–1,j],L[i,j–1]]);
    • Như vậy chi phí không gian của bài toán là O(n2), chi phí thời gian là O(n2). Có một phương pháp cài đặt tốt hơn, chỉ với chi phí không gian O(n) dựa trên nhận xét sau: để tính ô L[i,j] của bảng phương án, ta chỉ cần 3 ô L[i–1,j–1],L[i–1,j] và L[i,j–1]. Tức là để tính dòng L[i] thì chỉ cần dòng L[i–1]. Do đó ta chỉ cần 2 mảng 1 chiều để lưu dòng vừa tính (P) và dòng đang tính (L) mà thôi. Cách cài đặt mới như sau:
      • for j:=0 to n do P[j]:=0;
        
        for i:=1 to m do 
            begin
        
                  L[0] := 0;
        
                  for j:=1 to n do
        
                       if X[i]=Y[j] then L[i,j]:=P[j–1]+1
        
                            else L[i,j]:=max(P[j], L[j–1]); P := L;
        
            end;
  • Bắc cầu
    • Hai nước Anpha và Beta nằm ở hai bên bờ sông Omega, Anpha nằm ở bờ bắc và có M thành phố được đánh số từ 1 đến m, Beta nằm ở bờ nam và có N thành phố được đánh số từ 1 đến n (theo vị trí từ đông sang tây). Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu, hãy chỉ ra cách bắc cầu được nhiều cầu nhất.
    • Hướng dẫn: Gọi các thành phố của Anpha lần lượt là A1,A2,…Am; các thành phố của Beta là B1,B2,...Bn. Nếu thành phố  Ai và Bj kết nghĩa với nhau thì coi Ai "bằng”  Bj. Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố (Ai,Bj) để xây cầu thì cặp tiếp theo phải là cặp (Au,Bv) sao cho u>i và v>j. Như vậy các cặp thành phố được chọn xây cầu có thể coi là một dãy con chung của hai dãy A và B.
    • Bài toán của chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở  đây hai phần tử bằng” nhau nếu chúng có quan hệ kết nghĩa.
  • Palindrom (IOI 2000)
    • Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
    • Hướng dẫn: Bài toán này có một công thức QHĐ như sau:
      • Gọi L[i,j] là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng.
      • Đáp số của bài toán sẽ là L[1,n] với n là số kí tự của S. Ta có công thức sau để tính L[i,j]:
        • L(i,i)=0.
        • L(i,j)=L(i+1,j–1) nếu Si=Sj
        • L(i,j)=max(L(i+1,j), L(i,j–1))   nếu Si≠Sj
    • Bạn đọc dễ dàng có thể kiểm chứng công thức đó. Ta có thể cài đặt trực tiếp công thức đó bằng phương pháp đệ quy có nhớ. Tuy nhiên khi đó chi phí không gian là O(n2). Có một phương pháp cài đặt tiết kiệm hơn (bạn đọc có thể tham khảo ở bài báo trên của thầy Trần Đỗ Hùng), tuy nhiên phương pháp đó khá phức tạp.
    • Ta có thuật toán đơn giản hơn như sau:
      • Gọi P là xâu đảo của S và T là xâu con chung dài nhất của S và P. Khi đó các kí tự của S không thuộc T cũng là các kí tự cần thêm vào để S trở thành đối xứng. Đáp số của bài toán sẽ là n–k, với k là độ dài của T.
      • Ví dụ: S=edbabcd, xâu đảo của S là P=dcbabde. Xâu con chung dài nhất của S và P làT=dbabd. Như vậy cần thêm 2 kí tự là e c vào để S trở thành xâu đối xứng.

IV. Vali (A)

1. Mô hình

  • Cho n vật, vật i nặng Ai và có giá trị Bi. Hãy chọn ra một số vật để cho vào balô sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Chú ý rằng mỗi vật có thể được chọn nhiều lần.

2. Công thức

  • Gọi L(i,j) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào balô với tổng khối lượng không vượt quá j. L(n,W) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt quá W).
  • Công thức tính L(i,t) như sau:
    • L[i,0]=0;
    • L[0,j]=0.
    • L[i,j]=L[i-1,j] nếu t<Ai.
    • L[i,t]=max( L[i,j] ,  L[i-1,j–Ai ]+Bi) nếu t ≥Ai
  • Trong đó: L[i–1,j] là giá trị có được nếu không đưa vật i vào balô, L[i-1,j–Ai]+Bi  là giá trị có được nếu chọn vật i.

3. Cài đặt

  • Ta có thể dùng một mảng 2 chiều để lưu bảng phương án, tuy nhiên dựa trên nhận xét rằng để tính dòng i của bảng phương án chỉ cần dòng i–1, ta chỉ cần dùng 2 mảng một chiều P và L có chỉ số từ 0 đến m để lưu 2 dòng đó. Đoạn chương trình con tính bảng phương án như sau.
    • L[t] := 0; {với mọi t}
      for i := 1 to n do 
         begin
               P:=L;
               for t := 0 to m do
                   if t<a[i] then L[t]:=P[t]
                   else L[t] := max(P[t],P[t–a[i]]);
         end;
  • Nếu để ý kĩ bạn sẽ thấy rằng đoạn trình trên chỉ viết giống công thức QHĐ chứ chưa tối ưu. Chẳng hạn đã có lệnh gán P:=L, sau đó lại có gán L[t]:=P[t] với các giá trị t<a[i] là không cần thiết. Bạn đọc có thể tự cải tiến để chương trình tối ưu hơn.
  • Chi phí không gian của cách cài đặt trên là O(m) và chi phí thời gian là O(n.m).

4. Một số bài toán khác

  • Farmer (IOI 2004)
    • Một người có N mảnh đất và M dải đất. Các mảnh đất có thể coi là một tứ giác và các dải đất thì coi như một đường thẳng. Dọc theo các dải đất ông ta trồng các cây bách, dải đất thứ i có Ai cây bách. Ông ta cũng trồng các cây bách trên viền của các mảnh đất, mảnh đất thứ j có Bj cây bách. Cả ở trên các mảnh đất và dải đất, xen giữa 2 cây bách ông ta trồng một cây ôliu. Ông ta cho con trai được chọn các mảnh đất và dải đất tuỳ ý với điều kiện tổng số cây bách không vượt quá Q. Người con trai phải chọn thế nào để có nhiều cây ôliu (loài cây mà anh ta thích) nhất.
    • Hướng dẫn: Dễ thấy mảnh đất thứ i có Ai cây ôliu và dải đất thứ j có bj–1 cây ôliu. Coi các mảnh đất và dải đất là các “đồ vật”, đồ vật thứ k có khối lượng Wk  và giá trị Vk  (nếu k là mảnh đất i thì  Wk=Vk=Ai, nếu k là dải đất j thì Wk=Bj, Vk=bj –1). Ta cần chọn các “đồ vật”, sao cho tổng “khối lượng” của chúng không vượt Q và tổng “giá trị” là lớn nhất. Đây chính là bài toán xếp balô đã trình bày ở trên.
  • Đổi tiền
    • Ở đất nước Omega người ta chỉ tiêu tiền xu. Có N loại tiền xu, loại thứ i có mệnh giá là ai đồng. Một người khách du lịch đến Omega du lịch với số tiền M đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.
    • Hướng dẫn: Bài toán này khá giống bài toán xếp balô (“khối lượng” là mệnh giá, “giá trị” là 1), chỉ có một số thay đổi nhỏ: số đồng xu mỗi loại được chọn tuỳ ý (trong bài toán xếp balô mỗi đồ vật chỉ được chọn 1 lần) và tổng giá trị yêu cầu là nhỏ nhất.
    • Do đó ta cũng xây dựng hàm QHĐ một cách tương tự: Gọi L[i,t] là số đồng xu ít nhất nếu đổi t đồng ra i loại tiền xu (từ 1 đến i). Công thức tính L[i,t] như sau:
      • L[i,0]=0;
      • L[0,t]= ∞ với t>0.
      • L[i,t]=L[i–1,t] nếu t<Ai.
      • L[i,t]=min(L[i–1,t], L[i,t–Ai]+1) nếu t ≥Ai.
    • Công thức này khác công thức của bài xếp balô ở chỗ: dùng hàm min chứ không phải hàm max (vì cần tìm cách chọn ít hơn) và nếu chọn đồng xu thứ i thì L[i,t]=L[i,t–Ai]+1 (vì ta vẫn còn được chọn đồng xu thứ i đó nữa), khác với khi xếp balô là: nếu chọn đồ vật thứ i thì L[i,t]=L[i–1,t–Ai])+Bi vì đồ vật i chỉ được chọn một lần.

V. Nhân ma trận

1. Mô hình

  • Nhân một ma trận kích thước m×n với một ma trận n×p, số phép nhân phải thực hiện là m.n.p. Mặt khác phép nhân các ma trận có tính kết hợp, tức là: (A.B).C = A.(B.C) 
  • Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự tính sẽ quyết định số phép nhân cần thực hiện.
  • Cho N ma trận A1 ,A2 …AN , ma trận A có kích thước là di-1– ×di . Hãy xác định trình tự nhân ma trận A1.A2…AN sao cho số phép nhân cần thực hiện là ít nhất.

2. Công thức

  • Gọi F(i,j) là số phép nhân để tính tích các ma trận từ Aiđến Aj  (Ai.Ai+1....Aj).
    • F[i,i]=0.
    • F[i,i+1]=di-1 x dx di+1
    • F[i,j] = min(F[i,k]+F[k+1,j] + di-1 x dx di+1 với k=i+1,i+2,...,j–1
  • Công thức hơi phức tạp nên tôi xin giải thích như sau:
    • F[i,i]=0 là hiển nhiên.
    • F[i,i+1] là số phép nhân khi nhân Ai và Ai+1 . Ai có kích thước di-1 x di ,Ai+1  có kích thước di×di+1, do đó F[i,i+1]=di-1 x dx di+1
    • Với j>i+1 thì ta thấy có thể tính Ai.Ai+1....Aj bằng cách chọn một vị trí k nào đó để đặt ngoặc theo trình tự: Ai.Ai+1....Aj  = (Ai..Ak).(Ak+1..Aj)
  •  Ma trận kết quả của phép nhân (Ai ..Ak ) có kích thước di-1  ×di , ma trận kết quả của phép nhân (Ak+1..Aj) có kích thước dk×dj. Với cách đặt đó ta sẽ mất F[i,k] phép nhân để có kết quả trong dấu ngoặc thứ nhất, mất thêm F[k+1,j] phép nhân để có kết quả trong dấu ngoặc thứ hai, và cuối cùng mất di-1.dk.dj  để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt đó là: F[i,k]+F[k+1,j]+di-1xdk x dj

 

  • Ta chọn vị trí k cho số phép nhân ít nhất.

3. Cài đặt

  • Bảng phương án là một mảng 2 chiều F để lưu F[i,j]. Chú ý khi cài đặt là để tính được F(i,j), ta phải tính F[i,k] và F[k+1,j] trước. Phương pháp đơn giản để làm điều đó là phương pháp đệ quy có nhớ.
  • Tuy nhiên dựa vào nhận xét là trong công thức QHĐ: j–i lớn hơn k–i và j–k, ta có thể tính theo trình tự khác: tính các phần tử F[i,j] với j–i từ nhỏ đến lớn (không phải là tính các giá trị F[i,j] với i,j từ nhỏ đến lớn như vẫn làm). Với cách đó, khi tính đến F[i,j] thì ta đã có F[i,k] và F[k+1,j].
  • Đoạn chương trình tính bảng phương án như sau:
    • for i:=1 to n do F[i,i]:=0;
      
      for i:=1 to n–1 do F[i,i+1] := d[i–1]*d[i]*d[i+1];
      
      for m:=2 to n–1 do 
      
          begin 
      
               for i:=1 to n–m do 
      
                    begin
      
                          j:=i+m; 
                        
                          F[i,j]:=oo;
      
                          for k:=i+1 to j–1 do F[i,j]:=min(F[i,j], F[i,k]+F[k+1,j]+d[i–1]*d[k]*d[j]);
      
                    end;
      end;
  • Với cách cài đặt trên,chi phí không gian là O(n2), chi phí thời gian là O(n3) (đây là bài toán có chi phí lớn nhất trong tất cả các bài toán QHĐ thường gặp).

4. Một số bài toán khác

  • Chia đa giác
    • Cho một đa giác lồi N đỉnh. Bằng các đường chéo không cắt nhau, ta có thể chia đa giác thành N–2 tam giác. Hãy xác định cách chia có tổng các đường chéo ngắn nhất.
    • Hướng dẫn: Để đơn giản ta coi mọi đoạn thẳng nối 2 đỉnh đều là “đường chéo” (nếu nối 2 đỉnh trùng nhau hoặc 2 đỉnh liên tiếp thì có độ dài bằng 0).
    • Gọi F(i,j) là tổng độ dài các đường chéo khi chia đa giác gồm các đỉnh từ i đến j thành các tam giác. Nếu j<i+3 thì đa giác đó có ít hơn 4 đỉnh, không cần phải chia nên F(i,j)=0. Ngược lại ta xét cách chia đa giác đó bằng cách chọn một đỉnh k nằm giữa i,j và nối i,j với k. Khi đó F[i,j]=F[i,k]+F[k,j]+d[i,k]+d[k,j]; d(i,k) là độ dài đường chéo (i,k).
    • Tóm lại công thức QHĐ như sau:
      • F[i,j]=0 với j<i+3.
      • F[i,j]=min(F[i,k]+F[k,j]+d[i,k]+d[k,j] với k=i+1,...j–1). F[1,n)] là tổng đường chéo của cách chia tối ưu.
  • Biểu thức số học (IOI 1999)
    • Cho biểu thức A1•A2•…•AN, trong đó ai  là các số thực không âm và • là một phép toán + hoặc × cho trước. Hãy đặt các dấu ngoặc để biểu thức thu được có kết quả lớn nhất.
    • Hướng dẫn: Gọi F[i,j] là giá trị lớn nhất có thể có của biểu thức Ai•Ai+1•…•Aj. Dễ thấy nếu i=j thì F[i,j]=Ai, nếu j=i+1 thì F[i,j]=Ai•Aj. Nếu j>i+1 thì có thể tính biểu thức Ai•Ai+1•…•Aj  bằng cách chia thành 2 nhóm: (Ai•Ai+1•…•Ak)•(Ak+1•…•Aj), Khi đó F[i,j]=F[i,k]•F[k+1,j].
    • Tóm lại, công thức QHĐ là:
      • F[i,i]=Ai
      • F[i,i+1]=Ai•Ai+1
      • F[i,j]=max(F[i,k]•F[k+1,j] với k=i+1,i+2,..j–1).
    • (Chú là là các hạng tử của dãy đều không âm và các phép toán là + hoặc × nên F[i,k] và F[k+1,j] đạt max thì F[i,k]•F[k+1,j] cũng đạt max).

VI. Ghép cặp

1.Mô hình

  • Có n lọ hoa sắp thẳng hàng và k bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cằm k bó hoa trên vào n lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng khi cắm hoa i vào lọ thứ j là v(i,j)   Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được 1 bó hoa. (IOI –1999)

2. Công thức 

  • Nhận xét rằng bài toán nêu trên là một bài toán ghép cặp có yêu cầu về thứ tự nên ta có thể giải quyết bằng phương pháp QHĐ.
  • Hàm mục tiêu : f: tổng giá trị thẩm mỹ của cách cắm.
  • Giá trị thẩm mỹ phụ thuộc vào các hoa và các lọ đang được xét nên ta sẽ dùng mảng 2 chiều để lưu bảng phương án.
  • L(i,j): tổng giá trị thẩm mỹ lớn nhất khi xét đến hoa i và lọ j. Khi tính L(i,j) hoa đang xét sẽ là hoa i và lọ j.
    • Nếu i = j. Chỉ có một cách cắm L[i,i]:= V[1,1]+V[2,2]+...V[i,i]
    • Nếu i>j . Không có cách cắm hợp lý
    • Nếu i<j : Có 2 trường hợp xảy ra:
  • Cắm hoa i vào lọ j. Tổng giá trị thẩm mỹ là L[i-1,j-1]+V(i,j). (Bằng tổng giá trị trước khi cắm cộng với giá trị thẩm mỹ khi cắm hoa i vào lọ j)
  • Không cắm hoa i vào lọ j (có thể cắm vào lọ trước j), giá trị thẫm mỹ của cách cắm là như cũ : L[i,j-1]

3. Cài đặt :

  • L[i,j]:= -maxint;
    
    For i:=1 to k do
    
        For j:=i to n do
    
             If i = j then L[i,j]:=sum(i)
    
             else if i<j then L[i,j]:=max(L[i-1,j-1]+v[i,j],L[i,j-1]);

 

4. Một số bài toán khác

  • Câu lạc bộ:( Đề thi chọn HSG Tin Hà Nội năm 2000)
    • Có n phòng học chuyên đề và k nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp k nhóm trên vào n phòng học sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ, nhóm có số hiệu lớn phải được xếp vào phòng có số hiệu lớn.Với mỗi phòng có chứ học sinh, các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì lấy vào cho đủ ghế .Biết phòng i có Ai ghế ,nhóm j có Bj học sinh. Hãy chọn 1 phương án bố trí sao cho tổng số lần chuyển ghế ra và vào là ít nhất.
    • Hướng dẫn : Khi xếp nhóm i vào phòng j thì số lần chuyển ghế chính là độ chênh lệch giữa số ghế trong phòng i và số học sinh trong nhóm. Đặt V[i,j]:=|Ai-Bj|
  • Mua giày (Đề QG bảng B năm 2003)
    • Trong hiệu có n đôi giày, đôi giày i có kích thước HI. Có k người cần mua giày, người i cần mua đôi giày kích thước Si . Khi người i chọn mua đôi giày j thì độ lệch sẽ là |hI-sJ|. Hãy tìm cách chọn mua giày cho k người trên sao cho tổng độ lệch là ít nhất. Biết rằng mỗi người chỉ mua 1 đôi giày và 1 đôi giày cũng chỉ có một người mua.
    • Hướng dẫn : Lập công thức giải như bài Câu lạc bộ. Chú ý chứng minh tính đúng đắn của bổ đề heuristic sau :Cho 2 dãy tăng dần các số dương A1A2...AN  , B1B2...BN. Gọi C1C2....CN là một hoán vị  của dãy {BN}. Khi đó :   |A1-B1|+ |A2-B2|+...+ |AN-BN| < |A1-C1+   |A2- C2|+...+ |AN-CN|

VII. Di chuyển

1. Mô hình

  • Cho bảng A gồm MxN ô. Từ ô (i,j) có thể di chuyển sang 3 ô (i+1,j), (i+1,j–1) và (i+1,j+1). Hãy xác định một lộ trình đi từ hàng 1 đến hàng M sao cho tổng các ô đi qua là lớn nhất.

2. Công thức

  • Gọi F(i,j) là giá trị lớn nhất có được khi di chuyển đến ô (i,j). Có 3 ô có thể đi đến ô (i,j) là (i–1,j), (i–1,j–1) và (i–1,j+1). Do đó ta có công thức QHĐ như sau:
    • F[1,j]=A[1,j]
    • F[i,j]=max(F[i–1,j],F([i–1,j–1],F[i–1,j+1])+A[i,j] với i>1

3. Cài đặt

  • Bảng phương án là bảng 2 chiều F[0..m,0..n]. (Tất cả các ô trên biên đều cho giá trị bằng 0).
  • Quá trình tính như sau:
    • for i:=1 to m do
      
           for j := 1 to n do
      
                F[i,j]=max[F[i–1,j],F[i–1,j–1],F[i–1,j+1]]+A[i,j];
  • Cách cài đặt này cho chi phí không gian và thời gian đều là O(n2). Ta có thể tiết kiệm không gian nhớ bằng cách tính trực tiếp trên mảng A.

4. Một số bài toán khác

  •  Tam giác (IOI 1994)
    • Cho một tam giác gồm các số nguyên không âm. Hãy tính tổng lớn nhất các số trên đường đi từ đỉnh tam giác xuống một điểm nào đó ở đáy tam giác nào đó. Tại mỗi ô ta chỉ có đi thẳng xuống, sang ô bên trái hoặc bên phải.
    • Hướng dẫn: Mô tả các phần tử của tam giác số như một ma trận, A[i,j] là phần tử thứ j trên dòng i (với 1≤i≤N và 1≤j≤i). Có 2 ô có thể di chưyển đến ô (i,j) là ô (i–1,j–1) và ô (i–1,j). Gọi F(i,j) là tổng lớn nhất có thể có khi đi đến ô (i,j) ta có:
      • F[1,1]=A[1,1]
      • F[i,1]=F[i–1,1]+A[i,1]
      • F[i,j]=max( F[i–1,j–1],F[i–1,j] ) + A[i,j]
  • Con kiến
    • Có một ống hình trụ, khi trải phẳng ra có thể là một bảng MxN ô. Giá trị A[i,j] là lượng thức ăn có ở ô ở dòng i cột j. Một con kiến xuất phát từ một ô ở mép bên trái của hình trụ và bò sang mép bên phải. Từ ô (i,j) kiến có thể bò sang 1 trong 3 ô (i–1,j+1), (i,j+1) hoặc (i+1,j+1). (Chú ý: vì ống hình trụ nên kiến đang ở dòng 1 có thể bò xuống dòng M và ngược lại). Bò qua ô nào thì kiến mang theo toàn bộ lượng thức ăn ở ô đó. Hãy tìm đường đi mà kiến kiếm được nhiều thức ăn nhất.
  • Hướng dẫn: Để xử lí tình huống hình trụ, ta lưu dòng 0 là dòng M và dòng M+1 là dòng 1. Khi đó tương tự như bài toán ban đầu, gọi F(i,j) là lượng thức ăn kiến có được khi bò đến ô (i,j), ta thiết lập được công thức QHĐ sau:
    • F[i,1]=A[i,1]
    • F[i,j]=max( F[i–1,j–1],F[i,j–1],F[i+1,j+1] )+A[i,j] với j>1

Xem bài viết trên trang web của khanhptnk

Biển học là vô bờ. Hai chữ "vô bờ" bản thân nó vốn ám chỉ rằng không có đích đến rồi. Bạn rong ruổi trên một con tàu theo năm tháng trên đại dượng tri thức. Vậy thì ý nghĩa của một cuộc sống như vậy nằm ở đâu? Là vẻ đẹp của những hòn đảo bạn ghé thăm, những trải nghiệm về phong ba bão táp của đại dương, những cuộc gặp gỡ duyên phận với những con tàu khác, những cuộc đua và những khi tản mạn.

Năm 2007, tôi nộp đơn thi vào trường Phổ Thông Năng Khiếu-Đại học quốc gia thành phố Hồ Chí Minh. Tôi không hề biết gì về trường này trước đó, chỉ biết rằng học sinh trường này ắt hẳn phải là siêu nhân sau khi tôi xem qua đề tuyển sinh môn toán. Tôi lúc ấy cũng đang học chuyên môn toán. Tôi không biết gì về lập trình dù đã được học được hơn tháng về Pascal (người dạy tôi khi ấy chỉ chép lên bảng code từ sách ra, bảo tôi gõ lại và không giảng gì thêm). Tôi nộp đơn vào lớp chuyên toán của PTNK. Kết qủa là tôi thiếu 0.25 điểm để đậu vào lớp chuyên toán. May mắn thay lớp chuyên Tin của trường vẫn lấy một nửa chỉ tiêu từ số học sinh có nguyện vọng vào lớp toán. Tôi đủ điểm để vào chuyên Tin nhưng tôi cảm thấy rất lo: xa nhà, học ở một trường qúa sức, chuyên một môn học bí ẩn. Tôi nói: "Con không học chuyên Tin đâu!". Nhưng rồi tôi cũng đi. Mẹ tôi khóc nhiều. Ba tôi chạy khắp nơi để lo chỗ ở, xe cộ, chỗ ăn uống cho tôi ở một thành phố lớn, nhưng lạ. 

Ngày đầu tiên tôi bước vào lớp, tôi bị sốc. Bạn tôi đố nhau về toán học và tin học. Đi đâu tôi cũng nghe cái từ "lệ quy". Bài nào cũng giải được bằng "lệ quy". Tôi thấy cái từ này sao nó hay, nó đẹp thế. Mãi sau này tôi mới biết là tôi nghe nhầm từ "đệ quy". 

Trường chúng tôi năm ấy nhập học sớm, lớp tôi được học thêm một vài tuần về toán rời rạc trước khi vào chương trình của năm học. Vài tuần đầu, chúng tôi được học cơ bản về ngôn ngữ Pascal: dùng vòng lặp for để vẽ sao. Rồi tiếp theo là vẽ những hình phức tạp hơn, buộc tôi phải học “đệ quy” và "vòng lặp" mới giải được. Vòng lặp và đệ quy, hai khái niệm rất khó nuốt cho một học sinh chuyên toán như tôi. Dẫu rằng trong toán học vẫn có những công thức truy hồi nhưng tôi thường nghĩ về chúng như một công thức toán hoặc một hàm số, tức là ta cứ thế số vào, trải qua một số công đoạn tính nhất định để ra kết quả. Vòng lặp lại khác, ta làm đi làm lại cùng một thứ, nhưng kết quả của ta biến đổi dần dần rồi đi đến giá trị cuối cùng khi vòng lặp kết thúc. Trong cách hiểu về Toán học của tôi, tôi quan tâm đến bên trong hàm của tôi bao gồm những phép tính gì (cộng trừ nhân chia ra sao), nhưng trong tư duy Tin học mới, tôi có thể xem hàm của tôi như những chiếc hộp đen. Tôi quan tâm nhiều hơn về thứ nó nhận vào (input) và thứ nó trả ra (output). Hãy lấy dãy Fibonacci làm ví dụ:

1, 1, 2, 3, 5, 8, …

Giá trị của một số bằng tổng của hai số liền trước nó trừ hai số đầu. Ta tạm gọi Fn là sô Fibonacci thứ n. Tôi rất muốn tính nhanh giá trị của số này.

Trong toán học phổ thông mà tôi được học, tôi sẽ cố gắng tìm ra một công thức tổng quát cho số Fibonacci thứ N:

Mục đích của điều này là để giảm thiểu số phép tính. Ví dụ tôi muốn tính số thứ 1000 của dãy trên, việc thay giá trị n = 1000 và công thức tổng quát trên của dãy sẽ nhanh hơn việc áp dụng số công thức truy hồi:

Fn = Fn - 1 + Fn - 2

và tính ra 999 số trước đó! 1, 1, 2, 3, 5, 8, 13, 21, 34, ... (tính tay thì rất là mệt!)

Khi tôi học toán ở cấp hai, nhìn vào công thức tổng quát của số Fibinacci tôi chỉ thấy một phép trừ, một phép chia, vài phép căn bậc hai và lũy thừa. Tôi trông cậy vào máy tính cầm tay để thực hiện những phép tính đó. Nhưng tôi không để ý rằng thực hiện phép căn bậc hai khó hơn rất nhiều so với phép trừ. “Khó” ở đây không những là về thời gian mà còn về độ chính xác. Giá trị của căn bậc hai của 5 mà máy tính cầm tay hiển thị ra luôn chứa sai số vì chúng ta đều biết rằng đây là một số vô tỉ trong khi độ dài màn hình máy tính thì hữu hạn. Trong công thức tổng quát trên còn chứa nhiều phép tính phức tạp như phép lũy thừa một số thập phân chẳng hạn. Thực tế rất ít người sử dụng công thức ấy vì nó luôn cho sai số. Hãy dùng số nguyên khi còn có thể!

Ngược lại, trong công thức truy hồi, tôi chỉ thấy một phép cộng đơn giản. Tôi gõ ra một hàm số nhận input là hai số nguyên và trả output là tổng của hai số đó. Tôi lại tiếp tục nâng cấp hàm số đó lên thành một quy trình như sau: tôi loại số nhỏ hơn trong input ra khỏi hàm số và thay nó bằng output tôi vừa nhận được. Tôi có một bộ input mới, và từ đó lại tính ra một output mới. Khi tôi chạy quy trình đó, bạn đầu tôi cho vào hai số (1, 1). Tôi lặp lại quy trình nhiều lần (bao nhiêu lần đố bạn?) cho đến khi tôi nhận được số Fibonacci thứ N. Nói cách khác, tôi đang sử dụng một vòng lặp:

F0 = 1

F1 = 1

For n = 2 to 1000:

      Fn = Fn - 1 + Fn - 2

Hãy nhớ lại vì sao tôi lại không dùng công thức này ngay từ đầu? Vì muốn tính số thứ 1000 tôi phải tính tay ra 999 số trước đó. Đấy là khi tôi chưa biết lập trình. Khi tôi biết lập trình, tôi ở trong một tình huống khác hẳn. Tôi chỉ cần gõ một vòng lặp, và gõ một lần duy nhất. Máy tính sẽ giúp tôi thực hiện phần tính toán. Bạn có thấy điều khác biệt không? Lần trước công sức tôi bỏ ra là phải ngồi tính tay 1000 giá trị nhưng bây giờ thì chỉ việc ngồi gõ ra một công thức trừu tượng và để máy tính thực hiện phần tính toán với giá trị cụ thể. Điều này đảo ngược lựa chọn của tôi như thế nào? Giờ tôi sẽ thích công thức truy hồi hơn vì nó ngắn hơn để gõ so với công thức tổng quát.

Máy tính làm tốt những việc con người làm không tốt, và ngược lại. Con người có thể làm những việc phức tạp nhưng ở tốc độ thấp; còn máy tính lại có thể làm những việc đơn giản nhưng ở tốc độ cao và có thể lặp lại nhiều lần mà không biết chán. Học thuật toán tức là kết hợp sự sắp đặt khéo léo của con người với tốc độ và sự bền bỉ của máy tính. Học thuật toán không phải là học ngôn ngữ lập trình, không phải là học Pascal, học C, học Java. Học thuật toán tức là nghĩ về quá trình chuyển động, sự thay đổi trạng thái của các thành phần trong suốt một quá trình, bản chất cũng giống y như học Vật lý, Sinh học, Hóa học vậy. Ngôn ngữ lập trình chỉ là phụ trợ. Tôi viết vòng lặp ở trên không phải theo một ngôn ngữ lập trình nào cả. Bạn có thể tạo ra một ngôn ngữ lập trình mang tên bạn. Bạn cũng có thể làm nó chạy được vòng lặp tôi viết ở trên.

Quay lại vấn đề, tại sao tôi lại nói vòng lặp là một trong những khái niệm quan trọng nhất. Có hai lý do. Thứ nhất là tôi cảm thấy tư duy của Tin học, của lập trình, tinh túy nhất ở những thuật toán mà ta chỉ thấy có một quá trình được lặp đi lặp lại mãi, và bất ngờ cuối cùng chúng ta lại được kết quả nhưng mong muốn. Thuật toán Euclid tìm ước chung lớn nhất của hai số, thuật toán chia nhị phân tìm giá trị nhỏ nhất của một hàm số lồi là một số ví dụ. Thực tế thì khá khó tìm được một thuật toán mà không có vòng lặp. Bạn có thể tưởng tượng sự vận hành của thuật toán như một ván cờ: bàn cờ là một thứ cố định và các quân cờ sẽ di chuyển, số lượng quân cờ sẽ ít dần đi theo thời gian đến khi đạt được trạng thái kết thúc là chiếu bí. Lý do thứ hai, việc lặp một quá trình như trong vòng lặp mở ra một lối tư duy mới trong việc giải quyết một vấn đề. Không nhất thiết rằng bạn phải ngay tính ra kết quả của bài toán ngay lập tức. Bạn thử tính lần thứ nhất, đáp số có thể sai, nhưng lặp lại dần thì kết quả sẽ đi gần hơn đến đáp án. Đầu óc bạn sẽ phải làm quen với những thứ trừu tượng có giá trị luôn luôn thay đổi (biến số), và bạn phải nhẩm lấy sự vận động của chúng. Cũng cùng là một dòng lệnh đó nhưng vỡi những giá trị khác nhau sẽ tạo ra những kết quả khác nhau.  

Lúc mới học tin, tôi thấy hứng thú với lối tư duy mới này. Tôi thấy nó giúp tôi tiếp cận gần hơn với những gì đang xảy ra trong cuộc sống. Nếu như lúc trước tôi chỉ biết bấm máy tính thì bây giờ tôi đã biết quan tâm xem nó thực hiện những phép tính thế nào. Hiểu thêm về thế giới xung quanh làm tôi thấy hạnh phúc. Mọi môn học khác đều có cái hay của nó và đều có thể dẫn tôi đến cái cảm giác đó nhưng tôi đến với Tin học là một cái duyên. Vì thế khi bảo tôi nói ra lý do cần phải học Tin học, tôi không nghĩ ra lý do nào. Một ngày nọ tôi ăn được một món ngon, thế là tôi là về quyết định học cách nấu món đó. Chỉ vậy thôi.

Cách đặt câu hỏi thông minh

    Khi đọc post của các bạn, mình cảm thấy cách 1 số bạn đặt câu hỏi trên diễn đàn hiện nay chưa hợp lý, làm cho người đọc rất khó để trả lời cho bạn, mình xin phép viết một chút về vấn đề này, đây hoàn toàn là những kinh nghiệm được đúc kết từ cá nhân do đó còn nhiều sai sót và rất mong nhận được sự góp ý từ các bạn.

“Sự thông minh của Bạn không hẳn ở chỗ trả lời được các câu hỏi mà thể hiện ở cách Bạn biết đặt ra những câu hỏi hay”

 

1> Sự quan trọng của cách đặt câu hỏi

    Câu hỏi được các bạn đặt ra và gửi lên diễn đàn với mục đích được người khác đọc, thảo luận và trả lời giúp bạn. Trong tường hợp xấu nhất là câu hỏi của bạn lửng lơ trên diễn đàn cả tuần mà không có một ai trả lời khúc mắc của bạn. Nguyên nhân thì có nhiều nguyên nhân từ khách quan cho đến chủ quan. Nhưng một trong những nguyên nhân khó tin những lại là một vấn đề nan giải đó là “Người đọc nhìn thấy cách hỏi của bạn đã không muốn đọc chứ chả nói là muốn trả lời giúp bạn”.

    Việc các bạn đặt câu hỏi “ngây thơ”, thiếu kinh nghiệm sẽ khiến cho người đọc cảm thấy khó chịu và không muốn trả lời. Những câu hỏi như thế nào là ngây thơ và thiếu kinh nghiệm? Đó là những câu hỏi mà bạn không tìm tòi kỹ lưỡng trước khi hỏi, ỷ lại và quyền được hỏi mà cứ hỏi đại, hỏi bừa mong được sự giúp đỡ. Kiểu này gọi là “Há miệng chờ sung”. Đây là kiểu chuyển giao toàn bộ trách nhiệm của người hỏi sang người trả lời. Ví dụ như

  • “Tại sao mình lại TLE nhỉ?” (Không đưa ra code của bạn thì sao mọi người biết bạn làm như thế nào mà TLE?),
  • “Bài này sol như thế nào nhỉ ?” (Bạn đã tìm hiểu kỹ lưỡng trước khi hỏi chưa? )

    Do đó việc gây ấn tượng tốt cho người đọc là việc tối quan trọng trong việc đặt câu hỏi. Vậy làm sao để đặt một câu hỏi hữu ích, gây thiện cảm cho người đọc, hãy theo dõi ở các phần ngay dưới đây.

2> Cách đặt câu hỏi hữu ích

Phần này gồm 2 phần con, trước khi đặt câu hỏi và cách đặt câu hỏi.

2.1> Trước khi đặt câu hỏi

    Việc trước tiên bạn cần làm trước khi hỏi đó là tìm hiểu và đào sâu tư duy về vấn đề cần hỏi để tránh được những câu hỏi thừa thãi, tốn thời gian của cả người hỏi lẫn trả lời. Cách tốt nhất để học đó là tự đưa ra câu hỏi cho bản thân mình và trả lời. Khi không thể tự trả lời được thì mới đặt câu hỏi nhằm kêu gọi sự giúp đỡ từ người khác.

2.2> Câu hỏi thông minh

  • Hỏi đúng chỗ: Câu hỏi của bạn phải được hỏi đúng vị trí mà nó thuộc về. Ví dụ như hỏi về thuật toán thì phải post trong mục “Thuật toán” chứ không thể post trong mục “Đóng góp ý kiến cho VNOI” được.

  • Không lặp lại câu hỏi: Những câu hỏi đã hỏi rồi thì không được hỏi lại, không được lập nhiều topic cho cùng một nội dung câu hỏi.

  • Tiêu đề mạch lạc rõ ràng: Tiêu đề là thứ đầu tiên mà người đọc nhìn vào, do đó tiêu đề mạch lạc rõ ràng sẽ tạo thiện cảm cho người trả lời.

  • Ngôn ngữ rõ ràng, mạch lạc: Viết tiếng Việt có dấu, trình bày gọn gàng khoa học.

  • Mô tả vấn đề đầy đủ thông tin: Cần mô tả thông tin một cách ngắn gọn súc tích mà vẫn đầy đủ thông tin.

    • Nói rõ về vấn đề bạn gặp phải

    • Trình bày tóm tắt sự cố gắng của bạn trong việc giải quyết vấn đề. Nhiều người khá ngại việc đọc code của người khác, do đó việc trình bày ngắn gọn thuật toán của bạn sẽ giúp ích cho người trả lời.

    • Cung cấp thông tin cho người đọc. Ví dụ như code của bạn.

  • Nói rõ mục đích hỏi: Hỏi về độ phức tạp, thuật toán, hay nhờ sửa code…

  • Không dùng các câu hỏi vu vơ không rõ mục đích: Kiểu như “bài này làm thế nào nhỉ”, “ai giúp mình bài này đi”, “ahihi bài này khó quá, chả biết làm sao, săm ba đi hép mi”...

  • Hành văn một cách lịch sự: Vì bạn là người cần sự trợ giúp, do đó phép lịch sự là điều cần thiết để giúp người đọc muốn giúp đỡ bạn hơn.

2.3> Ví dụ về câu hỏi thông minh

  • “Các bạn ơi bài này mình quy hoach động thử nhưng vẫn chỉ có 10đ, ai vào xem giúp mình với?”

    • Đây là một câu hỏi mà không hề được chuẩn bị trước, cũng như không có bất kỳ một sự cố gắng hay nỗ lực tìm câu trả lời của người hỏi. Do đó việc topic này bị “quả bơ” cả một năm trời là điều dễ hiểu

  • “Các bạn ơi, bài này mình đã thử cách làm quy hoạch động. Cách làm của mình như sau (nêu vắn tắt cách làm). Mình đã submit và nhận được kết quả WA. Mình đã test với dữ liệu lớn và nhỏ. Mình nghi ngờ phần công thức có vấn đề. Các bạn có thể xem giúp mình không. Đây là link code của mình (Chèn code ở dưới)”

    • Theo mình đây là một câu hỏi thông minh, viết bằng tiếng Việt có dấu, giọng điệu nhẹ nhàng, cung cấp đầy đủ thông tin thu hút người đọc cũng như đã có nỗ lực tìm lời giải đáp.

3> Tổng kết

    Qua bài viết ngắn ngủi của mình, mình hi vọng sẽ giúp các bạn phần nào đấy có thể đặt được các câu hỏi hữu ích hơn. Một phần giúp các bạn có thể có câu trả lời hiệu quả trong thời gian ngắn nhất cũng như giúp diễn đàn VNOI có những topic thảo luận có giá trị.

P/s: Cảm ơn anh Trung và anh Khánh đã giúp em hoàn thiện bài viết này.

                                                                                                                                                  Lê Hồng Quang

 

Một số tài liệu hay về thuật toán

1. Giải thuật và lập trình - thầy Lê Minh Hoàng
Chắc hẳn những bạn học chuyên tin đều biết đến cuốn sách này, bởi nó như là một cuốn sách giáo khoa cho chuyên tin với các kiến thức cơ bản từ quay lui, sắp xếp đến quy hoạch động, đồ thị.
Link Download: https://www.dropbox.com/s/e7buuj7qt0lg0r1/Thuat%20toan%20-%20Le%20Minh%20Hoang.pdf?dl=0

2. Tài liệu giáo khoa chuyên tin
Về cơ bản, phần một và phần hai giống với giải thuật và lập trình, tuy nhiên được bổ sung thêm một số kiến thức như: số Catalan, xử lý số lớn bằng xâu,... Kèm theo đó là những bài tập vô cùng hấp dẫn để các bạn luyện tập.
Phần ba chứa các kiến thức nâng cao hơn, đó là hình học và lý thuyết trò chơi.
Link Download:
Tập 1: https://www.dropbox.com/s/5q75x48fjinp3i2/Tai_lieu_giao_khoa_chuyen_tin_1.pdf?dl=0
Tập 2: https://www.dropbox.com/s/rbipskk2fk6y98q/Tai_lieu_giao_khoa_chuyen_tin_2.pdf?dl=0
Tập 3 - phần1: https://www.dropbox.com/s/wie005d42ae7qi2/Chuyen%20tin%203%20-%20Tap%201.pdf?dl=0
Tập 3 - phần 2: https://www.dropbox.com/s/6qqd61ii3858b7p/Chuyen%20tin%203%20-%20Tap%202.pdf?dl=0

3. KC-BOOK
Đây là một cuốn sách cực kỳ hay về Quy hoạch động. Bạn có thể luyện tập hơn 40 bài quy hoạch động ( có gợi ý lời giải ) để có phản xạ tư duy mỗi khi gặp các bài QHĐ. Ngoài ra sách còn một số bài tập và gợi ý các dạng bài: duyệt, xử lý bit và phân đôi tập hợp
Link Download: https://www.dropbox.com/s/gxs9w2ladktqksx/KC-BOOK.pdf?dl=0

4. Một số vấn đề đáng chú ý trong môn tin học
Cuốn sách này được viết bởi các cựu học sinh trường chuyên Phan Bội Châu - Nghệ An. Nó chứa các kiến thức tuyệt hay mà tài liệu giáo khoa chuyên tin hay giải thuật và lập trình đều không có như: duyệt ưu tiên, thuật toán tìm kiếm chuỗi KMP, quy hoạch động trạng thái, quy hoạch động vị trí cấu hình, quy hoạch động trên cây, tô màu đồ thị, thuật toán Dijkstra với đỉnh ảo, Interval Tree, Binary Index Tree, ...
Link Download: https://www.dropbox.com/s/as1yujdy5ewufke/Mot%20so%20van%20de%20dang%20chu%20y.PDF?dl=0

5. DP-SpeedUp - admin Ngô Minh Đức
Cuốn sách giới thiệu về phương pháp giảm độ phức tạp cho một số bài Quy hoạch động ( chú ý được viết bằng tiếng Anh )
Link Download: https://www.dropbox.com/s/7riqokgn9ceqpi6/DpSpeedup.pdf?dl=0

6. LCA - bangcht
Giới thiệu về thuật toán LCA
Link Download: https://www.dropbox.com/s/5dqgf6dtnawdehc/LCA_bangcht_doc.pdf?dl=0

7. Hash - Lê Khắc Minh Tuệ
Giới thiệu về thuật toán Hash. ( đã được bạn only_love97 up lên thư viện )
Link Download: https://www.dropbox.com/s/7joccxnc0pyzyeo/Hash.pdf?dl=0

8. KC-BOOK3

Link download: http://www.mediafire.com/download/x0kwqv8sv7xxhpg/252136344-KCBOOK3.pdf