Coding - HackMD

CSES: - hangnt20 - Nth@2022 Codeforces: - hangnt20 - nth@2023 Codechef: - hangnt20 - Nth@2023 ## 1. Brute force **03/03** - ~~Two sum: https://leetcode.com/problems/two-sum/~~ - ~~Merge two sorted array: https://leetcode.com/problems/merge-sorted-array~~ - ~~Remove duplicate from sorted array: https://leetcode.com/problems/remove-duplicates-from-sorted-array/~~ - ~~Search insert position: https://leetcode.com/problems/search-insert-position~~ - ~~Contains duplicate: https://leetcode.com/problems/contains-duplicate/~~ **Homework** - ~~Restore the Permutation by Merger: https://codeforces.com/problemset/problem/1385/B~~ ## 2. Working with Input/Output and Optimize brute force. **06/03** ### Sliding window ~~- The Great Run: https://www.codechef.com/problems/PROC18A~~ ~~- Nice pairs: https://www.codechef.com/problems/NPAIRS~~ ~~- Where am i: http://www.usaco.org/index.php?page=viewproblem2&cpid=964, https://ide.usaco.guide/NQhd_cd5uWA0WfjOgkM~~ **7đ :<** - The way to home: https://codeforces.com/problemset/problem/910/A **Homework 14/03** ~~- K beauty number: https://leetcode.com/problems/find-the-k-beauty-of-a-number/~~ **_10đ_** - Count the number of nice subarray: https://leetcode.com/problems/count-number-of-nice-subarrays/ ### Introduction to two pointer: - ~~Two sum II: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/~~ **Homework** ~~- Sereja and Dima: https://codeforces.com/problemset/problem/381/A~~ ~~- Best to to buy and sell stock: https://leetcode.com/problems/best-time-to-buy-and-sell-stock~~ **Homework** ~~- Pairs: http://www.usaco.org/index.php?page=viewproblem2&cpid=738, https://ide.usaco.guide/NQYSPd2JnCdvib3NiPC~~ **_10đ_ - min(0,1)** - Boast Competition: https://codeforces.com/problemset/problem/1399/C ~~- Books: https://codeforces.com/contest/279/problem/B~~ **Brute force Solution:** Ta sẽ tính số cuốn sách ta đọc được nếu bắt đầu đọc ở vị trí $l$ chạy từ $0 \rightarrow n-1$. Việc này thực hiện bằng việc cộng thêm cuốn sách $r$ nếu tổng $sum <= t$ ($sum$ là tổng số phút nếu bắt đầu đọc từ cuốn sách $l$. Và ta sẽ lấy số cuốn sách đọc được nhiều nhất làm output. **Brute force implementation** ``` int rs=0; for (int l=0; l<n; l++) { int sum = 0, r = l; while (r<n && sum+arr[r] <= t) { sum += arr[r]; r++; } if (r-l >= rs) rs = r-l; } ``` **Optimized Solution with two pointer:** Dùng 2 con trỏ, $l, r$, khởi tạo giá trị bằng $0$. Định nghĩa 1 biếm sum ban đầu = $0$ (ý nghĩa là lưu tổng từ $l$ tới $r$), $l$ là cuốn sách ta bắt đầu đọc, $r$ là cuốn sách ta đọc được đến nếu bắt đầu đọc từ cuốn sách $l$. Xét nếu ``sum + arr[r] <= t`` thì ta cộng và tăng $r$ lên (ý nghĩa của việc này là có thể đọc được thêm cuốn sách $r$ mà k bị quá thời gian). Khi không thể thêm cuốn sách $r$ nữa thì ta dừng lại. Kiểm tra tra lại kết quả từ $l$ đến $r$ là bao nhiêu cuốn sách, nếu lớn nhất thì ta lấy, lưu lại kết quả. Sau khi đã xét xong thì ta tăng $l$ lên $l+1$ và trừ sm giá trị tại $l$ - việc này có ý nghĩa là ta xét nếu ta bắt đầu đọc từ cuốn sách $l+1$ và tới cuốn sách $r$. Tối ưu hơn so với cách brute force là ta không phải tính lại số phút đọc từ cuốn $l+1$ cho tới $r$ lại nữa. **Optimized implementation with two pointer** ``` int rs=0, r=0, sum=0; for (int l=0; l<n; l++) { while (r<n && sum+arr[r] <= t) { sum += arr[r]; r++; } if (r-l >= rs) rs = r-l; sum -= arr[l]; } ``` ~~- Container with most water: https://leetcode.com/problems/container-with-most-water/~~ **7đ** - Cellular Network: https://codeforces.com/contest/702/problem/C **Solution:** Dùng 2 con trỏ, $i, j$ để lần lượt xét city, tower. So sánh nếu $abs(citi[i] - tower[j])$ $\ge$ $abs(citi[i] - tower[j+1])$ (nghĩa là city mình đang xét nó gần trụ $j+1$ hơn trụ $j$) lúc này t k cần xét tiếp các trụ trước đó (nhỏ hơn $j$) nữa, nên ta tăng $j$ lên. Ta cũng lần lượt cập nhật kq của bài toán $rs - a=max(rs, abs(citi[i]-tower[j]))$ ## 3. Presum **Tổng cộng dồn**: Cho một mảng $a$ gồm $n$ phần tử: $$a_0, a_1, ...,a_n$$ Cấu trúc mảng tổng cộng dồn $prefixSum$ gồm $n+1$ phần tử, và tại vị trí thứ i+1 biểu diễn tổng cộng dồn của mảng $a$ từ $a_0$ đến $a_i$ (với phần tử đầu tiên bằng $0$, $prefixSum[0] = 0$): $$prefixSum[i] = prefixSum[i-1] + a[i]$$ $$prefixSum[j] = \sum_{i=0}^{j}a[i]$$ - Static Range Sum: https://judge.yosupo.jp/problem/static_range_sum - Breed counting: http://www.usaco.org/index.php?page=viewproblem2&cpid=572, https://ide.usaco.guide/usaco/572 - Black and White Stripe: https://codeforces.com/problemset/problem/1690/D ## 4. Observation, greedy, tìm quy luật, Ad Hoc ~~- Possitive and Negative: https://codeforces.com/problemset/problem/1791/E~~ ~~- Pails: https://ide.usaco.guide/usaco/615~~ ## 7. BFS, DFS - BFS (Bread First Search) ``` void bfs(dt, start) { queue q; q.push(start) visit[start] = true; while (q.size() > 0) { u = q.front(); q.pop(); cout << u << "->"; for (auto &e : dt[u]) { if (visit[e] == false) { q.push(e); visit[e] = true; } } } } ``` - DFS (Depth First Search) ``` void dfs(dt, u) { if (visited[u] == true) return visited[u] = true for (auto v in u) { dfs(dt, v); } } ``` ~~- Building Roads: https://cses.fi/problemset/task/1666/~~ ~~- Number of island: https://leetcode.com/problems/number-of-islands/~~ ~~- Max Area of Island: https://leetcode.com/problems/max-area-of-island/~~ **10đ** ~~- RISK: https://www.codechef.com/problems/RISK~~ **8đ** ~~- Keys and Rooms: https://leetcode.com/problems/keys-and-rooms/~~ **10đ** ~~- Rotten Oranges: https://leetcode.com/problems/rotting-oranges/~~ - Book Exchange: https://codeforces.com/contest/1249/problem/B1 - Book Exchange2: https://codeforces.com/contest/1249/problem/B2 ~~- King escape: https://codeforces.com/problemset/problem/1033/A~~ **____** - Connect: https://codeforces.com/problemset/problem/1130/C - Serial time: https://codeforces.com/problemset/problem/60/B - Soldier card: https://codeforces.com/problemset/problem/546/C - Fox and two dots: https://codeforces.com/problemset/problem/510/B - Biridian Forest: https://codeforces.com/problemset/problem/329/B - Igor and his way to work: https://codeforces.com/problemset/problem/793/B ## 8. Binary Search - https://codeforces.com/contest/1201/problem/C Solution: Ta biết max median sẽ nằm trong khoảng từ $l=a[n/2+1] \rightarrow r=a[n/2+1]+k$, ở mỗi giá trị $val = (l+r)/2$ ta kiểm tra xem giá trị có thỏa mãn là số median không. Một giá trị $val$ thỏa là median sau k phép tăng là $\sum_{i=n/2+1}^{n-1} max(0,val-a[i]) <= k$. vì ta chỉ cần quan tâm tới giá trị từ $n/2$ trở đi, và cần ít nhất $sum$ phép biến đổi để $median$ của $arr$ là $val$, nên ta có công thức ở trên. Dùng binary search tìm giá trị $val$ lớn nhất trong khoảng $l \rightarrow r$ - Hungry Chef: https://www.codechef.com/problems/BURGERS2?tab=statement ## 9. SWPCT ### Cần có - Xinh đẹp (tuy nhiên đã có rồi :<) - Đọc hiểu đề. - Quen thuộc, vững về cách thực thi và làm việc với các ctdl (vector, map, set, pair, queue,...) - Nắm vững cách thực thi BFS (dễ x, trung bình khó xxx, khó xx) - Nắm tốt và vận dụng tốt các phương pháp tối ưu. ### 1. Code understanding Cho một đề bài và đoạn code có sẵn, việc của mình là đọc hiểu đề, hiểu yêu cầu của đề bài và sửa (thưởng chỉ 1 vài dòng trong code có sẵn). Việc quan trọng nhất là hiểu đề, hiểu code có sẵn để biết chỗ sửa lại cho đúng. - Sleepy Cow Herding: http://www.usaco.org/index.php?page=viewproblem2&cpid=915, https://ide.usaco.guide/NSjsbLXv-URn_wuNqbT - Odd set: https://codeforces.com/contest/1542/problem/A ~~- Shuffle Hashing: https://codeforces.com/group/yg7WhsFsAp/contest/355494/problem/P31~~ ~~- New Year Count Down: https://codeforces.com/group/yg7WhsFsAp/contest/355496/problem/P35~~ **bánh tráng trộn** - Vasya and Golden Ticket: https://codeforces.com/group/yg7WhsFsAp/contest/355496/problem/P38 - Fill the gaps: https://atcoder.jp/contests/abc301/tasks/abc301_b ### 2. Brute force but need optimize Thường thường là dạng bài toán có thể brute force nhưng sẽ k pass hết test cases, lúc này muốn pass hết tc thì mình phải tối ưu, hoặc nghĩ ra hướng giải khác. - Next greater element: https://leetcode.com/problems/next-greater-element-ii/ - Roof garden of the building: https://codepro.lge.com/exam/19/overseas-questions-for-previous-test/quiz/9 Solution: Dùng stack để lưu lại next greater elements. Duyệt từ phải sang trái, loại bỏ các phần tử strong stack có giá trị nhỏ hơn phần tử đang duyệt `while (!st.empty() && arr[i] >= arr[st.top]) st.pop()`, nếu sau khi loại bỏ không còn phần tử nào trong stack thì tức là không có phần tử nào bên phải lớn hơn phần tử đang xét. Bước tiếp theo là push phần tử đang xét vào stack. Tiếp tục xét đến phần tử tiếp theo. ``` void solve() { stack<int> st; long long rs=0; for (int i=N-1; i>=0; i--) { while (!st.empty() && H[i] > H[st.top()]) st.pop(); // pop all the shorter buildings than the current building if (st.empty()) // if no building taller than the current building, take all the right buildings rs += (N - i - 1); else // take the building from the current building to its first taller building rs += (st.top() - i - 1); st.push(i); } cout << rs << "\n"; } ``` ![](https://i.imgur.com/Isge8eW.png) - Sum of subarray: https://leetcode.com/problems/sum-of-subarray-ranges/ - Unstable Subarray: https://www.codechef.com/problems/COUNTSUB - Positive or Negative Subarrays: https://www.codechef.com/problems/POSITNEG - Stick Length: https://cses.fi/problemset/task/1074 ### 3. Thường thường liên quan đến BFS, DFS Thường là các dạng bài có input là dạng lưới, ma trận. Cần nắm vững về lý thuyết và cách thực thi BFS. ## __Practice__ - Fast i/o - Template, library ### 10. Implementation - https://atcoder.jp/contests/abc297/tasks/abc297_b - https://atcoder.jp/contests/abc294/tasks/abc294_b - https://atcoder.jp/contests/abc295/tasks/abc295_b - https://atcoder.jp/contests/abc254/tasks/abc254_a Practice more: https://codeforces.com/group/yg7WhsFsAp/contests **Ôn lại thao tác với cấu trúc dữ liệu:** *map, unordered_map, vector, set, arr* **Problems with array:** - https://www.codechef.com/LP1TO205/problems/PAIREQ - chia array làm 3 đoạn ~~- Permutation check: https://atcoder.jp/contests/abc205/tasks/abc205_b~~ ~~- Cho 1 dãy N số, in ra các ước của dãy này với 1 số nếu là ước thì chỉ in ra 1 lần duy nhất.~~ ~~- Cho 1 dãy N vị trí, tính tổng số lượng vị trí chia hết cho 3 giữa 2 vị trí liên tiếp trong mảng mảng.~~ ex: ``` 6 1 4 8 16 7 8 ``` 1 $\rightarrow$ 4: có 1 vị trí (3) 4 $\rightarrow$ 8: có 1 vị trí (6) 8 $\rightarrow$ 16: có 3 vị trí (9, 12, 15) 16 $\rightarrow$ 7: có 3 vị trí (15, 12, 9) 7 $\rightarrow$ 8: ko có vị trí nào $tổng = 1 + 1 + 3 + 3 = 8$ ~~- Can you buy them all: https://atcoder.jp/contests/abc209/tasks/abc209_b~~ ~~- Studying algorithms: https://codeforces.com/gym/102951/problem/B~~ **22/05/2023** - maximum sum of a subsequence: https://www.codechef.com/LP1TO205/problems/SIGNFLIP - ![](https://hackmd.io/_uploads/S1M6onurn.png) - https://codeforces.com/group/yg7WhsFsAp/contest/355490/problem/P05 - https://www.codechef.com/problems/THREEAPFREE - The missing one: https://codeforces.com/group/yg7WhsFsAp/contest/355504/problem/P51 ~~**23/05/2023** - The odd one: https://codeforces.com/group/yg7WhsFsAp/contest/355504/problem/P53~~ - Array: https://codeforces.com/group/yg7WhsFsAp/contest/355504/problem/P52 **24/05/2023** - Blank space: https://codeforces.com/contest/1829/problem/B - The lakes: https://codeforces.com/contest/1829/problem/E ** - Powering the hero _easy_: https://codeforces.com/contest/1800/problem/C1 - Powering the hero _hard_: https://codeforces.com/contest/1800/problem/C2 **25/05/2023** - https://codeforces.com/problemset/problem/621/A - https://codeforces.com/problemset/problem/1183/B - ![](https://hackmd.io/_uploads/SkoBnShHh.png) Cho hình như trên, hàng 1 có 1 số, hàng 2 có 2 số tiếp theo của hàng 1, hàng 3 có 3 số tiếp theo của hàng 2, hàng n có n số. Cho 1 số k, hãy xác định số K thuộc hàng nào. | Input | Output | | -------- | -------- | | 5 | 3 | | 14 | 5 | | 21 | 6 | - Blobby Volley Scores: https://www.codechef.com/problems/BLOBBYVOLLEY?tab=statement **26/05/2023** - Amr and The Large Array: https://codeforces.com/group/yg7WhsFsAp/contest/355504/problem/P52 - Một kim tự tháp được xếp từ nhiều tầng, mỗi tầng chứa 1 số lượng dấu X khác nhau, tăng dần từ tầng thấp nhất lên tầng cao nhất. Ví dụ ở tầng cao nhất có 1 dấu X, tầng cao nhì sẽ có 3 dấu X, tầng cao thứ 3 sẽ có 6 dấu X,... Ví dụ 1 kim tự thấp 4 tầng với số lượng dấu X của từng tầng như hình dưới ![](https://hackmd.io/_uploads/SJ24Y3pr2.png) Hãy in ra số tổng số lượng dấu X của kim tự tháp n tầng. | Input | Output | | -------- | -------- | | 1 | 1 | |2|4| |4|20| |5|35| |8|120| |20|1540| **Giải thích** Kim tự thấp 4 tầng sẽ có 10 dấu X ở tầng 1, 6 dấu X ở tầng 2, 3 dấu X ở tầng 3 và 1 dấu X ở tầng 4. Vậy có tổng 20 dấu X. Tương tự như vậy với các input khác. - Maximum sum: https://codeforces.com/contest/1832/problem/B - Alternating Cards:https://codeforces.com/contest/1786/problem/A1 **28/05/2023** - Make it beautiful: https://codeforces.com/contest/1783/problem/A - Odd queries: https://codeforces.com/problemset/problem/1807/D - Beautiful Sequence: https://codeforces.com/problemset/problem/1810/A - Bananas: https://codeforces.com/problemset/problem/546/A - Stones on the table: https://codeforces.com/problemset/problem/266/A **30/02/2023** - Maiak and array: https://codeforces.com/problemset/problem/1726/A - Orac and factor: https://codeforces.com/problemset/problem/1350/A - Discord: https://atcoder.jp/contests/abc303/tasks/abc303_b **31/05/2023** ~~- Equal Elements: https://www.codechef.com/problems/EQUALELE~~ ~~- Divisible: https://www.codechef.com/problems/BOOKPAGES~~ ~~- Movies festival: https://cses.fi/problemset/task/1629~~ ~~- Diamonds collector: https://ide.usaco.guide/usaco/639, http://www.usaco.org/index.php?page=viewproblem2&cpid=639~~ **BFS** ~~- Counting room: https://cses.fi/problemset/task/1192~~ ~~- Maze: https://codeforces.com/contest/1365/problem/D~~ **01/06/2023** **10đ** - Biết điểm tối đa của học sinh 1 ($arr_0$) có thể đạt được là bao nhiêu trong 2 trường hợp, - Biết tìm ra giải pháp để thay đổi giá trị của các giá trị sau đó ($arr_1 \rightarrow arr_{n-1}$) khi đã thay đổi giá trị $arr_0$ ~~- Grade Allocation: https://codeforces.com/contest/1316/problem/A~~ ~~- Middle class: https://codeforces.com/contest/1334/problem/B~~ **02/06/2023** ~~- Cashier: https://codeforces.com/group/yg7WhsFsAp/contest/355490/problem/P08~~ - Challenging Valleys: https://codeforces.com/problemset/problem/1760/D ~~- Make it increasing: https://codeforces.com/problemset/problem/1675/B~~ - Movers: lgedvoj **03/06/2023** Làm típ bài Maze với bài Challenging Valleys hôm qua chưa làm nha :< Bài maze hơi rối 1 xí nhưng cũng ko khó quá đâu, bài Daily Temperature cứ vét cạn trước iik, mình chỉ cách dùng stack để tối ưu sau :< **iu Hằng nhìu <3** ~~- Maze: https://codeforces.com/contest/1365/problem/D~~ - Challenging Valleys: https://codeforces.com/problemset/problem/1760/D Biết cách làm, làm tốt :< ưng lắm, nhưng cần cẩn thận review lại code trước khi submit, cũng như khi nghĩ được phương án nên nghĩ xem nhiều chỗ có thể tối ưu được để cho code gọn lại và rõ ràng cũng như dễ thực thi hơn (việc này khá quan trọng khi có những phương án đúng nhưng việc thực thi lại rườm rà và dễ sai, dẫn đến tuy phương án là đúng nhưng lại lúc mình thực thi lại không được). **Tổng kết: cho 10đ :< nhưng vẫn cần phải cẩn thận hơn** ~~- Count subisland: https://leetcode.com/problems/count-sub-islands/~~ $10.0đ$ ~~- Daily temperature: https://leetcode.com/problems/daily-temperatures/~~ **05/06/2023** ~~- Virus: https://atcoder.jp/contests/abc304/tasks/abc304_c~~ **10đ** ~~- Matrix Rotation: https://codeforces.com/contest/1772/problem/B~~ **06/06/2023** **Làm típ mấy bài chưa làm** ~~- Plus one of the subset: https://codeforces.com/contest/1624/problem/A~~ **07/06/2023** **Làm típ mấy bài chưa làm** ~~- Plus one of the subset: https://codeforces.com/contest/1624/problem/A~~ ~~- Fall down: https://codeforces.com/problemset/problem/1669/G~~ ~~- Movers: lgedvoj~~ **08/06/2023** - Eating Candies: https://codeforces.com/problemset/problem/1669/F ## TEST 1 (08/06/2023) #### A (30/30) https://codeforces.com/contest/215/problem/A Hơi mất thời gian cho bài này, nhưng chung quy vẫn oke. Cách làm hay. Thơm miếng nè :* #### B (30/30) https://codeforces.com/problemset/gymProblem/101343/H Làm tốt, nhanh. 10 đỉm :* #### C (0/40) https://leetcode.com/problems/shortest-bridge/ Cần phải xem lại về cách tính khoảng cách giữa hai vùng. Tổng: **60/100** **10/06/2023** ~~- Maximum width ramp: https://leetcode.com/problems/maximum-width-ramp~~ ~~- Eating Candies: https://codeforces.com/problemset/problem/1669/F~~ ~~- Nearest Exit: https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/~~ **12/06/2023** - Snuke the Cookie Picker: https://atcoder.jp/contests/abc305/tasks/abc305_c - Dash: https://atcoder.jp/contests/abc303/tasks/abc303_c **TEST 2** **A. Three sum closest:** https://leetcode.com/problems/3sum-closest/ $30/30đ$ **Gợi ý:** Ta có thể sort mảng lại và dùng 2 con trỏ. Bởi vì mình cần tìm 3 số có tổng gần với target nhất, gọi 3 số này là $nums[i], nums[l], nums[r]$. Mình có thể chạy 1 vòng for từ đầu đến cuối để cố định điểm $i$ và khi đó $l = i+1$, $r = n-1$. Ta xét nếu $nums[i] + nums[l] + nums[r]$ lớn hơn hoặc nhỏ hơn $target$ thì ta tăng giảm $l,r$ tương ứng, hoặc trả về kết quả luôn nếu bằng. Trong mỗi lần xét đểu phải tính lại kết quả để nếu không có 3 số cộng lại bằng $target$ ta vẫn có thể có kết quả gần với $target$ nhất. **B. Sprial matrix:** https://leetcode.com/problems/spiral-matrix/ $0/40đ$ **Gợi ý:** Ta nhận thấy nếu đặt điểm đầu tiên push vào, hàng và cột lần lượt là $(0,0)$, thì ta sẽ push tiếp các điểm có cùng hàng với nó và cột thì tăng dần đến $(0,0)$ $\rightarrow$ $(0,n-1)$ sau khi tới cuối cùng thì ta sẽ push tiếp các điểm có cùng cột với nó và hàng thì tăng dần $(0,n-1)$ $\rightarrow$ $(m-1,n-1)$ sau đó lại push những điểm có cùng hàng với nó nhưng cột lại giảm dần $(m-1,n-1)$ $\rightarrow$ $(m-1,0), và cuối cùng là push những điểm có cùng cột với nó nhưng hàng thì giảm dần $(m-1,0)$ $\rightarrow$ $(1,0)$ (vì điểm $(0,0)$ ta đã push vào rồi nên ta chỉ push tới điêm $(1,0)$. Như vậy ta sẽ có 1 vòng lặp lặp lại 4 bước trên. Ta có thể đánh dấu những vị trí nào đã push để không thêm những vị trí đó vào lại. ![](https://hackmd.io/_uploads/SyOhv0SD2.png) **C. number of closed islands:** https://leetcode.com/problems/number-of-closed-islands/ $40/40đ$ **Tổng: 70/100đ** ## Bài tập - ~~Largest number: https://leetcode.com/problems/largest-number/~~ - ~~Maximal Square: https://leetcode.com/problems/maximal-square/~~ - ~~Game of life: https://leetcode.com/problems/game-of-life/~~ - ~~Array merging: https://codeforces.com/problemset/problem/1831/B~~ **BFS:** - ~~Umanned Train (Codepro): https://codepro.lge.com/exam/19/overseas-questions-for-previous-test/quiz/10~~ - Minimum Obstacble to reach corner: https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/ - Escaping the spreading fire: https://leetcode.com/problems/escape-the-spreading-fire/ - Shorted path in a grid: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ **24/06/2023** - ~~Trapping water: https://leetcode.com/problems/trapping-rain-water/description/~~ - ~~First missing positive integer: https://leetcode.com/problems/first-missing-positive/~~ - ~~Merge intervals: https://leetcode.com/problems/merge-intervals/~~ - ~~Longest consecutive sequence: https://leetcode.com/problems/longest-consecutive-sequence/description/~~ BFS: - Marking a large island: https://leetcode.com/problems/making-a-large-island/description/ - ~~Count servers that communicate: https://leetcode.com/problems/count-servers-that-communicate/~~ **25/06/2023** - Gas station: https://leetcode.com/problems/gas-station/ **BFS** - Treasure hunting: https://www.codechef.com/problems/N1 **nhắc bạn trả tiền -.-** **ê, m có tiền chưa, t đang cần tiền gấp á** **cuối tháng làm form** ### Batch 3 #### C.cpp ``` #include <bits/stdc++.h> using namespace std; #define int long long int n; pair<int, int> a_pos, b_pos; vector<pair<int, int>> pos; vector<int> per; int32_t main() { cin >> n; pos.resize(n); per.resize(n); cin >> a_pos.first >> a_pos.second; cin >> b_pos.first >> b_pos.second; for (int i=0; i<n; i++) cin >> pos[i].first >> pos[i].second; for (int i=0; i<n; i++) per[i] = i; int rs = 1e9; do { for (int i=0; i<=n; i++) { vector<pair<int, int>> truck_A, truck_B; for (int j=0; j<i; j++) truck_A.push_back(pos[per[j]]); for (int j=i; j<n; j++) truck_B.push_back(pos[per[j]]); int cost = 0, w = 1; int prev_first = a_pos.first, prev_second = a_pos.second; for (int i=0; i<truck_A.size(); i++) { cost += w * (abs(truck_A[i].first - prev_first) + abs(truck_A[i].second - prev_second)); w++; prev_first = truck_A[i].first, prev_second = truck_A[i].second; } cost += w * (abs(a_pos.first - prev_first) + abs(a_pos.second - prev_second)); prev_first = b_pos.first, prev_second = b_pos.second; w = 1; for (int i=0; i<truck_B.size(); i++) { cost += w * (abs(truck_B[i].first - prev_first) + abs(truck_B[i].second - prev_second)); w++; prev_first = truck_B[i].first, prev_second = truck_B[i].second; } cost += w * (abs(b_pos.first - prev_first) + abs(b_pos.second - prev_second)); rs = min(rs, cost); } } while (next_permutation(per.begin(), per.end())); cout << rs << endl; return 0; } ``` **___** - Card swipe: ~~https://www.codechef.com/problems/CARDSWIPE~~ - Exlusion-Inclusion: https://www.codechef.com/problems/ONEFROMK **08/08** - ~~https://atcoder.jp/contests/abc309/tasks/abc309_d~~ - ~~https://atcoder.jp/contests/abc302/tasks/abc302_d~~ - ~~https://atcoder.jp/contests/abc312/tasks/abc312_c~~ **09/08** - ~~https://atcoder.jp/contests/abc313/tasks/abc313_c~~ - ~~https://atcoder.jp/contests/abc302/tasks/abc302_c~~ **11/08** - ~~https://atcoder.jp/contests/abc294/tasks/abc294_d~~ - ~~https://atcoder.jp/contests/abc290/tasks/abc290_c~~ - https://atcoder.jp/contests/abc233/tasks/abc233_c - ~~https://atcoder.jp/contests/abc234/tasks/abc234_d~~ - ~~https://atcoder.jp/contests/abc232/tasks/abc232_d~~ - ~~https://atcoder.jp/contests/abc233/tasks/abc233_d~~ **16/08** - ~~https://codeforces.com/contest/1855/problem/A~~ **17/08** - ~~https://codeforces.com/contest/1847/problem/A~~ **21/08** - ~~https://atcoder.jp/contests/abc315/tasks/abc315_c~~ - ~~https://codeforces.com/contest/1857/problem/A~~ - ~~https://codeforces.com/contest/1857/problem/C~~ - ~~https://codeforces.com/problemset/problem/1843/B~~ - ~~https://codeforces.com/contest/1836/problem/A~~ - ~~https://codeforces.com/contest/1843/problem/A~~ **23/08** - Tiles Comeback: https://codeforces.com/contest/1851/problem/C - Prefix Permutation Sums: https://codeforces.com/contest/1851/problem/D ``` // SOURCE CODE 1851_D #include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { int tc; cin >> tc; while (tc--) { int n; cin >> n; int arr[n-1]; for (int i=0; i<n-1; i++) { cin >> arr[i]; } map<int, int> mp; mp[arr[0]]++; for (int i=1; i<n-1; i++) { mp[arr[i] - arr[i-1]]++; } int cnt = 0; bool visited[n+1] {}, rs = true; for (int i=1; i<=n; i++) { if (mp[i] != 0) visited[i] = true, mp[i]--; if (mp[i] == 0) mp.erase(i); if (visited[i] == false) cnt++; } if (cnt > 2) rs = false; else if (cnt == 1) rs = true; else if (cnt == 2) { if (mp.size() != 1) rs = false; else { int sm = 0; for (int i=1; i<=n; i++) if (visited[i] == false) sm += i; pair<int, int> remain; for (auto &e : mp) remain = e; if (remain.second > 1 || remain.first != sm) rs = false; else rs = true; } } cout << (rs ? "YES" : "NO") << endl; } return 0; } ``` ~~- Nastya and Potions: https://codeforces.com/contest/1851/problem/E~~ **01/09:** - ~~https://codeforces.com/contest/1864/problem/A~~ **05/09** - ~~https://codeforces.com/contest/1790/problem/B~~ - https://codeforces.com/contest/1790/problem/C (Code: https://codeforces.com/contest/1790/submission/221803810) - ~~https://codeforces.com/contest/1790/problem/D~~ (Code: https://codeforces.com/contest/1790/submission/221890252) **11/09** - ~~https://codeforces.com/contest/1872/problem/B~~ - ~~https://codeforces.com/contest/1869/problem/B~~ **12/09** - ~~https://codeforces.com/contest/1867/problem/A~~ **14/09** - ~~https://cses.fi/problemset/task/1674~~ **15/09** - https://codeforces.com/problemset/problem/363/B - **(*)** https://codeforces.com/problemset/problem/1380/C <ins>solution</ins>: Bởi vì chúng ta muốn lập được nhiều team nhất nên với những người có skills lớn hơn x, mỗi người ta lập thành 1 đội riêng. Đối với những người còn lại, duyệt theo thứ tự lớn đến nhỏ theo skills (bởi vì điều kiện là min_skill * số người >= x nên nếu để những người có skill thấp với những người có skill cao thì sẽ phí do lúc đó skill của những người có skills lớn sẽ ko được xét đến, nên ta sẽ lập nhóm cho những người có skill lớn trước, cứ khi nào đủ điều kiện (min_skill * số người >= x) thì ta lập thành một team mới. <ins>implementation</ins>: ``` #include <bits/stdc++.h> using namespace std; #define int long long int tc, n, x; vector<int> arr; int32_t main() { cin >> tc; while (tc--) { cin >> n >> x; int rs = 0, e; for (int i=0; i<n; i++) { cin >> e; if (e >= x) rs++; else arr.push_back(e); } sort(arr.begin(), arr.end(), greater<>()); n = arr.size(); if (n == 0) { cout << rs << endl; continue; } int mMin = arr[0], cnt = 1; for (int i=1; i<n; i++) { mMin = min(mMin, arr[i]); cnt++; if (mMin * cnt >= x) { rs++; cnt = 0; mMin = INT_MAX; } } cout << rs << endl; arr.clear(); } return 0; } ``` **18/09** - https://www.codechef.com/problems/S100 **19/09** - **(*)** https://codeforces.com/problemset/problem/1848/B <ins>solution</ins>: có k màu từ 1 đến k. Xét một màu i (1 <= i <= k): Ta sẽ tìm khoảng cách giưã những ô có màu i này với nhau (cả khoảng cách từ ô 0 (tượng trưng cho bên này cầu) đến ô đầu tiên, khoảng cách từ ô cuối cùng đến ô N+1 (tượng trưng cho bên kia cầu)). Bởi vì ta chỉ có thể sơn lại 1 ô nên nếu chọn màu i để đi, số bước nhỏ nhất (có thể) ta cần phải nhảy sẽ là khoảng cách lớn nhất (khi đã chia 2 một giá trị khoảng cách nhỏ nhất, vd khoảng cách của màu i lần lượt là 1 2 2 thì sau khi chia 2 một giá trị khoảng cách lớn nhất là 2 ta sẽ còn lại: 1 1 2 (chia đôi cái 2 đầu tiên)). Vậy lặp qua k màu để xem số bước đi nhỏ nhất của màu nào là nhỏ nhất. <ins>implementation</ins>: ``` Note: - Mảng prev ban đầu để lưu vị trí trước đó của màu i, sau khi assign lại (prev.assign(k+1,-1)) thì dùng để lưu số bước nhảy nhỏ nhất có thể (khoảng cách lớn nhất) của màu i. - Không nhất thiết làm theo cách này, cũng có thể dùng một mảng khác để lưu. ``` ``` #include <bits/stdc++.h> using namespace std; int n, k, arr[200100]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tc; cin >> tc; while (tc--) { cin >> n >> k; for (int i=1; i<=n; i++) cin >> arr[i]; vector<vector<int>> dist(k+1); vector<int> prev(k+1,0); vector<int> mMax(k+1,-1); vector<bool> used(k+1,false); for (int i=1; i<=n; i++) { dist[arr[i]].push_back(i - prev[arr[i]] - 1); mMax[arr[i]] = max(mMax[arr[i]], i - prev[arr[i]] - 1); prev[arr[i]] = i; } int mMin = 1e9; for (int i=1; i<=k; i++) { dist[i].push_back(n - prev[i]); mMax[i] = max(mMax[i], n - prev[i]); } prev.assign(k+1,-1); for (int i=1; i<=k; i++) { for (auto &e : dist[i]) { if (e == mMax[i] && !used[i]) { e /= 2; used[i] = true; } prev[i] = max(prev[i], e); } mMin = min(mMin, prev[i]); } cout << mMin << endl; } } ``` - https://codeforces.com/problemset/problem/1075/B **20/09** - https://codeforces.com/contest/1870/problem/C **CSES 27/09** - Sum of three values: https://cses.fi/problemset/task/1641 - Rooms allocation: https://cses.fi/problemset/task/1164 - Traffic lights: https://cses.fi/problemset/task/1163 **CSES** - https://codeforces.com/contest/1882/problem/C CF: - https://codeforces.com/contest/1138/problem/A - https://codeforces.com/contest/1105/problem/B