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...

★ 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ã...

★ 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