Hướng dẫn cho COLORBOX (OLP MT&TN 2023 Sơ Loại Không Chuyên)
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): \(n \leq 10^{2}\).
Tutorial
Với \(n\) nhỏ, ta có thể duyệt qua tất cả các cách chọn đoạn \([l, r]\) và kiểm tra dãy sau khi xóa có phân biệt hay không. Lưu ý trường hợp kết quả bằng \(0\).
Độ phức tạp: \(\mathcal{O}(n^{3})\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005;
int n;
int a[MAX_N];
bool check[MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int index = 1; index <= n; index++) {
cin >> a[index];
}
int answer = 0;
for (int index = 1; index <= n; index++) {
if (check[a[index]]) {
answer = n;
break;
}
check[a[index]] = true;
}
for (int left = 1; left <= n; left++) {
for (int right = left; right <= n; right++) {
for (int index = 1; index <= n; index++) {
check[a[index]] = false;
}
bool flag = true;
for (int index = 1; index < left; index++) {
if (check[a[index]]) {
flag = false;
break;
}
check[a[index]] = true;
}
for (int index = right + 1; index <= n; index++) {
if (check[a[index]]) {
flag = false;
break;
}
check[a[index]] = true;
}
if (flag) {
answer = min(answer, right - left + 1);
}
}
}
cout << answer;
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
Tutorial
Ta sẽ cố định \(l\) và duyệt \(r\) tăng tăng dần từ từ. Với mỗi cách chọn \([l,r]\), ta sẽ duy trì một biến \(dup\) là số lượng giá trị khác nhau bị lặp. Ví dụ dãy \(\{1; 3; 4;2\}\) có \(dup = 0\), dãy \(\{2; 2; 3; 3\}\) có \(dup = 2\). Dễ thấy cách chọn đoạn \([l, r]\) là thỏa mãn khi \(dup\) của dãy tạo bởi đoạn \([1, l - 1] \cap [r + 1, n]\) là bằng \(0\). Vậy ta sẽ cập nhật \(dup\) như thế nào? Khi thêm xóa một phần tử vào dãy đang xét, ta biết \(dup\) sẽ tăng khi và chỉ khi số lượng phần tử có giá trị bằng với giá trị của phần tử vừa thêm vào là đúng bằng \(2\). Tương tự, \(dup\) sẽ giảm khi và chỉ khi ta xóa một phần tử và số lượng phần tử có giá trị bằng với giá trị phần tử vừa xóa là đúng bằng \(1\). Với các nhận xét trên, ta có thể cài đặt hai hàm add(x) và del(x) để mô phỏng hai quá trình thêm và xóa phần tử.
Độ phức tạp: \(\mathcal{O}(n^{2})\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005;
int n;
int a[MAX_N], cnt[MAX_N];
int duplicate;
void add(int value) { duplicate += (++cnt[value] == 2); }
void del(int value) { duplicate -= (--cnt[value] == 1); }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int index = 1; index <= n; index++) {
cin >> a[index];
}
int answer = 0;
for (int index = 1; index <= n; index++) {
if (cnt[a[index]]) {
answer = n;
break;
}
cnt[a[index]]++;
}
for (int left = 1; left <= n; left++) {
duplicate = 0;
for (int index = 1; index <= n; index++) {
cnt[index] = 0;
}
for (int index = 1; index <= n; index++) {
add(a[index]);
}
for (int right = left; right <= n; right++) {
del(a[right]);
if (duplicate == 0) {
answer = min(answer, right - left + 1);
}
}
}
cout << answer;
return 0;
}
Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^{5}\).
Tutorial
Ta nhận xét rằng nếu tồn tại một phương án chọn đoạn \([l, r]\) có độ dài là \(len\) thì chắc chắn tồn tại ít nhất một phương án chọn đoạn có độ dài là \(len + 1, len + 2, \ldots\). Do đó ta có thể áp dụng chặt nhị phân để tìm kết quả. Với mỗi giá trị \(mid\), ta sẽ kiểm tra các cách xóa đoạn có độ dài \(mid\) có tạo dãy phân biệt hay không. Ta có thể kiểm tra trong \(\mathcal{O}(n)\) bằng kỹ thuật Sliding Window - duyệt các đoạn dần dần từ trái sang phải kết hợp với hai hàm add(x)và del(x) đã được đề cập ở subtask 2.
Độ phức tạp: \(\mathcal{O}(n \times log_{2}(n))\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005;
int n;
int a[MAX_N], cnt[MAX_N];
int duplicate = 0;
void add(int value) { duplicate += (++cnt[value] == 2); }
void del(int value) { duplicate -= (--cnt[value] == 1); }
bool check(int len) {
for (int index = 1; index <= n; index++) {
cnt[index] = 0;
}
duplicate = 0;
for (int index = 1; index <= n; index++) {
add(a[index]);
}
for (int index = 1; index <= len; index++) {
del(a[index]);
}
if (duplicate == 0) {
return true;
}
for (int left = 2; left + len - 1 <= n; left++) {
add(a[left - 1]);
del(a[left + len - 1]);
if (duplicate == 0) {
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int index = 1; index <= n; index++) {
cin >> a[index];
}
int answer = 0;
for (int index = 1; index <= n; index++) {
if (cnt[a[index]]) {
answer = n;
break;
}
cnt[a[index]]++;
}
int left = 1, right = n;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
answer = min(answer, left);
cout << answer;
return 0;
}
Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Thừa hưởng ý tưởng từ subtask 2, ta có nhận xét rằng khi \(l\) càng tăng thì \(r\) tối ưu cũng sẽ tăng dần. Do đó ta có thể áp dụng kỹ thuật Two Pointer và tương tự áp dụng hai hàm add(x) và del(x) đã được đề cập trong subtask 2.
Độ phức tạp: \(\mathcal{O}(n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005;
int n;
int a[MAX_N], cnt[MAX_N];
int duplicate = 0;
void add(int value) { duplicate += (++cnt[value] == 2); }
void del(int value) { duplicate -= (--cnt[value] == 1); }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int index = 1; index <= n; index++) {
cin >> a[index];
}
for (int index = 1; index <= n; index++) {
add(a[index]);
}
del(a[1]);
int right = 1, answer = n;
for (int left = 1; left <= n; left++) {
while (right < n && duplicate > 0) {
del(a[++right]);
}
if (duplicate == 0) {
answer = min(answer, right - left + 1);
}
add(a[left]);
}
cout << answer;
return 0;
}
Bình luận