Ad Hoc

Thử nhỏ để thấy quy luật

Có $n$ bóng đèn xếp hàng, đánh số từ 1, ban đầu đều tắt. Ở vòng $k$ ($k = 1, 2, \dots, n$) ta bấm công tắc của mọi bóng có số thứ tự chia hết cho $k$. Sau $n$ vòng có bao nhiêu bóng sáng, với $n$ tới $10^{18}$?

Mô phỏng đúng như đề tốn $n/1 + n/2 + \dots + n/n$ lần bấm, khoảng $12n$ khi $n = 10^5$: được với $n = 10^5$, vô nghĩa với $10^{18}$. Ta chưa vội nghĩ cách nhanh. Việc đầu tiên là viết phiên bản chậm nhưng chắc đúng, chạy cho $n$ nhỏ, rồi nhìn kết quả.

Với $n = 12$, mỗi cột là một bóng, ô tô màu là vòng có bấm bóng đó. Đọc theo cột thì bóng $i$ bị bấm một lần cho mỗi ước của $i$. Bóng sáng khi số lần bấm lẻ, và trong 12 bóng chỉ có 1, 4, 9 thỏa: đều là số chính phương. Giả thuyết: bóng $i$ sáng khi và chỉ khi $i$ là số chính phương.

Chứng minh ngắn: các ước của $i$ ghép thành cặp $(d, i/d)$ với $d \ne i/d$, mỗi cặp góp hai ước nên số ước chẵn. Chỉ khi $i = d^2$, ước $d$ đứng một mình và số ước lẻ. Vậy số bóng sáng là số các số chính phương không vượt $n$, tức $\lfloor \sqrt n \rfloor$. Ký hiệu $\lfloor x \rfloor$ là phần nguyên của $x$, số nguyên lớn nhất không vượt $x$: $\lfloor \sqrt{12} \rfloor = 3$ vì $3^2 \le 12 < 4^2$. Chương trình dưới đối chứng công thức với vét cạn cho mọi $n \le 3000$:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll on[3005];

ll brute(ll n) {
    for (ll i = 1; i <= n; i++) on[i] = 0;
    for (ll k = 1; k <= n; k++)
        for (ll i = k; i <= n; i += k) on[i] = 1 - on[i];
    ll cnt = 0;
    for (ll i = 1; i <= n; i++) cnt += on[i];
    return cnt;
}

ll isqrt(ll n) {
    ll r = sqrtl(n);
    while (r * r > n) r--;
    while ((r + 1) * (r + 1) <= n) r++;
    return r;
}

signed main() {
    bool ok = true;
    for (ll n = 1; n <= 3000; n++)
        if (brute(n) != isqrt(n)) ok = false;
    cout << (ok ? "khớp với mọi n từ 1 đến 3000" : "SAI") << '\n';
    cout << isqrt(1e18) << '\n';
}

Outputkhớp với mọi n từ 1 đến 3000
1000000000

Hàm isqrt sửa kết quả của sqrtl bằng hai vòng while, vì căn số thực có thể lệch một đơn vị khi $n$ cỡ $10^{18}$. Quy trình này dùng được cho rất nhiều bài: viết vét cạn, chạy với đầu vào nhỏ và in thành bảng, đoán quy luật, rồi chứng minh hoặc ít nhất đối chứng với vét cạn trên mọi đầu vào nhỏ liệt kê được.

Bước cuối không phải thủ tục cho đủ. Nối $n$ điểm trên đường tròn bằng mọi dây cung thì hình tròn bị chia thành $1, 2, 4, 8, 16$ miền với $n = 1, \dots, 5$. Rất dễ đoán $2^{n-1}$, nhưng với $n = 6$ kết quả là 31. Vài số hạng khớp chưa phải chứng minh.

Ví dụBước Nhảy Theo Chẵn Lẻ

Đề. Điểm xuất phát ở $x_0$, $|x_0| \le 10^{14}$. Bước thứ $i$ dịch $i$ đơn vị: sang trái nếu tọa độ ngay trước bước chẵn, sang phải nếu lẻ. In tọa độ sau $n \le 10^{14}$ bước, $t \le 10^4$ test.

Lời giải. Thử nhỏ với $x_0 = 0$: vị trí sau $0, 1, \dots, 8$ bước là $0, -1, 1, 4, 0, -5, 1, 8, 0$. Hướng đi là trái, phải, phải, trái, rồi lặp lại; mỗi khối bốn bước $-(4j+1) + (4j+2) + (4j+3) - (4j+4) = 0$ đưa điểm về chỗ cũ.

Vì sao chu kỳ 4: dịch $i$ đơn vị, trái hay phải, đều đổi chẵn lẻ của vị trí đúng bằng chẵn lẻ của $i$. Vậy sau $k$ bước, vị trí cùng chẵn lẻ với $x_0 + \frac{k(k+1)}{2}$, và dãy $\frac{k(k+1)}{2} = 0, 1, 3, 6, 10, 15, \dots$ có chẵn lẻ là chẵn, lẻ, lẻ, chẵn rồi lặp lại. Bỏ các khối đủ bốn bước, chỉ còn r = n % 4 bước cuối; với $x_0$ chẵn, độ dời là $0$, $-n$, $1$, $n + 1$ ứng với $r = 0, 1, 2, 3$. Với $x_0$ lẻ mọi hướng đổi ngược nên độ dời đổi dấu. Mỗi test $O(1)$.

Chỗ dễ sai là số lẻ âm: trong C++ -5 % 2 bằng -1, nên phải kiểm x % 2 != 0 chứ không phải x % 2 == 1.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll t, x, n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> x >> n;
        ll d = 0;
        if (n % 4 == 1) d = -n;
        if (n % 4 == 2) d = 1;
        if (n % 4 == 3) d = n + 1;
        if (x % 2 != 0) d = -d;
        cout << x + d << '\n';
    }
}

Input6
0 0
2 1
3 2
-5 3
10 4
-2 5

Output0
1
2
-9
10
-7

Bất biến: đại lượng mà thao tác nào cũng giữ nguyên

Nhiều bài hỏi “sau một chuỗi thao tác tùy ý, có đạt được trạng thái này không”. Vét cạn mọi chuỗi thao tác bùng nổ rất nhanh. Nhưng đôi khi có một đại lượng không bao giờ đổi; đại lượng đó là bất biến (invariant). Nếu trạng thái đích có giá trị bất biến khác trạng thái đầu thì đích không thể đạt được, dù đi bao nhiêu bước.

Ví dụ kinh điển là lát domino. Bàn cờ $8 \times 8$ bỏ hai ô ở hai góc đối diện, còn 62 ô. Có lát kín bằng 31 quân domino $1 \times 2$ không? Tô bàn cờ hai màu như thường lệ. Mỗi quân domino phủ đúng một ô mỗi màu, nên hiệu “số ô xanh đã phủ trừ số ô trắng đã phủ” luôn bằng 0. Nhưng hai góc đối diện cùng màu, bỏ đi thì còn 30 ô một màu và 32 ô màu kia, nên không có cách lát nào.

Bất biến hay gặp: tổng, phần dư của tổng khi chia cho một số, tính chẵn lẻ, hiệu số ô của hai màu. Nhưng bất biến chỉ cho điều kiện cần. Muốn khẳng định “có thể” phải chỉ ra cách làm.

Thử một bài lập trình: dãy $n$ số, mỗi thao tác chọn hai phần tử kề nhau và đổi dấu cả hai; có đưa mọi phần tử về không âm được không? Nếu dãy không có số 0, số lượng số âm chỉ đổi $-2$, $0$ hoặc $+2$, nên chẵn lẻ của nó là bất biến: số âm lẻ thì không thể. Số 0 phá bất biến, vì đổi dấu số 0 vẫn là 0. Chiều ngược lại cần dựng: đổi dấu hai phần tử ở $i < j$ bằng chuỗi thao tác trên các cặp $(i, i+1), \dots, (j-1, j)$, các phần tử ở giữa bị đổi hai lần nên như cũ. Vậy đáp án là có khi và chỉ khi số âm chẵn hoặc dãy có số 0.

Ví dụThoát Khỏi Tầm Hậu

Đề. Bàn cờ $n \times n$ ($n \le 1000$), hậu đứng yên ở $(a_x, a_y)$, khống chế cả hàng, cột và hai đường chéo. Vua ở $(b_x, b_y)$ muốn tới $(c_x, c_y)$, mỗi bước sang một trong tám ô kề, không bao giờ đứng trên ô bị khống chế. Đầu và đích đều an toàn. Vua có tới được không?

Lời giải. Hàng và cột của hậu chia bàn cờ thành bốn góc. Vua đi mỗi bước một ô nên muốn sang góc khác phải đứng lên hàng hoặc cột của hậu, mà đó là ô bị khống chế. Vậy “vua ở góc nào” là bất biến: nếu đầu và đích khác góc thì chắc chắn không tới được.

Chiều ngược lại cần dựng: trong một góc, các đường chéo của hậu chỉ đi qua đúng một góc theo một hướng, và vua bước chéo được nên vượt qua đường chéo ấy mà không đứng lên nó. Đi trong cùng một góc luôn tới được đích. Đáp án là có khi và chỉ khi $b_x, c_x$ cùng phía với $a_x$ và $b_y, c_y$ cùng phía với $a_y$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, ax, ay, bx, by, cx, cy;

signed main() {
    cin >> n >> ax >> ay >> bx >> by >> cx >> cy;
    bool okx = (bx < ax) == (cx < ax);
    bool oky = (by < ay) == (cy < ay);
    cout << (okx && oky ? "YES" : "NO") << '\n';
}

Input8
4 4
1 2
3 1

OutputYES

Nghĩ ngược từ kết quả

Màn hình hiện số $n$. Máy có hai nút: nhân đôi số trên màn hình, hoặc trừ nó đi 1. Ít nhất bao nhiêu lần bấm để màn hình hiện $m$, với $n, m \le 10^9$?

Đi xuôi từ $n$, mỗi bước có hai lựa chọn; thử mọi cách bấm phải đi qua hàng tỉ giá trị. Đi ngược từ $m$ thì khác: từ $v$ ta quay về $v + 1$ (hoàn tác phép trừ) hoặc $v / 2$ (hoàn tác nhân đôi, chỉ khi $v$ chẵn). Với $v$ lẻ chỉ còn một lựa chọn, vì kết quả của phép nhân đôi luôn chẵn.

Với $v$ chẵn và $v > n$, cứ chia đôi. Nếu một đường đi tối ưu mở đầu bằng $+1$ ở số chẵn, nó phải cộng 1 một số chẵn lần $2j$ rồi mới chia đôi được, tới $v/2 + j$ sau $2j + 1$ bước; chia đôi ngay rồi cộng $j$ lần cho cùng kết quả chỉ sau $j + 1$ bước. Khi $v \le n$, còn lại $n - v$ lần cộng 1. Cứ hai vòng thì $m$ giảm ít nhất một nửa, mà $10^9$ chia đôi 30 lần là về 1, nên vòng lặp chạy không quá khoảng 60 lần.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, steps;

signed main() {
    cin >> n >> m;
    while (m > n) {
        if (m % 2 == 1) m++;
        else m /= 2;
        steps++;
    }
    cout << steps + n - m << '\n';
}

Input3 10

Output3

Từ $10$ ta đi ngược $10 \to 5 \to 6 \to 3$; đảo lại thành $3 \to 6 \to 5 \to 10$ (nhân đôi, trừ 1, nhân đôi).

Nghĩ ngược còn một dạng quen thuộc: các thao tác ghi đè lên nhau. Khi nhiều thao tác lần lượt gán giá trị cho cùng một ô, chỉ thao tác cuối cùng chạm vào ô đó còn thấy được.

Ví dụVệt Sơn Cuối Cùng

Đề. Bảng $8 \times 8$ ban đầu trống. Mỗi thao tác tô cả một hàng bằng R hoặc cả một cột bằng B, màu mới ghi đè màu cũ. Cho bảng cuối (bảo đảm tạo được, có ít nhất một thao tác), hỏi thao tác cuối cùng tô màu gì. $t \le 4000$ bảng.

Lời giải. Dựng lại cả chuỗi thao tác là việc khó, vì nhiều chuỗi cho cùng một bảng. Nhưng thao tác cuối không bị ai ghi đè nên vệt nó tô còn nguyên. Nếu thao tác cuối tô một hàng đỏ, bảng có một hàng đủ tám ô R. Nếu thao tác cuối tô một cột xanh, cột đó cắt mọi hàng, nên không hàng nào đủ tám ô R. Vậy có hàng RRRRRRRR thì in R, ngược lại in B.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll t;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        bool red = false;
        for (ll i = 1; i <= 8; i++) {
            string row;
            cin >> row;
            if (row == "RRRRRRRR") red = true;
        }
        cout << (red ? 'R' : 'B') << '\n';
    }
}

+17 dòngInput2
.B....B.
.B....B.
.B....B.
RRRRRRRR
.B....B.
.B....B.
.B....B.
.B....B.
...B....
RRRBRRRR
...B....
...B....
...B....
...B....
...B....
RRRBRRRR

OutputR
B

Dữ liệu có thể có dòng trống giữa các bảng; cin >> row tự bỏ qua khoảng trắng nên không phải xử lý riêng.

Chứng minh một cận, rồi dựng cách đạt cận

Bài tối ưu kiểu ad hoc thường có hai nửa. Nửa thứ nhất chứng minh đáp án không thể tốt hơn một giá trị $B$ (cận). Nửa thứ hai chỉ ra cách làm đạt đúng $B$. Hai nửa gặp nhau thì $B$ là đáp án; thiếu một nửa mới chỉ là phỏng đoán. Cách nghĩ này quay lại ở bài 04 (tham lam).

Ví dụ: $n$ chồng sỏi, chồng $i$ có $a_i$ viên; mỗi lượt lấy một viên từ hai chồng khác nhau. Làm được nhiều nhất bao nhiêu lượt? Gọi $S$ là tổng, $M$ là chồng lớn nhất. Mỗi lượt lấy 2 viên nên không quá $\lfloor S/2 \rfloor$ lượt; mỗi lượt lấy ít nhất một viên ngoài chồng lớn nhất nên không quá $S - M$ lượt. Cận $\min(\lfloor S/2 \rfloor, S - M)$ đạt được: nếu $M > S - M$ thì ghép mỗi viên ngoài chồng lớn nhất với một viên của nó; ngược lại xếp mọi viên thành hàng (cùng chồng đứng cạnh nhau) và ghép viên $j$ với viên $j + \lfloor S/2 \rfloor$, hai viên ghép luôn khác chồng vì một chồng dài không quá $\lfloor S/2 \rfloor$.

Cận thứ hai đến từ việc nhìn vào phần tử cực trị. Khi đề có quá nhiều lựa chọn, phần tử lớn nhất, nhỏ nhất hay đầu mút gần nhất thường là chỗ chặn đáp án.

Ví dụBốn Ô Đồng Màu

Đề. Ảnh $2 \times 2$ ô, mỗi ô một màu (chữ cái thường). Mỗi thao tác chọn không quá hai ô đang cùng màu và đổi chúng sang cùng một màu khác. Ít nhất bao nhiêu thao tác để bốn ô cùng màu? $t \le 1000$ test.

Lời giải. Gọi $d$ là số màu khác nhau. Cận: một thao tác chỉ đổi các ô của một màu, nên làm biến mất nhiều nhất một màu; muốn còn một màu phải làm biến mất $d - 1$ màu, tức cần ít nhất $d - 1$ thao tác. Dựng: giữ màu chiếm nhiều ô nhất làm đích. Mỗi màu còn lại chiếm không quá hai ô (màu nào chiếm ba ô thì đã là màu nhiều nhất), nên đổi sang màu đích được trong một thao tác. Vậy đáp án là $d - 1$. Đếm $d$ bằng cách duyệt bốn ô: ô nào có màu chưa gặp ở các ô trước thì cộng 1.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll t;

signed main() {
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a >> b;
        string s = a + b;
        ll d = 0;
        for (ll i = 0; i < 4; i++) {
            bool seen = false;
            for (ll j = 0; j < i; j++)
                if (s[j] == s[i]) seen = true;
            if (!seen) d++;
        }
        cout << d - 1 << '\n';
    }
}

Input4
aa
aa
aa
ab
ab
ac
ab
cd

Output0
1
2
3

Gom vô số trường hợp về vài dạng chuẩn

Đôi khi một không gian trông rất lớn nhưng chỉ có vài kiểu thật sự khác nhau. Việc cần làm là mô tả các kiểu đó rồi thử từng kiểu, thay vì tìm cách biến đổi tổng quát.

Ví dụ: đổi ít ký tự nhất trong xâu nhị phân để không còn hai ký tự kề nhau giống nhau. Xâu hợp lệ phải xen kẽ, và ký tự đầu quyết định cả xâu, nên chỉ có hai xâu đích: 0101… và 1010…. Đếm số vị trí lệch $c$ so với xâu thứ nhất; xâu thứ hai lệch đúng $n - c$ vị trí, đáp án là $\min(c, n - c)$.

ll c = 0;
for (ll i = 0; i < n; i++)
    if (s[i] - '0' != i % 2) c++;
cout << min(c, n - c) << '\n';

Cùng ý tưởng hiện ra ở nhiều chỗ. Quay ma trận $90^\circ$ lặp lại chỉ cho 4 trạng thái. Một dãy tuần hoàn chu kỳ $p$ chỉ có $p$ điểm bắt đầu khác nhau. Trước khi tối ưu cách duyệt, hãy đếm xem số trường hợp có thật sự là vô số không.

Ví dụMa Trận Sau Những Lần Quay

Đề. Ma trận $2 \times 2$ gồm bốn số đôi một khác nhau. Ma trận đẹp nếu mỗi hàng tăng từ trái sang phải và mỗi cột tăng từ trên xuống. Được quay cả ma trận $90^\circ$ theo chiều kim đồng hồ bao nhiêu lần tùy ý; có thu được ma trận đẹp không?

Lời giải. Quay bốn lần trở về ban đầu, nên “bao nhiêu lần tùy ý” thật ra chỉ là 4 trạng thái: quay $0, 1, 2, 3$ lần. Thử cả bốn. Quay theo chiều kim đồng hồ đưa ma trận có hàng trên a b, hàng dưới c d thành ma trận có hàng trên c a, hàng dưới d b.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll t, a, b, c, d;

signed main() {
    cin >> t;
    while (t--) {
        cin >> a >> b >> c >> d;
        bool ok = false;
        for (ll k = 0; k < 4; k++) {
            if (a < b && c < d && a < c && b < d) ok = true;
            ll na = c, nb = a, nc = d, nd = b;
            a = na, b = nb, c = nc, d = nd;
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

Input4
1 3
2 4
3 1
4 2
1 4
2 3
4 3
2 1

OutputYES
YES
NO
YES