---
title
Contest 8/3 - Lời giải
---

Contest 8/3 - Lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Bài 1: Themaver1cks và món quà cho waifu
## Subtask 1, 2, 3
- Ở subtask 1, vì chỉ có $2$ xâu nên ta chỉ cần làm 1 trong 2 cách sau:
+ Sinh mọi hoán vị của cả $2$ xâu rồi tính xâu hiệu và so sánh với đáp án hiện có
+ Tính xâu hiệu từ $2$ xâu ban đầu rồi sinh mọi hoán vị của xâu hiệu đó và so sánh với đáp án hiện có

→ Cả 2 cách này đều có độ phức tạp là $O(k! * k)$
- Ở subtask 2, vì mỗi xâu chỉ có độ dài là $1$ nên ta chỉ cần duyệt qua mọi cặp xâu rồi tính xâu hiệu (chỉ gồm duy nhất 1 kí tự) của chúng và so sánh với đáp án hiện có mà không cần sinh hoán vị.

→ Độ phức tạp $O(n^{2})$

- Ở subtask 3, ta kết hợp cách làm của cả 2 subtask trên và có 2 cách:
+ Ta duyệt qua mọi cặp xâu rồi tính xâu hiệu giữa chúng, sinh mọi hoán vị của xâu hiệu đó và so sánh với đáp án hiện có
+ Ta sinh mọi hoán vị của toàn bộ các xâu, với mỗi hoán vị thì tính xâu hiệu giữa mọi cặp xâu và so sánh với đáp án hiện có

→ Độ phức tạp $O(n^{2} * k! * k)$

## Subtask 4
Ta thấy rằng việc sinh hoán vị ở bài toán này không cần thiết vì ta chỉ cần tìm xâu hiệu nhỏ nhất. Ta có thể tìm xâu hiệu của mỗi cặp xâu với độ phức tạp $O(n^{2} * k)$ sau đó thực hiện thao tác sort lại xâu hiệu và so sánh với xâu hiệu nhỏ nhất hiện tại.

:::spoiler **Code mẫu**

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string ans = "z";
    int n, k; cin >> n >> k;
    vector <string> a(n+1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    //
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i+1; j <= n; ++j)
        {
            string dif = "";
            for (int x = 0; x < k; ++x)
            {
                int d = a[i][x] - a[j][x];
                d = abs(d);
                dif += char('A' + d);
            }
            sort(dif.begin(), dif.end());
            if (dif < ans) ans = dif;
        }
    }
    cout << ans << '\n';
    return 0;
}

:::

# Bài 2:
- **Nhận xét 1**: Số thao tác đổi chỗ cần phải thực hiện để một hình chữ nhật con chứa toàn bộ kí tự $c$ là **tổng số ô trong hình chữ nhật đó - số lượng kí tự $c$ trong hình chữ nhật đó** (lưu ý là tổng số lượng kí tự $c$ trong ma trận cần phải $\ge$ diện tích hình chữ nhật).
- **Nhận xét 2**: Để một hình chữ nhật có diện tích là $S$, độ dài các cạnh của hình chữ nhật đó phải là **ước** của $S$.
- Từ hai nhận xét trên, ta có ý tưởng như sau: Ta sẽ duyệt mọi độ dài chiều rộng có thể có của hình chữ nhật, gọi là $r$, như vậy $r$ là ước của $S$ và chiều dài $d = S/r$. Như vậy ta đã có kích thước của hình chữ nhật cần tìm, tiếp theo ta sẽ tìm mọi vị trí có thể của hình chữ nhật con với kích thước $r \times d$ trong ma trận ban đầu bằng cách duyệt từng vị trí có thể có của **ô phải dưới** hình chữ nhật con trên trong ma trận.
- Số lượng ô trong một hình chữ nhật cũng chính là diện tích của hình chữ nhật đó. Vậy ta cần tính số lượng ô có kí tự $c$ trong hình chữ nhật theo cách tối ưu nhất. Để tính nhanh số lượng ô có kí tự $c$ trong hình chữ nhật con bất kì, ta sẽ sử dụng kĩ thuật [mảng cộng dồn 2 chiều (prefix sum)](https://hackmd.io/@2SchoolGuideline/H1HY_VKbp#M%E1%BA%A3ng-c%E1%BB%99ng-d%E1%BB%93n-2-chi%E1%BB%81u).

:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 1;
int pre[N][N][4];

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

    vector<int> uoc;
    for (int i = 1; i <= sqrt(s); i++)
        if (s % i == 0)
        {
            uoc.push_back(i);
            if (i != s/i) uoc.push_back(s/i);
        }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k < 4; k++) pre[i][j][k] = 0;

    string str[n + 1];
    for (int i = 1; i <= n; i++)
    {
        cin >> str[i];
        str[i] = ' ' + str[i];
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 4; k++)
            {
                pre[i][j][k] = pre[i-1][j][k]+pre[i][j-1][k]-pre[i-1][j-1][k];
                if (str[i][j]-'a' == k) pre[i][j][k]++;
            }
    }

    int ans = -1;
    for (int id = 0; id < (int)uoc.size(); id++)
    {
        int w = uoc[id], h = s/w;
        for (int i = w; i <= n; i++)
            for (int j = h; j <= m; j++)
                for (int k = 0; k < 4; k++)
                {
                    if (pre[n][m][k] < s) continue;
                    int sum = pre[i][j][k]-pre[i-w][j][k]-pre[i][j-h][k]+pre[i-w][j-h][k];
                    if (ans == -1 || s-sum < ans) ans = s-sum;
                }
    }
        
    cout << ans;
    return 0;
}

**Ý tưởng**:
- Tìm tất cả ước của $S$, lưu vào vector `uoc`.
- Gọi `pre[i][j][k]` là số lượng ô chứa kí tự thứ $k+1$ trong tập hợp các chữ cái $a, b, c, d$ trong hình chữ nhật con có ô trái trên ở vị trí $(1, 1)$ và ô phải dưới ở vị trí $(i, j)$, ta khởi tạo tất cả các phần tử trong mảng là $0$ và tính giá trị cho từng phần tử bằng kĩ thuật **mảng cộng dồn**.
- Duyệt qua từng phần tử trong `uoc`, với từng phần tử, ta sẽ xem nó là 1 cạnh của hình chữ nhật cần tìm, duyệt qua từng ô trong ma trận để kiểm tra xem hình chữ nhật con có kích thước **w** $\times$ **h** ($w, h$ là ước của $S$) chứa bao nhiêu kí tự của từng loại. Số lượng thao tác đổi chỗ cần thực hiện sẽ là diện tích hình chữ nhật đó - tổng số lượng kí tự từng loại trong hình chữ nhật đó (lưu ý tổng kí tự từng loại phải đủ để thực hiện thao tác đổi chỗ).
:::

# Bài 3: Zero_OP và hành trình vô tận

Khi nhìn bài toán ở một góc độ khác, đây chính là mô hình **đồ thị**. Quy bài toán về **đồ thị**, đỉnh ta bắt đầu thăm là $n$ và đích đến là $r$ và yêu cầu cần tìm **đường đi ngắn nhất** từ đỉnh bắt đầu đến đỉnh kết thúc.
Đây chính là kỹ thuật **BFS (Breadth-First-Search)**. Khi ta bắt đầu ở đỉnh $u$, ta có thể loang ra sang $3$ đỉnh kề là $(u + a) \bmod p$, $(u + b) \bmod p$ và $(u + a + b) \bmod p$. Nếu không tồn tại đường đi thì in ra $-1$.
Do $1 \leq p \leq 10^6$ và ta chỉ thăm mỗi đỉnh **đúng** một lần nên độ phức tạp của thuật toán là $O(p)$ hay $O(10^6)$

:::spoiler **Code mẫu**

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1e6 + 5;

int n, p, a, b, r, dist[MAX];
queue<int> q;

void init(){
    cin >> n >> p >> a >> b >> r;
}

void find_next(int u){
    int v;

    v = (u + a) % p;
    if(dist[v] == -1) {
        dist[v] = (u == n ? 0 : dist[u]) + 1;
        q.push(v);
    }

    v = (u + b) % p;
    if(dist[v] == -1) {
        dist[v] = (u == n ? 0 : dist[u]) + 1;
        q.push(v);
    }

    v = (u + a + b) % p;
    if(dist[v] == -1) {
        dist[v] = (u == n ? 0 : dist[u]) + 1;
        q.push(v);
    }
}

void process(){
    if(n == r){
        cout << 0 << '\n';
        return;
    }

    memset(dist, -1, sizeof(dist));
    find_next(n);

    while(!q.empty()){
        int u = q.front(); q.pop();
        if(u == r){
            cout << dist[r] << '\n';
            return;
        }
        find_next(u);
    }

    cout << -1 << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    init();
    process();

    return 0;
}

:::

# Bài 4: Phucthuhigh và dàn harem
## Subtask 1 $(n, s_i \le 100)$
Ở subtask này, ta nhận thấy rằng $n$ đủ nhỏ để cài đặt một thuật toán cỡ như $O(n^2\cdot m)$. Vì bắt tính chi phí nhỏ nhất, tuy nhiên thuật tham lam lại không thể chứng minh tính đúng đắn. Vậy chúng ta sẽ ứng dụng phương pháp quy hoạch động vào để giải quyết bài toán này.

Ta gọi $dp[i][j]$ là chi phí tối thiểu để mua được $j$ thanh chocolate ở $i$ gian hàng đầu tiên. Ta có thể chuyển trạng thái như sau:

- Nếu không mua thanh chocolate nào ở cửa hàng $i$: $dp[i][j] = dp[i-1][j]$
- Nếu mua $1$ thanh chocolate ở cửa hàng thứ $i$: $dp[i][j] = dp[i-1][j-1] + 1\cdot p[i] + w[i]$
- Nếu mua $2$ thanh chocolate ở cửa hàng thứ $i$: $dp[i][j] = dp[i-1][j-2] + 2\cdot p[i] + w[i]$
- Nếu mua $3$ thanh chocolate ở cửa hàng thứ $i$: $dp[i][j] = dp[i-1][j-3] + 3\cdot p[i] + w[i]$
- ...
- Nếu mua $s[i]$ thanh chocolate ở cửa hàng thứ $i$: $dp[i][j] = dp[i-1][j-s[i]] + s[i]\cdot p[i] + w[i]$

Tổng quát lại ta có công thức sau:
$$
\begin{cases}
dp[i][j] = dp[i - 1][j] & \text{với } k=j \\
dp[i][j] = min(dp[i-1][k] + (j - k)\cdot p[i] + w[i]) & \text{với } max(0, j - s[i]) \le k \le j - 1
\end{cases}
$$

Kết quả của bài toán là $dp[m][n]$.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>
#define endl '\n'
#define sz(x) (int)x.size()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

struct shop {
    ll s, p, w; // so san pham, gia tien 1 san pham, thue
} a[1005];

ll dp[1005][10005];

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i].s >> a[i].p >> a[i].w;
    // dp[i][j] la so tien it nhat de mua j san pham khi xet den cua hang thu i 
    memset(dp, 0x3f, sizeof dp); // dp[i] = INFINITY
    dp[1][0] = 0;
    for (int i = 1; i <= a[1].s; i++) {
        dp[1][i] = i*a[1].p + a[1].w;
    }
    for (int i = 2; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = dp[i-1][j];
            for (int k = max(0ll, j - a[i].s); k <= j - 1; k++) {
                dp[i][j] = min(dp[i][j], dp[i-1][k] + (j - k)*a[i].p + a[i].w);
            }
        }
    }
    cout << dp[m][n];
}

int main() {
    fastIO
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    cerr << "Times: " << TIME << "s." << endl;
    return 0;
}

/**
  *    {\__/}
  *    (• .•)
  *    / >♥️
**/

:::

## Subtask 2 (không có điều kiện gì thêm)
Ta vẫn sẽ dùng công thức trên, tuy nhiên sẽ biến đổi 1 tí như sau
$$
\begin{cases}
dp[i][j] = dp[i - 1][j] & \text{với } k=j \\
dp[i][j] = min(dp[i-1][k] - k\cdot p[i] + j\cdot p[i] + w[i]) & \text{với } max(0, j - s[i]) \le k \le j - 1
\end{cases}
$$

Ở công thức trên, ta thấy được rằng $j\cdot p[i] + w[i]$ là có sẵn trong lúc đang duyệt 2 vòng lặp. Vậy vấn đề là chúng ta phải tìm ra $dp[i - 1][k] - k\cdot p[i]$ nhanh. Ta nhận thấy rằng biến $k$ tịnh tiến tăng dần, mà ta lại cần phải tìm $min$, vậy nên từ đây chúng ta có thể áp dụng [kĩ thuật tìm max min trên đoạn tịnh tiến](https://hackmd.io/BCb1tDCeTb-z1kUVbWsqhA#%C4%90%E1%BB%81-b%C3%A0i-Ch%E1%BB%A7-%C4%91%E1%BB%81-T%C3%ACm-max-min-tr%C3%AAn-%C4%91o%E1%BA%A1n-t%E1%BB%8Bnh-ti%E1%BA%BFn) đã được học ở vài bài trước của 2SG.

:::spoiler **Code mẫu**

// author: phucthuhigh
#include <bits/stdc++.h>
#define endl '\n'
#define sz(x) (int)x.size()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

struct shop {
    ll s, p, w; // so san pham, gia tien 1 san pham, thue
} a[1005];

ll dp[1005][10005];

ll cost(int i, int k) {
    return dp[i-1][k] - a[i].p*k;
}

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i].s >> a[i].p >> a[i].w;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++) dp[0][i] = 0;
    dp[1][0] = 0;
    for (int i = 1; i <= a[1].s; i++) {
        dp[1][i] = i*a[1].p + a[1].w;
    }
    for (int i = 2; i <= m; i++) {
        deque<ll> dq;
        for (int j = 0; j <= n; j++) {
            while (sz(dq) && cost(i, j) <= cost(i, dq.back())) dq.pop_back();
            dq.push_back(j);
            if (dq.front() + a[i].s < j) dq.pop_front();
            if (sz(dq)) {
                dp[i][j] = min(dp[i - 1][j], cost(i, dq.front()) + a[i].p*j + a[i].w);
            }
        }
    }
    cout << dp[m][n] << endl;
}

int main() {
    fastIO
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    cerr << "Times: " << TIME << "s." << endl;
    return 0;
}

/**
  *    {\__/}
  *    (• .•)
  *    / >♥️
**/

:::