Minh Vu

 I should have put some dummy text for this post. Please go to  https://dminhvu.github.io , this is my main personal page from now on!

Given a 2D matrix, find the maximum sum of a rectangular submatrix in it.  For example, the maximum sum of the matrix is shown below. And the total value of this maximum submatrix is 15. As far as we know, Kadane's algorithm is used for finding the maximum subarray in a 1D array in O(n) time complexity: From the beginning, start to accumulate every element it goes through. If at a time, the sum is negative, we will reset the sum to 0, because it is always more beneficial to start from 0 rather than a negative value. I made the gif below to make it easier to understand this approach. The idea for solving the 2D array is similar: We will fix the two columns of the matrix - the left and the right - one by one. Then, we would consider every row of the matrix (lying between two columns) to be an element in a 1D array and apply Kadane's algorithm to this array. In other words, we will fix two columns i and j. Let's call b[k] = sum(a[k][i], a[k][i + 1], ..., a[k][j]), we can calcu...

  Madrid, Spain

  Paris - France Taken from someone on the Internet. Let me give a thank to you!

Link:  https://codeforces.com/group/FLVn1Sc504/contest/274518/problem/W Tags: dp, dijkstra, shortest path Difficulty: ez++ Tóm tắt: Cho đồ thị gồm n đỉnh đánh số từ 1 đến n. Cần tìm tổng số đường đi ngắn nhất từ 1 đến n. Ý tưởng: Sử dụng thuật toán dijkstra tìm đường đi ngắn nhất như bình thường, tuy nhiên ta đặt thêm mảng dp[i] với ý nghĩa dp[i] là số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i. Ta vừa dijkstra vừa update như sau: Giả sử ta đang ở đỉnh u và đỉnh tiếp theo là v, và trọng số cạnh giữa u và v là w: Nếu dist[v] > dist[u] + w thì dist[v] = dist[u] + w và dp[v] = dp[u] Nếu dist[v] == dist[u] + w thì dp[v] += dp[u] Khởi tạo dp[1] = 1 vì luôn có 1 đường đi từ đỉnh 1 đến chính nó. Code:  https://ideone.com/XxdyLB

 

★ Link:  https://codeforces.com/group/FLVn1Sc504/contest/274506/problem/M ★ Difficulty: ezpz ★ Tags: deque ★ Kiến thức: https://vnoi.info/wiki/algo/data-structures/deque-min-max.md ★ Tóm tắt: Cho dãy a[] gồm n phần tử và số k. Với mỗi vị trí i từ 1 đến n - k + 1, hãy tìm min(a[i], ..., a[i+k-1]). ★ Ý tưởng: sử dụng deque tịnh tiến và CTDL deque.  Đầu tiên ta vẫn tìm vị trí xa nhất về bên phải đối với phần tử i (gọi là r[i]) sao cho a[i] = min(a[i], ...a[r[i]]). Sau đó vừa duyệt i vừa dùng cấu trúc dữ liệu deque (tương tự vector nhưng có khả năng bỏ phần từ vào trước (front) hoặc sau (back) đều được) để bỏ phần tử chứ i vào phía trước deque. Phần tử ở cuối deque (gọi là j) sẽ là đáp án của vị trí i nếu thoả cả 3 điều kiện sau: a[j]<=a[i] (a[j] vẫn là min trong đoạn chứ [j...i]. r[j]>=i (vì phần tử xa nhất về bên phải của j sao cho a[j] = min(a[j],...,a[r[j]]) vẫn chứa được i, khi đó phần tử i vẫn nằm trong đoạn từ [j...r[j]]). j>=i-k+1 (để thoả điều kiện k phần tử liên...

★ Link:  https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/M ★ Difficulty: ezpz ★ Tags: deque ★ Kiến thức:  https://vnoi.info/wiki/algo/data-structures/deque-min-max.md ★ Tóm tắt: Cho dãy số a[] với n phần tử. Ta cần tìm giá trị k = a[i] * (ri - li + 1) là lớn nhất với a[i] = min(a[li], a[li+1],.., a[ri]). Nói cách khác a[i] là phần tử nhỏ nhất trong đoạn a[li...ri]. ★ Ý tưởng: sử dụng deque cơ bản. Gọi L[i] là vị trí xa nhất về bên trái đối với phần từ a[i] thoả điều kiện a[L[i]...i-1] đều lớn hơn hoặc bằng a[i]. Gọi R[i] là vị trí xa nhất về bên phải đối với phần tử a[i] thoả điều kiện a[i+1...R[i]] đều lớn hơn hoặc bằng a[i]. Để tìm các vị trí L[i] và R[i] như trên ta sẽ dùng deque. Các bạn xem code và đọc tài liệu bên trên sẽ rõ. ★ Code:  https://ideone.com/bsCxZe

★ Link: https://codeforces.com/contest/1245/problem/D ★ Tags: dsu (disjoint set union), mst (minimum spanning tree) ★ Difficulty: 1900 ★ Kiến thức:  https://vnoi.info/wiki/algo/data-structures/disjoint-set.md ★ Tóm tắt: Cho n thành phố, mỗi thành phố có một toạ độ (xi, yi) tương ứng. Cần làm cho tất cả các thành phố đều có điện sao cho chi phí là nhỏ nhất, biết rằng: Chi phí xây dựng trạm điện ở thành phố i là ci; Chi phí nối dây điện giữa 2 thành phố i và j là (|xi - xj| + |yi - yj|) * (ki + kj); ★ Ý tưởng: Sử dụng dsu để dựng cây khung nhỏ nhất. Bài này ta sẽ phải sử dụng thêm một trick đó là tạo cạnh nối một đỉnh ảo với tất cả các đỉnh i khác, và cạnh này có trọng số là ci. Còn lại với mỗi đỉnh i và j thì tạo cạnh giữa đỉnh i và đỉnh j với trọng số (|xi - xj| + |yi - yj|) * (ki + kj) như trên. ★ Code:  https://ideone.com/lNDgEc

1. Problem 8.02: Code:  https://pastebin.com/rpp0ceCx 2. Problem 8.03: Code:  https://pastebin.com/Fg449M6J 3. Problem 8.04: 4. Problem 8.05: 5. Problem ngày lễ: Code:  https://ideone.com/hL2o8r 6. Problem 8.06: Code:  https://pastebin.com/EMbm3C9A 7. Problem 8.08: Code:  https://pastebin.com/wjyDYEps 8. Problem 8.09: Code:  https://pastebin.com/mTpN6ApS 9. Problem 8.10: Code:  https://pastebin.com/vDbhjbuf

★ Today's tune:  https://youtu.be/Oj18EikZMuU ★ Link:  https://codeforces.com/contest/1415/problem/C ★ Tags: dp ★ Difficulty: 1400 ★ Ý tưởng: Bài này thuần dp. Công thức quy hoạch động như sau: Khi đang ở một vị trí i (i >= p, vì bóng được ném p đơn vị trước khi nảy), ta sẽ có 2 cách chọn: i là điểm bóng được ném tới, hoặc i là điểm bóng bị nảy tới. Nếu chọn i là điểm được ném tới, ta sẽ phải bỏ đi các vị trí từ 1 đến i - p, và nếu tại vị trí i chưa được xây sẵn thì ta phải xây thêm: dp[i] = min(dp[i], (i - p) * y + (s[i]=='1' ? 0 : x)) Nếu chọn i là điểm nảy, suy ra điểm trước khi bóng nảy tới i sẽ là i - k, và nếu tại vị trí i chưa được xây sẵn thì ta phải xây thêm: dp[i] = min(dp[i], dp[i - k] + (s[i]=='1' ? 0 : x)) ★ Code:  https://ideone.com/jQac9B

Phần 1: Tài liệu 1. Competitive Programming 3 : Đây là cuốn sách khá chi tiết và đầy đủ các dạng bài tập từ trên trời xuống đáy biển, tuy nhiên yêu cầu độc giả có nền tảng tiếng Anh khá. 2. Competitive Programmer's Handbook : Đây là cuốn sách tóm tắt sơ bộ lại các dạng thuật toán và cấu trúc dữ liệu, và có thêm một số trick hay. 3. VNOI Wiki : Đây là trang được tạo ra bởi các đàn anh trong nền Tin học Việt Nam, nội dung đa dạng bao gồm các bài viết và các bài dịch từ nguồn nước ngoài. Vì vậy sẽ phù hợp với học sinh Việt Nam, đặc biệt là các bạn chưa có khả năng tiếng Anh tốt. 4. Giải thuật và Lập trình : Đây là tài liệu gối đầu giường của học sinh, sinh viên Việt Nam khi bước vào con đường lập trình thi đấu. Tuy nhiên ngôn ngữ sử dụng trong đây là Pascal, các bạn sẽ phải tự dịch sang ngôn ngữ mà các bạn đang sử dụng. Phần 2: Nguồn bài tập 1. Codeforces : trang này của nước ngoài, bài tập chủ yếu dạng ACM. Mỗi tuần đều có các contest cho lập trình viên trên toàn thế giới tham gia vớ...

★ Taken on Dec 21, 2020 - exactly two years since the day I started to learn programming ★

★ Today's tune:  https://youtu.be/gH476CxJxfg ★ Link:  https://codeforces.com/contest/1183/problem/C ★ Tags: binary search, math ★ Difficulty: 1400 (though easier) ★ Tóm tắt:  Vova đang chơi game. Máy tính của Vova ban đầu có K đơn vị pin.  Trong khi chơi game: Nếu lượng pin còn lớn hơn a , Vova chỉ được chơi (just play), và sau đó lượng pin sẽ giảm a đơn vị. (thao tác loại 1) Nếu lượng pin còn lớn hơn b (b<a), Vova vừa chơi vừa sạc (play and charge), sau đó lượng pin sẽ giảm b đơn vị. (thao tác loại 2) Nếu lượng pin nhỏ hơn hoặc bằng a hoặc b thì trò chơi dừng lại và Vova thua. Vova muốn chơi đúng N lượt chơi và thao tác loại 1 (just play) được sử dụng nhiều nhất có thể. ★ Ý tưởng: bài này thuần chặt nhị phân vì N lớn nên không thể chạy for từ 0 đến N được. Ta sẽ tìm kiếm nhị phân đáp án, với mỗi mid = (l+r)/2, ta sẽ kiểm tra nếu K - mid * a - (N - mid) * b có lớn hơn 0 hay không. Nếu có thì nghĩa là số thao tác loại 1 (mid) là hợp lệ và tiếp tục tìm ở nửa sau...

★ Today's tune:  https://youtu.be/dQw4w9WgXcQ Problem 6.07: Bài này có nhiều cách, tuy nhiên ở đây sẽ sử dụng set để xử lý (trước sau gì cũng phải học thì học trước cho khoẻ). Nói một cách đơn giản, set là một tập chứa các phần tử không trùng nhau và được sắp xếp theo thứ tự từ nhỏ đến lớn. Vì vậy ta sẽ lợi dụng điều này để tìm phần tử lớn thứ hai. Các bạn có thể tìm hiểu thêm về set tại đây:  http://www.cplusplus.com/reference/set/set/ Code:  https://ideone.com/GuyDQ5 Problem 6.08: Đề yêu cầu xoá x ra khỏi mảng -> ta chỉ cần xuất những giá trị khác x. Code:  https://ideone.com/QaaYxu Problem 6.09: Đề yêu cầu xoá k phần từ tính từ chỉ số p -> ta chỉ cần xuất các giá trị nằm ngoài khoảng [p...p+k-1]. Code:  https://ideone.com/q34o34 Problem 6.10: Code:  https://ideone.com/AkCdGk Problem 7.05: Đề yêu cầu tính tổng giá trị trên đường chéo chính -> vừa đọc ma trận vừa xử lý -> nếu i==j thì cộng thêm giá trị vừa đọc vào đáp án. Code:  https://id...

★ Taken on Dec 12, on the return trip from Can Tho ★

★ Today's tune:  https://youtu.be/Y9NpOCWcz8E  (hôm nay hơi lạnh nên nghe bài này) ★ Link:  https://codeforces.com/contest/356/problem/A ★ Tags: segment tree, dsu ★ Difficulty: 1500 ★ Kiến thức:  https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md ★ Tóm tắt: Cho n võ sĩ được đánh số theo thứ tự từ 1 -> n.  Có m trận đấu đã diễn ra, biết rằng trận đấu thứ j gồm các võ sĩ có số từ Lj đến Rj tham gia và chỉ có một võ sĩ thắng mang số Xj . Hãy cho biết từng võ sĩ bị đánh bại bởi võ sĩ nào. ★ Ý tưởng: Bài này có nhiều cách xử lý. Tuy nhiên ở đây sẽ sử dụng segment tree kết hợp lazy propagation để đánh dấu. Với một trận đấu bất kỳ:     -  Gọi võ sĩ đánh thắng trận đấu là bố.      -  Update các võ sĩ trong đoạn [L...X - 1]  có bố là X nếu đoạn đó chưa có bố.      - Update các võ sĩ trong đoạn [X + 1...R] có bố là X nếu đoạn đó chưa có bố. ★ Lưu ý: trong code có sử dụng trick xử lý bit tha...

★ Today's tune:  https://youtu.be/OcpO-cjIKYM ★ Link:  https://codeforces.com/problemset/problem/1454/D ★  Tags: math, number theory ★  Difficulty: 1300 (hard to think, easy to implement) ★  Tóm tắt: Cho số nguyên n (2 <= n <= 10^10). Tìm dãy số nguyên a1, a2, a3, ..., aK sao cho:     - ai > 1 với mọi i;     - a1 * a2 * a3 * ... * aK = n;     - a[i + 1] chia hết cho a[i] với mọi i <= n - 1;     - K lớn nhất có thể (dãy tìm được có độ dài lớn nhất). ★  Nhận xét: dãy tìm được có dạng (p1*a1), (p2*a1), (p3*a1), ... , (pK*a1) (vì a[i + 1] chia hết cho a[i] suy ra a[i] là ước của a[i + 1], hay nói cách khác a[i + 1] = p[i] * a[i]). ★  Ý tưởng: từ nhận xét trên suy ra n có thể viết lại thành dạng: p1 * p2 * p3 * ... * pK * (a1^K) => độ dài dãy lớn nhất khi K lớn nhất => tìm được a1 nhỏ nhất sao cho (p1 * p2 * p3 * ... * pK) cũng chia hết cho a1 và n chia hết cho a1 (gọi số a1 này là base). Khi đó dã...

  ★   Capturing the highest building of Vietnam while standing on the top floor of another building.  ★

★ Today's tune:  https://youtu.be/UVmWLJVMBa8 ★ Link:  https://codeforces.com/contest/877/problem/B ★ Tags: prefix sum ★ Difficulty: 1500 (much easier than this rating) ★ Today's tune:  https://youtu.be/64_O0cvQs0M ★ Tóm tắt:  Cho xâu s chỉ gồm các ký tự "a" và "b". Định nghĩa một xâu đẹp là xâu khi cắt thành 3 phần (có thể rỗng) thì phần đầu và phần cuối chỉ gồm ký tự "a", và phần giữa chỉ gồm ký tự "b". Từ xâu s có thể xoá một số ký tự để thu được một xâu đẹp. Yêu cầu tìm độ dài lớn nhất có thể của xâu đẹp thu được. ★ Ý tưởng: sử dụng prefix sum để đếm số ký tự "a" và "b". Gọi prefA[i] là số ký tự "a" xuất hiện từ đầu xâu s đến vị trí i (s[1...i]). Gọi prefB[i] là số ký tự "b" xuất hiện từ đầu xâu s đến vị trí i (s[1...i]). Suy ra để đếm số ký tự "a" từ đoạn i + 1 --> j ta sẽ lấy prefA[j] - prefA[i], tương tự với ký tự "b". Ta nhận xét xâu thu được sẽ có một trong các dạng s...