# Intro
Đây là cái nhật ký khổ dâm của tôi khi học thuật toán ứng dụng. Thầy xóa bài nên phải có cái này để lưu lại ạ. Khổ đéo chịu được các mom ơi.
# Lý thuyết
## Mảng cộng dồn (prefix sum)
Bài toán minh họa: Cho dãy $a_1,a_2,...,a_n$. Tính tổng $S_{ij}=a_{i} + a_{i+1}+...+a_j$ $\forall i\leq j$
Thuật toán:
* Với mỗi số k, ta sẽ định nghĩa $S_k = a_i+a_{i+1}+...+a_j$
# Code Hustack
## Chapter 1: Prefix sum, sliding window, two pointers
### Feasible subsequence (sliding window)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, Q;
    cin >> n >> Q;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int max_length = 0;
    int left = 0;
    long long current_sum = 0;

    for (int right = 0; right < n; ++right) {
        current_sum += a[right];

        while (current_sum > Q && left <= right) {
            current_sum -= a[left];
            left++;
        }

        max_length = max(max_length, right - left + 1);
    }

    cout << (max_length > 0 ? max_length : -1) << endl;

    return 0;
}

### Sum of Elements (prefix sum)

#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<int>> prefixSum;

public:
    void buildPrefixSum(int n, int m, const vector<vector<int>>& matrix) {
        prefixSum = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                prefixSum[i][j] = matrix[i-1][j-1] + 
                                  prefixSum[i-1][j] + 
                                  prefixSum[i][j-1] - 
                                  prefixSum[i-1][j-1];
            }
        }
    }

    int query(int r1, int c1, int r2, int c2) {
        return prefixSum[r2][c2] - 
               prefixSum[r1-1][c2] - 
               prefixSum[r2][c1-1] + 
               prefixSum[r1-1][c1-1];
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> matrix(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    Solution sol;
    sol.buildPrefixSum(n, m, matrix);

    int q;
    cin >> q;

    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << sol.query(r1, c1, r2, c2) << endl;
    }

    return 0;
}

### Count pairs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long countPairs(vector<int>& a, int M) {
    sort(a.begin(), a.end());
    
    long long count = 0;
    int left = 0;
    int right = a.size() - 1;
    
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == M) {
            if (a[left] == a[right]) {
                // Nếu a[left] == a[right], tính tổ hợp chập 2
                long long sameCount = right - left + 1;
                count += (sameCount * (sameCount - 1)) / 2;
                break;
            } else {
                int leftCount = 1, rightCount = 1;
                while (left + 1 < right && a[left] == a[left + 1]) {
                    leftCount++;
                    left++;
                }
                while (right - 1 > left && a[right] == a[right - 1]) {
                    rightCount++;
                    right--;
                }
                count += (long long)leftCount * rightCount;
                left++;
                right--;
            }
        } else if (sum < M) {
            left++;
        } else {
            right--;
        }
    }
    
    return count;
}

int main() {
    int n, M;
    cin >> n >> M;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    long long result = countPairs(a, M);
    cout << result << endl;
    
    return 0;
}

## Chapter 2: Advanced data structures
### Range Minimum Query

Input: 
16
2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4
4
1 5
0 9
1 15
6 10
Output:
6

Tính $M[i,j]$ là chỉ số của phần tử nhỏ nhất của dãy con bắt đầu từ $a_j$ và có $2^i$ phần tử, với i = $0,1,2,..., log_2 (N+1)$ và j = $0, 1, 2, …, N-1$.

Sparse table:
Recursion formula:
Code:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 1e6 + 5;  
const int LOG = 20;       

// Sparse Table
int st[MAXN][LOG];
int log_table[MAXN];

void build_sparse_table(const vector<int>& arr, int n) {
    for (int i = 0; i < n; ++i) {
        st[i][0] = arr[i];
    }

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 0; i + (1 << j) - 1 < n; ++i) {
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
}

void preprocess_log(int n) {
    log_table[1] = 0;
    for (int i = 2; i <= n; ++i) {
        log_table[i] = log_table[i / 2] + 1;
    }
}

int query(int l, int r) {
    int j = log_table[r - l + 1];
    return min(st[l][j], st[r - (1 << j) + 1][j]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;

    cin >> n;

    vector<int> arr(n);

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    preprocess_log(n);
    build_sparse_table(arr, n);

    cin >> m;

    long long sumQ = 0;

    for (int k = 0; k < m; ++k) {
        int i, j;
        cin >> i >> j;

        sumQ += query(i, j);
    }

    cout << sumQ << endl;

    return 0;
}

### Segment Tree

Input:
10
1 10 9 7 1 4 2 4 8 10 
5
get-max 5 8
get-max 5 9
get-max 3 8
update 9 20
get-max 4 10

Output:
4
8
9
20

Cơ sở lý thuyết về segment tree:
Code:

#include <bits/stdc++.h>
int n;
const int MAXN = 100000;
int A[4 * MAXN];
using namespace std;
void Update(int id, int left, int right, int index, int value){
    if (index<left||index>right) // index outside [left,right]
        return;
    if (left == right){ //the interval has only 1 factor.
        A[id] = value;
        return;
    }
    // recursion to handle child node of node id-th
    int mid = (left + right)/2;
    Update(id*2, left, mid, index, value);
    Update(id*2+1, mid+1, right, index, value);
    A[id] = max(A[id*2],A[1+id*2]);
}
int Get_max(int id, int left, int right, int lower, int upper){
    if (upper<left||lower>right) // lower < left or right < upper: out of the interval
        return -1;
    if (lower<=left && right<=upper)
        return A[id];
    int mid = (left + right)/2;
    return max(Get_max(id * 2, left, mid, lower, upper), Get_max(id * 2 + 1, mid + 1, right, lower, upper));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int a[n+1];
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        Update(1, 1, n, i, a[i]);
    }
    int m;
    cin >> m;
    cin.ignore(); // Ignore the newline character after m

    while (m--) {
        string tmp;
        getline(cin,tmp);
        stringstream ss(tmp);
        string cmd;
        ss >> cmd;
        if (cmd == "get-max") {
            int lower, upper;
            ss >> lower >> upper;
            cout << Get_max(1, 1, n, lower, upper) << "\n";
        } else if (cmd == "update") {
            int index, value;
            ss >> index >> value;
            Update(1, 1, n, index, value);
        }
    }
    return 0;
}

## Chapter 3: Recursion branch and boundary CRVP
### CBUS

Input
3  2
0  8  5  1  10  5  9
9  0  5  6  6  2  8
2  2  0  3  8  7  2
5  3  4  0  3  2  7
9  6  8  7  0  9  10
3  8  10  6  5  0  2
3  4  4  5  2  2  0
Output
25

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 100; //pvi du lieu
int x[N]; //
int f, f_best; //do dai lo trinh bo phan va do dai ngan nhat
int n,Q; //input
int d[N][N];//ma tran khoang cach
int dm;//phan tu nho nhat cua ma tran d
int load;//so nguoi tren xe
bool visited[N]; //mang danh dau
void input(){
    cin>>n>>Q;
    dm = 1e9;
    for (int i=0;i<=2*n;i++){
        for (int j=0;j<=2*n;j++){
            cin>>d[i][j];
            if (i!=j && d[i][j]<dm) dm = d[i][j];
        }
    }
}
bool check(int v, int k){
    if (visited[v]) return false;
    if (v<=n){ // v la diem don
        if (load>=Q) return false;
    }
    else{//v la diem tra
        if (!visited[v-n]) return false;
    }
    return true;
}
void updateBest(){
    if (f + d[x[2*n]][x[0]] < f_best){
        f_best = f + d[x[2*n]][x[0]];
    }
}
void Try(int k){
    for (int v=1;v<=2*n;v++){
        if (check(v,k)){
            x[k]=v;
            f = f + d[x[k-1]][x[k]];
            if (v<=n) load++;
            else load--;
            visited[v]= true;
            if (k==2*n) updateBest();
            else{
                if (f+dm*(2*n+1-k)<f_best)
                    Try(k+1);
            }
            visited[v]=false;
            if (v<=n) load--;
            else load++;
            f = f - d[x[k-1]][x[k]];
        }
    }
}
int main()
{
    input();
    for (int i=0;i<=2*n;i++) visited[i]=false;
    f=0;load=0;
    f_best = 1e9;
    x[0]=0;
    Try(1);
    cout<<f_best;
    return 0;
}

### Cut Material

Input
7 5
4
1 5
6 2
2 2
4 3
Output
1

Code:

#include <bits/stdc++.h>
using namespace std;
//define max height and width
const int max_h = 10;
const int max_w = 10;
bool mark[max_h][max_w];
vector <int> Height, Width; //initialize 2 vectors Height and Width
int h,w,n;// height, width and the number of smaller rectangles
bool check(int vo, int vx, int vy, int k){ //vx is vertical (row index), vy is horizontal(col index)
    int wk = Width[k], hk = Height[k];
    if (vo==1){ // if rotation happens, swap height and width
        wk = Height[k];
        hk = Width[k];
    }
    if (vx + hk > h || vy + wk > w) return false;
    // Check if the area is already occupied
    for (int i = vx; i< vx + hk; i++){
        for (int j = vy; j< vy + wk; j++){
            if (mark[i][j]) return false; //if (i,j) is marked, return false
        }
    }
    return true; //can be used
}
//mark or unmark the cells occupied by the k-th rectangle at position (vx, vy) with orientation vo
void doMark(int vx, int vy, int vo, int k, bool mark_value){
    int wk = Width[k], hk = Height[k];
    if (vo==1){
        wk = Height[k];
        hk = Width[k];
    }
    for (int i=vx; i<vx + hk;i++){
        for (int j=vy; j<vy+wk;j++){
            mark[i][j] = mark_value;
        }
    }
}
bool Try(int k){
    if (k==n) return true;
    for (int vo=0;vo<=1;vo++){
        int wk = Width[k], hk = Height[k];
        if (vo==1){
            wk = Height[k];
            hk = Width[k];
        }
        // try all possible positions
        for (int vx=0; vx<=h-hk;vx++){
            for (int vy=0; vy<=w-wk;vy++){
                if (check(vo,vx,vy,k)){//check if the rectangle can be placed
                    doMark(vx,vy,vo,k,true);// Mark the area as occupied
                    if (Try(k+1)) return true;// Recursively try to place the next rectangle
                    doMark(vx,vy,vo,k,false);// Unmark the area if placement fails
                }
            }
        }
    }
    return false; // there is no placement found
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>h>>w>>n;
    Height.resize(n);
    Width.resize(n);
    for (int i=0;i<n;i++){
        cin>>Height[i]>>Width[i];
    }
    for (int i=0;i<h;i++){
        for (int j=0;j<w;j++){
            mark[i][j] = false; // initialize all the cells are not occupied
        }
    }
    //if try(0) true, it returns 1 else return 0;
    if (Try(0)) cout<<1;
    else cout<<0;
    return 0;
}

### Find husband

Input   (stdin)
5
208   750 114 184 538
897
Output   (stdout)
33

Ý tưởng cũng không có gì lắm, ở mỗi index, mình sẽ backtrack thông qua vòng lặp :v

void backtrack(int index, int current_sum){
    if (current_sum>M) return;
    diff = min(diff, M - current_sum);
    for (int i = index; i < n; ++i) {
        backtrack(i + 1, current_sum + arr[i]);
    }
}

Ở mỗi vị trí của i, cho nó chạy và duyệt tổng đến khi thu được thằng lớn nhất. `diff` càng nhỏ thì mình càng sướng. Bắt đầu từ việc `backtrack(0,0)` là xong r. Sau đây là full code:

#include <bits/stdc++.h>
using namespace std;
vector <int> arr;
int n, M, diff;
void backtrack(int index, int current_sum){
    if (current_sum>M) return;
    diff = min(diff, M - current_sum);
    for (int i = index; i < n; ++i) {
        backtrack(i + 1, current_sum + arr[i]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    arr.resize(n);
    for (int i=0;i<n;i++) cin>>arr[i];
    cin>>M;
    diff = M;
    backtrack(0,0);
    cout<<diff;
    return 0;
}

### Capacitaed Vehicle Routing

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
int N, K, Q;
// y[i] the first destination of i-th truck
// x[i] the next destination followed the point i
vector<int> d, X, Y, load;
vector<vector<int>> c; //the cost matrix
vector <bool> visited;
int f, f_best;
int nbr;//the number of actual assigned trucks
int segments;//the number of segments connecting two points on the track
//segments = N + nbr when it finishes
//check when assigning the first client to a truck's route
bool checkY(int v, int k){
    if (v==0) return true; //becuz truck can return to client 0 anytime
    if (load[k]+d[v]>Q) return false; //overloaded
    if (visited[v]) return false;//if v is already visited, truck k can't approach it
    return true;
}
//check when assigning subsequent clients in a truck's route
bool checkX(int v, int k){
    if (load[k]+d[v]>Q) return false;
    if (visited[v] && v>0) return false;
    return true;
}
void update_best(){
    if(f<f_best) f_best = f;
}
void Try_X(int s, int k);
//implement the logic for assigning the first client to each truck's route.
void Try_Y(int k){
    int s = 0; //starting point
    if (Y[k-1]>0) s=Y[k-1]+1;
    for (int v=s; v<=N; v++){
        if (checkY(v,k)){
            Y[k] = v;
            if (v>0) segments++;
            visited[v]=true;
            f += c[0][v];
            load[k] = load[k]+d[v];
            if (k<K) Try_Y(k+1);
            else {
                nbr = segments;
                Try_X(Y[1],1);
            }
            load[k] = load[k] - d[v];
            f -= c[0][v];
            if (v > 0) segments--;
            visited[v] = false;
        }
    }
}
//implement the logic for assigning subsequent clients to each truck's route.
void Try_X(int s, int k){
    if (s==0){
        if (k<K) Try_X(Y[k+1],k+1);
        return;
    }
    for (int v=0;v<=N;v++){
        if (checkX(v,k)){
            X[s]=v;
            visited[v] = true;
            f += c[s][v];
            load[k] += d[v];
            segments++;
            if (v>0){
                if (f + (N+nbr-segments)*1<f_best) Try_X(v,k);
            }
            else {
                if (k==K){
                    if (segments == N + nbr) update_best();
                }
                else{
                    if (f + (N + nbr - segments) * 1 < f_best) Try_X(Y[k+1], k+1);
                }
            }
            visited[v] = false;
            f -= c[s][v];
            load[k] = load[k] - d[v];
            segments--;
        }
    }
}
void solve(){
    f=0;f_best = INF;Y[0]=0;
    for (int v=1;v<=N;v++)
        visited[v] = false;
    Try_Y(1);
    cout<<f_best;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K >> Q;

    d.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> d[i];
    }

    c.resize(N + 1, vector<int>(N + 1));
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            cin >> c[i][j];
        }
    }

    Y.resize(K + 1);
    X.resize(N + 1);
    load.resize(K + 1, 0);
    visited.resize(N + 1);

    solve();
    return 0;
}

# Code thực hành
## Tuần 1:
### Telco data check & query

Input
call 0912345678 0132465789 2022-07-12 10:30:23 10:32:00
call 0912345678 0945324545 2022-07-13 11:30:10 11:35:11
call 0132465789 0945324545 2022-07-13 11:30:23 11:32:23
call 0945324545 0912345678 2022-07-13 07:30:23 07:48:30
#
?check_phone_number
?number_calls_from 0912345678
?number_total_calls
?count_time_calls_from 0912345678
?count_time_calls_from 0132465789
#

Output
1
2
4
398
120

Code using regex:

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

int time_to_seconds(const string& time_str) {
    int h, m, s;
    sscanf(time_str.c_str(), "%d:%d:%d", &h, &m, &s);
    return h * 3600 + m * 60 + s;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    bool all_phone_numbers_correct = true;
    long long total_calls = 0;

    unordered_map<string, pair<int, long>> calls_from_map;
    regex call_regex("^call (\\S{10}) (\\S{10}) (\\d{4}-\\d{2}-\\d{2}) (\\d{2}:\\d{2}:\\d{2}) (\\d{2}:\\d{2}:\\d{2})$");
    smatch match;

    while(getline(cin, line)){
        if(line == "#") break;
        if(regex_match(line, match, call_regex)){
            string from_number = match[1];
            string to_number = match[2];
            string date = match[3];
            string from_time_str = match[4];
            string end_time_str = match[5];

            auto is_digits = [](const string& s) -> bool {
                return all_of(s.begin(), s.end(), ::isdigit);
            };

            if(!is_digits(from_number) || !is_digits(to_number)){
                all_phone_numbers_correct = false;
            }

            int from_time = time_to_seconds(from_time_str);
            int end_time = time_to_seconds(end_time_str);
            long duration = end_time - from_time;
            if(duration < 0){
                duration = 0; 
            }

            total_calls++;
            calls_from_map[from_number].first += 1;
            calls_from_map[from_number].second += duration;
        }
        else{
            all_phone_numbers_correct = false;
        }
    }

    while(getline(cin, line)){
        if(line == "#") break;

        if(line.empty()) continue;

        if(line == "?check_phone_number"){
            cout << (all_phone_numbers_correct ? "1" : "0") << "\n";
        }
        else if(line.find("?number_calls_from ") == 0){
            // Extract phone_number
            string phone_number = line.substr(19); 
            if(phone_number.length() != 10 || !all_of(phone_number.begin(), phone_number.end(), ::isdigit)){
                cout << "0\n";
            }
            else{
                auto it = calls_from_map.find(phone_number);
                if(it != calls_from_map.end()){
                    cout << it->second.first << "\n";
                }
                else{
                    cout << "0\n";
                }
            }
        }
        else if(line == "?number_total_calls"){
            cout << total_calls << "\n";
        }
        else if(line.find("?count_time_calls_from ") == 0){
            string phone_number = line.substr(23);
            if(phone_number.length() != 10 || !all_of(phone_number.begin(), phone_number.end(), ::isdigit)){
                cout << "0\n";
            }
            else{
                auto it = calls_from_map.find(phone_number);
                if(it != calls_from_map.end()){
                    cout << it->second.second << "\n";
                }
                else{
                    cout << "0\n";
                }
            }
        }
        else{
            cout << "0\n";
        }
    }

    return 0;
}

### Maze

Input
8 12 5 6
1 1 0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 1 0 1 0 0 1 1
0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 1 0 1
1 0 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 0 0 1 0 1 0
0 0 0 0 1 0 1 0 0 0 0 0
1 0 1 1 0 1 1 1 0 1 0 1

Output
7

Ý tưởng đơn giản thôi, tìm đường đi ngắn nhất thì cứ BFS mà phang:v

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int n,m,r,c;
vector <vector<int>> maze; //vector used for marking visited
struct Pos{
    int x;
    int y;
    int steps;
};
bool isValid(int row, int col){
    return row>=0 && row<n && col>=0 && col<m && maze[row][col]==0;
}
int BFS(int row, int col){
    queue <Pos> q;
    q.push({row-1,col-1,0});
    maze[row-1][col-1] = 1; //mark the starting point as visisted
    while (!q.empty()){
        Pos current = q.front();
        q.pop();
        if (current.x==0||current.y==0||current.x==n-1||current.y==m-1)
            return current.steps;
        for (int i=0;i<4;i++){
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];
            if (isValid(newX,newY)){
                q.push({newX,newY,current.steps+1});
                maze[newX][newY]=1;
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>r>>c;
    maze.resize(n,vector<int>(m));
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            cin>>maze[i][j];
        }
    }
    int res = BFS(r,c);
    if (res>0) cout<<res+1;
    else cout<<res;
    return 0;
}

### RMQ
Y hệt bài week 2:b
### Largest black subrectangle

Example 
Input
4 4
0 1 1 1
1 1 1 0
1 1 0 0
1 1 1 0
Output
6

Gợi ý giải thuật:

Code:

#include <bits/stdc++.h>
using namespace std;
vector<int> LeftBoundary(vector<int> &h){
    int n = h.size();
    vector<int> L(n);
    stack<int> s;
    for (int i=0;i<n;i++){
        while (!s.empty() && h[i]<=h[s.top()]){
            s.pop();
        }
        L[i] = s.empty()?-1:s.top();
        s.push(i);
    }
    return L;
}
vector<int> RightBoundary(vector<int> &h){
    int n = h.size();
    vector<int> R(n);
    stack<int> s;
    for (int i=n;i>=0;i--){
        while (!s.empty() && h[i]<=h[s.top()]){
            s.pop();
        }
        R[i] = s.empty()?-1:s.top();
        s.push(i);
    }
    return R;
}
int largest_Rectangle_area(vector<int>& heights){
    vector<int> L = LeftBoundary(heights);
    vector<int> R = RightBoundary(heights);
    int maxArea = 0;
    for (int i=0;i<heights.size();i++){
        int area = (R[i]-L[i]-1)*heights[i];
        maxArea = max(maxArea,area);
    }
    return maxArea;
}
int maximal_Rectangle(vector<vector<int>>& matrix){
    if (matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n,0);
    int maxArea = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                heights[j]++;
            } else {
                heights[j] = 0;
            }
        }
        maxArea = max(maxArea, largest_Rectangle_area(heights));
    }

    return maxArea;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    vector<vector<int>> matrix(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    cout << maximal_Rectangle(matrix) << endl;
    return 0;
}

## Tuần 2
### Count Integers

Input
3 4
2 3 2 
Output
3

Bài này sẽ sử dụng quy hoạch động. Ta sẽ khởi tạo mảng $dp[M+1]$ để lưu trữ kết quả, trong đó $dp[i]$ là số cách tạo ra tổng $i$ từ dãy hệ số cho trước. Hiển nhiên $dp[0]=1$ vì khi đó ta chỉ cần cho tất cả hệ số bằng $0$ là được.
Với mỗi $a[i]$:
* Cho $j$ chạy từ $a[i]$ đến $M$. Ta chạy từ $a[i]$ vì không thể tạo ra tổng nhỏ hơn $a[i]$ từ $a[i]$ được
* Nếu chúng ta đã có $dp[j - a[i]]$ cách để đạt được tổng $j - a[i]$, thì khi thêm hệ số $a[i]$, chúng ta sẽ đạt được tổng $j$. Do đó, ta thêm giá trị $dp[j - a[i]]$ vào $dp[j]$ để cập nhật số lượng cách đạt được tổng $j$.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,M;cin>>n>>M;
    vector <int> a,dp;
    a.resize(n);dp.resize(M+1,0);
    for (int i=0;i<n;i++){
        cin>>a[i];
    }
    dp[0]=1;
    for (int i=0;i<n;i++){
        for (int j=a[i];j<=M;j++){
            dp[j] = dp[j] + dp[j-a[i]];
        }
    }
    cout<<dp[M];
    return 0;
}

### Balanced Courses Assignments

Input
4 12
5 1 3 5 10 12
5 9 3 4 8 12
6 1 2 3 4 9 7
7 1 2 3 5 6 10 11
25
1 2
1 3
1 5
2 4
2 5
2 6
3 5
3 7
3 10
4 6
4 9
5 6
5 7
5 8
6 8
6 9
7 8
7 10
7 11
8 9
8 11
8 12
9 12
10 11
11 12

Output
3

**Giải thích thuật toán:**

**Code:**

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

int teacher_course[15][45], conflict[45][45], X[45], load[15], min_max_load=100000; 
int m,n;

bool check(int k, int v) {
    if(teacher_course[v][k]==0) return false;
    for(int i=1; i<k; i++) {
        if(conflict[i][k]==1 && X[i]==v) return false;
    }
    return true;
}

void update() {
    int max_load = 0;
    for(int i=1; i<=m; i++) {
        max_load = max(load[i], max_load);
    }
    if(max_load < min_max_load) min_max_load = max_load;
}


void solve(int k) {
    for(int i=1; i<=m; i++) {
        if(check(k, i)) {
            X[k] = i;
            load[i]++;
            if(k==n) {
                update();
            } else {
                if(load[i]<min_max_load) solve(k+1);
            }
            load[i]--;
        }
    }
}

int main() {
    cin>>m>>n;
    for(int i=1; i<=m; i++) {
        load[i] = 0;
    }
    int k, c1, c2;
    for(int i=1; i<=m; i++) {
        cin>>k;
        for(int j=1; j<=k; j++) {
            cin>>c1;
            teacher_course[i][c1] = 1;
        }
    }

    cin>>k;
    for(int i=1; i<=k; i++) {
        cin>>c1>>c2;
        conflict[c1][c2] = 1; conflict[c2][c1] = 1;
    }
    solve(1);
    cout<<min_max_load;
    return 0;
}