# IT003.P21.CTTN
Lớp thực hành .2

Vũ Hoàng Long - 24520019 - ATTN24

Nộp lời giải Assignment 2 (Basic và Advance)

Code: https://github.com/UITlogn/DSA_Assigment2

# Advance


## MaxMinSum

Đề bài:
Cho mảng số nguyên $A$ có $N$ phần tử và một số $K$. Trong tất cả các cách chọn $K$ phần tử trong $A$, tính tổng chênh lệnh giữa phần tử nhỏ nhất và lớn nhất.

Solution:
Vì việc chọn các số là không có tính thứ tự, nên ta có thể sắp xếp lại mảng $A$. Khi đó, trong một cách chọn tập hợp thì số lớn nhất là số phải cùng, số bé nhất là số trái cùng.

Như vậy mỗi số $A_i$ thì ta có thể tính được nó sẽ là số lớn nhất trong bao nhiêu tập hợp, cụ thể là tất cả những cách chọn tập K phần tử trong đoạn $A_{1..i}$ mà có chứa phần tử $A_i$ $\rightarrow$ sau khi chọn $A_i$ thì chọn $k - 1$ phần tử nữa ở bên trái (không thể chọn ở bên phải vì nó sẽ lớn hơn $A_i$) $\rightarrow$ số cách chọn là $C_{i - 1}^{k - 1}$.

Tương tự khi muốn tính $A_i$ là phần tử nhỏ nhất trong bao nhiêu tập hợp $\rightarrow$ số cách chọn $k - 1$ phần tử trong đoạn $A_{i + 1 .. n} \rightarrow C^{k - 1}_{n - i}$.

Vì $N, K$ không quá lớn nên có thể tiền xử lí trước mảng giai thừa để tính nhanh tổ hợp. Xử lí modulo phép chia thành nhân nghịch đảo fermat nhỏ bằng lũy thừa chia để trị, phép trừ để tránh âm thì cộng cho $MOD$.

## khangtd.Login1

Vì độ dài $S$, $T$ nhỏ cùng với $N$, $Q$ không quá lớn nên có thể dùng ```map``` để lưu với key là user $S$ và value là password $T$. Có thể **hash** xâu $S$ thành số nguyên để tăng tốc độ tìm kiếm key trong ```map```

## khangtd.Login2

Giống bài 1 nhưng cần lưu lại toàn bộ lịch sử password nên value của map sẽ thay bằng ```vector<string>```.

## khangtd.DetectVirus

## khangtd.DetectVirus2

Có thể duyệt qua hết tất cả các xâu liên tiếp độ dài $t$ trong $s$ với độ phức tạp $O(n)$, tuy nhiên do việc so khớp xâu cũng mất độ phức tạp $O(n)$ nên với $n$ lớn.

Việc so khớp xâu có thể thực hiện trong $O(1)$ bằng **hash**, mã hóa một đoạn xâu kí tự thành một số nguyên để so sánh hai số trong $O(1)$.

## Linear Search 4

Nhận xét: chỉ quan tâm đến số lượng số xuất hiện một lần và từ hai lần, gọi là ```cnt1``` và ```cnt2```.

Với ```cnt1``` thì những số đó chỉ có thể xuất hiện ở chính xác một nhóm. Còn ```cnt2``` vì nó có nhiều hơn một phần tử việc chia bao nhiêu phần tử và một nhóm là không quan trọng, chỉ cần biết là có thể chia hết vào một nhóm hoặc chia sao cho hai nhóm đều có là được.

Không tồn tại cách chia nhóm khi: $cnt_1 + 2cnt_2 < 2k$ (không đủ k dạng cho mỗi nhóm) hoặc $cnt_1 + cnt_2 > 2k$ (bị thừa khi mỗi nhóm chỉ được k dạng). Còn lại đều có thể tìm cách chia thỏa mãn.

## Pickleball v2

Thuật toán quan trọng nhất của bài này là tìm **median** của tất cả các đoạn liên tiếp $k$ phần tử trong thời gian tối ưu nhất.

Có nhiều thuật toán có thể xử lí vấn đề này:
* Dùng ```multiset``` để lưu $2$ nửa tập hợp, sau mỗi thao tác thêm xóa thì cân bằng lại kích thước $2$ tập, thì **median** sẽ nằm ở cuối tập này hoặc đầu tập kia (hoặc trung bình cộng nếu $k$ chẵn). Nhưng cách này không dùng được vì đã bị cấm các thư viện đặc biệt
* Tự cài đặt lại một ```ordered_set``` bằng heap rồi xử lí cùng ý tưởng như trên. Cách này khá dài dòng nên sẽ không code
* Vì giới hạn $A_i$ nhỏ ($200$), nên có thể dùng một mảng đếm phân phối để quản lí các số đang có trong đoạn hiện tại, các thao tác thêm xóa chỉ cần tăng giảm tần số trong đó. Median sẽ được tìm thấy ở vị trí đầu tiên mà prefixsum trong mảng đếm bằng với $k / 2$ (vì sẽ có $k / 2$ số < ```median``` trong một tập hợp, lưu ý k chẵn và k lẻ). Độ phức tạp O(N*200)
* Có thể tối ưu thêm bằng fenwick tree và chặt nhị phân để tìm vị trí **median** nhanh hơn trong $O(log_2 200)$.

## Bốn ông điên

Note: tuy đề không ghi rõ nhưng bài này các số $A_i$ là phân biệt với nhau (khác nhau đôi một). Có thể kiểm chứng bằng cách dùng map để đánh dấu. Nếu không thì sẽ là một dạng np-hard không có lời giải tuyến tính.

Với mỗi vị trí $A_i$, ta cần tìm ```pos[a[i]]``` là vị trí chính xác của giá trị $A_i$ sau khi sắp xếp (xử lí riêng biệt hai trường hợp xếp tăng và giảm, lấy min). Vì $A_i$ lớn nên có thể dùng ```map```

Vậy để tối ưu số lần swap, ```a[i]``` sẽ được swap thẳng tới ```a[pos[a[i]]]```. Lặp lại cho đến khi ai nằm đúng vị trí ```pos[a[i]] == i```.

Nếu coi mỗi ```a[i]``` là một nút và một lần swap là một cạnh thì ta sẽ có một đồ thị gồm nhiều chu trình khép kín tách biệt nhau. Chi phí để swap về đúng vị trí trong một chu trình là ```numNode - 1```.


## Huấn luyện chuột

Số cách để tạo một dãy số $A$ gồm $N$ phần tử nguyên mà mỗi phần tử thuộc đoạn từ $1$ đến $N$ là $C^n_{2n-1}$

Vấn đề ở bài này là $N$ lớn ($10^{12}$), nhưng $p$ là số nguyên tố nhỏ ($10^5$) và cố định cho các testcase, nên ta có thể sử dụng định lí [lucas](https://en.wikipedia.org/wiki/Lucas%27s_theorem):

* Phân tích $N$ theo hệ cơ số $p$
* Tính các tổ hợp với $n$ nhỏ (vì đã được mod $p$)
* Kết quả là tích của các tổ hợp con theo modulo $p$.

# Basic


## Task

Có thể biến đổi tọa độ chỗ ngồi thành số thứ tự (đánh số từ trên xuống, trái sang phải) bằng công thức:

$(x, y) \rightarrow id = 2(x - 1) + y$

Và từ thứ tự sang tọa độ:

$id \rightarrow x = (id + 1) / 2, y = (id + 1) % 2 + 1$

Sau khi chuyển tọa độ $(p, q)$ thành số thứ tự $id$ thì những vị trí cùng đề gần nhất với nó là $id + k$ và $id - k$. Kiểm tra thứ tự đó có nằm trong lớp không và xét chênh lệnh với tọa độ ban đầu để lấy tọa độ gần nhất.

## Point3D

Dùng ```quickSort``` như mảng ```int``` nhưng thành bằng một ```struct``` gồm 3 số là tọa độ $(x,y,z)$ và định nghĩa hàm so sánh <.

## an.512.Trộn 2 mảng

Vì bị cấm hàm sort nên ở đây ta sẽ dùng thuật toán hai con trỏ:
* $i$ chạy trên mảng $A$, $j$ chạy trên mảng $B$
* Ở mỗi bước lấy số nhỏ hơn trong hai số $A_i$ và $B_i$ để thêm vào cuối $C$
* Số nào được lấy thì tăng biến con trỏ ở đó lên một đơn vị

Độ phức tạp $O(|A| + |B|)$. (Tối ưu hơn việc dùng sort với hằng số là log)

## Find MEX

Vì bị cấm map để đếm phân phối nên ở đây ta sẽ chỉ đơn thuần là sort bằng quicksort và tìm ```mex``` từ $0$ lên, nếu $A_i$ bằng ```mex``` thì tăng ```mex``` lên một đơn vị.

## Point2D (template)

Có thể code giống như bài Point3D nhưng ở đây còn có thể dùng pair thay cho struct để tận dụng các phép so sánh đã định nghĩa sẵn, đảo dấu (*-1) của giá trị nào muốn sắp xếp giảm dần.

## VU33_MaxStr

Note: bài này test bị sai so với yêu cầu đề bài là tạo **XÂU** lớn nhất, còn trong test chấm đáp án là tạo **SỐ** lớn nhất.

3 Code:
* DSA2_VU33_MaxStr.cpp: tạo **SỐ** lớn nhất (AC full)
* DSA2_VU33_MaxStr_.cpp: là code trâu tạo **XÂU** lớn nhất (WA 3, TLE 14)
* DSA2_VU33_MaxStr_real.cpp: code chuẩn tạo **XÂU** lớn nhất (WA 5 test).

Sinh test:
input: 44422

Nếu cần tạo **SỐ** lớn nhất thì đáp án là 4422 (là output của DSA2_VU33_MaxStr.cpp là code full)

Nếu theo yêu cầu đề bài là tạo **XÂU** lớn nhất thì đáp án phải là "444" (là output của DSA2_VU33_MaxStr_.cpp là code WA 5 test), vì ở vị trí thứ 3 kí tự '4' > '2' nên đáp án này tối ưu hơn.

Solution chung là sắp xếp lại xâu theo thứ tự giảm dần để đạt được giá trị lớn nhất, sau đó xóa đi các kí tự nhỏ nhất có thể để tổng chia hết cho 3. Nếu tổng đã chia hết cho 3 thì in ra đáp án, còn nếu không thì:
* Xâu lớn nhất: có thể xóa đi 1 số nhỏ nhất có cùng số dư khi mod 3 với tổng, hoặc xóa đi 2 số nhỏ nhất khác số dư (và khác 0) khi mod 3 với tổng. Xét theo thứ tự ưu tiên từ 1 đến 9, dùng mảng đếm phân phôi để tiện thao tác.
* Số lớn nhất: khác với việc tạo xâu lớn nhất, việc tạo số lớn nhất còn phụ thuộc vào độ dài, không thể ưu tiên giữ lại kí tự lớn hơn mà làm cho độ dài bị ngắn lại như cách trên, nên thứ tự ưu tiên không phải là duyệt từ 1 dến 9 mà là từ cách xóa 1 số đến cách xóa 2 số, việc xóa thì tương tự như trên.

## VQ44_FLOWERS(template)

Giống với Assignment 1 nhưng dùng quicksort.

## Kiểm Kê

Sắp xếp lại và đếm số vị trí kề nhau khác nhau cộng thêm 1

## MergeSort

## InsertionSort

## BubbleSort

## SelectionSort