Vòng cù lao (Đề tự luyện HSG Tin 9 – Bài 2)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 2 (đề tự soạn)Độ khó: Trung bìnhHai con trỏCửa sổ trượtDãy vòng tròn

Đề bài

Vòng cù lao. Quanh một cù lao có $N$ nhà học trò, bến các nhà xếp thành vòng tròn, đánh số $1..N$ theo chiều nước chảy (sau bến $N$ là bến $1$). Thầy Sơn chọn bến xuất phát $s$ rồi ghé lần lượt các nhà $s, s+1, \dots$ (vòng qua bến $N$ về bến $1$), không bỏ nhà nào, không ghé nhà nào hai lần. Ghé nhà $i$ mất $a_i$ phút ($a_i$ có thể bằng $0$), tổng thời gian không vượt quá $T$. Tìm $K$ = số nhà nhiều nhất có thể ghé, và $C$ = số bến xuất phát đạt được đúng $K$ nhà (nếu $K = 0$ thì $C = 0$).

Dữ liệu vào: dòng 1 là $N, T$ $(1 \le N \le 2\cdot 10^5,\ 0 \le T \le 10^{18})$; dòng 2 là $a_1..a_N$ $(0 \le a_i \le 10^9)$.

Kết quả: hai số $K$ và $C$.

• Subtask 1 (20%): $N \le 300$.
• Subtask 2 (30%): $N \le 5000$.
• Subtask 3 (50%): không ràng buộc thêm.

Input

6 12
3 6 2 7 2 9

Output

3 2

Giải thích

Xuất phát từ bến $1$: ghé $1, 2, 3$ hết $11$ phút. Xuất phát từ bến $3$: ghé $3, 4, 5$ hết $11$ phút. Các bến khác ghé được $2$ nhà (bến $6$ ghé nhà $6$ rồi vòng qua nhà $1$, hết đúng $12$ phút). Vậy $K = 3$, $C = 2$.

Input

6 6
0 5 0 4 7 2

Output

3 1

Giải thích

Chỉ xuất phát từ bến $1$ mới ghé được $3$ nhà ($0 + 5 + 0 = 5$ phút). Các bến $2, 3, 4, 5, 6$ ghé được lần lượt $2, 2, 1, 0, 2$ nhà. Vậy $K = 3$, $C = 1$.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Vòng cù lao

Lời mở đầu

Nếu các bến xếp trên một đường thẳng thì đây là bài quen thuộc: tìm đoạn con liên tiếp dài nhất có tổng không vượt quá $T$. Cái "nút thắt" của bài nằm ở chữ vòng tròn: đoạn tốt nhất có thể đi vòng qua bến $N$ để về bến $1$, như đoạn $5 \to 6 \to 1$ trong ví dụ minh họa ở Hình 1 ($N = 6$, $T = 9$, $a = 4, 6, 7, 3, 4, 1$). Lưu ý: hai ví dụ của đề cố ý được chọn sao cho code "quên vòng tròn" vẫn ra đúng, nên đừng tin là code đúng chỉ vì qua được ví dụ.

Hình 1. Hai đoạn dài nhất: bến 4 → 6 (cam) và bến 5 → 6 → 1 (xanh lá, đi vòng). Bỏ quên đoạn vòng là mất ngay một nửa số cách xuất phát.

Gọi $len(s)$ là số nhà nhiều nhất ghé được khi xuất phát từ bến $s$. Vì mọi $a_i \ge 0$, đi càng xa thì tổng càng lớn, nên $len(s)$ chính là: cứ ghé tiếp cho tới khi ghé thêm một nhà nữa thì vượt $T$ (hoặc đã ghé đủ $N$ nhà). Bài toán là tính $len(s)$ cho mọi $s$, rồi lấy $K = \max len(s)$ và đếm $C$.

Ba chi tiết dễ sai cần nhớ ngay từ đầu:

• Tối đa $N$ nhà: khi $T$ rất lớn, thầy cũng chỉ ghé $N$ nhà (không ghé lại). Chẳng hạn $N = 3$, $T = 20$, $a = 5, 0, 7$ cho $K = C = 3$ (không phải $K = 5$).
• $K = 0$ thì $C = 0$: khi mọi $a_i > T$.
• Tổng dùng long long: tổng có thể tới $2\cdot 10^5 \cdot 10^9 = 2\cdot 10^{14}$, còn $T$ tới $10^{18}$.

Cách 1Thử mọi đoạn, cộng lại từ đầu · 20%Cách 2Mỗi bến xuất phát, cộng dồn · 50%Cách 3Hai con trỏ trên dãy nhân đôi · 100%

Cách 1Thử mọi đoạn – O(N³) · 20%

Cách tự nhiên nhất: với mỗi bến xuất phát $s$, thử ghé $k = 1, 2, \dots, N$ nhà; mỗi lần thử thì cộng lại tổng $a_s + a_{s+1} + \dots$ từ đầu. Để "đi vòng", nhà thứ $j$ kể từ $s$ có chỉ số $(s + j) \bmod N$ (đánh số từ $0$). Gặp tổng đầu tiên vượt $T$ thì dừng.

Mỗi bến thử tối đa $N$ độ dài, mỗi độ dài cộng tối đa $N$ số, nên tốn $O(N^3)$: với $N = 300$ là khoảng $2{,}7\cdot 10^7$ phép, ổn. Với $N = 5000$ thì lên cỡ $10^{11}$ — quá chậm.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    ll T;
    cin >> n >> T;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int K = 0, C = 0;
    for (int s = 0; s < n; s++) {          // thu moi ben xuat phat
        int best = 0;                       // so nha nhieu nhat khi xuat phat tu s
        for (int k = 1; k <= n; k++) {      // thu ghe k nha
            ll sum = 0;
            for (int j = 0; j < k; j++) sum += a[(s + j) % n];
            if (sum <= T) best = k;
            else break;
        }
        if (best > K) { K = best; C = 1; }
        else if (best == K && best > 0) C++;
    }
    cout << K << ' ' << C << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); T = int(data[1])
    a = list(map(int, data[2:2 + n]))
    K = 0; C = 0
    for s in range(n):                  # thu moi ben xuat phat
        best = 0                        # so nha nhieu nhat khi xuat phat tu s
        for k in range(1, n + 1):       # thu ghe k nha
            sm = 0
            for j in range(k):
                sm += a[(s + j) % n]
            if sm <= T:
                best = k
            else:
                break
        if best > K:
            K = best; C = 1
        elif best == K and best > 0:
            C += 1
    print(K, C)

main()

Không gian$O(N)$

Thời gian$O(N^3)$

Cách 2Cộng dồn cho mỗi bến xuất phát – O(N²) · 50%

Cách 1 lãng phí ở chỗ: tổng của $k+1$ nhà bằng tổng của $k$ nhà cộng thêm một nhà nữa, không cần cộng lại từ đầu. Vậy với mỗi $s$, ta giữ biến sum và ghé thêm từng nhà một, chừng nào sum + a[nhà kế] <= T và chưa đủ $N$ nhà.

Mỗi bến xuất phát tốn tối đa $N$ bước, tổng $O(N^2)$: với $N = 5000$ là $2{,}5\cdot 10^7$, chạy tốt. Nhưng với $N = 2\cdot 10^5$ thì là $4\cdot 10^{10}$ — quá thời gian (bộ test cố tình cho $T$ lớn để các đoạn đều dài hàng chục nghìn nhà).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    ll T;
    cin >> n >> T;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int K = 0, C = 0;
    for (int s = 0; s < n; s++) {          // thu moi ben xuat phat
        ll sum = 0;
        int best = 0;
        while (best < n && sum + a[(s + best) % n] <= T) {
            sum += a[(s + best) % n];       // cong don, khong tinh lai tu dau
            best++;
        }
        if (best > K) { K = best; C = 1; }
        else if (best == K && best > 0) C++;
    }
    cout << K << ' ' << C << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); T = int(data[1])
    a = list(map(int, data[2:2 + n]))
    K = 0; C = 0
    for s in range(n):                  # thu moi ben xuat phat
        sm = 0
        best = 0
        while best < n and sm + a[(s + best) % n] <= T:
            sm += a[(s + best) % n]     # cong don, khong tinh lai tu dau
            best += 1
        if best > K:
            K = best; C = 1
        elif best == K and best > 0:
            C += 1
    print(K, C)

main()

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 3Hai con trỏ trên dãy nhân đôi – O(N) · 100%

Bước 1: "duỗi" vòng tròn thành đường thẳng

Ta tạo dãy $b$ dài $2N$ bằng cách viết $a$ hai lần liên tiếp: $b = a_1, a_2, \dots, a_N, a_1, a_2, \dots, a_N$. Khi đó mọi đoạn vòng xuất phát từ bến $s$ đều là một đoạn liên tiếp bình thường của $b$, bắt đầu tại vị trí $s$ (trong nửa đầu) và dài không quá $N$.

Hình 2. Đoạn vòng 5 → 6 → 1 trở thành đoạn liên tiếp b[4..6] (đánh số từ 0). Chỉ cho bến xuất phát chạy trong nửa đầu, và cửa sổ không được dài quá N.

Bước 2: con trỏ cuối không bao giờ lùi

Gọi cửa sổ của bến $s$ là $b[s..e-1]$ với $e$ lớn nhất có thể. Nhận xét then chốt: khi chuyển từ $s$ sang $s+1$, ta bỏ nhà $b[s]$ ra khỏi cửa sổ, tổng chỉ giảm (vì $b[s] \ge 0$), nên đoạn $b[s+1..e-1]$ vẫn hợp lệ. Nghĩa là $e$ của bến $s+1$ không nhỏ hơn $e$ của bến $s$. Ta không cần đếm lại từ đầu: chỉ việc cho $e$ tiến tiếp.

Vì $e$ chỉ tăng và không vượt quá $2N$, tổng số lần tăng $e$ trong cả chương trình là $O(N)$. Đó là kỹ thuật hai con trỏ (cửa sổ trượt).

Bẫy: cửa sổ dài hơn N

Trên dãy nhân đôi, nếu $T$ đủ lớn thì cửa sổ có thể nuốt luôn cả bản sao, dài hơn $N$ — tức là thầy ghé lại nhà cũ! Điều kiện vòng lặp phải là e < s + n chứ không phải e < 2 * n. Bộ test có các test $T = 10^{18}$ hoặc $T$ gấp đôi tổng cả vòng để bắt lỗi này.

Bẫy: cửa sổ rỗng

Nếu $b[s] > T$ thì cửa sổ của $s$ rỗng ($e = s$), lúc đó không được trừ $b[s]$ khỏi tổng. Sang bến kế tiếp, ta đặt lại $e = s$, sum = 0. Đếm $C$ thì chỉ đếm khi $len > 0$ (để $K = 0$ cho $C = 0$).

Mô phỏng dưới đây cho các bạn xem hai con trỏ chạy trên dãy nhân đôi. Ô viền cur là bến xuất phát $s$, các ô xanh là cửa sổ hiện tại.

Dãy a T

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll T;
    cin >> n >> T;
    vector<ll> b(2 * n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i + n] = b[i];             // nhan doi day de "duoi" vong tron
    }
    int e = 0;                       // cua so dang xet: b[s..e-1]
    ll sum = 0;
    int K = 0, C = 0;
    for (int s = 0; s < n; s++) {
        if (e < s) { e = s; sum = 0; }
        while (e < s + n && sum + b[e] <= T) {   // khong qua n nha
            sum += b[e];
            e++;
        }
        int len = e - s;
        if (len > K) { K = len; C = 1; }
        else if (len == K && len > 0) C++;
        if (e > s) sum -= b[s];      // bo nha s ra khoi cua so
    }
    cout << K << ' ' << C << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); T = int(data[1])
    a = list(map(int, data[2:2 + n]))
    b = a + a                        # nhan doi day de "duoi" vong tron
    e = 0                            # cua so dang xet: b[s..e-1]
    sm = 0
    K = 0; C = 0
    for s in range(n):
        if e < s:
            e = s; sm = 0
        lim = s + n                  # khong qua n nha
        while e < lim and sm + b[e] <= T:
            sm += b[e]
            e += 1
        ln = e - s
        if ln > K:
            K = ln; C = 1
        elif ln == K and ln > 0:
            C += 1
        if e > s:
            sm -= b[s]               # bo nha s ra khoi cua so
    print(K, C)

main()

Không gian$O(N)$

Thời gian$O(N)$

C++▶ Chạy tay từng dòng codeHai con trỏ s, e trên dãy nhân đôi, cửa sổ dài tối đa n.

Dữ liệu vào (stdin) – sửa thoải mái6 12 3 6 2 7 2 9

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4int main() {

5 ios::sync_with_stdio(false);

6 cin.tie(nullptr);

7 int n;

8 ll T;

9 cin >> n >> T;

10 vector<ll> b(2 * n);

11 for (int i = 0; i < n; i++) {

12 cin >> b[i];

13 b[i + n] = b[i]; // nhan doi day de "duoi" vong tron

14 }

15 int e = 0; // cua so dang xet: b[s..e-1]

16 ll sum = 0;

17 int K = 0, C = 0;

18 for (int s = 0; s < n; s++) {

19 if (e < s) { e = s; sum = 0; }

20 while (e < s + n && sum + b[e] <= T) { // khong qua n nha

21 sum += b[e];

22 e++;

23 }

24 int len = e - s;

25 if (len > K) { K = len; C = 1; }

26 else if (len == K && len > 0) C++;

27 if (e > s) sum -= b[s]; // bo nha s ra khoi cua so

28 }

29 cout << K << ' ' << C << '\n';

30 return 0;

31}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 32 test: Subtask 1 có 10 test ($N \le 300$, gồm các test biên $N = 1$, $K = 0$, toàn số $0$, ghé hết vòng), Subtask 2 có 10 test ($N \approx 5000$), Subtask 3 có 12 test ($N \approx 2\cdot 10^5$). Ở hai subtask sau, $T$ luôn đủ lớn để các đoạn dài hàng nghìn tới hàng trăm nghìn nhà, và nhiều test có đoạn tốt nhất phải đi vòng qua bến $N$. Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10 test)	Sub 2 (10 test)	Sub 3 (12 test)	Điểm
Cách 1 – Thử mọi đoạn, cộng lại từ đầu	Đúng 10/10	TLE 0/10	TLE 0/12	20
Cách 2 – Cộng dồn cho mỗi bến xuất phát	Đúng 10/10	Đúng 10/10	TLE 0/12	50
Cách 3 – Hai con trỏ trên dãy nhân đôi (chuẩn)	Đúng 10/10	Đúng 10/10	Đúng 12/12	100
Sai: quên vòng tròn (chỉ xét đoạn thẳng)	WA 3/10	WA 2/10	WA 3/12	24,5
Sai: điều kiện e < 2 * n (cửa sổ dài quá N)	WA 7/10	WA 9/10	WA 11/12	86,8
Sai: biến sum kiểu int	WA 7/10	WA 2/10	WA 2/12	28,3

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 22 test còn lại; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3; Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,05 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test, chạy dưới 0,4 giây ngay cả với CPython. Lỗi "cửa sổ dài quá N" chỉ lộ ra khi $T$ lớn hơn tổng cả vòng, nên nó lọt được nhiều test — nhưng vẫn mất điểm ở mỗi subtask. Đúng là chi tiết nhỏ mà mất điểm oan!

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇