Tham Dự Đại Hội Thể Thao (BAI2 – HSG)

Nguồn: Đề thi HSG Tin học (Bài 2) Độ khó: Trung bình Chia lấy dư Mảng đánh dấu Đếm phân phối Tham lam

Đề bài

Bài 2 (6,0 điểm) – Tham dự Đại hội thể thao

Tham dự Đại hội thể thao quốc tế, có $n$ người tham gia, được đánh số hiệu từ $1$ đến $n$, biết $a_i$ là độ thân thiện của người thứ $i$ $(1 \le i \le n)$. Trong buổi giao lưu với nhau, Ban tổ chức lên kế hoạch tổ chức một trò chơi. Trò chơi cần nhiều người tham gia. Biết rằng nếu hai người cùng tham gia trò chơi mà có tổng độ thân thiện của hai người đó chia hết cho $k$ thì sẽ đối kháng nhau.

Yêu cầu: Hãy giúp ban tổ chức chọn nhiều người tham gia trò chơi nhất sao cho hai người bất kì tham gia trò chơi thì tổng độ thân thiện của họ không chia hết cho $k$.

Dữ liệu vào từ tệp văn bản BAI2.INP có cấu trúc:

• Dòng thứ nhất chứa hai số nguyên dương $n$ và $k$ $(1 \le n \le 10^5,\ 1 \le k \le 100)$;
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$, với $a_i$ là độ thân thiện của người thứ $i$ $(1 \le a_i \le 10^9,\ 1 \le i \le n)$. Các số $a_1, a_2, \dots, a_n$ đều phân biệt.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI2.OUT có cấu trúc:

• Ghi một số duy nhất là số lượng người được chọn nhiều nhất tham gia trò chơi sao cho tổng độ thân thiện của hai người bất kỳ được chọn không chia hết cho $k$.

Ràng buộc:

• Subtask 1: 70% số điểm với $n \le 10^3$;
• Subtask 2: 30% số điểm với $n \le 10^5$.

Ghi chú: đề thi gốc đọc/ghi file BAI2.INP / BAI2.OUT; trên hệ thống chấm online thì đọc/ghi chuẩn (bàn phím/màn hình).

Ví dụ – BAI2.INP

4 5
5 2 6 3

Ví dụ – BAI2.OUT

3

Giải thích: Chọn 3 người có độ thân thiện lần lượt là: $5, 2, 6$ thỏa mãn yêu cầu bài toán.

Lời mở đầu

Bài này nhìn qua thì tưởng phải thử chọn các nhóm người rất phức tạp, nhưng chỉ cần dùng tính chất của phép chia lấy dư kết hợp với mảng đánh dấu là giải quyết gọn gàng với độ phức tạp $O(N + K)$ luôn đó các bạn 😎.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $4$ người với độ thân thiện $5, 2, 6, 3$ và $k = 5$. Nếu chọn cả 4 người thì cặp $(2, 3)$ có tổng $5$ chia hết cho $5$ ⇒ đối kháng, không được. Chọn $5, 2, 6$ thì các tổng là $5 + 2 = 7$, $5 + 6 = 11$, $2 + 6 = 8$, không tổng nào chia hết cho $5$ ⇒ hợp lệ, được $3$ người. (Chọn $5, 3, 6$ cũng được 3 người.) Vì không chọn được cả 4 nên đáp án là $3$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Nhận xétChỉ cần quan tâm a[i] % kCách 1Đếm số dư + chọn nhóm O(N + K) · 100%

Nhận xétChỉ cần quan tâm số dư khi chia cho k

Khi mình chia lấy dư cho $k$ thì về mặt toán học, phần dư luôn nhỏ hơn $k$, nghĩa là các kết quả chỉ nằm trong phạm vi từ $0$ đến $k - 1$. Mà $k$ tối đa chỉ có $100$ – quá bé! Dù $k$ lớn nhất là $100$ thì các số dư cũng chỉ nằm trong đoạn $0 \to 99$. Phạm vi nhỏ như vậy là dấu hiệu cho thấy ta có thể dùng kỹ thuật mảng đánh dấu ở chỗ này.

Hơn nữa, tổng hai số có chia hết cho $k$ hay không thì chỉ phụ thuộc vào số dư của chúng: $(x + y) \bmod k = \big(x \bmod k + y \bmod k\big) \bmod k$. Với hai số dư $p, q$ trong đoạn $[0, k - 1]$ thì $p + q$ nằm trong $[0, 2k - 2]$, nên để $p + q$ chia hết cho $k$ chỉ có 2 tình huống:

1. Cả hai đều dư 0: tức là từng số đều chia hết cho $k$, cộng lại cũng chia hết cho $k$.
2. Tổng hai số dư bằng đúng $k$. Ví dụ $k = 5$: các số $\% 5 = 1$ ghép với các số $\% 5 = 4$ thì tổng chia hết cho $5$. Như $6$ và $9$: $6 \% 5 = 1$, $9 \% 5 = 4$, $1 + 4 = 5$ nên $6 + 9 = 15$ chia hết cho $5$.

Ý tưởng

Dùng mảng đánh dấu cnt[r] = số người có độ thân thiện chia $k$ dư $r$. Rồi chọn nhiều người nhất sao cho không có 2 người nào "va chạm" theo 2 tình huống ở trên.

Cách 1Đếm số dư + chọn nhóm đông hơn – O(N + K)

Sau khi đếm xong cnt[0..k-1], mình xét lần lượt:

① Nhóm dư 0. Nếu có từ 2 người trở lên dư 0 thì chắc chắn chỉ được chọn 1 người thôi, vì chọn 2 người dư 0 thì tổng chia hết cho $k$ ngay. Vậy cnt[0] > 0 thì cộng 1 vào kết quả.

② Các cặp số dư có tổng bằng $k$: $(1, k - 1)$, $(2, k - 2)$, $(3, k - 3)$, … Trong mỗi cặp $(l, r)$ với $l + r = k$:

• Người dư $l$ và người dư $r$ không được đứng chung ⇒ chỉ được lấy một trong hai nhóm.
• Nhưng trong cùng nhóm dư $l$ (với $l \ne r$) thì hai người bất kỳ có tổng dư $2l \bmod k \ne 0$ ⇒ lấy cả nhóm cũng không sao.

Vì đề muốn chọn nhiều người nhất nên ta lấy nhóm đông hơn: cộng max(cnt[l], cnt[r]). Ví dụ $k = 5$, có 4 số dư 1 và 7 số dư 4: giữa 4 và 7 thì chọn 7 người dư 4, bỏ 4 người dư 1, đúng không nào 😉.

③ Trường hợp đặc biệt: cặp "tự ghép với chính nó". Với $k = 5$ các cặp là $(1, 4)$, $(2, 3)$ rồi hết, vì xét tiếp sẽ bị lặp lại. Nhưng với $k = 6$ thì có $(1, 5)$, $(2, 4)$, rồi $(3, 3)$ – hai số dư trùng nhau! Hai người cùng dư $3$ thì tổng dư $6 \equiv 0$ ⇒ đối kháng. Vậy nhóm này giống y nhóm dư 0: dù có tới 10 người dư 3 thì cũng chỉ lấy được 1 người (nếu nhóm có người).

Nhóm số dư	Được lấy	Lý do
0	tối đa 1 người	2 người dư 0 ⇒ tổng dư 0
cặp (l, k − l), l < k − l	max(cnt[l], cnt[k − l])	2 nhóm "kỵ" nhau, mỗi nhóm tự nó thì ổn
k/2 (khi k chẵn)	tối đa 1 người	2 người dư k/2 ⇒ tổng dư k ≡ 0

Công thức

$res = [cnt_0 \gt 0] + \sum\limits_{l = 1}^{l \lt k - l} \max(cnt_l, cnt_{k-l}) + \big[k \text{ chẵn và } cnt_{k/2} \gt 0\big]$. Trong code, mình duyệt hai con trỏ l = 1, r = k - 1 tiến lại gần nhau cho tới khi l >= r; nếu dừng ở l == r thì đó chính là nhóm $k/2$.

Vì sao cách chọn này là nhiều nhất?

Các nhóm thuộc những "cặp" khác nhau không hề ảnh hưởng nhau (tổng số dư của chúng không thể là $0$ hay $k$). Nên ta tối ưu riêng từng cặp: nhóm 0 và nhóm $k/2$ không thể lấy quá 1 người; mỗi cặp $(l, k - l)$ không thể lấy người của cả hai bên, nên tối đa là $\max(cnt_l, cnt_{k-l})$. Cộng các giá trị tối đa đó lại là đáp án, và cách chọn ở trên đạt đúng giá trị đó.

Minh hoạ chia nhóm theo số dư

Em nhập $k$ và dãy độ thân thiện, rồi bấm Tiếp để xem từng nhóm số dư được xét: xanh = lấy cả nhóm, tím = chỉ lấy 1 người, đỏ = bỏ.

k Dãy a

Ví dụ nhanh:

Source code theo đúng ý tưởng ở trên để các bạn tham khảo:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int cnt[k] = {0};
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        cnt[x % k]++;
    }
    int res = 0;
    if(cnt[0] > 0){
        res++;
    }
    int l = 1, r = k - 1;
    while(l < r){
        res += max(cnt[l], cnt[r]);
        l++;
        r--;
    }
    if(l == r){
        if(cnt[l] > 0){
            res++;
        }
    }
    cout << res;
    return 0;
}

import sys

data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
cnt = [0] * k
for i in range(2, 2 + n):
    x = data[i]
    cnt[x % k] += 1

res = 0
if cnt[0] > 0:
    res += 1
l, r = 1, k - 1
while l < r:
    res += max(cnt[l], cnt[r])
    l += 1
    r -= 1
if l == r and cnt[l] > 0:
    res += 1
print(res)

C++▶ Chạy tay từng dòng codeĐếm cnt[a[i] % k], lấy 1 người nhóm dư 0, max của mỗi cặp (l, k − l), và 1 người nhóm k/2.

Dữ liệu vào (stdin) – sửa thoải mái4 5 5 2 6 3

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n, k;

8 cin >> n >> k;

9 int cnt[k] = {0};

10 for(int i = 1; i <= n; ++i){

11 int x;

12 cin >> x;

13 cnt[x % k]++;

14 }

15 int res = 0;

16 if(cnt[0] > 0){

17 res++;

18 }

19 int l = 1, r = k - 1;

20 while(l < r){

21 res += max(cnt[l], cnt[r]);

22 l++;

23 r--;

24 }

25 if(l == r){

26 if(cnt[l] > 0){

27 res++;

28 }

29 }

30 cout << res;

31 return 0;

32}

ChậmVừaNhanhRất nhanh

Vài lưu ý nhỏ về code

• Đề thi gốc đọc/ghi file BAI2.INP / BAI2.OUT. Code ở trên mình để đọc/ghi chuẩn cho hệ thống chấm online; đi thi offline thì các bạn thêm 2 dòng freopen("BAI2.INP", "r", stdin); freopen("BAI2.OUT", "w", stdout); ở đầu main nhé (bản Python thì thêm sys.stdin = open("BAI2.INP", "r"), sys.stdout = open("BAI2.OUT", "w")).
• Khai báo int cnt[k] = {0}; với k là biến (mảng độ dài biến – VLA) chạy được trên g++ (các trình chấm hiện nay đều dùng g++), nhưng không phải C++ chuẩn. Muốn chắc ăn tuyệt đối thì có thể khai báo cố định int cnt[100] = {0}; vì $k \le 100$.
• Trường hợp $k = 1$: mọi tổng đều chia hết cho 1, code cho ra res = 1 (chỉ lấy được 1 người) – đúng luôn, vì lúc đó mọi số đều dư 0 và vòng while không chạy lần nào.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(K)$ cho mảng cnt (không cần lưu cả dãy $a$).
• Thời gian: đọc và đếm $N$ số mất $O(N)$, duyệt các cặp số dư mất $O(K)$ ⇒ tổng $O(N + K)$, hay có thể nói là $O(\max(N, K))$. Bài cho $N$ tối đa $10^5$, $K$ tối đa $10^2$, nên trường hợp xấu nhất cũng chỉ cần lặp cỡ $10^5$ lần. Ngưỡng 1 giây là khoảng $10^8$ phép tính thì $10^5$ là quá bé, yên tâm không sợ quá thời gian, ăn trọn cả 2 subtask 😁.

Không gian$O(K)$

Thời gian$O(N + K)$

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với 500 bộ test ngẫu nhiên nhỏ ($n \le 12$, $k$ từ 1 đến 100, có cả $k$ chẵn và $k = 1$), so với code vét cạn thử mọi tập con – khớp hết. Với test lớn nhất $n = 10^5$, $k = 100$: bản C++ chạy chưa tới 0.02 giây CPU, bản Python khoảng 0.06 giây CPU.

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 😇