0
$\begingroup$

I am new to Algorithms and Competitive Coding. I have a problem as follow: enter image description here

For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic Programming or any other way which can run in less than O(nlogn) or even O(n) and the limit memory is 256 Mb.

Initially, I have a simple approach to dynamic programming as follows: I just create a table size nxn and fill it with numbers that represent the minimum element from the index I to index j (i <= j). After that, I refer to the given indexes (ik and jk) on the table and add them up.

However, as submitting the code as the previous approach, I get 3 cases of wrong answers and even runtime errors. The runtime error is due to the input constraint: up to 10^6 elements which cause the exceed of memory (10^6 * 10^6 = 10^12, which is very large). I also get accepted status on 3 tests however, the number of wrong answers makes me quite confused. I really need your help to check and update the algorithms.

Sample test case:

Input:

16

2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4

4

1 5

0 9

1 15

6 10

Output:

6
void make_table()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            if(i == j)
            {
                Table[i][j] = arr[i];
            }
            else
            {
                Table[i][j] = min(arr[j], Table[i][j - 1]);
            }
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    make_table();
    ll sum = 0;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        sum += Table[x][y];
    }
    cout << sum << endl;
}
```
$\endgroup$
3
1
$\begingroup$

You can use the concept of segment trees. Check this link: https://en.wikipedia.org/wiki/Segment_tree and https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

The above link works for finding the sum of all the elements in a given range [i,j]. However, you can use the same approach to find the minimum element in the range [i,j] in $O(\log n)$ time. The idea is that you can break the range [i,j] into $O(\log n)$ smaller ranges, and for each of these ranges you already know their minimum values via some binary tree (built during pre-processing step). Thus, you can take the minimum over all these small ranges, and it will give the overall minimum in the range [i,j] in $O(\log n)$ time.


Building the binary tree comes under the pre-processing step and it will only take $O(n)$ time.
Also, there are $m$ queries and each query takes $O(\log n)$ time. The overall time complexity would be $O(n + m \log n)$. Since $m < n$, the overall complexity is $O(n \log n)$.

$\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.