4
\$\begingroup\$

Here is the text of the problem:

There are 5 brands of cameras sold on your website – Nikon, Canon, Sigma, Fujifilm and Sony. Each of these brands sell different cameras at distinct prices. For simplicity, each brand is represented by an integer between 1 to 5. Your website has q shoppers each of whom has a list of brands they are willing to buy from. Based on every user's buying history, you know that they are most likely to buy the kth cheapest camera amongst the brands they like. Your task involves finding this kth cheapest camera for each shopper.

Given a list of brands and the prices of their cameras, the list of shoppers and their preferences, for each shopper, determine the kth cheapest camera. If no such camera exists, print -1.

Input Format

The first line contains integer n denoting the total number of cameras being sold. The second line contains an array of n integers describing the brands of the cameras. The third line contains an array of n integers describing the prices of those particular cameras.

After that, q queries describing the shoppers' preferences follow. A single query is described in 3 lines.

  • d represents the number of brands the shopper will buy from.
  • d space separated integers in ascending order denoting the index of the brands.
  • kth cheapest camera to display.

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ q ≤ 105
  • 1 ≤ pricesi ≤ 109
  • 1 ≤ brandsi ≤ 5
  • 1 ≤ lj ≤ 5
  • 1 ≤ k ≤ 5 * 105
  • all pricesi are distinct

Output Format

Output exactly q lines. In the jth of them print a single integer denoting the price of the camera lens the jth shopper will buy. If no such lens exists, print -1.

Here is my solution:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main() {  
    int n;
    cin >> n;
    vector<int> brands;
    for (int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        brands.push_back(tmp);
    }

    unordered_map<int, vector<int>> dict;
    for (int i = 0; i < n; i++){
        auto it = dict.find(brands[i]);
        if( it == dict.end() ) {
        dict.insert({brands[i], vector<int>()});
        }
    }
    for (int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        dict[brands[i]].push_back(tmp);
        }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int number_of_brands;
        cin >> number_of_brands;
        vector<int> indexes;
        for (int i = 0; i < number_of_brands; i++){
            int tmp;
            cin >> tmp;
            indexes.push_back(tmp);
            }
        int k;
        cin >> k;
        vector<int> potential_cameras;
        for (auto i : indexes){
            for (auto x : dict[i]){
                potential_cameras.push_back(x);
                }
            }
        sort(potential_cameras.begin(), potential_cameras.end());
        if (potential_cameras.size() >= k){
            cout << potential_cameras[k - 1] << '\n';
            }
        else {
            cout << -1 << '\n';
        }
    }
    return 0;
}

This algorithm times out for every single one of the bigger sized test cases. It is one of my very first attempt at writing C++ code, so please be merciless with any bad habit or code smell you can spot, but in this specific case I am curious to know what the main issue is, and if I could have used more suitable data structures than the ones I chose.

\$\endgroup\$
  • 1
    \$\begingroup\$ @pacmaninbw it works for the three or four easier test cases \$\endgroup\$ – Dalamar Nov 25 '17 at 18:16
  • \$\begingroup\$ That line is just cycling through the test cases. It's supposed to be that way otherwise I would not answer every test case. \$\endgroup\$ – Dalamar Nov 25 '17 at 18:17
1
\$\begingroup\$

Prefer Clear Naming over using namespace std

According to the [MSDN website]:

Namespaces are used to organize code into logical groups and to prevent name collisions that can occur especially when your code base includes multiple libraries.

A collision is when 2 different functions have the same name, the same arguement types and a similar functionallity (this is why they have the same name). Someone developing software may want to override a function such as std::cout, std::cin or they may want to override the functionallity of a class such as std::vector or std::stack. Namespaces allow these constructs to be overriden.

The use of the programming statement:

using namespace std;

hides the fact that cin, cout, vector and stack are coming from the namespace std where cin, cout, vector and stack are used in the code. This can cause confusion of where the code is actually coming from.

As the software becomes more complex and uses more libraries this becomes a bigger problem.

For a more detailed discussion of why it is a bad idea to use using namespace std; see this stackoverflow question.

Just Include the Necessary Headers
The code starts of with 6 C++ header files. At least two of those headers, cmath and cstdio are not necessary, since the code isn't using old C style I/O and it isn't using any of the old C library math functions. Including too many header files can slow the compilation time, and it may reduce the names you can use in the code.

Meaningful Variable Names
The problem statement does use symbol names such as n and q, however it also states than n is the number of brands and q is the number of buyers. Single letter variable names don't help others reading and maintaining the code, but descriptive variable, function and class names do. If you are programming in a team, someone else may need to maintain or update the code you write because you are busy doing something else, or on vacation.

The term buyer is completely missing from the code, and I'm not sure what the variable indexes represents.

In some languages such as C which is closely related to C++ the following code would be broken because the variable i is defined multiple times within a loop where i is used as the loop control variable.

    for (int i = 0; i < q; i++){
        int number_of_brands;
        cin >> number_of_brands;
        vector<int> indexes;
        for (int i = 0; i < number_of_brands; i++){ // i redefined here.
            int tmp;
            cin >> tmp;
            indexes.push_back(tmp);
            }
        int k;
        cin >> k;
        vector<int> potential_cameras;
        for (auto i : indexes){                     // i redefined here.
            for (auto x : dict[i]){
                potential_cameras.push_back(x);
                }
            }
        sort(potential_cameras.begin(), potential_cameras.end());
        if (potential_cameras.size() >= k){
            cout << potential_cameras[k - 1] << '\n';
            }
        else {
            cout << -1 << '\n';
        }
    }

The use of i, j, k, l as loop counters from older versions of FORTRAN which allow implicit declaration of these variables as integers. It is better to use more meaningful names to avoid naming collisions and broken code.

Code Complexity
Generally in C++ and C the main function is used to control the program and other functionality is moved to other functions. In this case the main() function should be broken up into smaller functions. This helps the programmer initially writing the code and anyone that has to maintain the code. One of the best ways to design procedural programs is to use Top Down Design.

In top down design or step-wise refinement one keeps breaking the problem down into smaller and smaller pieces until everything is atomic and easy to implement.

During this process one ends up creating functions and sub-functions that make the code more meaningful in context. One of the benefits of Object Oriented Design is that it allows top down and bottom up design at the same time.

Some object oriented principles also apply and might be useful to you:

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows:
    `A class should have only one reason to change.`

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines in procedural languages like C as well.

The KIS(S) principle simply states Keep it simple.

Some possible functions that could be added std::vector inputBrands(); std::unordered_map mapBrands(std::vector brands); void inputPrices(std::unordered_map> dict, std::vectorbrands);

The for loop above can be broken into at least 2 functions, I'm just not sure what to call them.

Another benefit of breaking the program up into functions is that it can be profiled and you can find out where the program is spending the most time.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks a lot for this very articulate answer, I really appreciate you taking the time. I made the indexes corrections and the algorithm still fails the test cases it used to fail. Any insight on what is really wrong about it performance wise? \$\endgroup\$ – Dalamar Nov 26 '17 at 18:58
  • \$\begingroup\$ @Dalamar Do you think you can figure out a way to do it without the sort? \$\endgroup\$ – pacmaninbw Nov 26 '17 at 21:19
  • \$\begingroup\$ It's hard to think how. The kth less expensive thing is requested which seems to imply some type of sorting \$\endgroup\$ – Dalamar Nov 26 '17 at 22:07
  • \$\begingroup\$ @Dalamar: Yes, it's possible to find the n-th element of a collection without sorting the whole collection. See std::nth_element. FWIW, this is normally O(N) rather than O(N log N). \$\endgroup\$ – Jerry Coffin Nov 27 '17 at 5:51
  • \$\begingroup\$ Finding nth element can be done by quick select algorithm. \$\endgroup\$ – noman pouigt Nov 29 '17 at 2:43
3
\$\begingroup\$
        vector<int> potential_cameras;
        for (auto i : indexes){
            for (auto x : dict[i]){
                potential_cameras.push_back(x);
                }
            }
        sort(potential_cameras.begin(), potential_cameras.end());

Let's review the important constraints:

  • At most 5 brands
  • At most 10000 cameras
  • Up to 10000 queries

So this code is executed up to 10000 times, and each time is filtering up to 10000 cameras and then sorting up to 10000 cameras.

Given that each query includes at least one brand out of the five, there are only 31 possible brand combinations. So by pre-computing you could execute this code 31 times rather than 10000 times, and since it's the obvious candidate for the bottleneck that might give you a 300-times speedup.

If that's still not fast enough, then you need to look at linear time median algorithms. But frankly if the queries are evenly distributed then ~300 queries per brand combination is much larger than \$\lg 10000 \approx 13\$, so it's probably faster to quicksort once per combination than to execute a linear time median once per query. If you really want to overkill it then you could create a custom data structure which supports multiple median queries by maintaining state of which ranges of the array have been partitioned around which pivot, but KISS, YAGNI.

Alternatively, but still violating KISS, you could do just five sorts (one per camera) and then some complicated multiple binary chop. I'd still prefer one sort per brand combination.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.