# Solution #1: Lời giải bài "Sắp xếp bộ ba" (nvnamson)
**Tác giả: Phan Thành Hưng (hungg_261)**

___
## Đề bài:

**Link chấm:** [nvnamson_sapxepboba](https://oj.vnoi.info/problem/nvnamson_sapxepboba)
> <u>**Yêu cầu**</u>: gia nhập tổ chức: [nvnamson](https://oj.vnoi.info/organization/nvnamson) (VNOI)

**Tóm tắt đề:**
Cho số nguyên dương $N$ và dãy gồm $N^3$ bộ ba $(i,j,k)$ với $(1\le i,j,k\le N)$ được đánh số thứ tự lần lượt $1,2,...,N^3$ và đã sắp xếp theo tiêu chuẩn sau:
- Bộ ba có tổng $i+j+k$ nhỏ hơn đứng trước;
- Nếu tổng bằng nhau thì bộ ba có $i$ nhỏ hơn đứng trước;
- Nếu vẫn bằng nhau thì bộ ba có $j$ nhỏ hơn đứng trước.

Ví dụ với $N=2$ thì dãy đó là: $\{(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)\}$.
Cho số $T$, hãy tìm bộ ba ở vị trí thứ $T$ của dãy.

Ràng buộc: $1 \le N \le 10^6$ và $1 \le T \le N^3$.

## Lời giải

Gọi $(x_1,x_2,x_3)$ là bộ ba nằm ở vị trí $T$ trong dãy.
Giả sử tổng của bộ ba đó là một số nguyên dương $S$, ta cần đếm xem có bao nhiêu bộ ba thỏa điều kiện đó. Cụ thể hơn, ta cần giải bài toán đếm số bộ nghiệm:
$$ x_1+x_2+x_3=S $$
với $1 \le x_i \le N$ và $x_i \in \mathbb{Z}$.

> Chắc hẳn sẽ có nhiều bạn nhận ra đây có liên quan tới [bài toán chia kẹo Euler](https://viblo.asia/p/bai-toan-chia-keo-euler-L4x5xqvqKBM) kinh điển (tiếng Anh có tên gọi khác là là [bài toán "stars and bars"](https://cp-algorithms.com/combinatorics/stars_and_bars.html)). Tuy nhiên mình để ý thấy rằng có khá ít giải thích cho một phiên bản mở rộng khác của bài toán, đó chính là thêm điều kiện miền trên ($x_i \le N$). Do vậy mình vẫn sẽ giải thích lại từ đầu.

Giờ, để cho dễ hiểu, mình sẽ đặt $⚫$ có giá trị tương ứng là 1 ($⚫=1$). Điều đó nghĩa là mình có thể biểu diễn $S$ dưới dạng $S$ hình tròn (⚫):
$$ \overbrace{⚫⚫⚫...⚫}^\text{S} $$

Để tìm một bộ nghiệm cũng tương tự với việc chia những hình tròn đó thành 3 phần tương ứng với giá trị của $x_1,x_2,x_3$. Ví dụ, đây là một bộ nghiệm hợp lệ:
$$ \overbrace{\underbrace{⚫⚫⚫}_{x_1}|\underbrace{⚫⚫...⚫}_{x_2}|\underbrace{⚫⚫}_{x_3}}^{S} $$

Có thể thấy rõ, số bộ nghiệm chính là số cách chia $S$ hình tròn đó thành 3 phần khác nhau như trên. Mà giữa $S$ hình tròn sẽ có $S-1$ vị trí mà ta có thể đặt các thanh dọc để chia, đồng thời, để chia chúng thành 3 phần khác nhau tương đương với việc chỉ cần đặt 2 thanh dọc vào vị trí khác nhau trong $S-1$ vị trí có thể đặt. Vậy số bộ nghiệm sẽ là:
$$ \binom {S-1}{2} = \frac{(S-1)(S-2)}{2} $$

Có thể thấy ta đã xử lý được điều kiện $x_i \ge 1$ do việc đặt 2 thanh dọc để chia luôn nằm ở vị trí khác nhau nên đảm bảo không có $x_i=0$. Tuy nhiên, ta chưa xử lý điều kiện $x_i \le N$. Ví dụ như trường hợp sau đây:
$$ \overbrace{\underbrace{\underbrace{⚫⚫}_{N}⚫}_{x_1}|\underbrace{⚫⚫...⚫}_{x_2}|\underbrace{⚫⚫}_{x_3}}^{S} $$

Như vậy, $x_1>N$, trái với yêu cầu $1 \le x_i \le N$ của đề bài. Vậy ta cần phải xử lý những trường hợp như vậy.

___

### Bao hàm - loại trừ

Lúc này, ta sẽ cần áp dụng **Nguyên lý bao hàm - loại trừ** để giải quyết phần còn lại của bài toán.

#### Đếm tổng số bộ nghiệm bất kì

Trước hết, ta cứ mặc kệ cuộc đời, cứ tính hết số bộ nghiệm thỏa $x_i \ge 1$ bằng công thức trên cái đã. Kết quả lúc này là:
$$ \binom {S-1}{2} $$

#### Số bộ nghiệm có ít nhất một giá trị không thỏa

Với biến $x_i$, số bộ nghiệm chứa $x_i$ vượt quá $N$ có thể được tính bằng công thức $\binom {S-N-1}{2}$. Đó là bởi vì ta đã coi như $N$ hình tròn đã chắc chắn được chọn vào một biến, thì ta chỉ cần đặt 2 thanh dọc vào giữa $S-N$ hình tròn còn lại thì sẽ khiến cho ít nhất 1 hình tròn được chọn rơi vào nhóm chứa $N$ hình tròn đã được chọn, từ đó làm cho nhóm đó có giá trị nhỏ nhất là $N+1$, khiến nó luôn có giá trị lớn hơn $N$ và được tính. Ví dụ minh họa như sau:

$$ \overbrace{\underbrace{\overbrace{{\text{🔴🔴}}}^{N}⚫}_{x_1}|\underbrace{⚫⚫...⚫}_{x_2}|\underbrace{⚫⚫}_{x_3}}^{S} $$

Có thể thấy, việc đặt 2 thanh dọc vào giữa $S-N$ hình tròn còn lại luôn đảm bảo tạo ra được ít nhất 1 biến $x_i$ thỏa $x_i>N$. Do ta có 3 biến là $x_1,x_2,x_3$ nên ta cần nhân 3 lần với số bộ thỏa mãn đó lên để đếm cho cả 3 biến là được. Vậy kết quả lúc này là:
$$ \binom {S-1}{2} - 3 \times \binom {S-N-1}{2} $$

#### Số bộ nghiệm có ít nhất hai giá trị không thỏa

Tương tự, với một bộ 2 biến $x_i$ và $x_j$ thì công thức sẽ là $\binom {S-2N-1}{2}$. Lí do là ta sẽ tách $2N$ hình tròn ra khỏi $S$ hình tròn, tượng trưng cho 2 nhóm sao cho mỗi nhóm đều có $N$ hình tròn. Việc đặt 2 thanh dọc vào giữa $S-2N$ hình tròn còn lại giúp ta luôn chọn ra được 2 nhóm trong đó sao cho chúng có ít nhất 1 hình tròn, kết hợp lần lượt với 2 nhóm $N$ hình tròn mà ta đã tách ra từ trước sẽ tạo ra được 2 nhóm mới sao cho mỗi nhóm đều có ít nhất $N+1$ hình tròn và được tính (nhóm còn lại ta không quan tâm do ta chỉ đang xét ít nhất 2 nhóm). Ví dụ minh họa như sau:
$$
\overbrace{{🔴🔴}}^{N}
\quad
\overbrace{{🔵🔵}}^{N}
\quad\quad\quad\quad
\overbrace{{🟠🟠}|⚫...⚫|{🟢}}^{S-2N}
$$
Ghép nhóm:
$$
\overbrace{{🔴🔴}{🟠🟠}}^{>N}
\quad
\overbrace{{🔵🔵}{🟢}}^{>N}
\quad \longleftarrow \quad
|⚫...⚫|
$$

Do có tổng cộng $\binom{3}{2}=3$ cách chọn một bộ 2 biến bất kì trong 3 biến $x_1,x_2,x_3$ nên ta phải nhân số cách chọn một cặp 2 biến với 3. Đồng thời do trước đó ta đã trừ đi số bộ nghiệm có **ít nhất** 1 biến không thỏa, nghĩa là cũng bao gồm luôn số bộ nghiệm có ít nhất 2 biến không thỏa nên lúc này ta phải cộng lại giá trị tìm được ở bước này để đảm bảo đưa ra được kết quả đúng (tính chất của **Nguyên lý bao hàm - loại trừ**). Vậy kết quả lúc này là:
$$ \binom {S-1}{2} - 3 \cdot \binom {S-N-1}{2} + 3 \cdot \binom {S-2N-1}{2} $$

#### Số bộ nghiệm có ít nhất ba giá trị không thỏa

Tương tự, với một bộ 3 biến $x_i,x_j,x_k$ thì công thức sẽ là $\binom {S-3N-1}{2}$. Lúc này thì lí do cũng khá rõ ràng (giống ở phần trên) nên mình không giải thích lại.
Do có $\binom{3}{3}=1$ cách chọn bộ nghiệm có 3 biến bất kì trong 3 biến, đồng thời do trước đó ta đã công vào số bộ nghiệm có **ít nhất** 2 biến không thỏa, nghĩa là cũng bao gồm luôn số bộ nghiệm có ít nhất 3 biến không thỏa nên lúc này ta phải trừ đi giá trị tìm được ở bước này để đảm bảo đưa ra được kết quả đúng. Vậy kết quả lúc này là:
$$ \binom {S-1}{2} - 3 \cdot \binom {S-N-1}{2} + 3 \cdot \binom {S-2N-1}{2} - \binom {S-3N-1}{2} $$

___

### Tổng quát hóa bài toán

Ta có thể tổng quát hóa bài toán như sau. Đếm số bộ nghiệm của phương trình:
$$ x_1+x_2+...+x_d=S $$
với $1 \le x_i \le N$ và $x_i \in \mathbb{Z}$.

Dựa vào **Nguyên lý bao hàm - loại trừ** kết hợp với các ý tưởng mà mình đã giải thích rất kĩ ở trên, ta có thể tìm ra được công thức tổng quát cho bài toán là:

$$ \sum_{i=0}^{d} (-1)^i \binom {d}{i}\binom {S- N\cdot i-1}{d-1} $$

Lúc này ta có thể gọi hàm `dem_tong_bang_s(d,s,N)` để đếm số bộ nghiệm hợp lệ. Cách cài đặt cũng khá đơn giản như sau:

int C(int n,int k) {
    // tính tổ hợp chập k của n (nCk)
    // ...
}

int dem_tong_bang_s(int d,int S,int N) {
    int ans=0;

    for(int i=0; i<=d; ++i) {
        int cur=C(d,i) * C(S-N*i-1, d-1);
        
        // (-1)^i => nếu i chẵn thì là +1 còn i lẻ thì -1
        if(i%2==0) ans+=cur;
        else ans-=cur;
    }

    return ans;
}

___

### Áp dụng bài toán vào lời giải

Nếu ta định nghĩa `dem_tong_bang_s(d,S,N)` là số bộ gồm $d$ số nguyên dương mà có tổng bằng $S$ sao cho không số nào lớn hơn $N$.
Bộ ba có tổng nhỏ nhất là $(1,1,1)$ có tổng là $3$, còn bộ ba có tổng lớn nhất là $(N,N,N)$ có tổng là $3N$. Như vậy ta chỉ cần chạy một vòng lặp biến $S$ từ $3$ tới $3N$ và liên tục cộng dồn `dem_tong_bang_s(3,S,N)` (gọi biến cộng dồn là $prefix$). Ở giá trị $S$ đầu tiên thỏa $T \le prefix$ chứng tỏ rằng:
$$prefix-\text{dem_tong_bang_s(3,S,N)}<T \le prefix$$
Điều đó nghĩa là bộ ba thứ $T$ có tổng bằng $S$. Lúc này ta có thể dừng vòng lặp và biết được rằng tổng của bộ ba cần tìm là $S$. Đồng thời, ta cũng biết được đó là bộ ba thứ $pos$ mà có tổng bằng $S$ bằng cách lấy $pos=T-(prefix-\text{dem_tong_bang_s(3,S,N)})$.

Code tham khảo:

pair<int,int> find_sum(int N,int T,int d) {
    int tong_cong_don=0;
    for(int sum=3; sum<=N*3; ++sum) {
        // giá trị trước khi cộng dồn
        int temp=tong_cong_don;
        
        // thực hiện cộng dồn
        tong_cong_don+=dem_tong_bang_s(d,sum,N);
        
        if(T<=tong_cong_don) {
            // đã tìm được tổng thỏa mãn, trả lại tổng "S" và vị trí "pos"
            return {sum,T-temp};
        }
    }
    return {-1,-1};
}

___

Bây giờ, ta đã biết bộ ba $(x_1,x_2,x_3)$ có tổng bằng $S$ và là bộ ba thứ $pos$ có tổng bằng $S$. Lúc này ta nhận thấy rằng, số lượng bộ ba có $x_1$ là một giá trị là $S'$ cho trước phụ thuộc vào số cách chọn các bộ $(x_2,x_3)$ hợp lệ, nghĩa là phụ thuộc vào số bộ nghiệm của phương trình sau:
$$ x_2+x_3=S' = S-x_1 $$
với $1 \le x_i \le N$ và $x_i \in \mathbb{Z}$.

Có thể thấy rõ đây thực chất chính là bài toán tổng quát mà ta vừa giải ở trên nhưng với trường hợp $d=2$ và $S=S'$. Vậy ta chỉ cần gọi lại hàm `dem_tong_bang_s(...)` là được. Vậy đến lúc này ta chạy `x1` ($x_1$) từ $1$ tới $N$, đồng thời liên tục cộng dồn giá trị của `dem_tong_bang_s(2,S-x1,N)`. Giá trị $x_1$ đầu tiên mà thỏa $pos$ bé hơn hoặc bằng tổng cộng dồn thì đó chính là tổng $x_2+x_3$. Đồng thời y chang như hàm `find_sum()` lúc trước, ta cũng có thể tính được vị trí $pos'$ của bộ $x_2,x_3$ cần tìm trong số những bộ $x_2,x_3$ có tổng là $S'$. Code tham khảo:

void tim_x1(int sum,int pos,int N) {
    int tong_cong_don=0;
    for(int x1=1; x1<=N; ++x1) {
        // giá trị trước khi cộng dồn
        int temp=tong_cong_don;
        
        // thực hiện cộng dồn
        tong_cong_don+=dem_tong_bang_s(2,sum-x1,N);
        
        if(pos<=tong_cong_don) {
            // đã tìm được x1 thỏa mãn
            cout<<x1<<' ';
            
            // bắt đầu thực hiện tìm x2
            tim_x2(sum-x1,pos-temp,N);
            return;
        }
    }
}

___

Dựa vào các bài toán trước, ta đã có:
$$ x_2+x_3=S-x_1=S' $$
và $1 \le x_2,x_3 \le N$.

Bây giờ ta chỉ cần tìm cặp $(u,v)$ thứ $pos'$ thỏa điều kiện trên.
Đến lúc này ta chỉ cần duyệt vòng lặp để tìm $x_2$, từ đó tính luôn được $x_3=S'-x_2$. Nếu $x_3$ thỏa điều kiện $1 \le x_3 \le N$ thì ta đã gặp được một cặp thỏa mãn. Tiếp tục như vậy cho đến khi gặp cặp thứ $pos'$ thì dừng và in ra cặp đó là $x_2, x_3$ đang xét hiện tại và thoát vòng lặp. Code tham khảo:

void tim_x2(int sum,int pos,int N) {
    for(int x2=1; x2<=N; ++x2) {
        int x3=sum-x2;

        // nếu x3 thỏa điều kiện thì ta vừa tìm được một cặp thỏa mãn
        if(1<=x3&&x3<=N) {
            // lúc này còn lại pos-1 cặp cần xét nữa nên ta trừ pos cho 1
            --pos;
            
            // nếu không còn cặp cần xét, nghĩa là cặp (x2,x3) hiện tại là cặp cần tìm
            if(pos==0) {
                // in ra kết quả và dừng lại
                cout<<x2<<' '<<x3<<'\n';
                return;
            }
        }
    }
}

___

Cuối cùng, ta chỉ cần tính $\binom nk$ một cách hiệu quả (cho hàm `C(n,k)`). Nhận thấy rằng trong bài này ta chỉ cần tính $k$ có giá trị tối đa là $3$ (do cần đếm số bộ ba). Do vậy ta chỉ xử lý phần tính toán tổ hợp với các giá trị $k$ từ $0$ tới $3$. Ta có thể khai triển công thức $\frac{n!}{k!(n-k)!}$ để tìm ra công thức tính trực tiếp trong $O(1)$:

| Giá trị $k$ | Giá trị $\binom nk$ |
| :--------: | :--------: |
| $0$ | $1$ |
| $1$ | $n$ |
| $2$ | $\frac{n(n-1)}2$ |
| $3$ | $\frac{n(n-1)(n-2)}6$ |

Code tham khảo:

int C(int n,int k){
    // nếu n<0 thì chắc chắn không có cách nào chọn ra k phần tử cả
    if(n<0)return 0;
    
    if(k==0) return 1; // nC0
    if(k==1) return n; // nC1
    if(k==2) return n*(n-1)/2; // nC2
    if(k==3) return n*(n-1)*(n-2)/6; // nC3
    
    return -1;
}

___

Tổng hợp các đoạn code tham khảo đó lại, ta được code hoàn chỉnh cho bài như sau:

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

int C(int n,int k){
    // nếu n<0 thì chắc chắn không có cách nào chọn ra k phần tử cả
    if(n<0)return 0;
    
    if(k==0) return 1; // nC0
    if(k==1) return n; // nC1
    if(k==2) return n*(n-1)/2; // nC2
    if(k==3) return n*(n-1)*(n-2)/6; // nC3
    
    return -1;
}

int dem_tong_bang_s(int d,int S,int N) {
    int ans=0;

    for(int i=0; i<=d; ++i) {
        int cur=C(d,i) * C(S-N*i-1, d-1);
        
        if(i%2==0) ans+=cur;
        else ans-=cur;
    }

    return ans;
}

pair<int,int> find_sum(int N,int T,int d) {
    int tong_cong_don=0;
    for(int sum=3; sum<=N*3; ++sum) {
        // giá trị trước khi cộng dồn
        int temp=tong_cong_don;
        
        // thực hiện cộng dồn
        tong_cong_don+=dem_tong_bang_s(d,sum,N);
        
        if(T<=tong_cong_don) {
            // đã tìm được tổng thỏa mãn, trả lại tổng "S" và vị trí "pos"
            return {sum,T-temp};
        }
    }
    return {-1,-1};
}

void tim_x2(int sum,int pos,int N) {
    for(int x2=1; x2<=N; ++x2) {
        int x3=sum-x2;

        // nếu x3 thỏa điều kiện thì ta vừa tìm được một cặp thỏa mãn
        if(1<=x3&&x3<=N) {
            // lúc này còn lại pos-1 cặp cần xét nữa nên ta trừ pos cho 1
            --pos;
            
            // nếu không còn cặp cần xét, nghĩa là cặp (x2,x3) hiện tại là cặp cần tìm
            if(pos==0) {
                // in ra kết quả và dừng lại
                cout<<x2<<' '<<x3<<'\n';
                return;
            }
        }
    }
}

void tim_x1(int sum,int pos,int N) {
    int tong_cong_don=0;
    for(int x1=1; x1<=N; ++x1) {
        // giá trị trước khi cộng dồn
        int temp=tong_cong_don;
        
        // thực hiện cộng dồn
        tong_cong_don+=dem_tong_bang_s(2,sum-x1,N);
        
        if(pos<=tong_cong_don) {
            // đã tìm được x1 thỏa mãn
            cout<<x1<<' ';
            
            // bắt đầu thực hiện tìm x2
            tim_x2(sum-x1,pos-temp,N);
            return;
        }
    }
}

void solve(int N,int T) {
    // tổng của bộ ba cần tìm và vị trí của bộ ba đó trong các bộ ba có tổng tương tự 
    int sum,pos;
    tie(sum,pos)=find_sum(N,T,3);
    
    // bắt đầu tìm x1
    tim_x1(sum,pos,N);
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int N,T;
    cin>>N>>T;

    solve(N,T);
    return 0;
}

Hoặc có thể xem code tại [đây](https://onlinegdb.com/6O1foui5b).

### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(N)$
- Độ phức tạp không gian: $O(1)$

## Tổng kết

### Lời kết
Vậy ta vừa giải xong bài "Sắp xếp bộ ba". Với mình thì đây là một bài khá khó và không hề dễ dàng để làm, và cũng tốn khá nhiều thời gian để giải. Hi vọng bạn thấy lời giải của mình hữu ích và dễ hiểu :Đ. **Bye bye!**

### Kết quả

- **Thời gian chạy test chậm nhất:** 0.027s
- **Bộ nhớ test cao nhất:** 2.02 MB

## Tài liệu tham khảo
- https://viblo.asia/p/bai-toan-chia-keo-euler-L4x5xqvqKBM
- https://cp-algorithms.com/combinatorics/stars_and_bars.html
+ https://cp-algorithms.com/combinatorics/stars_and_bars.html#number-of-upper-bound-integer-sums
- https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
+ https://cp-algorithms.com/combinatorics/inclusion-exclusion.html#number-of-upper-bound-integer-sums
- https://vi.wikipedia.org/wiki/Nguy%C3%AAn_l%C3%BD_bao_h%C3%A0m-lo%E1%BA%A1i_tr%E1%BB%AB