Khôi Phục Mảng A Từ Bảng Tổng

Nguồn: Bài tập Facebook (đề thi chấm online) Độ khó: Dễ Mảng 2 chiều Tư duy Nhận xét

Đề bài

Bạn X có một mảng số nguyên $A$ gồm $n$ phần tử $A_1, A_2, \ldots, A_n$. X lập một bảng mà hàng đầu tiên và cột đầu tiên ghi các phần tử của mảng $A$, còn ô ở hàng $A_i$, cột $A_j$ ghi tổng $A_i + A_j$:

	A1	A2	…	An
A1	A1+A1	A1+A2	…	A1+An
A2	A2+A1	A2+A2	…	A2+An
…	…	…	…	…
An	An+A1	An+A2	…	An+An

Tuy nhiên, trong một lần vô ý, X đã xóa mất hàng đầu tiên và cột đầu tiên của bảng này. Hãy giúp X tìm lại mảng $A$ từ bảng còn lại.

Đầu vào:

• Số nguyên $n$ chỉ kích thước mảng $A$ $(1 \le n \le 1000)$.
• $n$ dòng, mỗi dòng có $n$ số nguyên, mỗi số nguyên có giá trị tuyệt đối không quá $5000$.

Đầu ra: Chương trình in ra $n$ số nguyên của mảng $A$, mỗi số nguyên cách nhau 1 khoảng trắng, không có khoảng trắng ở cuối cùng.

Lưu ý:

• Thí sinh tự viết chương trình từ đầu đến cuối, dữ liệu được đọc vào từ đầu vào chuẩn (stdin), và xuất kết quả ra đầu ra chuẩn (stdout).
• Đề đảm bảo tồn tại mảng $A$ thỏa yêu cầu đã cho.
• Thí sinh có tối đa 3 lần nộp bài. Khi nộp sai, thí sinh sẽ không bị trừ điểm.

Ví dụ (mình tự thêm) – input

3
2 -1 4
-1 -4 1
4 1 6

Ví dụ (mình tự thêm) – output

1 -2 3

Lời mở đầu

Anh em thử sức với bài tập xử lý mảng này nhé 🤗. Bài này nhìn thì dễ, nhưng sẽ khó nếu bị giới hạn bộ nhớ được phép dùng. Lúc này phải nhìn ra mấu chốt để AC. Đây cũng là một kinh nghiệm cho anh em khi làm trên các web chấm bài 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

Bài này xuất phát từ một bạn nhắn tin hỏi mình. Bạn ấy đã hiểu là những phần tử trên đường chéo chính chia 2 là ra các phần tử cần tìm, nhưng lấn cấn ở chỗ: đầu vào là "một mảng" hay là "những dòng được nhập vào", và có phải tạo mảng động để nhét từng phần tử vào rồi lúc cần gọi ra không. Mình viết lại cuộc trò chuyện đó thành bài giải chi tiết để nhiều bạn được tham khảo.

Đề gốc không kèm ví dụ nên mình tự thêm một ví dụ: mảng $A = [1, -2, 3]$ thì bảng đầy đủ (sau khi bị xóa hàng đầu, cột đầu) là:

• Hàng 1: $1+1 = 2,\ 1+(-2) = -1,\ 1+3 = 4$.
• Hàng 2: $-2+1 = -1,\ -2+(-2) = -4,\ -2+3 = 1$.
• Hàng 3: $3+1 = 4,\ 3+(-2) = 1,\ 3+3 = 6$.

Nhiệm vụ của mình là đi ngược lại: từ bảng $3 \times 3$ này tìm lại $1, -2, 3$.

Mấu chốt

Ô ở hàng $i$, cột $i$ (đường chéo chính) chính là $A_i + A_i = 2A_i$, nên $A_i = \dfrac{\text{ô}[i][i]}{2}$. Trong ví dụ: đường chéo là $2, -4, 6$ ⇒ chia 2 được $1, -2, 3$.

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

Cách 1Mảng 2 chiều · O(n²) bộ nhớCách 21 biến x, đường chéo · O(1) bộ nhớCách 3Chỉ dùng dòng đầu · O(1) bộ nhớ

Cách 1Cách chính quy: đọc vào mảng 2 chiều – O(n²) bộ nhớ

Đề nói rõ dữ liệu input đầu vào là mảng 2 chiều có $n$ dòng, $n$ cột, vì vậy cách chính quy là tạo mảng 2 chiều đúng như vậy để đọc dữ liệu vào, sau đó có mảng rồi thì xử lý trên mảng đó: in ra a[i][i] / 2 với $i$ chạy từ đầu đến cuối.

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

#include <iostream>
using namespace std;
int a[1005][1005];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];
    for(int i = 0; i < n; i++){
        if(i > 0) cout << " ";
        cout << a[i][i] / 2;
    }
    return 0;
}

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
print(' '.join(str(a[i][i] // 2) for i in range(n)))

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

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

Tốn bộ nhớ không cần thiết

Với $n = 1000$ thì mảng 2 chiều có $10^6$ số. Nếu web chấm giới hạn bộ nhớ chặt (ví dụ chỉ vài MB), hoặc bạn khai báo mảng cục bộ trong main (dễ tràn stack), thì cách này bị lỗi. Mà thật ra ta chỉ cần $n$ số trên đường chéo thôi!

Cách 2Một biến x đọc hết input, canh vị trí đường chéo chính – O(1) bộ nhớ

Tuy nhiên bản chất ta nhìn thấy một điều là không cần phải tốn nhiều bộ nhớ để tạo ra mảng 2 chiều đọc vào làm gì. Giả sử giờ ta tạo ra một biến số nguyên $x$, cho đọc dữ liệu đủ $n \cdot n$ lần vào biến $x$ thì coi như đã đọc hết được input của đề bài. Và trong quá trình lặp $n \cdot n$ lần đó, với những trường hợp $x$ ở trên đường chéo chính thì ta xuất kết quả $x / 2$ ra màn hình, đó là đáp án của bài này. Như thế này thì khỏe hơn rất nhiều, chẳng cần mảng lưu trữ gì cả 😃.

Lần đọc thứ mấy thì rơi vào đường chéo chính?

Giả sử $n = 5$, tức là ta cần lặp 25 lần để đọc dữ liệu bảng $5 \times 5$ vào biến $x$, thì ở các lần đọc thứ $1, 7, 13, 19, 25$ sẽ là các trường hợp mà tại đó $x$ là giá trị trên đường chéo chính. Tương tự giả sử $n = 8$ thì tại các lần đọc $1, 10, 19, 28, 37, 46, 55, 64$ sẽ là các giá trị tại đường chéo chính.

Vậy các bạn có nhìn ra công thức tổng quát không? Bắt đầu từ 1, và cứ tại các lần tiếp theo cộng thêm $(n + 1)$ thì sẽ là các lần mà giá trị tại đó nằm trên đường chéo chính. Ví dụ $n = 8$ thì bắt đầu từ 1, rồi cứ thế $+9$ cho đến khi nào chạm đến $n \cdot n = 64$ thì dừng.

Công thức

Lần đọc thứ $i$ (đếm từ 1) nằm trên đường chéo chính khi và chỉ khi $(i - 1) \bmod (n + 1) = 0$. Lý do: ô hàng $r$, cột $c$ (đếm từ 0) được đọc ở lần thứ $i = r \cdot n + c + 1$; ô đường chéo $r = c$ cho $i - 1 = r \cdot (n + 1)$.

Các bạn nhập bảng rồi bấm Tiếp để xem từng lần đọc vào biến $x$, ô nào thuộc đường chéo chính thì được in ra:

Mảng A gốc (để tạo bảng)

Ví dụ nhanh:

Số nhỏ ở góc mỗi ô là thứ tự lần đọc; ô xanh lá là ô đường chéo đã đọc, ô tím là ô đã đọc nhưng bỏ qua.

Xử lý "không có khoảng trắng ở cuối"

Vì đề đã nói không được có khoảng trắng ở cuối cùng nên ta cho vòng lặp chạy đến < size, tức là $n \cdot n - 1$ lần thôi (mỗi lần in kèm một dấu cách phía sau), còn lần đọc cuối cùng làm riêng nó ra bên ngoài để không bị khoảng trắng ở cuối. Lần đọc cuối (thứ $n \cdot n$) luôn là ô $[n][n]$ trên đường chéo, vì $n \cdot n - 1 = (n - 1)(n + 1)$ chia hết cho $n + 1$.

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

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int x;
    int size = n * n;
    for(int i = 1; i < size; ++i){
        cin >> x;
        if((i - 1) % (n + 1) == 0)
            cout << x / 2 << " ";
    }
    cin >> x;
    cout << x / 2;
    return 0;
}

import sys

def tokens():  # đọc từng dòng, không lưu cả bảng
    for line in sys.stdin:
        yield from line.split()

it = tokens()
n = int(next(it))
size = n * n
res = []
for i in range(1, size + 1):
    x = int(next(it))
    if (i - 1) % (n + 1) == 0:
        res.append(x // 2)
print(' '.join(map(str, res)))

C++▶ Chạy tay từng dòng codeĐọc n·n số vào cùng một biến x; lần đọc thứ i với (i − 1) % (n + 1) == 0 là ô đường chéo, in x / 2.

Dữ liệu vào (stdin) – sửa thoải mái3 2 -1 4 -1 -4 1 4 1 6

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 int x;

8 int size = n * n;

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

10 cin >> x;

11 if((i - 1) % (n + 1) == 0)

12 cout << x / 2 << " ";

13 }

14 cin >> x;

15 cout << x / 2;

16 return 0;

17}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ vài biến $n$, $x$, $size$, $i$: $O(1)$.
• Thời gian: vẫn phải đọc hết $n^2$ số: $O(n^2)$.

Không gian$O(1)$

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

Bản Python

Trong bản Python mình đọc input theo từng dòng (hàm tokens()) thay vì sys.stdin.read() cả file, để đúng tinh thần "không lưu cả bảng". Các phần tử đáp án gom vào list rồi ' '.join nên tự nhiên không có khoảng trắng cuối.

Cách 3Chỉ cần dòng đầu tiên – O(1) bộ nhớ

Hoặc ta có thể nhìn thấy rõ hơn như sau. Hãy nhìn dòng đầu tiên: $A_1 + A_1,\ A_1 + A_2,\ A_1 + A_3,\ \ldots,\ A_1 + A_n$. Nghĩa là $n$ số đầu tiên thì đều có $A_1$ cộng dồn vào. Nên với số đầu tiên ta chia 2 thì ra được $A_1$; từ đó các giá trị tiếp theo trên dòng đầu tiên trừ cho $A_1$ này sẽ ra được $A_2, A_3, A_4, \ldots, A_n$. Còn lại thì $n - 1$ dòng còn lại cứ đọc vào thôi nhưng không xử lý gì cả.

Công thức

$A_1 = \dfrac{b_{1,1}}{2}$, và $A_j = b_{1,j} - A_1$ với $j = 2..n$ ($b_{1,j}$ là số thứ $j$ ở dòng đầu tiên).

Trong ví dụ: dòng đầu là $2, -1, 4$ ⇒ $A_1 = 2 / 2 = 1$, $A_2 = -1 - 1 = -2$, $A_3 = 4 - 1 = 3$. Đúng $1, -2, 3$ 👍.

Tóm lại không cần nhất thiết phải tạo mảng 2 chiều lưu trữ rồi đọc giá trị từ input vô mảng làm gì, cứ đại diện biến $x$ cho nó đọc đủ input thôi, rồi canh những vị trí thích hợp để xử lý in ra kết quả tương ứng là được 😃.

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

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int x;
    cin >> x;
    int a1 = x / 2;
    cout << a1;
    for(int i = 1; i < n; ++i){
        cin >> x;
        cout << " " << x - a1;
    }
    for(int i = 1; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> x;
    return 0;
}

import sys

n = int(sys.stdin.readline())
row = list(map(int, sys.stdin.readline().split()))  # chỉ cần dòng đầu tiên
a1 = row[0] // 2
print(' '.join(str(x - a1) for x in row))

Mình bổ sung một dòng

Trong đoạn code mình gõ nhanh lúc nhắn tin, mình tính a1 = x / 2 rồi in các số " " << x - a1 nhưng quên in chính $A_1$ ra trước. Ở đây mình thêm dòng cout << a1; (dòng 10) cho đủ $n$ số; nhờ in $A_1$ trước, các số sau in kèm dấu cách phía trước nên cũng không bị khoảng trắng cuối. Bản Python chỉ cần đọc đúng dòng đầu tiên là đủ.

C++▶ Chạy tay từng dòng codeA1 = (số đầu tiên) / 2, các số còn lại của dòng đầu trừ A1; n − 1 dòng sau đọc bỏ.

Dữ liệu vào (stdin) – sửa thoải mái3 2 -1 4 -1 -4 1 4 1 6

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 int x;

8 cin >> x;

9 int a1 = x / 2;

10 cout << a1;

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

12 cin >> x;

13 cout << " " << x - a1;

14 }

15 for(int i = 1; i < n; ++i)

16 for(int j = 0; j < n; ++j)

17 cin >> x;

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(n^2)$ (vẫn đọc hết input)

Chia 2 với số âm

Số trên đường chéo là $2A_i$ nên luôn chẵn, phép chia 2 luôn chia hết, kể cả khi âm (ví dụ $-4 / 2 = -2$). Vì vậy dùng x / 2 trong C++ hay x // 2 trong Python đều cho kết quả đúng.

Ghi chú của mình: code C++ và Python của cả 3 cách đã được kiểm tra với 300 bộ test ngẫu nhiên ($n \le 8$, $|A_i| \le 2500$): sinh mảng $A$, lập bảng tổng rồi so output với mảng $A$ gốc theo từng byte (đúng định dạng, không có khoảng trắng cuối) – khớp hết. Với $n = 1000$ (một triệu số), các bản C++ chạy khoảng 0.3–0.4 giây.

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 😇