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

dhl001

Đã tốn tiền

• 5/7/25

• #481

bài đó quên bảng chữ cái phải ngồi google

 

aNotHeRNo0b

Senior Member

• 5/7/25

• #482

:> Ranking to the moon, lại hiến rate cho các bác rồi

 

freedom.9

Senior Member

• 5/7/25

• #483

Q4 dùng Segment tree + greedy mà còn mấy case cuối mãi éo pass huhu, cay lỏ dái

 

freedom.9

Senior Member

• 5/7/25

• #484

Q4 hiếp dâm con heo đẩy bà già xuống biển greedy theo length ko được vì chưa xử lí overlapsed.

 

aNotHeRNo0b

Senior Member

• 5/7/25

• #485

Thấy Q4 bọn nó dùng Binary Search :v mà không hiểu nó check kiểu gì @@

 

dhl001

Đã tốn tiền

• 5/7/25

• #486

bài đấy đọc đề chả hiểu gì. May mả bỏ sớm chứ không lại mất ngủ

 

dhl001

Đã tốn tiền

• 5/7/25

• #487

freedom.9 đã nói:

Xem tệp đính kèm 3126903
Q4 hiếp dâm con heo đẩy bà già xuống biển greedy theo length ko được vì chưa xử lí overlapsed.

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

à hiều đề rồi.
Test này maxC là 0 thì thím return luôn cái longest chứ đi greedy làm gì thê

 

fkphua3

Senior Member

• 5/7/25

• #488

Leetcode sau contest có chạy lại testcase à các bác? Trước bài kia giải được sau vô lại bị TLE. Mà bài đó code ngu

 

freedom.9

Senior Member

• 6/7/25

• #489

aNotHeRNo0b đã nói:

Thấy Q4 bọn nó dùng Binary Search :v mà không hiểu nó check kiểu gì @@

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

Tụi nó check là nếu gcd từ i đến j mà >=2 thì ở j nó modify về 1, lúc đấy thì sub array từ i đến j - 1 là stable. Và từ j sẽ ko gọi là stable nữa.
Nên binary search được.
Dùng python chạy segment tree thì TLE phải chuyển qua sparse table để lấy 0(1) ở query left, right

 

Husqvarna701SM

Senior Member

• 6/7/25

• #490

freedom.9 đã nói:

Tụi nó check là nếu gcd từ i đến j mà >=2 thì ở j nó modify về 1, lúc đấy thì sub array từ i đến j - 1 là stable. Và từ j sẽ ko gọi là stable nữa.
Nên binary search được.
Dùng python chạy segment tree thì TLE phải chuyển qua sparse table để lấy 0(1) ở query left, right

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

Má c++ thằng bạn mình dùng segment tree thì pass

 

Husqvarna701SM

Senior Member

• 6/7/25

• #491

aNotHeRNo0b đã nói:

Thấy Q4 bọn nó dùng Binary Search :v mà không hiểu nó check kiểu gì @@

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

BS thì do bài này dạng tìm min của max. Còn check thì greedy thôi.
Ban đầu ngồi check full window r chọn đoạn đè để cập nhật xong thấy greedy đổi thằng cuối là đủ r

 

freedom.9

Senior Member

• 6/7/25

• #492

Husqvarna701SM đã nói:

Má c++ thằng bạn mình dùng segment tree thì pass

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

Sau python users phải niệm thần chú thôi, cơ mà mình greedy ngu nên ko pass cũng đúng rồi

Solution của mình cũng bisearch và greedy, mà mình bisearch ở mỗi i rồi tìm cái longest length bằng binary search với segment tree rồi greedy bằng cách chia 2 ra, ăn mấy bug mới nhận ra là nó có case overlapsed nữa, đúng là ngu

Binary search on the answer là ngon rồi

 

freedom.9

Senior Member

• 6/7/25

• #493

Má nó gặp bài trục tọa độ rồi dễ toang quá

 

lovelyly

Senior Member

• 6/7/25

• #494

Q4 20 phút xong, mà 3Q đầu mất nhiều thời gian quá

 

aNotHeRNo0b

Senior Member

• 6/7/25

• #495

:v Dậy muộn húp vội 3Q rồi tới Q4 không kịp code rồi

 

freedom.9

Senior Member

• 6/7/25

• #496

Q4 đoán là BFS theo reverse order rồi. Code ko ra

 

lovelyly

Senior Member

• 6/7/25

• #497

aNotHeRNo0b đã nói:

:v Dậy muộn húp vội 3Q rồi tới Q4 không kịp code rồi

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

Thật ra Q4 code không dài đâu, tìm ngược từ (tx, ty) đến (sx, sy) thôi

 

freedom.9

Senior Member

• 6/7/25

• #498

Q4: Use BFS queue backwards from tx, ty. For any x, y, it could have come from (x/2, y), (x, y/2), (x-y,y), (x,y-x) each under certain constraints for x,y. Discard anything you've seen before or x < sx or y < sy.

Biết ngay, đi theo reverse order là ăn. Nhận thấy nó halving by 2 mà code éo ra đm nhà nó

 

lovelyly

Senior Member

• 6/7/25

• #499

freedom.9 đã nói:

Q4 đoán là BFS theo reverse order rồi. Code ko ra

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

• ty > 2 * tx => Đi từ (tx, ty/2)
• tx < ty < 2 * tx => Đi từ (tx, ty-tx)'
• tx == ty => Nếu sx == 0 đi từ (0, tx), nếu sy == 0 đi từ (tx, 0)

 

aNotHeRNo0b

Senior Member

• 6/7/25

• #500

Đi ngược giảm search space chứ đi xuôi thì :v TLE ngay từ trong trứng