Random pics #3 - wandering clouds

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




A student who loves reading, writing, and coding. Currently doing a Bachelor's degree in Artificial Intelligence at FPT University. Please go to the "About me" section to find more information.

Comments

Post a Comment

Popular posts from this blog

Tổng hợp tài liệu thuật toán và cấu trúc dữ liệu C++

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ớ...
Read more

Kadane's algorithm - Finding maximum rectangular submatrix

Image
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...
Read more

Codeforces - 1454D - Number into Sequence

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