Minh Vu

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

★ Today's tune:  https://youtu.be/AVDSZXtRgMU ★ Link:  https://codeforces.com/contest/1443/problem/C ★ Difficulty: 1400 ★ Tags: binary search, greedy ★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu): Petya muốn chuẩn bị N món ăn cho tiệc sinh nhật của hắn. Nhưng N món ăn này phải được đặt từ N nhà hàng khác nhau (người giàu thì làm gì cũng được). Cho dãy a[] và b[] , mỗi dãy gồm N phần tử, là thời gian để có được món ăn nếu nhà hàng thứ i vận chuyển (a[i]), hoặc Petya tự đến nhà hàng thứ i  lấy và quay về (b[i]). Yêu cầu tính thời gian nhỏ nhất có thể để tất cả món ăn đều được chuyển đến nhà Petya. Với dãy a[], mỗi nhà hàng sẽ bắt đầu vận chuyển tính từ thời điểm 0 -> thời gian tối đa để các món ăn do nhà hàng vận chuyển đến nơi là max của dãy a[] đã chọn được (max(a1,...)). Với dãy b[], Petya sẽ lần lượt đến từng nhà hàng để lấy -> thời gian tối đa để các món ăn do Petya tự lấy đến nơi là tổng của dãy b[] đã chọn được (sum(b2,...)). ★ Ý tưởng:...

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

★ Today's tune:  https://youtu.be/LZZexCVBHfM ★ Link: https://codeforces.com/contest/1253/problem/D ★ Tags: dfs, sortings ★ Difficulty: 1700 ★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu):  Cho đồ thị vô hướng với n đỉnh và m cạnh. Cần thêm bao nhiêu cạnh để với mỗi bộ ba L, M, R (1≤L<M<R≤n) lần lượt là 3 đỉnh trong đồ thị đã cho thoả điều kiện: Nếu có đường đi từ L tới R thì cũng sẽ có đường đi từ L tới M. ★ Ý tưởng: Đầu tiên ta sẽ dùng dfs để tìm đỉnh nhỏ nhất và đỉnh lớn nhất trong 1 thành phần liên thông. Sau đó sắp xếp lại danh sách thành phần liên thông đã tìm được theo thứ tự tăng dần của đỉnh nhỏ nhất trong mỗi thành phần liên thông.  Giả sử có 2 tplt i và j: đỉnh nhỏ nhất và lớn nhất của i lần lượt là minV[i], maxV[i]; đỉnh nhỏ nhất và lớn nhất của j lần lượt là minV[j], maxV[j] -> nếu minV[j] <= maxV[i] khi đó mọi đỉnh của j lớn hơn hoặc bằng minV[j] và nhỏ hơn hoặc bằng maxV[i] sẽ phải thuộc i, suy ra j phải liên thông vớ...

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