Hướng dẫn cho LQDOJ CUP 2022 - Round 4 - COMPRESS
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors: ,
Subtask \(1\) (\(20\%\) số điểm): \(k = 2\), \(n \leq 5000\) và tổng giá trị \(n\) trong các test không vượt quá \(5000\).
Tutorial
Nhận thấy: Vì \(n\) rất lớn nên không thể nào duyệt qua \(n!\) hoán vị và kiểm tra được.
Ta buộc phải suy luận ra tập các hoán vị thỏa mãn từ dãy \(s\) đã cho.
Nếu biết được \(p_1\) thì sẽ có \(p_2 = s_1-p_1\). Từ đó có \(p_3 = s_2-p_2\). Cứ như vậy sẽ tính được toàn bộ \(p\) bằng công thức \(p_{i+1} = s_i - p_i\).
Ta duyệt qua \(O(n)\) giá trị của \(p_1\), sau đó lại tốn \(O(n)\) phép tính để tính các giá trị của \(p\).
Lọc ra được tối đa \(n\) hoán vị thỏa mãn (có các giá trị nằm trong phạm vi \([1,n]\)). Vì tất cả đều có \(p_1\) khác nhau nên chi phí so sánh là \(O(1)\) và ta dễ xác định được hoán vị thứ \(x\)
Độ phức tạp: \(\mathcal{O}(n^2)\)
Solution
#include <bits/stdc++.h>
using namespace std;
int numTest;
int n, k;
long long x;
vector<int> s;
bool check(vector<int> p) {
vector<bool> mark(n + 1, false);
for (int i = 1; i <= n; i++) {
if (p[i] < 1 or p[i] > n) return false;
if (mark[p[i]]) return false;
mark[p[i]] = true;
}
return true;
}
void subtask1() {
vector<int> p(n + 1); // 1-based index
int cnt = 0;
for (p[1] = 1; p[1] <= n; p[1]++) {
for (int i = 2; i <= n; i++) {
p[i] = s[i - 1] - p[i - 1];
}
if (check(p)) {
if ((++cnt) == x) {
for (int i = 1; i <= n; i++) {
cout << p[i] << " \n"[i == n];
}
return;
}
}
}
cout << "-1\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("COMPRESS.inp", "r", stdin);
freopen("COMPRESS.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> k >> x;
s.resize(n - k + 1 + 1);
for (int i = 1; i <= n - k + 1; i++) {
cin >> s[i];
}
subtask1();
}
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): \(k = 2\), \(n \leq 100000\) và tổng giá trị \(n\) trong các test không vượt quá \(100000\).
Tutorial
Quá trình tính \(p\) ở subtask trên có thể rút thành nhận xét như sau: "Với \(k = 2\), với \(p_1\) cố định thì ta xác định được toàn bộ \(p\)"
Cụ thể hơn, toàn bộ dãy \(p\) đều có thể biểu diễn theo \(p_1\).
Thật vậy:
- \(p_2 = s_1-p_1\)
- \(p_3 = s_2-p_2 = s_2-(s_1-p_1) = p_1-s_2+s_1\)
- \(p_4 = s_3-p_3 = -p_1+s_3+s_2-s_1\)
- \(\dots\)
Các số \(p_i\) có dạng \(p_i = -p_1 + c\) hoặc \(p_i = p_1 + c\) với \(c\) là hằng số nào đó. Cụ thể: nếu \(i\) chẵn thì sẽ có dạng \(-p_1 + c\), nếu \(i\) lẻ sẽ có dạng \(p_1 + c\).
Như vậy giá trị \(1\) (GTNN) chỉ có một trong hai dạng như trên. Dù ở dạng nào thì các giá trị \(c\) trong mỗi dạng đó đều phân biệt (vì nếu không sẽ tồn tại \(p_i = p_j\) với \(i \neq j\)). Do đó dù giá trị \(1\) ở dạng nào thì phải có \(1 = \pm p_1 + c\) với \(c\) nhỏ nhất. Từ đó xác định được toàn dãy \(p\).
Độ phức tạp: \(\mathcal{O}(n)\)
Solution
#include <bits/stdc++.h>
using namespace std;
int numTest;
int n, k;
long long x;
vector<int> s;
bool check(vector<int> p) {
vector<bool> mark(n + 1, false);
for (int i = 1; i <= n; i++) {
if (p[i] < 1 || p[i] > n) {
return false;
}
if (mark[p[i]]) {
return false;
}
mark[p[i]] = true;
}
return true;
}
void calculateP(vector<int>& p) {
for (int i = 2; i <= n; i++) {
p[i] = s[i - 1] - p[i - 1];
}
}
void subtask2() {
if (x > 2) {
cout << "-1\n";
return ;
}
vector<int> sign(n + 1), c(n + 1); // tính dấu và hệ số c trong biểu diễn của p_i
sign[1] = +1;
c[1] = 0;
for (int i = 2; i <= n; i++) {
sign[i] = -sign[i - 1];
c[i] = -c[i - 1] + s[i - 1]; // p[i] = s[i-1] - p[i-1] = s[i-1] - (sign[i-1] * p[1] + c[i-1])
if (abs(c[i]) >= 2 * n) {
cout << "-1\n";
return;
}
}
vector<vector<int>> candidates;
for (int r = 0; r <= 1; r++) {
int minC = 2 * n;
for (int i = 2 - r; i <= n; i += 2) {
if (c[i] == minC) {
cout << "-1\n";
return;
}
minC = min(minC, c[i]);
}
vector<int> p(n + 1);
// 1 = sign * p[1] + minC
p[1] = (1 - minC) / sign[2 - r];
calculateP(p);
if (check(p)) {
candidates.push_back(p);
}
}
if (x > (int)candidates.size()) {
cout << "-1\n";
return;
}
sort(candidates.begin(), candidates.end());
auto p = candidates[x - 1];
for (int i = 1; i <= n; i++) {
cout << p[i] << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("COMPRESS.inp", "r", stdin);
freopen("COMPRESS.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> k >> x;
s.resize(n - k + 1 + 1);
for (int i = 1; i <= n - k + 1; i++) {
cin >> s[i];
}
subtask2();
}
return 0;
}
Subtask \(3\) (\(30\%\) số điểm): \(k = 3\), \(n \leq 100000\) và tổng giá trị \(n\) trong các test không vượt quá \(100000\).
Tutorial
Tương tự như trên, nếu biết được \(p_1, p_2\) ta sẽ biết được toàn bộ \(p\).
Ta biểu diễn các giá trị của \(p\) bởi \(p_1, p_2\) và \(p_3\).
\(p_i = s_{i-2} - p_{i-2} - p_{i-1} = s_{i-2} - (p_{i-2}+p_{i-1}+p_{i-3}) +p_{i-3} = p_{i-3} - s_{i-3} + s_{i-2}\).
Do đó:
- \(p_4 = p_1 - s_1 + s_2\)
- \(p_5 = p_2 - s_2 + s_3\)
- \(p_6 = p_3 - s_3 + s_4\)
- \(p_7 = p_4 - s_4 + s_5 = p_1 - s_1 + s_2 - s_4 + s_5\)
- \(\dots\)
Vậy mỗi số chỉ có dạng \(p_1 + c, p_2 + c\) hoặc \(p_3 + c\).
Giả sử \(1=p_j+c (1\le j\le3)\). Lúc này, bài toán đưa về như subtask 2. Đó là bởi vì đã tính được \(p_j = 1-c\) nên mọi số có dạng \(p_i + c (i \equiv j \mod 3)\) đều tính được. Lúc này, trong \(p\), cứ 3 số liên tiếp thì ta biết được giá trị của đúng một số.
Chỉ cần biết thêm giá trị của \(p_i (i \neq j, 1 \le i \le 3)\) nữa thì xác định được toàn bộ \(p\). Nói cách khác, tất cả những số còn lại đều có thể biểu diễn theo \(p_i\) (có dạng \(p_i+c\) hoặc \(-p_i+c\) như đã phân tích ở trên). Lưu ý rằng GTNN lúc này không phải là \(1\) nữa mà là một giá trị chưa xuất hiện trong các số có dạng \(p_j + c\) mà ta vừa tính được.
Độ phức tạp: \(\mathcal{O}(n)\)
Hướng dẫn cài đặt
Giả sử trong lúc thi bạn chỉ có thể nghĩ tới subtask 3, vậy phải code như thế nào để nhanh & gọn & chính xác nhất để ăn được 30% số điểm? Sau đây là một số gợi ý:
- Tạo hàm
fillNumber(r,vmin)để điền vào tất cả những vị trí chia \(3\) dư \(r\), mà giá trị nhỏ nhất chưa điền là vmin. Sẽ có \(3 \times 2 = 6\) cách điền khác nhau. - Hướng khác (không khuyến cáo): sử dụng lại code sub 2.
Hướng 2
Giả sử \(1\) có dạng \(p_j + c\), vậy tất cả số khác có dạng này đều xác định. Tiếp tục sử dụng logic của subtask 2 để điền vào những vị trí còn lại.
Muốn được như vậy thì hàm subtask2() cần sửa một số điểm như sau:
- nhận vào tham số
vminlà giá trị nhỏ nhất chưa điền ở trong các số có dạng \(p_j + c\). Việc tính \(p_1\) dùng giá trị vmin này thay vì số \(1\)p[1] = (1 - minC) / sign[2-r];(đoạn code cũ) - tạo ra những mảng \(p',s'\) mới (bỏ đi những vị trí đã xác định) để đưa về bài toán với \(k=2\) giống hệt như subtask 2, tránh phải sửa code quá nhiều (vì cách code này dựa trên tinh thần kế thừa code cũ, giả sử bạn đang có code subtask 2 và muốn tận dụng nó cho subtask 3).
- và do đó, hàm
subtask2()phải tính toán, xử lý trên những mảng \(p,s\) cục bộ (truyền tham số vào hàm)
Solution - Hướng 1
#include <bits/stdc++.h>
using namespace std;
int numTest;
int n, k;
long long x;
vector<int> s;
vector<int> p, c; // p: hoán vị, c: hệ số cộng vào
int minC[3];
void fillNumber(int r, int vmin) {
int sta = r ? r : 3;
p[sta] = vmin - minC[r];
for (int i = sta; i <= n; i += 3) {
p[i] = p[sta] + c[i];
}
}
int findMinval() {
vector<bool> mark(n + 1, false);
for (int i = 1; i <= n; i++) {
mark[p[i]] = true;
}
for (int v = 1; v <= n; v++) {
if (!mark[v]) {
return v;
}
}
return -1;
}
bool check() {
vector<bool> mark(n + 1, false);
for (int i = 1; i <= n; i++) {
if (p[i] < 1 or p[i] > n) {
return false;
}
if (mark[p[i]]) {
return false;
}
mark[p[i]] = true;
}
return true;
}
void subtask3() {
c.assign(n + 1, 0);
for (int i = 4; i <= n; i++) {
c[i] = c[i - 3] - s[i - 3] + s[i - 2];
if (abs(c[i]) >= n) {
cout << "-1\n";
return;
}
}
for (int r = 0; r < 3; r++) {
minC[r] = n;
for (int i = r ? r : 3; i <= n; i += 3) {
minC[r] = min(minC[r], c[i]);
}
}
vector<vector<int>> candidates;
for (int j = 0; j < 3; j++) {
for (int r = 0; r < 3; r++)
if (r != j) {
p.assign(n + 1, 0);
fillNumber(j, 1);
fillNumber(r, findMinval());
fillNumber((0 + 1 + 2) - (j + r), findMinval());
if (check() && (p[1] + p[2] + p[3] == s[1])) candidates.push_back(p);
}
}
sort(candidates.begin(), candidates.end());
if (x > candidates.size()) {
cout << "-1\n";
return;
}
p = candidates[x - 1];
for (int i = 1; i <= n; i++) {
cout << p[i] << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("COMPRESS.inp", "r", stdin);
freopen("COMPRESS.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> k >> x;
s.resize(n - k + 1 + 1);
for (int i = 1; i <= n - k + 1; i++) {
cin >> s[i];
}
subtask3();
}
return 0;
}
Solution - Hướng 2
#include <bits/stdc++.h>
using namespace std;
const vector<vector<int>> nothing;
int numTest;
int n, k;
long long x;
vector<int> s;
bool check(int n, const vector<int>& p) {
vector<bool> mark(n + 1, false);
for (int i = 1; i <= n; i++) {
if (p[i] < 1 or p[i] > n) {
return false;
}
if (mark[p[i]]) {
return false;
}
mark[p[i]] = true;
}
return true;
}
vector<vector<int>> subtask2(int n, vector<int> s, int vmin = 1) {
auto calculateP = [&](vector<int>& p) {
for (int i = 2; i < p.size(); i++) {
p[i] = s[i - 1] - p[i - 1];
}
};
vector<int> p(n + 1), sign(n + 1), c(n + 1); // hoán vị, dấu và hệ số c
sign[1] = +1;
c[1] = 0;
for (int i = 2; i <= n; i++) {
sign[i] = -sign[i - 1];
c[i] = -c[i - 1] + s[i - 1];
}
vector<vector<int>> candidates;
for (int r : {0, 1}) {
int minC = 3e5;
for (int i = 2 - r; i <= n; i += 2) {
if (c[i] == minC) {
return nothing;
}
minC = min(minC, c[i]);
}
vector<int> p(n + 1);
p[1] = (vmin - minC) / sign[2 - r];
calculateP(p);
candidates.push_back(p);
}
return candidates;
}
void subtask3() {
vector<int> p(n + 3), c(n + 1);
s.resize(s.size() + 3);
for (int i = 4; i <= n; i++) {
c[i] = c[i - 3] - s[i - 3] + s[i - 2];
if (abs(c[i]) >= n) {
cout << "-1\n";
return;
}
}
vector<vector<int>> candidates;
for (int r = 0; r < 3; r++) { // dùng chữ 'r' thay vì 'j'
int minC = n, sta = r ? r : 3;
for (int i = sta; i <= n; i += 3) {
minC = min(minC, c[i]);
}
fill(p.begin(), p.end(), 0);
p[sta] = 1 - minC;
for (int i = sta; i <= n; i += 3) {
p[i] = p[sta] + c[i];
}
int siz = 0;
vector<int> s2;
s2.push_back(0);
for (int i = 1, j = sta; i <= n; i++) {
if (i % 3 == r) {
j = i + 3;
continue;
}
++siz;
int si = s[i] - p[j];
if (i > 1 && j == i + 2) {
si = s[i - 1] - p[i - 1];
}
s2.push_back(si);
}
int vmin = -1;
vector<bool> mark(n + 1, false);
for (int i = sta; i <= n; i += 3) {
mark[p[i]] = true;
}
for (int v = 1; v <= n; v++) {
if (!mark[v]) {
vmin = v;
break;
}
}
auto get = subtask2(siz, s2, vmin);
for (auto p2 : get) {
for (int i = 1, j = 1; i <= n; i++) {
if (i % 3 != r) {
p[i] = p2[j++];
}
}
if (check(n, p)) {
candidates.push_back(p);
}
}
}
sort(candidates.begin(), candidates.end());
if (x > candidates.size()) {
cout << "-1\n";
return;
}
p = candidates[x - 1];
for (int i = 1; i <= n; i++) {
cout << p[i] << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("COMPRESS.inp", "r", stdin);
freopen("COMPRESS.out", "w", stdout);
cin >> numTest;
while (numTest--) {
cin >> n >> k >> x;
s.assign(n - k + 1 + 1, 0);
for (int i = 1; i <= n - k + 1; i++){ cin >> s[i];}
subtask3();
}
return 0;
}
Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Để ý rằng: \(s_{i+1} - s_i = p_{i+k} - p_i (1)\).
Tổng quát hóa nhận xét ở subtask 2: "Nếu có \(k-1\) giá trị đầu tiên của \(p\) thì xác định được toàn dãy \(p\)" \(( * )\)
Hiển nhiên là không thể duyệt trong ĐPT \(O(n^k)\). Ta cần phải có cách hiệu quả để lấy ra được các hoán vị.
Nhận xét: Ta chia \(n\) vị trí trong \(p\) thành \(k\) nhóm, mỗi nhóm gồm những vị trí \(i\) đồng dư \(\mod k\).
Nếu biết được giá trị của phần tử bất kì trong nhóm, ta xác định được toàn bộ nhóm đấy, vì \(s\) đã cho thông tin về hiệu \(p_{i+k} - p_i \forall i+k \le n\).
Vậy \(( * )\) có thể tổng quát hơn thành \(k\) vị trí có số dư cho \(k\) khác nhau chứ không hẳn chỉ là những vị trí đầu tiên.
Kí hiệu \(m_j\) là vị trí số nhỏ nhất trong nhóm thứ \(j\).
Không mất tính tổng quát, giả sử có \(p_{m_1} < p_{m_2} < p_{m_3} < \dots < p_{m_k}\). Khi đó \(p\) có thể được xác định duy nhất như sau: Ta tiến hành điền lần lượt các giá trị vào các vị trí trong \(p\)
- Duy trì tập \(S\) các giá trị chưa dùng để điền. Lúc đầu \(S = \{1,2,3,\dots,n\}\)
- Mỗi lần điền, ta sẽ điền cho toàn bộ nhóm \(j\) nào đó. Duyệt tăng dần theo \(p_{m_j}\) (theo \(j\) trong TH này). Vì duyệt tăng dần nên vị trí \(m_j\) phải nhận giá trị bé nhất. Gán \(p_{m_j} = \min S\) và xóa giá trị này ra khỏi tập \(S\).
- Xác định giá trị cho mỗi vị trí trong nhóm \(j\): Giả sử phải có \(p_i = x\)
- Nếu \(x \in S\) thì gán \(p_i = x\) và xóa \(x\) khỏi \(S\)
- Ngược lại, hoán vị đang dựng không thỏa mãn.
Vì \(p\) là hoán vị, lại có \(m_j\) phân biệt nên khi ta so sánh các \(p_{m_j}\) sẽ có \(k!\) trường hợp khác nhau.
So sánh hai hoán vị bằng \(k\) giá trị đầu tiên.
Độ phức tạp: \(\mathcal{O}(k!n)\)
\((1):\) Lưu ý, để thỏa mãn hoán vị tạo ra có tổng các phần tử liên tiếp là dãy \(s\), cần phải kiểm tra xem tổng của \(k\) số đầu tiên có bằng đúng \(s_1\) hay không. Lí do là vì ta chỉ xây dựng hoán vị thỏa mãn ràng buộc về hiệu giữa các \(s\).
Tutorial của anh
Ta có \(P[i + k] - P[i] = S[i + 1] - S[i]\)
Từ đó ta có với mọi \(i\), ta có thể biểu diễn \(P[i] = P[j] + x[i]\) (với \(j = 1..k\)), với \(x[i]\) là một giá trị tính được. Rõ ràng hơn thì nếu ta biết được \(k\) giá trị đầu tiên của \(P\) thì có thể tính cả mảng \(P\).
Khi đó ta sẽ có \(k\) nhóm phần tử của \(P\), lần lượt là các nhóm tính được giá trị từ \(P_1, P_2,..., P_k\). Gọi các nhóm đó là là \(G_1, G_2, ..., G_k\)
Với mỗi nhóm này, nếu biết giá trị một phần tử bất kỳ trong nhóm ta sẽ biết hết giá trị cả nhóm
Gọi \(M_i\) là giá trị nhỏ nhất của nhóm \(G_i\). Với mội thứ tự giá trị của \(M_1, M_2, ..., M_k\). Ta sẽ xác định được các nhóm
Ví dụ như \(M_2\) là nhỏ nhất trong \(M\), khi đó phần tử nhỏ nhất của \(M_2\) là \(1 \Rightarrow\) tìm được nhóm \(G_2\)
\(M_3\) là nhỏ thứ 2 trong \(M\), khi đó \(M_3\) là phần tử nhỏ nhất trong các phần tử còn lại của hoán vị \(\Rightarrow\) tìm được nhóm \(G_3\),
\(\ldots\)
Khi đó thuật sẽ là xét \(k!\) các hoán vị thứ tự của \(M\). Từ đó sẽ kiểm tra hoán vị thứ tự của \(M\) đó có thỏa mãn hay không trong \(O(n)\). Bằng cách đó ta có thể tìm được tất cả các hoán vị thỏa mãn
Mỗi hoán vị thỏa mãn ta không cần lưu toàn bộ cả hoán vị để so sánh. Ta chỉ cần lưu \(k\) phần tử đầu tiên là đủ
Độ phức tạp: \(\mathcal{O}(k! \times N )\)
Solution
#include <bits/stdc++.h>
using namespace std;
int numTest;
int n, k;
long long x;
vector<int> s;
void subtask4() {
int maxCount = 1;
for (int i = 2; i <= k; i++) {
maxCount *= i;
}
if (x > maxCount) {
cout << "-1\n";
return;
}
vector<int> dif(n + 1), c(n + 1);
for (int i = 1; i + k <= n; i++) {
if (abs(c[i]) >= n) {
cout << "-1\n";
return;
}
dif[i] = s[i + 1] - s[i];
c[i + k] = c[i] + dif[i];
}
vector<int> order(k);
iota(order.begin(), order.end(), 1);
vector<vector<int>> candidates;
do {
vector<bool> mark(n + 1, false);
vector<int> p(n + 1);
auto valid = [&](int v) {
bool res = 1 <= v && v <= n && !mark[v];
mark[v] = true;
return res;
};
int minVal = 1;
bool failed = false;
for (int j = 0; j < k and !failed; j++) {
int sta = order[j];
while (mark[minVal]) {
++minVal;
}
int minC = 2 * n;
for (int i = sta; i <= n; i += k) {
minC = min(minC, c[i]);
}
p[sta] = minVal - minC;
if (!valid(p[sta])) {
failed = true;
}
for (int i = sta + k; i <= n; i += k) {
p[i] = p[sta] + c[i];
if (!valid(p[i])) {
failed = true;
break;
}
}
}
int s1 = 0;
for (int i = 1; i <= k; i++) {
s1 += p[i];
}
if (s1 != s[1]) {
failed = true;
}
if (!failed) {
candidates.push_back(vector<int>(p.begin(), p.begin() + k + 1));
}
} while (next_permutation(order.begin(), order.end()));
sort(candidates.begin(), candidates.end());
if (x > candidates.size()) {
cout << "-1\n";
return;
}
auto p = candidates[x - 1];
p.resize(n + 1);
for (int i = 1; i <= n; i++) {
if (i > k) {
p[i] = p[i - k] + dif[i - k];
}
cout << p[i] << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("COMPRESS.inp", "r", stdin);
freopen("COMPRESS.out", "w", stdout);
cin >> numTest;
while (numTest-- > 0) {
cin >> n >> k >> x;
s.resize(n - k + 1 + 1);
for (int i = 1; i <= n - k + 1; i++) {
cin >> s[i];
}
subtask4();
}
return 0;
}
Bình luận (1)