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

thuyduong2007 · 8/8/21

_Gia_Cat_Luong_ đã nói:
K rành C++ lắm nhưng về logic thì thay lower_bound thành upper_bound ?

T mới coi sơ qua, cũng đoán là change lower_bound thành upper_bound là đc

Lập Trình Viên Số Khổ · 8/8/21

LIS pair có thể làm nlogn được đấy.
sort theo phần tử đầu (nếu strictly LIS thì break tie bằng sort decresase thằng thứ 2, còn loosely LIS thì increase thằng thứ 2), sau đó làm LIS trên thằng thứ 2

C++:

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        auto n = envelopes.size();
        vector<pair<int,int>> v;
        v.reserve(n);
        for(auto& env:envelopes){
            v.emplace_back(env[0],env[1]);
        }
        sort(v.begin(),v.end(),[](const pair<int,int>& a,const pair<int,int>& b){
            return a.first == b.first ? a.second > b.second : a.first < b.first;
        });
        vector<int> lis;
        for(auto p:v){
            auto insert_pos = lower_bound(lis.begin(),lis.end(),p.second);
            if(insert_pos == lis.end()) lis.push_back(p.second);
            else *insert_pos = p.second;
        }
        return (int)lis.size();
    }

nhỡ sort theo phần tử thứ 2 ra kết quả tốt hơn thì sao

Lập Trình Viên Số Khổ · 8/8/21

thuyduong2007 đã nói:
T mới coi sơ qua, cũng đoán là change lower_bound thành upper_bound là đc

mà cái lower_bound với upper_bound thì khác nhau gì nhỉ, thấy có mã nó chọn low có đoạn mã khác cũng LIS lại chọn upper

clonemasteruwu · 8/8/21

Lập Trình Viên Số Khổ đã nói:
nhỡ sort theo phần tử thứ 2 ra kết quả tốt hơn thì sao

cần t mớm cho ăn luôn k :beat_brick:

ăn sẵn quen, code cho còn bắt chứng minh

clonemasteruwu · 8/8/21

Lập Trình Viên Số Khổ đã nói:
mà cái lower_bound với upper_bound thì khác nhau gì nhỉ, thấy có mã nó chọn low có đoạn mã khác cũng LIS lại chọn upper

https://en.cppreference.com/w/

Lập Trình Viên Số Khổ · 8/8/21

clonemasteruwu đã nói:
cần t mớm cho ăn luôn k ăn sẵn quen, code cho còn bắt chứng minh

quan trọng là ý tưởng và tính đúng đắn chứ các sách thuật toán toàn mã giả chứ cần gì code fen

clonemasteruwu · 8/8/21

Lập Trình Viên Số Khổ đã nói:
nhỡ sort theo phần tử thứ 2 ra kết quả tốt hơn thì sao

thế anh nói thế này thì đã ngâm code được bao lâu r ?
nghe câu đã k muốn giải thích :whistle:

do swap phần tử các cặp thì đáp án k đổi nên sort theo thằng nào k quan trọng (tính đối xứng)
chứng minh tường tận thì giả sử sort theo thằng 2 cho ra 1 đáp án tốt hơn, thì sort theo thằng thứ nhất cũng sẽ detect được đáp án đó.

Lập Trình Viên Số Khổ · 8/8/21

clonemasteruwu đã nói:
thế anh nói thế này thì đã ngâm code được bao lâu r ?
nghe câu đã k muốn giải thích

do swap phần tử các cặp thì đáp án k đổi nên sort theo thằng nào k quan trọng (tính đối xứng)
chứng minh tường tận thì giả sử sort theo thằng 2 cho ra 1 đáp án tốt hơn, thì sort theo thằng thứ nhất cũng sẽ detect được đáp án đó.

đấy fen phải giải thích mới hiểu được chứ, cái này mặc dù fen giải thích rùi tẹo tui vẫn phải nghĩ thêm 1 tiếng nữa chắc mới hiểu. Thấy lạ là ko ai hỏi thui

Lập Trình Viên Số Khổ · 8/8/21

Cho dãy có n phần tử, Tìm LIS, bỏ các phần tử ra, tiếp tục tìm LIS, bỏ các phần tử ra, tiếp tục... đến khi loại bỏ hết các phần tử ban đầu ra.
được k cái LIS. Suy ra Longest Non Increase Sequences = k.

Cái này có tên gọi hay thuộc nhóm bổ đề nào không nhỉ mấy fen?
@clonemasteruwu @_Gia_Cat_Luong_ @thuyduong2007

clonemasteruwu · 8/8/21

Lập Trình Viên Số Khổ đã nói:
Cho dãy có n phần tử, Tìm LIS, bỏ các phần tử ra, tiếp tục tìm LIS, bỏ các phần tử ra, tiếp tục... đến khi loại bỏ hết các phần tử ban đầu ra.
được k cái LIS. Suy ra Longest Non Increase Sequences = k.

Cái này có tên gọi hay thuộc nhóm bổ đề nào không nhỉ mấy fen?
@clonemasteruwu @_Gia_Cat_Luong_ @thuyduong2007

bồ câu, bớt quote tôi cái :confuse:

_Gia_Cat_Luong_ · 8/8/21

Lập Trình Viên Số Khổ đã nói:
Cho dãy có n phần tử, Tìm LIS, bỏ các phần tử ra, tiếp tục tìm LIS, bỏ các phần tử ra, tiếp tục... đến khi loại bỏ hết các phần tử ban đầu ra.
được k cái LIS. Suy ra Longest Non Increase Sequences = k.

Cái này có tên gọi hay thuộc nhóm bổ đề nào không nhỉ mấy fen?
@clonemasteruwu @_Gia_Cat_Luong_ @thuyduong2007

Xin nhỗi chứ k hiểu fen đang nói gì luôn ?
Sao làm vậy lại suy ra đc Longest Non Increase Sequences = k ? Mà định nghĩa LNIS là gì v ? Chuỗi con giảm dài nhất (loosely) ?

Lập Trình Viên Số Khổ · 8/8/21

_Gia_Cat_Luong_ đã nói:
Xin nhỗi chứ k hiểu fen đang nói gì luôn ?
Sao làm vậy lại suy ra đc Longest Non Increase Sequences = k ? Mà định nghĩa LNIS là gì v ? Chuỗi con giảm dài nhất (loosely) ?

chuẩn đó fen, thử làm mà xem

Lập Trình Viên Số Khổ · 8/8/21

clonemasteruwu đã nói:
bồ câu, bớt quote tôi cái

https://oj.vnoi.info/problem/lis2vn...IbZu65lYkFuyQ9E0m7Z7gHxrjyRiM-c8GVCvrr-eIuRQQ

LIS pair ko cho sort thì làm sao fen @_Gia_Cat_Luong_ @thuyduong2007

clonemasteruwu · 8/8/21

Lập Trình Viên Số Khổ đã nói:
https://oj.vnoi.info/problem/lis2vn...IbZu65lYkFuyQ9E0m7Z7gHxrjyRiM-c8GVCvrr-eIuRQQ

LIS pair ko cho sort thì làm sao fen @_Gia_Cat_Luong_ @thuyduong2007

trình ở 1k5 thì practice ở 1k5 đi :angry:

học bộp chộp tưởng là hay nhưng thực ra là tự phế võ công mình
bao giờ làm Leetcode contest p3 k bị ngượng tay thì tôi dạy anh bài trên :amazed:

Lập Trình Viên Số Khổ · 8/8/21

clonemasteruwu đã nói:
trình ở 1k5 thì practice ở 1k5 đi học bộp chộp tưởng là hay nhưng thực ra là tự phế võ công mình
bao giờ làm Leetcode contest p3 k bị ngượng tay thì tôi dạy anh bài trên

@_Gia_Cat_Luong_ bảo tui học LIS đầu luyện DP nên tui tìm các bài về LIS, web ý nó ko có rank, ai biết nó ở mức nào trời @@

.gears · 9/8/21

Lập Trình Viên Số Khổ đã nói:
Cho dãy có n phần tử, Tìm LIS, bỏ các phần tử ra, tiếp tục tìm LIS, bỏ các phần tử ra, tiếp tục... đến khi loại bỏ hết các phần tử ban đầu ra.
được k cái LIS. Suy ra Longest Non Increase Sequences = k.

Cái này có tên gọi hay thuộc nhóm bổ đề nào không nhỉ mấy fen?
@clonemasteruwu @_Gia_Cat_Luong_ @thuyduong2007

Cái này gọi là định lí Dilworth

https://en.wikipedia.org/wiki/Dilworth's_theorem

.gears · 9/8/21

Lập Trình Viên Số Khổ đã nói:
https://oj.vnoi.info/problem/lis2vn...IbZu65lYkFuyQ9E0m7Z7gHxrjyRiM-c8GVCvrr-eIuRQQ

LIS pair ko cho sort thì làm sao fen @_Gia_Cat_Luong_ @thuyduong2007

cái này là bài kinh điển cho 2D segment tree (ST với các ST ở các node) rồi.

gọi dp là độ dài của dãy tăng nhau to nhất tới pair i có (xi, yi) đang xét.

với mỗi pair (xi, yi), lấy max của ST trong đoạn (0,0) tới (xi - 1, yi - 1) rồi update (xi, yi) với giá trị đó + 1. muốn in ra thì truy vết lại.

vì giới hạn tới 10^9 nên phải thực hiện nén mảng (các quan hệ <, >, = vẫn giữ nguyên giữa các phần tử nhưng chiều dài của vùng thay đổi lại, vd 1 10^6 10^9 10^5 nén thành 1 3 4 2).

sau khi nén xong thì mỗi chiều vẫn còn cỡ 10^5, khá to nên phải cài đặt segment tree động ở các node để có thể có đủ bộ nhớ.

nên code LIS bth bằng segment tree 1D trước rồi chuyển đến bài này thì đơn giản hơn.

buonnguqua · 9/8/21

KimSoHyunGoddness đã nói:
Thấy mấy bác toàn dùng C/C++ để giải mấy bài toán.
Tại do mấy bác thích như vậy hay là C/C++ có gì đó đặc biệt nên giải mấy bài thuật toán sẽ tốt hơn vậy ?

Chạy nhanh, sướng, phê
Fen biết cảm giác ấn F5 xong IDE nó ra kết quả trong tích tắc phê lòi
Chứ dùng JS, Python 5-10 giây mới ra kết quả thì mình sẽ sinh ra nghi vấn là liệu solution của mình đã ngon chưa

Lập Trình Viên Số Khổ · 9/8/21

Bài này giải DP như nào vậy mn:
cho một mảng, và một giới hạn M, tìm số lượng tối thiểu số trong mảng để có tổng lớn nhất không vượt quá M.

ví dụ: Mảng = {4,5,7,10,12}, M = 20

thì có 4+5+10 =10 và 7 + 12 =19 nên chọn 7 và 12 vì số lượng số là 2, ít hơn.

_Gia_Cat_Luong_ · 9/8/21

Lập Trình Viên Số Khổ đã nói:
@_Gia_Cat_Luong_ bảo tui học LIS đầu luyện DP nên tui tìm các bài về LIS, web ý nó ko có rank, ai biết nó ở mức nào trời @@

Hic, fen hiểu nhầm ý tuôi. Ý tui là thay vì LCS thì LIS đỡ hại não hơn. Nhưng mà dù xao thì phen thẩm đc cái LIS thì giỏi hơn tui rồi. Hồi đó tui mất cả tháng mới hiểu nổi con hàng này T_T.

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

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này