Minh Vu

★ 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

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