# TST 2024

## Day 1

### Problem 1: MOUSE

_Time limit: 2s._

Đây là một bài thuộc dạng interactive. Bạn phải thêm thư viện "mouselib.h" vào chương trình của mình. Điều này cũng có nghĩa bạn chỉ có thể giải được bài này bằng C++. Lưu ý là trình chấm cho bài này không adaptive.

Cho ba số nguyên dương $N$, $M$, $T$. Có $N$ hũ gạo được đặt trên một đường thẳng và được đánh số từ $1$ đến $N$. Có $M$ con chuột trong những hũ gạo trên. Có đúng một trong $N$ hũ gạo trên là tổ chuột. Alice và Bob rất muốn tiêu diệt chuột trong nhà mình, vậy nên bạn cần giúp họ làm điều đó nhanh nhất có thể. Mỗi ngày, họ có thể làm những thao tác sau:

- _pick i_: Alice yêu cầu Bob tiêu diệt hết chuột ở hũ gạo $i$. Tuy nhiên, nếu hũ gạo thứ $i$ là tổ chuột, thì không con chuột nào bị tiêu diệt cả. Gọi $k$ là số lần thao tác _pick_ được gọi. Sau khi Bob đã xong việc tiêu diệt chuột ở hũ gạo thứ $i$, nếu $T | k$, tất cả những con chuột không nằm trong tổ sẽ nhảy qua một hũ gạo liền kề . Ví dụ: nếu con chuột đang ở hũ gạo thứ $j$, nó có thể nhảy qua hũ gạo $j+1$ hoặc $j-1$. Nếu một con chuột đang ở trong hũ gạo thứ $1$ hoặc $N$, thì chúng chỉ có một cách nhảy. Lưu ý rằng xác suất để một con chuột nhảy sang trái không nhất thiết phải là $50$%.
- _check S_: Alice yêu cầu Bob tới những hũ gạo có chỉ số nằm trong tập $S$, và thu thập mẫu không khí ở đó để xác định xem liệu có tồn tại chuột trong những hũ gạo đấy hay không. Tuy nhiên, vì việc phân tích tốn rất nhiều thời gian, nên bạn chỉ có thể biết kết quả sau $N$ ngày. Tức là nếu bạn sử dụng thao tác _check_ ở ngày $t$, bạn chỉ có thể biết được kết quả ở ngày $t + N$. Lưu ý rằng kể cả khi ta không thể tiêu diệt chuột trong tổ bằng thao tác _pick_, ta vẫn có thể xác nhận được sự tồn tại của chuột bằng thao tác _check_.

- _receive_: Vào cuối mỗi ngày, Bob sẽ thông báo lại cho Alice một cặp số nguyên: {số con chuột mới tiêu diệt được hôm nay, kết quả khảo sát của $N$ ngày trước}. Lưu ý rằng nếu $N$ ngày trước không sử dụng thao tác _check_, số thứ hai sẽ là $-1$.

Bạn phải sử dụng thao tác _receive_ để có thể chuyển sang ngày mới, và bạn sẽ không thể thực hiện quá một thao tác (không tính _receive_) trong cùng một ngày.

Bạn phải tìm ra tổ chuột, hoặc thông báo rằng không còn con chuột nào. Bạn chỉ có thể sử dụng thao tác _receive_ không quá $192$ lần.

:::spoiler Bạn sẽ phải cài đặt những hàm sau:
~~~~~cpp
int solve(int N, int M, int T);
~~~~~
Hàm này được gọi tối đa $1000$ lần mỗi test case.
Trả về vị trí tổ chuột. Nếu không còn chuột, bạn được phép trả về $-1$.
:::

:::spoiler Thư viện sẽ cung cấp cho bạn những hàm sau:
~~~~~cpp
void pick(int i);
~~~~~
Tiêu diệt hết chuột ở hũ gạo thứ $i$.
~~~~~cpp
void check(const std::vector<int> &S); // Checking if there are at least one box in S containing mice.
~~~~~
Kiểm tra xem có tồn tại ít nhất một hũ gạo trong tập $S$ có chuột hay không.
~~~~~cpp
pair<int, int> receive();
~~~~~
Gọi hàm này để bắt đầu một ngày mới.
Trả về hai giá trị: {số con chuột mới tiêu diệt được hôm nay, kết quả khảo sát của $N$ ngày trước}.

:::

:::spoiler Sample code:
~~~~~cpp
#include <bits/stdc++.h>
#include "mouselib.h"
int solve(int N, int M, int T){
pick(rand() % n + 1);
receive();
std::vector<int> S = {1};
check(S);
for(int i = 0; i<n;++i) receive();
if (receive().second == 0) return -1;
return (rand() % n + 1);
}
~~~~~

:::

#### Constraint:
- $2 \leq N \leq 63, M \leq 63, T \leq 2$.

#### Scoring

| Subtask | Điểm | Giới hạn |
| -------- | -------- | -------- |
| $1$ | $5$ | $N = 2$ |
| $2$ | $15$ | $N \leq 9$. |
| $3$ | $22$ | Những con chuột sẽ luôn đi về phía bên phải nếu có thể. |
| $4$ | $33$ | $N \leq 62$. |
| $5$ | $25$ | Không có ràng buộc gì thêm. |

### Problem 2: LEXIC

_Time limit: 3,5s._

Đây là một bài thuộc dạng batch (truyền thống). Bạn phải thêm thư viện "lexiclib.h" vào chương trình của mình. Điều này cũng có nghĩa bạn chỉ có thể giải được bài này bằng C++.

Xét một dãy số nguyên $D$ độ dài $N$ . Một xâu kí tự $A$ sẽ tương thích với $D$ nếu với mọi cặp $0 \leq i < j < N$, nếu $j - i \leq max(D_j, D_i)$, thì $A_i \neq A_j$. Lưu ý rằng ta đang đánh số mảng từ $0$.

Gọi $r(\alpha, \delta)$ là số xâu tương thích với $\delta$ mà có thứ tự từ điển **bé** hơn $\alpha$ .

Cedric muốn giải quyết bài toán này: cho một dãy số $\delta$ và hai xâu kí tự $\alpha, \beta$ ($\alpha, \beta$ đều tương thích với $\delta$). Tìm xâu $\gamma$ sao cho $\gamma$ cũng tương thích với $\delta$, và $r(\gamma, \delta) = r(\alpha, \delta) + r(\beta, \delta)$, hoặc chỉ ra rằng $\gamma$ không tồn tại.

Cedric nghĩ bài vẫn còn tương đối đơn giản, nên anh ấy làm bài khó hơn một chút. Cho một số nguyên $N$, một dãy $D$ và hai xâu ký tự $A, B$, tất cả đều có độ dài $N$ và chỉ chứa $k$ chữ cái đầu tiên của bảng chữ cái tiếng Anh. Bạn phải trả lời $Q$ truy vấn có dạng $[l,r]$, đó là tìm $\gamma$ nếu $\delta = D[l..r]$, $\alpha = A[l..r]$, $\beta = B[l..r]$. ($D[l..r]$ là kí hiệu cho dãy con $[D_l, D_{l+1}, ..., D_r]$). Bạn phải cho Cedric biết mã hash của xâu $\gamma$.

:::spoiler Đoạn mã dưới đây mô tả cách hàm hash hoạt động:
~~~~~cpp
int encode(std::string gamma){
#define ll long long
const int MOD = 1e9 + 7;
const int BASE = 26;
ll mul = 1, ans = 0;
for(char c: gamma){
ans = (ans + mul * (c - 'a')) % MOD;
mul = mul * BASE % MOD;
}
return ans;
}
~~~~~
:::

:::spoiler Bạn phải cài những hàm sau:
~~~~~cpp
void prepare(std::string const &A, std::string const &B, std::vector<int> const &D, int K);
~~~~~
Hàm _init_ được gọi $1$ lần mỗi bộ dữ liệu. Bạn dùng hàm này cho phần tiền xử lí.

~~~~~cpp
int query(int l, int r);
~~~~~
Hàm _query_ được gọi $Q$ lần mỗi bộ dữ liệu. Bạn dùng hàm này để trả lời truy vấn.

Trả về giá trị hash của xâu $\gamma$, nếu không tồn tại thì trả lại $-1$.
:::

:::spoiler Sample code:
~~~~~cpp
#include <bits/stdc++.h>
#include "lexiclib.h"
void prepare(std::string const &A, std::string const &B, std::vector<int> const &D, int K){
// This sample code is only for demonstrative purpose.
// It doesnt make any sense.
}

int query(int l, int r){
return -1;
}
~~~~~

:::

#### Constraint:
- $N \leq 200000, Q \leq 500000, k \leq 5$.
- $max(D) \leq N - 1.$
- $|D_i - D_{i+1}| \leq 1, \forall 0 < i < N-1.$

#### Scoring

| Subtask | Điểm | Giới hạn |
| -------- | -------- | -------- |
| $1$ | $6$ | $N \leq 10$. |
| $2$ | $11$ | $N \leq 25$. |
| $3$ | $14$ | $N \leq 600, max(D) = 0$. |
| $4$ | $14$ | $N \leq 600, r(\beta) \leq 10$. |
| $5$ | $16$ | $N \leq 600$. |
| $6$ | $10$ | $max(D) = 0$. |
| $7$ | $14$ | $N \leq 100000, Q \leq 200000$. |
| $8$ | $15$ | Không có ràng buộc gì thêm. |

### Problem 3: TRANSMIT

_Time limit: 2s._

Đây là một bài thuộc dạng two-step. Bạn phải thêm thư viện "transmitlib.h" vào chương trình của mình. Điều này cũng có nghĩa bạn chỉ có thể giải được bài này bằng C++.

Alice có một xâu nhị phân $S$ độ dài $26$, và cô ấy phải mã hóa nó thành một xâu nhị phân $T$ có độ dài không quá $64$ kí tự và gửi cho Bob. Vì hiệu suất truyền tải không tốt, nên một trong những trường hợp sau có thể xảy ra với xâu $T$.

1. $T$ giữ nguyên.
2. Một bit bị xóa khỏi $T$.
3. Một bit được thêm vào $T$. Bit đó có thể là $0$ hoặc $1$.
4. Một bit của $T$ bị đảo (từ $0$ thành $1$, từ $1$ thành $0$).

Từ xâu $T$ (có thể) bị lỗi đó, Bob sẽ phải khôi phục lại xâu $S$ ban đầu.

::: spoiler Bạn phải cài những hàm sau:
~~~~~cpp
string encode(std::string S);
~~~~~
Hàm _encode_ được gọi tối đa $100000$ lần trong mỗi bộ dữ liệu. Bạn sử dụng hàm này để mã hóa $S$ thành $T$.

~~~~~cpp
string decode(std::string T);
~~~~~
Hàm _decode_ được gọi tối đa $100000$ lần trong mỗi bộ dữ liệu. Bạn sử dụng hàm này để giải mã $T$ lại thành $S$.
:::

::: spoiler Sample code:
~~~~~cpp
#include <bits/stdc++.h>
#include "transmitlib.h"
string encode(std::string S){
return S + "0";
}

string decode(std::string T){
return T.substr(0, 26);
}
~~~~~
:::

#### Scoring

| Subtask | Điểm | Giới hạn |
| -------- | -------- | -------- |
| $1$ | $20$ | Chỉ có trường hợp $1$ và $2$ xảy ra với xâu $T$. |
| $2$ | $20$ | Chỉ có $\frac{1}{3}$ bit cuối của $T$ bị ảnh hưởng bởi hiệu suất truyền tin. |
| $3$ | $20$ | Chỉ có $\frac{1}{2}$ bit cuối của $T$ bị ảnh hưởng bởi hiệu suất truyền tin. |
| $4$ | $40$ | Không có ràng buộc gì thêm. |

#### Grading curve

| Trường hợp | Điểm |
| -------- | -------- |
|$38 \leq length(T)$|$5$%|
|$length(T) = 37$|$10$%|
|$length(T) = 36$|$20$%|
|$length(T) = 35$|$30$%|
|$length(T) = 34$|$40$%|
|$length(T) = 33$|$65$%|
|$length(T) = 32$|$100$%|

## Day 2

### Problem 4: CTREE

_Time limit: 1s._

Đây là một bài thuộc dạng batch (truyền thống). Bạn phải thêm thư viện "ctreelib.h" vào chương trình của mình. Điều này cũng có nghĩa bạn chỉ có thể giải được bài này bằng C++.

Cho hai số nguyên $M, K$, bạn phải tìm một cây có gốc có tối đa $2 * K$ đỉnh thỏa mãn tất cả $M$ ràng buộc. $M$ ràng buộc đó có dạng $[s_i, a_i, b_i, c_i, d_i]$ ($a_i \neq b_i, c_i \neq d_i$).

* Nếu $s_i = 1$, tồn tại một con đường xuất phát từ gốc đi qua $f(c_i, d_i)$ rồi mới đi qua $f(a_i, b_i)$ ( $f(c_i, d_i) \neq f(a_i, b_i)$ ).
* Nếu $s_i = 2$, $f(c_i, d_i) = f(a_i, b_i)$.
* Nếu $s_i = 3$, tồn tại một con đường xuất phát từ gốc đi qua cả hai nút $f(c_i, d_i)$ và $f(a_i, b_i)$.
* Nếu $s_i = 4$, không tồn tại một con đường xuất phát từ gốc đi qua cả hai nút $f(c_i, d_i)$ và $f(a_i, b_i)$.

_$f(u, v)$ ở đây là tổ tiên chung gần nhất của hai nút $u$ và $v$._

Dữ liệu đầu vào đảm bảo tồn tại một cây có $K$ nút thỏa mãn cả $M$ điều kiện trên.

:::spoiler Bạn phải cài những hàm sau:
~~~~~cpp
vector<int> solve(int M, int K, const std::vector<int> &s, const std::vector<int> &a, const std::vector<int> &b, const std::vector<int> &c, const std::vector<int> &d);
~~~~~
Hàm này được gọi $T$ lần trong mỗi bộ dữ liệu.
Trả về một dãy P độ dài không quá $2 * K$, miêu tả một cây. Cha của nút $i + 1$ là $P[i]$, nếu nút $i + 1$ là nút gốc thì $P[i] = 0$.
:::

:::spoiler Sample code:
~~~~~cpp
#include <bits/stdc++.h>
#include "ctreelib.h"

vector<int> solve(int M, int K, const std::vector<int> &s, const std::vector<int> &a, const std::vector<int> &b, const std::vector<int> &c, const std::vector<int> &d){
vector<int> ans(K);
for(int i = 1; i < K; ++i) ans[i] = i;
return ans;
}
~~~~~

:::

#### Constraint:
- $\sum M, \sum K \leq 5000, T \leq 1000$. ($\sum M, \sum K$ là tổng $M, K$ của tất cả lần gọi hàm _solve_ trong bộ dữ liệu.)

#### Scoring

| Subtask | Điểm | Giới hạn |
| -------- | -------- | -------- |
| $1$ | $15$ | $M, K \leq 7$, $T \leq 50$. |
| $2$ | $22$ | $M, K \leq 12$, $T \leq 50$ và $s_i = 1$. |
| $3$ | $20$ | $s_i = 1$. |
| $4$ | $24$ | Tồn tại một cây sao cho mỗi nút chỉ có tối đa một con và thỏa mãn cả $M$ ràng buộc. |
| $5$ | $19$ | Không có ràng buộc gì thêm. |

### Problem 5: WORDCOM

_Time limit: 2s._

Đây là một bài thuộc dạng batch (truyền thống). Bạn phải thêm thư viện "wordcomlib.h" vào chương trình của mình. Điều này cũng có nghĩa bạn chỉ có thể giải được bài này bằng C++.

Daniel đang thử nghiệm một cách dạy ghép từ mới cho học sinh cấp 1. Tuy nhiên, thí nghiệm của anh ấy cần một khối lượng tính toán khổng lồ, vì vậy anh ấy đã nhờ đến bạn.

Xét hai danh sách các xâu (gồm các kí tự trong bảng chữ cái tiếng Anh) $\alpha$ và $\beta$. Gọi $\omega(\alpha, \beta)$ là số lượng xâu phân biệt không rỗng Daniel thu được từ việc ghép một tiền tố bất kì của một xâu trong $\alpha$ với một hậu tố bất kì của một xâu trong $\beta$,

Ví dụ, $\omega([$'ab'$], [$'ba', 'c'$]) = 9$, vì Daniel chỉ có thể thu được $9$ xâu phân biệt: ['a', 'ab', 'ba', 'c', 'aa', 'aba', 'abba', 'abc', 'ac'].

Daniel có hai danh sách các xâu (gồm các kí tự trong bảng chữ cái tiếng Anh), $A$ chứa $N$ xâu và $B$ chứa $M$ xâu. Daniel phải trả lời $Q$ câu hỏi có dạng $[rA, uA, rB, uB]$, tức là anh ấy phải xây dựng hai danh sách các xâu $\alpha$ chứa $N$ xâu và $\beta$ chứa $M$ xâu, và tính $\omega(\alpha, \beta)$.

* Để xây dựng $\alpha$, với mỗi $0 \leq i < N$, Daniel làm như sau:
* Đặt $\alpha_i = A_i$.
* Bỏ $rA$ kí tự đầu tiên của $\alpha_i$.
* Trong khi $length(\alpha_i) > uA$, xóa kí tự cuối cùng của $\alpha_i$.
* Để xây dựng $\beta$, với mỗi $0 \leq i < M$, Daniel làm như sau:
* Đặt $\beta_i = B_i$.
* Bỏ $rB$ kí tự cuối cùng của $\beta_i$.
* Trong khi $length(\beta_i) > uB$, xóa kí tự đầu tiên của $\beta_i$.

:::spoiler Bạn phải cài những hàm sau:
~~~~~cpp
std::vector<long long> solve(int N, int M, int Q, const std::vector<std::string> &A, const std::vector<std::string> &B, const std::vector<int> &rA, const std::vector<int> &uA, const std::vector<int> &rB, const std::vector<int> &uB);
~~~~~
Hàm _solve_ được gọi $T$ lần trong mỗi bộ dữ liệu.
Trả về một dãy số nguyên độ dài Q: kết quả cho Q truy vấn trên.
:::

:::spoiler Sample Code:
~~~~~cpp
#include <bits/stdc++.h>
#include "wordcomlib.h"
std::vector<long long> solve(int N, int M, int Q, const std::vector<std::string> &A, const std::vector<std::string> &B, const std::vector<int> &rA, const std::vector<int> &uA, const std::vector<int> &rB, const std::vector<int> &uB){
return std::vector<long long> (Q, 69420);
}
~~~~~

:::

:::warning
_Lưu ý: Mình bịa constraint, chứ mình không nhớ chi tiết lắm._
:::

#### Constraint:
- $T \leq 1000, \sum N, \sum M \leq 200000, \sum Q \leq 400000$.
- $\sum length(A_i), \sum length(B_j) \leq 500000$.

#### Scoring

| Subtask | Score | Constraint |
| -------- | -------- | -------- |
| $1$ | $6$ | $\sum length(A_i), \sum length(B_j) \leq 50, \sum Q \leq 400$. |
| $2$ | $16$ | - $rA, rB \leq 3$. <br>- $\sum length(A_i), \sum length(B_j) \leq 1000, \sum Q \leq 20000$. <br>- $A_i$ chỉ gồm những kí tự từ 'a' đến 'm', $B_i$ chỉ gồm những kí tự từ 'n' đến 'z'. |
| $3$ | $14$ | - $rA, rB \leq 3$. <br>- $A_i$ chỉ gồm những kí tự từ 'a' đến 'm', $B_i$ chỉ gồm những kí tự từ 'n' đến 'z'. |
| $4$ | $18$ | $length(A_i), length(B_j) \leq 1000, \forall i, j, \sum Q \leq 20000$.
| $5$ | $18$ | $\sum length(A_i), \sum length(B_j) \leq 1000$. |
| $6$ | $23$ | $\sum length(A_i) \leq 300000, \sum length(B_j) \leq 1000, \sum Q \leq 60000$ |
| $7$ | $23$ | Không có ràng buộc gì thêm. |