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