1
\$\begingroup\$

I'm trying to solve the following question:

You have an array A of size n, containing −1 or 1 only, and s segments (not necessarily different). Each segment is defined by 2 integers li and ri (1 ≤ li ≤ ri ≤ n) and represent the subarray Ali, Ali +1 , ..., Ari of the array A.

A segment [li, ri] is called positive if the sum of elements in the subarray is strictly greater than 0. That is Ali, Ali +1 , ..., Ari ≥0. Forexample,ifA=[−1,−1,1,−1,1],thenthesegments[3,5]and[5,5] are positive (sum of elements is greater than 0), but the segments [1, 2] or [1, 5] are not positive.

Now you have q queries. In each query, you are given an integer j (1 ≤ j ≤ n) such that you set Aj = |Aj| (Absolute value of Aj). You have to find the minimum number of queries after which at least k (≤ s) of given segments become positive or tell it is impossible.

Note: It might happen that there already exists k positive segments.

Input First line of input consists of number of test cases t. Every test case is defined as follows- – First line contains 2 integer n and s. – Next line contains n integers where ith integer denotes Ai. – Following s lines contain 2 integers li and ri defining ith segment. – Next line contains 2 integers q and k. – Next line contains q integers where ith integer denotes x corresponding to ith query.

Output For each test case, output a line containing the minimum number of queries needed for that case. If it is impossible in all the queries then output -1 in that case.

There is an additional criteria to just use three libraries, i.e., iostream, vector & cstdlib.

My code for the same is:

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int countPositiveSegments(vector<int>& A, vector<vector<int>>& sets) {
    int count = 0;
    for (const vector<int>& segment : sets) {
        int sum = 0;
        for (int i = segment[0] - 1; i < segment[1]; i++) {
            sum += A[i];
        }
        if (sum > 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int total_cases;
    cin >> total_cases;
    while (total_cases > 0) {
        int n, s, q, k;
        cin >> n >> s;
        vector<int> A;
        vector<vector<int>> sets;
        while (n > 0) {
            int temp;
            cin >> temp;
            A.push_back(temp);
            n--;
        }
        while (s > 0) {
            int temp1, temp2;
            vector<int> temp3;
            cin >> temp1 >> temp2;
            temp3.push_back(temp1);
            temp3.push_back(temp2);
            sets.push_back(temp3);
            s--;
        }
        cin >> q >> k;
        vector<int> queries;
        while (q > 0) {
            int temp;
            cin >> temp;
            queries.push_back(temp);
            q--;
        }

        // Initialize variables
        int queries_needed = -1;
        int total_positive_sets = countPositiveSegments(A, sets);

        if (total_positive_sets < k) {
            // If there are not enough positive sets, then iterate through queries
            for (int i = 0; i < queries.size(); i++) {
                int x = queries[i] - 1; // Adjust the 0-based index
                A[x] = abs(A[x]);
                int new_positive_sets = countPositiveSegments(A, sets);

                if (new_positive_sets >= k) {
                    queries_needed = i + 1;
                    break;
                }
            }
        }

        if (queries_needed != -1) {
            cout << queries_needed << endl;
        } else {
            cout << -1 << endl;
        }

        total_cases--;
    }
    return 0;
}

It works perfectly fine for:

Input (stdin)
2
5 2
-1 -1 1 -1 -1
1 2
2 5
6 1
3 1 1 2 5 3
5 3
-1 -1 -1 -1 -1
1 3
2 2
1 1
3 2
2 4 5

Your Output (stdout)
4
-1

Expected Output
4
-1

For a few of the hidden test cases, it provides a Time Limit Exceeded error. I'm trying to ascertain a new way which can solve the problem.

\$\endgroup\$
1

1 Answer 1

3
\$\begingroup\$

Algorithmic deficiencies.

  • countPositiveSegments has a time complexity proportional to the combined size of all segments, which can grow quadratically with the size of array. And you do it for every query. I am not surprised at all that the solution times out.

    You can count initial positive segments much faster by computing a accumulated sum of the array, acc[i] = acc[i-1] + A[i]) (in \$O(n)\$ time); then the segment is positive if acc[ri] > acc[li] (in \$O(s)\$ time).

  • You don't need to recount positive segments when A[x] is 1. Fix is trivial.

  • Once a segment becomes positive, you don't need to account for it anymore. Just forget that it existed.

  • If A[x] is -1, only the segments containing x are affected; you don't need to bother about the rest. The fix is less trivial: you need more elaborate data structure. A segment tree perhaps?

Code review.

  • using namespace std; is a very bad habit.

  • temp, temp1, temp2, temp3 are not the greatest names. If you don't know how to name a variable, think twice: do you really need it?

  • More functions, please. Every loop implements an important operation, and therefore deserves a name, like get_array, get_segments, etc.

  • I don't see the need for vector<int> queries. It is a waste of space. You should process queries one by one.

  • if (total_positive_sets < k) does not need to be special cased. In fact, doing so results in the bug: if this condition is initially false, the loop is not entered, and queries_needed remains -1, even though you already have enough positive segments. A natural way to write the loop is

      while ((total_positive_sets < k) && (queries < q))
    
  • vector<int> temp3 does not deserve to be a vector. It is a pair<int, int>.

\$\endgroup\$
2
  • \$\begingroup\$ If you read the question again, it is mentioned only three libraries are allowed so pair can't be implemented \$\endgroup\$
    – driver
    Sep 12, 2023 at 5:00
  • 1
    \$\begingroup\$ Instead of std::pair<int, int> just create a struct segment { int li; int ri; }. Then std::vector<segment> sets; … sets.emplace_back(temp1, temp2); \$\endgroup\$
    – G. Sliepen
    Sep 12, 2023 at 10:16

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.