Minh Vu

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