Gặp lỗi ở 1 số testcase trong Day 8 của Hackerrank

#1

Hi mọi người,

Tình hình là mình giải 1 Day 8 trong Hackerrank bằng vector nhưng bị lỗi.

Đây là đề bài:

Pasted image855×627 59.3 KB

Pasted image838×358 10.6 KB

Đây là code của mình: http://codepad.org/ivr2QnAd

int main() {
    int n;
    std::cin >> n;
    std::vector<std::string> arr_name, arr_phone_number;
    for (int i = 0; i < n; ++i) {
        std::string name, phone_number;
        std::cin >> name >> phone_number;
        arr_name.push_back(name);
        arr_phone_number.push_back(phone_number);
    }
    std::string name;
    while (std::cin >> name) {
        bool Check = false;
        for (int i = 0; i < n; ++i) {
            if (name == arr_name.at(i)) {
                std::cout << arr_name.at(i) << "=" << arr_phone_number.at(i) << std::endl;
                Check = true;
                break;
            }
        }
        if (Check == false)
            std::cout << "Not found" << std::endl;
    }   
    return 0;
}

Còn đây là hình ảnh lỗi:

Pasted image1366×768 97 KB

Như đã thấy, code của mình chỉ vượt qua 1 vài testcase, còn mấy testcase kia nó báo Terminated due to timeout.

Còn đây là Input và Expected Output của những testcase bị lỗi:

Test Case #1 : http://bit.ly/2dJ1YCV
Expected Output : http://bit.ly/2dIZSTF

Test Case #2 : http://bit.ly/2es8CjS
Expected Output : http://bit.ly/2egwQM3

Test Case #3 : http://bit.ly/2dXwyX8
Expected Output : http://bit.ly/2eqRjOx

Đó là 3 Test Case mình bị lỗi!
Mọi người giúp mình nhé, xin cảm ơn !

#2

Ko phải lỗi mà giải thuật tốn quá nhiều thời gian nên nó ko cho pass đó.

2 Likes
#3

Vậy có cách nào cải thiện không anh, ngoại trừ dùng map ra

#4

Nếu ko muốn dùng map thì chỉ còn cách cải thiện cách search. :?
Vì mình thấy code chậm là do cách search kia

2 Likes
#5

Uhm … vậy anh có cách nào làm cái thuật toán search nó nhanh hơn đủ đáp ứng yêu cầu của hackerrank không ?
Chứ em giải thuật hỏng tốt lắm ^^

#6

Nhưng tại sao lại ko dùng map cho lẹ ;_;

Muốn nhanh hơn Linear Search nữa thì tìm hiểu Binary Search.
Nhưng nó yêu cầu mảng phải sắp xếp :smiley:

2 Likes
#7

một là dùng map
2 là dùng vector< pair<string, string> >
sort lại rồi tìm kiếm nhị phân
về cơ bản cả 2 đều O(QlogN) nhưng 1 thằng code khỏe 1 thằng code mệt

1 Like
#8

Cảm ơn mọi người nhiều nhé :slight_smile:

#9

Mà cho em hỏi string thì dùng Binary search kiểu gì anh ?
Vì thường Binary search em toàn dùng cho số, bây giờ nó là chuỗi nên thấy hơi lạ

#10

Đã cải thiện sang Linear Search nhưng vẫn không đủ nhanh như hackerrank yêu cầu :frowning:

int main() {
   int n;
    std::cin >> n;
    std::vector<std::string> arr_name, arr_phone_number;
    for (int i = 0; i < n; ++i) {
        std::string name, phone_number;
        std::cin >> name >> phone_number;
        arr_name.push_back(name);
        arr_phone_number.push_back(phone_number);
    }
    std::string name;
    while (std::cin >> name) {
        arr_name.push_back(name);
        int a;
        bool Check = false;
        for (int i = 0;; ++i) {
            if (name == arr_name.at(i)) {
                a = i;
                break;
            }
        }
        if (a != n) {
            std::cout << arr_name.at(a) << "=" << arr_phone_number.at(a) << std::endl;
        }
        else {
            std::cout << "Not found" << std::endl;
        }
        arr_name.pop_back();
    }    
    return 0;
}

Chắc phải dùng map quá

#11

linear search thi có cải thiện gì đâu??

binary search cho chuỗi thì cũng ko khác gì số, nếu guess < a[mid] thì cho right = mid, ngược lại thì left = mid rồi cứ thế mà tìm…

C++ có hàm tìm binary search sẵn là std::lower_bound với std::upper_bound. Tìm hiểu 2 hàm này rồi xài cũng được.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?