Posts

Showing posts with the label spoj

SPOJ - QBSCHOOL

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
2 comments
Read more

SPOJ - MINK

★ 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...
Post a Comment
Read more

SPOJ - KAGAIN

★ 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
Post a Comment
Read more

Popular posts from this blog

Codeforces - 1433D - Districts Connection

★ Today's tune:  https://youtu.be/QppXwgg7nC8 ★ Link:  https://codeforces.com/problemset/problem/1433/D ★ Difficulty: 1200  ★ Tags: dfs ★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu): Cho n đỉnh của đồ thị với các nhóm đỉnh khác nhau: đỉnh i được đánh số a[i] thì đỉnh i thuộc nhóm đỉnh a[i]. Yêu cầu dựng một đồ thị vô hướng liên thông có n - 1 cạnh (đồ thị này trở thành cây) từ các đỉnh đã cho và 2 đỉnh thuộc cùng một nhóm đỉnh không được nối trực tiếp với nhau. ★ Ý tưởng: vì 2 đỉnh thuộc cùng một nhóm không thể được nối trực tiếp -> ta sẽ nối bằng cách dùng 2 đỉnh trong 2 nhóm khác nhau và dfs để xây dựng tiếp đồ thị từ đỉnh đang xét cho đến khi tất cả các đỉnh đã được thăm hoặc không thể xây dựng thêm nữa. Đầu tiên ta sẽ dựng một đồ thị vô hướng có tối đa cạnh có thể có bằng cách nối từng đỉnh của một nhóm bất kỳ với từng đỉnh của một nhóm bất kỳ khác. Sau đó dùng dfs để xây dựng đồ thị theo đề bài. ★ Code:  https://ide...
Read more

Codeforces - 1462E2 - Close Tuples (hard version)

★ Today's tune:  https://youtu.be/TLVK0iTDev0 ★ Link: https://codeforces.com/problemset/problem/1462/E2 ★ Tags: binary search, combinatorics, modulo inverse ★ Difficulty: 1700 ★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu): Cho dãy a[] gồm N số. Yêu cầu đếm số cách để chọn ra một dãy có m phần tử, và chênh lệch giữa số lớn nhất và số nhỏ nhất trong dãy tìm được nhỏ hơn hoặc bằng k , lấy dư với 10^9 + 7 . ★ Nhận xét: Dãy tìm được không mất tính tổng quát khi so sánh giá trị giữa phần tử lớn nhất và nhỏ nhất trong dãy. Ví dụ: giả sử chọn được 3 số a[1], a[2], a[3] và a[1] là số lớn nhất, a[3] là số nhỏ nhất. Từ đó suy ra max(a[1], a[2], a[3]) = a[1] và min(a[1], a[2], a[3]) = a[3]. Nếu thay đổi vị trí 3 số này trở thành a[2], a[3], a[1] thì số lớn nhất vẫn là a[1] và số nhỏ nhất vẫn là a[3] -> không đổi. Suy ra dãy cần tìm không bị ràng buộc theo thứ tự vị trí. Ta chỉ cần đếm cách chọn m số trong đoạn từ [x, x + k]. Có thể sắp xếp lại và dùng tổ...
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