thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

freedom.9

Senior Member

• 28/9/25

• #961

Husqvarna701SM đã nói:

dùng bottom up làm ý tưởng xử lý bài 4 luôn thím

Nhấp để mở rộng...

Mình cắm đầu đi top down mà mix ko đc cái prefixSum, đi bottom up từ đầu thì chắc đủ thời gian xử lí rồi. Contest này toang rồi

 

aNotHeRNo0b

Senior Member

• 28/9/25

• #962

Bài 2:

 

Windows 2001

Member

• 28/9/25

• #963

Làm được Q4 mà Q3 không nghĩ ra

 

Husqvarna701SM

Senior Member

• 28/9/25

• #964

Windows 2001 đã nói:

Làm được Q4 mà Q3 không nghĩ ra
Xem tệp đính kèm 3259315

Nhấp để mở rộng...

thím đắp Q4 vào Q3 ăn luôn mà nhỉ?

 

freedom.9

Senior Member

• 28/9/25

• #965

Q4 sao AC nhiều thế, n cao vãi mà nhỉ. Phải có cách xử lí LogN chứ

 

aNotHeRNo0b

Senior Member

• 28/9/25

• #966

freedom.9 đã nói:

Q4 sao AC nhiều thế, n cao vãi mà nhỉ. Phải có cách xử lí LogN chứ

Nhấp để mở rộng...

:v giải cho n nhỏ rồi brake n lớn về m lần n nhỏ có được không bác?

 

Windows 2001

Member

• 28/9/25

• #967

Husqvarna701SM đã nói:

thím đắp Q4 vào Q3 ăn luôn mà nhỉ?

Nhấp để mở rộng...

T giải Q4 theo cách dưới đây. Độ phức tạp là O((r-l)^3 * log(n)) lận, cho vào Q3 không được.

Mã:

Tính số ZigZag array có arr[1] > arr[0] trước:
dp: dict chứa các matrix
dp[length][i][j]: số ZigZag array có có số phần tử là length, giá trị đầu là i, giá trị cuối là j
Để tính dp[n]: Chia mảng thành 2 phần có độ dài length1 và length2, phần đầu có số phần tử lẻ, 2 phần có 1 phần tử chung.
[LIST]
[*]Nếu n chẵn => length1 = n-1, length2 = 2
[*]Nếu n lẻ => length1 = n//2 hoặc n//2 + 1, length2 = n - length1 + 1
[*]dp[n] = dp[length1] . dp[length2] (nhân ma trận)
[/LIST]
Số ZigZag array có arr[1] < arr[0] cũng bằng trường hợp trên.

 

Sửa lần cuối: 28/9/25

Husqvarna701SM

Senior Member

• 28/9/25

• #968

à ừa q3 r-l 2000, chắc do t ném cách dp vào Q4 trc tạch ném vào Q3 ăn ))
câu cuối xử lý theo hướng này thôi:
Các chuỗi tăng với giảm song ánh 1-1, nên tổng toàn bộ chuỗi bằng 2* chuỗi bắt đầu tăng trước
Xong dùng ma trận chuyển trạng thái của vector ban đầu là [1,1,...,1] (v = số chuỗi kết thúc ở vị trí i) xong nhân ma trận đủ n lần thôi, nhân ma trận thì log n

 

freedom.9

Senior Member

• 28/9/25

• #969

Đần quá, chỉ cần xử lí cái direction chỉ cho nó up down là ngon tự dưng đi kẹp thêm cái biến streak làm mẹ gì ko biết DNA issue rồi

 

huungphan

Member

• 28/9/25

• #970

mấy thím trong này sôi nổi quá, như này thì pv faang chắc cũng đơn giản nhỉ?

 

Husqvarna701SM

Senior Member

• 28/9/25

• #971

huungphan đã nói:

mấy thím trong này sôi nổi quá, như này thì pv faang chắc cũng đơn giản nhỉ?

Nhấp để mở rộng...

K biết thím cod móc mỉa gì k chứ phỏng vấn vô vàn yếu tố lắm
Ví dụ nhưu hai bài cuối contest sáng nay bị hỏi thì gãy phết đấy nếu nó xoáy vào điều kiện liên tục
Chưa kể k phải có mỗi dsa trong phỏng vấn nữa.

 

huungphan

Member

• 28/9/25

• #972

Husqvarna701SM đã nói:

K biết thím cod móc mỉa gì k chứ phỏng vấn vô vàn yếu tố lắm
Ví dụ nhưu hai bài cuối contest sáng nay bị hỏi thì gãy phết đấy nếu nó xoáy vào điều kiện liên tục
Chưa kể k phải có mỗi dsa trong phỏng vấn nữa.

Nhấp để mở rộng...

móc mỉa gì đâu, mấy cty tier 1/faang thì pv mid level hỏi dsa là chính mà, mà đa số là medium thôi, chừng nào senior thì mới đòi hỏi cao về system design. Trong này quất hard ầm ầm làm mình thắc mắc là mấy thím có đi pv ko?

 

aNotHeRNo0b

Senior Member

• 28/9/25

• #973

huungphan đã nói:

móc mỉa gì đâu, mấy cty tier 1/faang thì pv mid level hỏi dsa là chính mà, mà đa số là medium thôi, chừng nào senior thì mới đòi hỏi cao về system design. Trong này quất hard ầm ầm làm mình thắc mắc là mấy thím có đi pv ko?

Nhấp để mở rộng...

:v tương lai sẽ có bác ạ, chuẩn bị chờ có cơ hội là quất luôn thôi bác

 

athxzz

Senior Member

• 28/9/25

• #974

huungphan đã nói:

móc mỉa gì đâu, mấy cty tier 1/faang thì pv mid level hỏi dsa là chính mà, mà đa số là medium thôi, chừng nào senior thì mới đòi hỏi cao về system design. Trong này quất hard ầm ầm làm mình thắc mắc là mấy thím có đi pv ko?

Nhấp để mở rộng...

thím đi pv FAANG r à, tôi tưởng nó có nhiều round vl mà chẳng nhẽ hỏi mỗi dsa

 

aNotHeRNo0b

Senior Member

• 28/9/25

• #975

athxzz đã nói:

thím đi pv FAANG r à, tôi tưởng nó có nhiều round vl mà chẳng nhẽ hỏi mỗi dsa

Nhấp để mở rộng...

Míc cờ rô sóp - SWE II 4 vòng full thuật toán đấy bác

 

Bruno Mars.

Senior Member

• 28/9/25

• #976

athxzz đã nói:

thím đi pv FAANG r à, tôi tưởng nó có nhiều round vl mà chẳng nhẽ hỏi mỗi dsa

Nhấp để mở rộng...

Dưới level senior/staff thì full thuật toán nhé bác, vào húp đi

 

athxzz

Senior Member

• 28/9/25

• #977

Phận vozlit rating 1900 thua đại đa số ae ở đây, hứa cày 2200 rồi đi apply mấy công ty tier 1.

 

freedom.9

Senior Member

• 29/9/25

• #978

Q3 khá hay, lâu rồi ko thấy contest ra mấy bài hay thế này.
Sau mấy bài mà cần prefix sum dp thì đi luôn bottom up cho nhẹ đầu, optimize top down mệt quá.
Với lại nhìn ko ra cái vụ up down theo kiểu ziczag. Nói chung làm ko ra nhưng khá thỏa mãn sau khi giải lại

Python viết code bị TLE khá tào lao, đề cứ cho N tầm 2000 là kiểu gì ae python cũng ăn bug do TLE dù chỉ giải bằng On^2.

 

freedom.9

Senior Member

• 29/9/25

• #979

huungphan đã nói:

mấy thím trong này sôi nổi quá, như này thì pv faang chắc cũng đơn giản nhỉ?

Nhấp để mở rộng...

Trong này làm contest giải đề chủ yếu để luyện não cho vui về già khỏi bị Alzheimer thôi chứ có ai đủ trình vào Fang phập gì đâu

via theNEXTvoz for iPhone

 

LmaoSuVuong

Senior Member

• 29/9/25

• #980

freedom.9 đã nói:

Trong này làm contest giải đề chủ yếu để luyện não cho vui về già khỏi bị Alzheimer thôi chứ có ai đủ trình vào Fang phập gì đâu

via theNEXTvoz for iPhone

Nhấp để mở rộng...

e giải toàn kiểu ngồi ngâm, observe data 1 lúc lâu mới giải, làm kiểu đó vào là thấy cho rớt từ vòng gửi xe r nghe mấy lò luyện pvan trên mạng toàn kêu chấm cảđiểm giao tiếp. điểm trình bày suy nghĩ nữa