Tạo Mảng B (TAOMANGB)

Nguồn: CLUE OJ Độ khó: Trung bình Mảng đánh dấu Mảng 2 chiều Vét cạn

Đề bài

Cho dãy số nguyên $A[\,]$ gồm có $N$ phần tử. Nhiệm vụ của bạn là tìm dãy số $B[\,]$ có tổng phần tử nhỏ nhất thỏa mãn tính chất $A[i] / B[i] = A[i+1] / B[i+1]$ với mọi chỉ số $i$ $(0 \le i \le N-2)$.

Phép chia trong bài toán này là phép chia nguyên (tức là chỉ lấy phần nguyên của kết quả: ví dụ $5/3 = 1$).

Dữ liệu vào:

• Dòng đầu tiên là số lượng phần tử $N$ $(1 \le N \le 1000)$.
• Dòng tiếp theo gồm $N$ số nguyên $A[i]$ $(1 \le A[i] \le 2000)$.

Kết quả: In ra một số nguyên là tổng các phần tử của dãy số $B[\,]$ tìm được.

Ví dụ – input

5
18 27 16 22 6

Ví dụ – output

25

Giải thích test: Dãy $B[\,]$ tìm được là 5, 7, 5, 6, 2.

Lời mở đầu

Bài này mình được một em học viên hỏi: "anh ơi em cũng có thấy bài này hay hay nhưng em code không ra anh ạ" 😅. Mình đã hướng dẫn chi tiết cho em ấy, và tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ ở đây. Cách của mình có thể chưa phải tối ưu nhất, nhưng về mặt cài đặt thì rất dễ, và với phạm vi dữ liệu của đề thì time limit 1 giây như tiêu chuẩn là yên tâm AC nhé 😇.

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õ. Với $A = [18, 27, 16, 22, 6]$, ta cần chọn mỗi $B[i]$ (số nguyên dương) sao cho tất cả các thương nguyên $A[i] / B[i]$ đều bằng nhau, và tổng các $B[i]$ nhỏ nhất. Đề chọn $B = [5, 7, 5, 6, 2]$:

$18/5 = 3,\quad 27/7 = 3,\quad 16/5 = 3,\quad 22/6 = 3,\quad 6/2 = 3$

Tất cả thương đều bằng $3$, tổng $5 + 7 + 5 + 6 + 2 = 25$. Bạn thử chọn cho mọi thương bằng $0$ chẳng hạn: phải lấy $B = [19, 28, 17, 23, 7]$ (mỗi số lớn hơn $A[i]$) thì tổng tới $94$ – lớn hơn nhiều. Vậy câu hỏi thật sự là: nên chọn "thương chung" $z$ bằng bao nhiêu, và với mỗi $z$ thì mỗi $B[i]$ nhỏ nhất là bao nhiêu?

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

Cách 1Bảng đánh dấu 2 chiều + duyệt thương chung z · O(V² + V·N) · 100%

Cách 1Bảng đánh dấu 2 chiều – O(V² + V·N)

Đầu tiên các bạn để ý: mỗi phần tử $A[i]$ chỉ nằm trong phạm vi từ $1$ đến $2000$. Khi phạm vi giá trị nhỏ như thế này thì 90% bài có thể giải quyết bằng mảng đánh dấu – đây là dấu hiệu nhận biết rất quen thuộc đó nha.

Quan sát: x / y chỉ ra được vài giá trị

Với một số $x$ bất kỳ, nếu $x / y = z$ (chia nguyên, $y \ge 1$) thì $z$ chỉ nằm trong đoạn từ $0$ đến $x$ thôi – không thể lớn hơn $x$, cũng không thể nhỏ hơn $0$. Ví dụ $x = 6$:

6/1 = 66/2 = 36/3 = 26/4 = 16/5 = 16/6 = 16/7 = 06/8 = 0…

Từ $y = 7$ trở đi thì $6 / y$ luôn bằng $0$ (vì $y \gt x$). Như vậy $z$ chỉ có các kết quả $0, 1, 2, 3, 6$. Các bạn cũng nhận ra có những giá trị trong đoạn $[0, 6]$ mà không có $y$ nào cho ra: chẳng có cách nào để $6$ chia cho một số mà được $4$ hay $5$ cả.

Vậy giờ ta tạo bảng thống kê: với mỗi giá trị $x$, với mỗi kết quả $z$ từ $0$ đến $x$, lưu lại $y$ nhỏ nhất sao cho $x / y = z$ (lưu $0$ nếu không có $y$ nào). Với $x = 6$:

z	0	1	2	3	4	5	6
y nhỏ nhất	7	4	3	2	0	0	1
giải thích	6/7, 6/8… đều ra 0, nhỏ nhất là 7	6/4, 6/5, 6/6 ra 1 → lấy 4	chỉ có 6/3	chỉ có 6/2	không có	không có	chỉ có 6/1

Cách dựng bảng b[x][z]

Với mỗi $x$ từ $1$ đến $2000$: đặt $b[x][0] = x + 1$ (số nhỏ nhất lớn hơn $x$). Rồi cho $y$ chạy tăng dần từ $1$ đến $x$, tính $z = x / y$; nếu $b[x][z]$ còn bằng $0$ (chưa có ai) thì gán $b[x][z] = y$. Vì $y$ đi từ nhỏ lên lớn nên giá trị được ghi đầu tiên vào mỗi ô chính là $y$ nhỏ nhất. Ô nào cuối cùng vẫn là $0$ nghĩa là không tồn tại $y$.

Duyệt thương chung z

Khi có bảng thống kê rồi thì xét qua mảng $a$ đề cho:

1. Tìm $Min$ của mảng $a$. Thương chung $z$ không thể vượt quá $Min$ (vì $A[i] / B[i] \le A[i]$), nên chỉ cần xét $z$ từ $0$ đến $Min$.
2. Với từng $z$, xét lần lượt từng $a[j]$, lấy $y$ nhỏ nhất của nó là $b[a[j]][z]$. Chỉ cần một $a[j]$ có $b[a[j]][z] = 0$ (không tồn tại $y$) là bỏ qua trường hợp $z$ đó. Còn nếu tất cả $a[j]$ đều có $y$ thì cộng các $y$ lại.
3. Đáp án là tổng nhỏ nhất trong các tổng tìm được.

Đây là bảng thống kê mình làm với ví dụ mẫu ($Min = 6$ nên chỉ cần cột $0..6$):

a \ z	0	1	2	3	4	5	6
18	19	10	7	5	4	0	3
27	28	14	10	7	6	5	4
16	17	9	6	5	4	3	0
22	23	12	8	6	5	4	0
6	7	4	3	2	0	0	1
Tổng	94	49	34	25	✗	✗	✗

Ví dụ với số $18$: giá trị nhỏ nhất mà $18$ chia cho nó được $0$ là $19$; được $1$ là $10$ ($18/10 = 1$); được $2$ là $7$ ($18/7 = 2$)… còn tại cột $5$ thì là $0$ – không có số nào để $18$ chia ra $5$ cả. Các cột $z = 4, 5, 6$ đều dính số $0$ nên loại:

• $z = 4$: không có $y$ nào để $6 / y = 4$.
• $z = 5$: không có $y$ nào để $18 / y = 5$ và $6 / y = 5$.
• $z = 6$: không có $y$ nào để $16 / y = 6$ và $22 / y = 6$.

Còn lại $z = 0, 1, 2, 3$ cho tổng $94, 49, 34, 25$ ⇒ đáp án nhỏ nhất là 25, ứng với $B = [5, 7, 5, 6, 2]$, tức là $18/5 = 27/7 = 16/5 = 22/6 = 6/2 = 3$ 🎉.

Minh hoạ duyệt từng cột z

Em nhập dãy $a$ (các số nhỏ thôi cho dễ nhìn) rồi bấm Tiếp để xem bảng $b[a[j]][z]$ và từng cột $z$ được xét như thế nào:

Dãy a

Ví dụ nhanh:

Mẹo nhỏ: viết thẳng công thức cho y nhỏ nhất

Bạn nào thích toán thì có thể thấy: $y$ nhỏ nhất để $x / y = z$ luôn là $y = x / (z + 1) + 1$ (chia nguyên), và nó hợp lệ khi và chỉ khi kiểm lại $x / y = z$. Ví dụ $x = 18, z = 3$: $y = 18/4 + 1 = 5$, và $18/5 = 3$ ✓; $x = 18, z = 5$: $y = 18/6 + 1 = 4$ nhưng $18/4 = 4 \ne 5$ ✗. Với giới hạn của đề thì cách bảng của mình đã thừa nhanh, mẹo này chỉ để các bạn tham khảo thêm (mình đã thử so khớp nó với cách bảng – ra y hệt).

Bảng của mình là mảng 2 chiều: hàng $x$ có $x + 1$ ô (cột $0..x$). Quan trọng là build ra được cái bảng đó, ra cái bảng rồi thì xét dễ ẹt 😎.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int solve(int a[], int n){
    vector<vector<int>> b(2001);
    for(int i = 1; i <= 2000; ++i){
        b[i].resize(i + 1, 0);
        b[i][0] = i + 1;
        for(int j = 1; j <= i; ++j){
            int x = i / j;
            if(b[i][x] == 0){
                b[i][x] = j;
            }
        }
    }
    int Min = a[0];
    for(int i = 1; i < n; ++i){
        Min = min(Min, a[i]);
    }
    int resMin = INT_MAX;
    int idxMin = -1;
    for(int i = 0; i <= Min; ++i){
        bool check = true;
        int sum = 0;
        for(int j = 0; j < n; ++j){
            sum += b[a[j]][i];
            if(b[a[j]][i] == 0){
                check = false;
                break;
            }
        }
        if(check == true && sum < resMin){
            resMin = sum;
            idxMin = i;
        }
    }
    return resMin;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    cout << solve(a, n);
    return 0;
}

import sys

def solve(a, n):
    b = [[0] * (i + 2) for i in range(2001)]
    for i in range(1, 2001):
        b[i][0] = i + 1
        for j in range(1, i + 1):
            x = i // j
            if b[i][x] == 0:
                b[i][x] = j
    Min = a[0]
    for i in range(1, n):
        Min = min(Min, a[i])
    resMin = float('inf')
    idxMin = -1
    for i in range(0, Min + 1):
        check = True
        sum_ = 0
        for j in range(n):
            if b[a[j]][i] == 0:
                check = False
                break
            sum_ += b[a[j]][i]
        if check and sum_ < resMin:
            resMin = sum_
            idxMin = i
    return resMin

input_data = list(map(int, sys.stdin.read().split()))
n = input_data[0]
a = input_data[1:n+1]
print(solve(a, n))

Lưu ý nhỏ khi đọc code

Trong code, mình cộng sum += b[a[j]][i] trước rồi mới kiểm tra ô đó có bằng $0$ không. Không sao cả, vì nếu ô bằng $0$ thì check = false và tổng đó bị bỏ qua luôn. Biến idxMin lưu lại $z$ tốt nhất (không cần cho đáp án, để bạn nào muốn in luôn dãy $B$ thì dùng). Bản gốc của mình còn một đoạn in bảng 2 chiều chi tiết (đang comment lại) – chính là bảng thống kê ở trên; ở đây mình lược đi cho gọn.

Các bạn bấm từng bước để xem code chạy thế nào. Để dễ theo dõi, mình cho chạy chi tiết vòng dựng bảng ở những hàng $i$ có trong mảng $a$; các hàng khác làm y hệt nên mình gom thành một bước.

C++▶ Chạy tay từng dòng codeDựng bảng b[i][z] = y nhỏ nhất để i / y = z, rồi duyệt z từ 0 đến Min và lấy tổng nhỏ nhất.

Dữ liệu vào (stdin) – sửa thoải mái5 18 27 16 22 6

Dữ liệu mẫu:

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

2using namespace std;

3

4int solve(int a[], int n){

5 vector<vector<int>> b(2001);

6 for(int i = 1; i <= 2000; ++i){

7 b[i].resize(i + 1, 0);

8 b[i][0] = i + 1;

9 for(int j = 1; j <= i; ++j){

10 int x = i / j;

11 if(b[i][x] == 0){

12 b[i][x] = j;

13 }

14 }

15 }

16 int Min = a[0];

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

18 Min = min(Min, a[i]);

19 }

20 int resMin = INT_MAX;

21 int idxMin = -1;

22 for(int i = 0; i <= Min; ++i){

23 bool check = true;

24 int sum = 0;

25 for(int j = 0; j < n; ++j){

26 sum += b[a[j]][i];

27 if(b[a[j]][i] == 0){

28 check = false;

29 break;

30 }

31 }

32 if(check == true && sum < resMin){

33 resMin = sum;

34 idxMin = i;

35 }

36 }

37 return resMin;

38}

39

40int main(){

41 ios::sync_with_stdio(0);

42 cin.tie(0);

43 int n;

44 cin >> n;

45 int a[n];

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

47 cin >> a[i];

48 }

49 cout << solve(a, n);

50 return 0;

51}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này (gọi $V = 2000$ là giá trị lớn nhất của $A[i]$):

• Không gian: bảng $b$ có hàng $i$ dài $i + 1$ ô, tổng cộng khoảng $V^2 / 2 \approx 2 \cdot 10^6$ số int (cỡ 8 MB) – thoải mái.
• Thời gian: dựng bảng mất $1 + 2 + \dots + V \approx 2 \cdot 10^6$ phép chia. Duyệt $z$ từ $0$ đến $Min \le V$, mỗi $z$ đi qua tối đa $N$ phần tử: $O(V \cdot N) \le 2 \cdot 10^6$. Tổng cộng chỉ cỡ vài triệu phép tính.

Không gian$O(V^2)$

Thời gian$O(V^2 + V \cdot N)$

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với 300 bộ test ngẫu nhiên nhỏ ($N \le 8$, $A[i] \le 2000$), so với code vét cạn (thử mọi thương chung $z$ và mọi $y$) – khớp hết. Với test lớn nhất $N = 1000$, $A[i]$ gần $2000$: bản C++ chạy chưa tới 0.05 giây, bản Python khoảng 0.3 giây (chủ yếu là lúc dựng bảng) – rất thoải mái.

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 😇