2
\$\begingroup\$

A school's task:

There are two sequences n_tab and m_tab.
For every element m in m_tab display how many n_tab elements are lesser than m_tab[i] up to the first n_tab element greater than m_tab[i].

Value limits:

1 <= n_tab.size(), m_tab.size() <= 500000
All elements of n_tab and m_tab are >= 1 and <= 10^9

Example:

Input:

3 6
2 5 1
1 2 3 4 5 6

Output:

0 0 1 1 1 3

Below a working simple procedure that I have written:

#include <iostream>

int main()
{
    int n, m;
    std::cin >> n >> m;

    int* n_tab = new int[n];
    for (int i = 0; i < n; i++)
        std::cin >> n_tab[i];

    int* m_tab = new int[m];
    for (int i = 0; i < m; i++)
        std::cin >> m_tab[i];

    for (int i = 0; i < m; i++) {
        int max = 0;
        for (int j = 0; j < n; j++) {
            if (m_tab[i] > n_tab[j])
                max++;
            else break;
        }

        std::cout << max << " ";
    }

    delete n_tab;
    delete m_tab;

    return 0;
}

This code works. But I get 63 points while 100 is possible. It's because this code is too slow.
(I get Time limit exceeded from page that test my code).

But I don't have idea how can I make it more efficient. I think the problem could be with the nested loops (it's like O(n×m)).

Unfortunately, I don't know for what input it fails because the testing page doesn't show it.

That's link to this task (in Polish lang, but I see that it's translated well by any translator): Task

NOTE: The n_tab and m_tab cannot be sorted. The task says that input order has meaning.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Please tell what the code is good for - in the code, but also as the question title. How would you go about merging both sequences? Is cannot be sorted to mean may be unordered in input? \$\endgroup\$
    – greybeard
    Commented May 27, 2023 at 20:16
  • \$\begingroup\$ Well, it's just an Polish Olympic task at the junior level (primary school). It's hard to say what this code is good for. \$\endgroup\$
    – Szyszka947
    Commented May 27, 2023 at 20:19
  • \$\begingroup\$ I added value limits, but see last sentence. The input order has meaning and shouldn't be changed. \$\endgroup\$
    – Szyszka947
    Commented May 27, 2023 at 20:30
  • 1
    \$\begingroup\$ It's too hard to figure out what the code is supposed to do just by looking at it. You should say what it does in your description, or in your title if possible. \$\endgroup\$ Commented May 27, 2023 at 21:29
  • \$\begingroup\$ @greybeard changing the order of n_tabs may also change the output. It should stop when a n_tabs element is greater than current m_tabs element. Changing the order of n_tabs may change how many lesser numbers in n_tabs are met before the stop element is reached. \$\endgroup\$
    – slepic
    Commented May 28, 2023 at 5:46

2 Answers 2

2
\$\begingroup\$

Neither Your Solution Nor the Example Matches the Specification

According to the problem statement, the algorithm is not supposed to stop until it encounters an element greater than the pivot. Thus, with the pivot value 5, the list 2 5 1 contains no elements greater than 5 and two less than 5. However, both the provided testcase and your program report the answer as 1, meaning you and it actually stop when you encounter an element equal to the pivot.

Since you say this problem was from a non-English-speaking country, was it mistranslated?

You Can Rearrange the Elements of m_tab and Possibly Memo-ize

If you know where the first element greater than 1 is, the first element greater than 2 cannot be to its left, and then once you find the first element greater than 2, the first element greater than 3 cannot be before that, and so on. This means you could sort the elements of m_tab (Hint: make a vector of indices into m_tab and sort_by a comparison function that looks them up). You can then make a single traversal through n_tab to find all the terminating values in O(N) time, rather than O(MN) time (not O(N²)). You would then permute the mapped values for m_tab back into their original order to output the answers.

Don’t Make two Comparisons Per Iteration

If you’re solving the same problem as the examples, just find the index, for each pivot value in m_tab, of the first element too large (or the end of n_tab if there is none). That is equal to the number of initial elements that are not too large.

If you’re solving the problem as specified, you need to also know the number of elements encountered so far equal to the pivot. If the possible range of elements is reasonable, say, ten million, you could keep a vector of the counts of each element, and populate it on the same single traversal. The number of elements less than the pivot would then be the difference of the number of elements less than or equal to it (the current index) and the number of elements equal to it (a constant-time lookup in the table of counts). However, with a range of 1 to 1 billion, this would take 4 GB of memory, still an excessive amount as of 2023.

Therefore, you want to find the endpoint of the subrange for each element of m_tab, and scan that subrange a second time for elements strictly less than the pivot. Doing it this way brings your time complexity back to O(MN). But there is a good chance your compiler can optimize these traversals to use SIMD.

Nobody Normally Needs Naked new

You are better off using std::vector<int>, or possibly std::unique_ptr, than allocating an array with new and deleting it manually.

One important advantage is that your memory will be managed automatically by RIAA, instead of needing you to remember to delete[] it.

Use Fast I/O

These programming-contest problems teach some bad habits, such as skipping input validation and using C-style I/O. If you profile the executable, you will probably find that you spend a significant amount of time doing iostream I/O. You might get a significant speed-up on some testcases from replacing cin >> with strtoul or even scanf.

Use the Correct Types

All the inputs are unsigned integers that fit in a 32-bit variable, but not a 16-bit one. Therefore, for maximum portability, their type should properly be unsigned long or long, not int (which on some implementations is too small). Granted, you don’t care about porting this code to a 16-bit CPU, so this is a bit language-lawyery.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I added link to the original task, I hope now goal will be clear. \$\endgroup\$
    – Szyszka947
    Commented May 28, 2023 at 9:42
0
\$\begingroup\$

(Good job on deleting what's new and not using what promises problems.)

Document, in the code, what "everything" is good for, especially if it is visible externally. (exempt main())

Figure out what "the business function" is:
A function taking input and determining the result in whatever forms are most convenient.

Functions are not only a means to reuse code. They are a way to think about parts of "functionality", the stricter the isolation the better.
And functions are an opportunity to document design, starting with name and parameter names:
(Caveat: I'm entirely out of touch with C++ and don't know what I'm doing there.
For one thing, I think there should be more autos.
And functions factored out, vector<int> becomes more attractive.)

#include <iostream>

/** Return count of elements lower than threshold up-to the first one higher. */
int
count_lower_upto_higher(int const *elements, int count, int threshold);

/** For each threshold, 
 *  output the number of values lower up-to the first one higher.
 */ void
output_lower_upto_higher(int const *values, int n_values,
                         int *threshold, int n_thresholds) {
    for (int i = 0; i < n_thresholds; i++)
        std::cout << count_lower_upto_higher(values, n_values, thresholds[i]) << " ";
}
   

/** Try reading count integers from std::cin into buffer.
 *  Return number of integers read. */
int
fill_int_buffer(int* buffer, int count) {
    for (int i = 0; i < n; i++) {
        std::cin >> buffer[i];
        if (!std::cin.good())
            return i;
    }
    return n;
}

/** Try allocating a buffer for count ints,
 *  and reading them from reading std::cin.
 *  Return "new" buffer. (Needs to be delete()d)
 */
int *
get_int_buffer(int count) {
    int* buffer = new int[count];
    if (count == fill_int_buffer(buffer, count))
        return buffer;
    std::cerr << "Failed to allocate and read " << count << " ints";
    return nullptr;
}

int main()
{
    int n, m;
    std::cin >> n >> m;

    int *n_tab, *m_tab;
    if (   nullptr == (n_tab = get_int_buffer(n))
        || nullptr == (m_tab = get_int_buffer(m)))
        exit(1);

    output_lower_upto_higher(n_tab, n, m_tab, m);

    delete n_tab;
    delete m_tab;
}

(return 0; is implicit reaching the end of main().)


My sketch above does not spell out count_lower_upto_higher() - assume it to take O(n) time for a total of O(nm).

Without implying all or any of the following approaches are viable:
When trying to improve run-time for large inputs, you may want to keep above structure: handle one threshold after the other.
But such limits the solution space needlessly: You don't want that.
The other approach suggesting itself is: handle one value after the other.
More obscure is order both, handle in order.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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