🔥 TỔNG KẾT CUỘC ĐUA VÒNG 3–4–5 & SIÊU CÚP 🔥

Ba vòng đấu nghẹt thở đã khép lại, và cuộc chiến Siêu Cúp vừa rồi thực sự nảy lửa! 💥 Hãy cùng điểm lại bảng vàng thành tích:

🏁 Kết quả từng vòng

• Vòng 3: 🥇 Thái · 🥈 Minh · 🥉 deptrai
• Vòng 4: 🥇 Luân · 🥈 Thái · 🥉 Minh
• Vòng 5: 🥇 Luân · 🥈 Thái · 🥉 deptrai

💰 Mỗi vòng thưởng: 🥇 50k · 🥈 30k · 🥉 20k

💵 Sau 3 vòng, BXH tạm thời: 1️⃣ Thái — 110k 2️⃣ Luân — 100k 3️⃣ Minh — 50k 4️⃣ deptrai — 40k

🏆 SIÊU CÚP — Đỉnh cao của đỉnh cao 🥇 deptrai — 100k (lội ngược dòng ngoạn mục!) 🥈 Thái — 50k

⚡ Kỷ lục “lời giải nhanh nhất”

• deptrai — 10k (Bài C)
• Luân — 20k (Bài E, G)
• Hạo — 10k (Bài A)
• santafe — 10k (Bài F)

💎 TỔNG THƯỞNG CHUNG CUỘC 👑 Thái — 160k 🔥 deptrai — 150k ⚡ Luân — 120k ⭐ Minh — 50k 🎯 Hạo — 10k 🚀 santafe — 10k

💬 Một mùa thi đấu bùng nổ cảm xúc! Từ những cú nước rút siêu tốc, pha bứt phá ngoạn mục cho tới các màn “chốt hạ” đầy kịch tính. 📦 BTC sẽ tổng hợp và gửi thưởng ngay trong tuần này. 💪 Hẹn tái đấu ở mùa sau, khi những huyền thoại mới sẽ lên ngôi! ✨

Hướng dẫn sử dụng mt19937 và mt19937_64 trong C++

📌 Mục tiêu

• Giải thích cách sử dụng bộ sinh số ngẫu nhiên chất lượng cao trong C++
• Phân biệt mt19937 (32-bit) và mt19937_64 (64-bit)
• Hướng dẫn sinh số ngẫu nhiên, số trong khoảng, số thực, mảng ngẫu nhiên

🧠 Tổng quan

mt19937 và mt19937_64 là gì?

• Là bộ sinh số ngẫu nhiên dựa trên thuật toán Mersenne Twister.
• mt19937: sinh số nguyên 32-bit (unsigned int).
• mt19937_64: sinh số nguyên 64-bit (unsigned long long).
• Chu kỳ rất dài, phân phối đồng đều, dùng nhiều trong lập trình thi đấu và mô phỏng.

🔧 Code mẫu cơ bản

#include <bits/stdc++.h>
using namespace std;

mt19937 rng32(time(0));         // Sinh số ngẫu nhiên 32-bit
mt19937_64 rng64(time(0));      // Sinh số ngẫu nhiên 64-bit

int main() {
    cout << "random 32 (bit): " << rng32() << endl;
    cout << "random 64 (bit): " << rng64() << endl;
}

📘 C++ Hash Map Cheatsheet: map, unordered_map, gp_hash_table

1. std::map

• Dạng: Cây đỏ-đen (Red-Black Tree)
• Tự động sắp xếp theo key
• Độ phức tạp: O(log n) cho các thao tác chèn, tìm kiếm, xóa

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> um;

int main() {
    map<int, int> mp;
    mp[1] = 100;
    if (mp.count(1)) {
        cout << mp[1];  // Output: 100
    }
}

✅ Ưu điểm:

• Sắp xếp theo key
• Ổn định

❌ Nhược điểm:

• Chậm hơn unordered_map hoặc gp_hash_table với dữ liệu ngẫu nhiên

2. std::unordered_map

• Dạng: Hash Table chuẩn
• Không sắp xếp theo key
• Độ phức tạp trung bình: O(1) (xấu nhất O(n))

🛠 Tip: Tăng hiệu năng bằng reserve() khi biết trước số phần tử:

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> um;

int main() {
    um.reserve(1000000);
    um[3] = 3;
    cout << um[3];
}

3. __gnu_pbds::gp_hash_table

• Cấu trúc dữ liệu thay thế unordered_map với hiệu suất cao hơn
• Cần include đặc biệt:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

int main() {
    gp_hash_table<int, int> m;
    m[3] = 1;
    cout << m[3];
}

✅ Ưu điểm:

• Rất nhanh cho dữ liệu ngẫu nhiên
• Ít bị đụng độ hash

❌ Nhược điểm:

• Không tương thích với Clang
• Không có trong chuẩn STL, chỉ dùng trên GCC (như Codeforces)

4. So sánh hiệu suất

5. Một số tối ưu khi dùng unordered_map

unordered_map<int, int> um;
um.reserve(1 << 20);              // Dự phòng bộ nhớ
um.max_load_factor(0.25);        // Giảm load factor để tránh đụng độ hash

6. Khi nào dùng cái nào?

7. Bài tập áp dụng

• Bedao Grand Contest 10 - PERFECT
• Atcoder ABC250E - Prefix Equality
• Hackerrank - Number Game on a Tree
• Codeforces 1175F - The Number of Subpermutations
• Codeforces 1418G - Three Occurrences

📌 Ghi chú

• Với test ngẫu nhiên lớn, gp_hash_table thường vượt trội về thời gian và bộ nhớ.
• Nếu không dùng được gp_hash_table, bạn có thể thử tùy biến unordered_map bằng cách tự viết hàm hash.

struct custom_hash {
    size_t operator()(uint64_t x) const {
        return x ^ (x >> 16);
    }
};
unordered_map<uint64_t, int, custom_hash> safe_map;

📘 C++ Cheatsheet: vector 1 chiều & 2 chiều

1. vector 1 chiều

🔹 Khai báo

vector<int> a;                // Vector rỗng
vector<int> b(5);             // Vector 5 phần tử, giá trị mặc định = 0
vector<int> c(5, -1);         // Vector 5 phần tử, mỗi phần tử = -1

🔹 Truy cập phần tử

a[0], a.at(0);               // Truy cập phần tử đầu tiên
a.front();                   // Phần tử đầu
a.back();                    // Phần tử cuối

🔹 Thêm / Xóa phần tử

a.push_back(10);             // Thêm vào cuối
a.pop_back();                // Xóa phần tử cuối
a.insert(a.begin() + 2, 100);// Chèn 100 tại vị trí thứ 2
a.erase(a.begin() + 1);      // Xóa phần tử tại vị trí thứ 1

🔹 Duyệt

for (int x : a) cout << x;
for (int i = 0; i < a.size(); ++i) cout << a[i];

🔹 Resize & Clear

a.resize(10);                // Thay đổi kích thước thành 10 phần tử
a.clear();                   // Xóa toàn bộ phần tử

🔹 Gán

a = vector<int>(5, 7);       // Gán lại vector a thành 5 phần tử = 7
a.assign(3, 100);            // Gán 3 phần tử bằng 100

2. vector 2 chiều

🔹 Khai báo

int n = 3, m = 4;
vector<vector<int>> mat(n, vector<int>(m));          // ma trận n x m, mặc định 0
vector<vector<int>> mat2(n, vector<int>(m, -1));     // ma trận n x m, mỗi phần tử = -1

🔹 Truy cập & Duyệt

mat[i][j];                    // Truy cập phần tử hàng i, cột j

for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        cout << mat[i][j];

🔹 Resize sau khai báo

vector<vector<int>> mat;
mat.resize(n, vector<int>(m, 0));   // Resize thành n x m, tất cả = 0

🔹 Gán lại toàn bộ

mat.assign(n, vector<int>(m, 1));  // Gán lại ma trận n x m toàn bộ = 1

3. Một số mẹo

• Duyệt nhanh:

  for (auto &row : mat)
    for (auto x : row)
        cout << x << " ";
  

• Xoay chiều ma trận:

  vector<vector<int>> rotate90(const vector<vector<int>>& mat) {
    int n = mat.size(), m = mat[0].size();
    vector<vector<int>> res(m, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            res[j][n - 1 - i] = mat[i][j];
    return res;
  }
  

🔚 Tổng kết