thảo luận [Học Tập] Topic thuật toán

htss said:
Linked list khác array nhé, array truy xuất O(1), linked list truy xuất O(n).

còn array ko bị giới hạn bởi bộ nhớ là dynamic array (mảng động) hay vector trong c++.
Click to expand...
giống ở đây là nó có thể lưu các element ấy thím, còn tốc độ truy xuất thì giữa 3 cái là khác nhau rồi :v
 
Coffe_Bên_Lề said:
giống ở đây là nó có thể lưu các element ấy thím, còn tốc độ truy xuất thì giữa 3 cái là khác nhau rồi :v
Click to expand...
truy xuất thì thằng vector với array như nhau thôi. thằng vector thì tự sửa kích thước nó được trong O(1). còn linked list thì nó lại truy xuất chậm, ứng dụng vô mấy cái khác như skip list.

còn lưu element thì cấu trúc dữ liệu nào cũng lưu element hết.
hB8nmx5.png
mỗi cái dùng trghợp khác nhau thôi.
 
htss said:
truy xuất thì thằng vector với array như nhau thôi. thằng vector thì tự sửa kích thước nó được trong O(1). còn linked list thì nó lại truy xuất chậm, ứng dụng vô mấy cái khác như skip list.

còn lưu element thì cấu trúc dữ liệu nào cũng lưu element hết.
hB8nmx5.png
mỗi cái dùng trghợp khác nhau thôi.
Click to expand...
lần đầu mới nghe skip list, kiến thức còn nông cạn nên em sẽ tiếp thu thêm :):)
 
Yêu em Thu Nga CN12 ptit said:
seunMSF.png

bác nào rảnh cho em ý tưởng bài này với ạ @@
Click to expand...
ý tưởng của em là sẽ xét từng cặp, dạng này có thể dùng backtracking nhưng độ phức tạp truy xuất có thể là O(N^2) nếu xét theo từng cặp, ở đây là giống test case 1 nhân 3->4->5 + 3+4+5 là tổng đầu tiên kiếm được, nhân (3->4), (3-> 5), (4->5) ra tổng bội số chung nhỏ nhất, nhưng cái này sẽ không hiệu quả khi gặp input lớn
 
Coffe_Bên_Lề said:
ý tưởng của em là sẽ xét từng cặp, dạng này có thể dùng backtracking nhưng độ phức tạp truy xuất có thể là O(N^2) nếu xét theo từng cặp, ở đây là giống test case 1 nhân 3->4->5 + 3+4+5 là tổng đầu tiên kiếm được, nhân (3->4), (3-> 5), (4->5) ra tổng bội số chung nhỏ nhất, nhưng cái này sẽ không hiệu quả khi gặp input lớn
Click to expand...
Ý là dùng brute-force đúng k? Nếu tạm coi việc tìm bcln là O(1) đi thì dùng brute-force trong bài này sẽ có độ phức tạp là 2^n.
 
thuyduong2007 said:
Ý là dùng brute-force đúng k? Nếu tạm coi việc tìm bcln là O(1) đi thì dùng brute-force trong bài này sẽ có độ phức tạp là 2^n.
Click to expand...
trình em còn non, nên em nghĩ dùng vét cạn là ngon nhất rồi, thím có ý tưởng gì khác không á? dạng này cũng có thể dùng công thức toán là thuận lợi nhất, nhưng em ngu toán quá :beat_brick::beat_brick:
 
Last edited:
Yêu em Thu Nga CN12 ptit said:
seunMSF.png

bác nào rảnh cho em ý tưởng bài này với ạ @@
Click to expand...
qui hoạch động thôi thím.

với mỗi số, phân tíhc nó thành thừa số nguyên tố.

vd n = 3, có 2, 6, 7
2 = 2
6 = 3 * 2
7 = 7

có thể biểu diễn mỗi số tạo được bằng một dãy số [b_0,b_1,b_2, ...] , vậy số đó là 2^b_0 * 3 ^b_1 * 5 ^ b_2 * ...

nhận thấy a <= 500, và lũy thừa lớn nhất của các snt <= 500 là: 2^8 <= 500, 3^5, 5^3 ,7^3, 11^2, 13^2, 17^2, 19^2. các snt > 19 thì chỉ có thể xuất hiện 0 hoặc 1 lần trong mỗi phân tích, thế nên ko cần lưu lại. vậy có tối đa 9 * 6 * 4 * 4 * 3 * 3 * 3 *3 = 69984 trạng thái trong mảng DP, với dp là thành phần chung.

vậy với mỗi phân tích thừa số nguyên tố, loại bỏ các thừa số > 19, lúc này số này số LCM có thể tạo ra là 69984.

rồi :
Nhóm các số theo thừa số nt > 19.

VD: 2, 3, 46, 69,62, 93, 74, 111
nhóm thành [2,3], [46,69] (thừa số 23), [62, 93] (thừa số 31), [74, 111](thừa số 37)
-> [2,3], 23 * [2,3], 31 * [2,3], 37 * [2,3]

áp dụng DP như đã mô tả vào từ nhóm đầu tiên.

Ra được các trạng thái như sau:

dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[6] = 1
-> lưu lại trong save

tới phần từ đầu trong nhóm 2 (là 2) gộp với nhóm 1 với cùng mảng dp từ nhóm 1:
dp[1] = 1
dp[3 = 2^0 * 3^1] = 1
dp[2^1 * 3^0 = 2] =3 (2 lặp lại 2 lần kết hợp 3 dc 2 tập con)
dp[2^1 * 3^1 = 6] = 3 (2 lặp lại 2 lần kết đc 3 tập con)
tượng tự, tới phần tử thứ 2 trong nhóm 3 (là 3) gợp với mảng dp từ nhóm 1:
duyệt qua hết nhóm 2 ra được:
dp[1] = 1
dp[3] = 3
dp[2] = 3
dp[6] = 9
kiểm tra lại thấy 1 + 3 + 3 + 9 = 16 = 2^4 (là số tập con có trong 16 tập).

sau đó, tính lại dp bằng mảng save:

dp <- (dp - save)* 23 + save
trong đó (dp - save) là số lượng tập sẽ được lập, chỉ dùng 23 thêm, cộng thêm với số tập từ nhóm 1.
vậy mảng dp được tạo ra từ nhóm 1 và 2:
dp[1] = (1 - 1) * 23 + 1 =1
dp[3] = (3 - 1) * 23 + 1 = 2 * 23 + 1
dp[2] = (3 - 1) * 23 + 1 =2 * 23 + 1
dp[6] = (9 - 1) * 23 + 1= 8 * 23 + 1
ra được tổng lcm của các tập con từ 2 nhóm đầu là (tính luôn 1 tập rỗng lcm = 1):
1*1+ 2*(2 * 23 + 1) + 3*(2 23 + 1) + 6(8 * 23 + 1) = 1346

tương tự như vậy, lưu lạii dp vào save, tính tiếp với nhóm 3.


nghĩ lại chút làm thuần DP thế này hay hơn
TG0OxM9.gif
không phải brute force như cách trước.
 
Last edited:
htss said:
qui hoạch động thôi thím.

với mỗi số, phân tíhc nó thành thừa số nguyên tố.

vd n = 3, có 2, 6, 7
2 = 2
6 = 3 * 2
7 = 7

có thể biểu diễn mỗi số tạo được bằng một dãy số [b_0,b_1,b_2, ...] , vậy số đó là 2^b_0 * 3 ^b_1 * 5 ^ b_2 * ...

nhận thấy a <= 500, và lũy thừa lớn nhất của các snt <= 500 là: 2^8 <= 500, 3^5, 5^3 ,7^3, 11^2, 13^2, 17^2, 19^2. các snt > 19 thì chỉ có thể xuất hiện 0 hoặc 1 lần trong mỗi phân tích, thế nên ko cần lưu lại. vậy có tối đa 9 * 6 * 4 * 4 * 3 * 3 * 3 *3 = 69984 trạng thái trong mảng DP.

vậy với mỗi phân tích thừa số nguyên tố, loại bỏ các thừa số > 19, lúc này số này số LCM có thể tạo ra là 69984.

vậy mảng dp[70000], thể hiện tới vị trí i, đếm số luần mỗi LCM từ 1 -> 70000 xuất hiện. và tính LCM với a hiện tại và cộng vào. dp[LCM(j, a)] với mỗi j từ 1 tới 70000 và LCM(j, a) < 70000. với các a có thừa số > 19, số thừa số > 19 trong a chỉ có thể là 0 hoặc 1, lúc này tách riêng các a này ra tập khác. lấy riêng các thừa số > 19 ra. trong tập này, nhận thấy nếu có thừa số > 19 thì các thừa số còn lại tích không quá 21 (500 / 23 ~= 21). lúc này chỉ cần brute force qua tập này là xong O(2^21).
Click to expand...
Vẫn k hiểu đoạn bruce force khi thừa số lớn hơn 19 lắm, thím có thể làm hộ ví dụ với case này không ?
Code: 
[3, 6, 23, 91]

Mình thấy worst case khi dùng qhđ là lúc toàn bộ các phần tử đều là snt (từ 1-500 có khoảng 90 snt). Lúc này thì bất kì một tập con nào cũng sẽ có bcnn là khác nhau, nên dùng qhđ cũng k tối ưu được gì. Đpt suy biến về 2^n, với n = 90 thì k thể giải được. K biết cách trên của bạn có xử lý được case này k ? Ví dụ một mảng như dưới đây, mình thật sự k nghĩ ra cách nào ngoài brute-force:
Code: 
[23, 29, 31, 37, 41]
 
htss said:
tập các tập có thừa số lớn, ta chia thành nhiều tập, theo (a / thùa số lớn của a)

vậy cái vd của thím:


[23, 29, 31, 37, 41]
tập [1]: [23, 29, 31, 37, 41], kết quả là (1 + 23) * (1+ 29) * (1+31) * (1+37) * (1+41) - 1, tính trong O(n).

VD: 46, 58, 93, 111, 82

46= 2 * 23
58 = 2 * 29
93 = 3 * 31
111 = 37 * 3
82 = 41 * 2

vậy, [2] : [46, 58, 82],
[3]: [93, 111]

vậy, tổng của toàn bộ các tập có thể trong tập [2] là 2 * ((1 + 23)* (1+29) * (1 + 41) - 1) = 58462.

tương tư, tổng của toàn bộ các tập có thể trong tập [3] là 3 * ((1 + 31)* (1+37) - 1) = 3645.

nhập 2 tập lại: 58462 + 3645 + 58462 * 3645 là kết quả.

nhận xét thấy sẽ có ko quá 20 tập (vì a < 500), thế nên brute force qua toàn tập của các tập và nhập tập các tập.

trong quá trình nhập các tập, nếu trùng các thừa số (vd 2 và 4 hay 6 và 4 ), thì dùng nguyên lí bao hàm loại trừ để giải quyết.
Click to expand...
Thank fen, nói thiệt mình vẫn hiểu lờ mờ thôi. Nhưng có 2 point mình thấy:
1. Đáp án của fen đưa ra là 58462 + 3645 + 58462 * 3645 = 213156097
Trong khi đáp án của bài trên là 220506433 (Mình brute-force bằng cơm). K biết mình hiểu sai chỗ nào k nữa T_T:
1629822921018.png


2. Việc combine kết quả của các tập thật ra cũng là bài toán 2^n, với n là số tập ? Đơn cử như trong trường hợp toàn bộ các phần tử input đều là số nguyên tố như mình share ở trên ? K biết mình hiểu đúng k ?

Edit: sry, để xem lại đã :D
 
htss said:
thím tính đúng rồi, mình bấm máy nhầm mấy phép tính ở trên.
H72qlgA.png

còn trường hợp số nguyên tố như trên thì tính theo công thức : (1 + a_0) * (1+a_1) * (1+a_2) * ... -1 ... ấy thím.
Click to expand...
Đã hiểu, h mới ngộ ra vụ 1 + a_i. Thank fen chỉ giáo nhiều :D.
 

Similar threads

Zuytori
Tiếp nhận đơn xin khai thác 'kho báu' 3 tấn vàng dưới lòng sông ở Bình Thuận
Replies
8
Views
473
yokitonara
Y
Nobitadiradivo
Phê duyệt gần 14.000 tỷ đầu tư tuyến đường nối cao tốc Biên Hòa – Vũng Tàu
Replies
4
Views
367
TraChanhMuoiMe
TraChanhMuoiMe
BaryonicLord
Tính toán kịch bản đánh thuế tiêu thụ đặc biệt, đảo ngược xu hướng tiêu thụ đồ uống có đường
2 3
Replies
47
Views
3K
Cún Xjnh
Cún Xjnh
sankhaukich
Nước cống đen kịt xả ra vịnh Hạ Long
4 5 6
Replies
103
Views
8K
Han sara
Han sara
N
thắc mắc Tìm phim trộm vàng
Replies
2
Views
111
nottelling
N

Share this page

Back
Top