thảo luận Leetcode contest, đường tới Guardian

[lovelyly]

Leetcode weekly lần này có vẻ dễ

 

[conalsun]

thôi bỏ q4 đi ăn sáng

 

[ti_say_hi]

Nghỉ sớm thôi, câu Q3 không có ý tưởng nơi

 

[seastar]

Contest nay hơi dễ. Bài 2 làm ẩu ăn 1 bọ,

 

[NguyenQUy1801]

câu 4 dp kiểu gì mấy bác nhỉ

 

[hieunm3538]

câu 4 dp kiểu gì mấy bác nhỉ

Không dùng dp cũng được )

 

[NguyenQUy1801]

2 3 tuần bỏ contest choke lòi kèn may vẫn đấm đủ 4q )

 

[NguyenQUy1801]

Không dùng dp cũng được )

bác cho e xin cách giải này với ạ

 

[freedom.9]

Má nó cái câu 2 cay thật.
Ăn 4 câu mà giải câu 2 mất cả tiếng đồng hồ gang thật

 

[freedom.9]

Contest nay hơi dễ. Bài 2 làm ẩu ăn 1 bọ,
View attachment 2500097

Đm nó toy làm bài 2 mất cả tiếng đồng hồ ăn cứt gà

 

[freedom.9]

Ae giải 4 bài 30ph kinh vãi nhái

 

[hieunm3538]

bác cho e xin cách giải này với ạ

Hết contest nhé

 

[ti_say_hi]

Chày cối được 3 câu, câu 4 không giải đc nơi

 

[lilleboybk]

Lần đầu em giải được Q4 . Tuy k<= 10^9, nhưng may phát hiện ra tập trạng thái để quy hoạch động lại khá nhỏ.

 

[maskup]

bài 2 đâm đầu vô segment tree rồi fix bug các kiểu tốn bà nó hơn 30 phút

 

[NguyenQUy1801]

Má nó cái câu 2 cay thật.
Ăn 4 câu mà giải câu 2 mất cả tiếng đồng hồ gang thật

E cũng hao hao bác , q2 ăn 3 bug

 

[freedom.9]

View attachment 2500185
Lần đầu em giải được Q4 . Tuy k<= 10^9, nhưng may phát hiện ra tập trạng thái để quy hoạch động lại khá nhỏ.

Ừ đúng rồi fence, thực ra nhảy lên 2^i thì i chỉ có 9 thôi, thêm cái boolean nữa thì dp 3 chiều là dễ dàng.
Bài 3 dễ mà giải bài 2 tốn tgian quá gang thật, biết là xài prefixSum rồi mà quên mẹ mất cách biến đổi, khuya rồi đầu óc thật sự rất ngáo

 

[ti_say_hi]

Má nó cái câu 2 cay thật.
Ăn 4 câu mà giải câu 2 mất cả tiếng đồng hồ gang thật

câu 2 em cũng bị 3 bug.
Lúc đầu em dùng chia để trị + cache nhưng vẫn bị TLE.
Sau đó em thấy tính monotonic, nếu A[l..r] không phải special thì => A[l..r+1] cũng không phải special => nên chọn binary search + cache

 

[lovelyly]

View attachment 2500094Nghỉ sớm thôi, câu Q3 không có ý tưởng nơi

Q3: đếm số chữ số theo từng hàng, từ hàng đơn vị lên hàng chục, hàng trăm,...
Ở mỗi hàng, đếm xong nếu thấy có m chữ số i, n chữ số j (với i khác j) thì result += m * n...

câu 4 dp kiểu gì mấy bác nhỉ

Q4: Sau m lần nhảy lên và n lần đi xuống thì sẽ dừng ở bậc thang 1 + 2^0 + 2^1 + ... + 2^(m-1) - n = 2*m - n
=> Với mỗi giá trị m tính n để 2*m - n = k rồi tính xem có bao nhiêu cách để nhảy lên m lần và đi xuống n lần (lưu ý: không được đi xuống 2 lần liên tục)

 

[hieunm3538]

câu 4 dp kiểu gì mấy bác nhỉ

Mình tìm số lần nhảy có thể dẫn đến bậc thang k, công thức là k = 2 **(jump) - back với 0 < back < jump + 1. Sau đấy duyệt từng số lượt jump, tính comb(jump + 1, back) là xong