sanjay6969's blog

Is this approach correct ?? any optimization for this problem?
By sanjay6969, 7 months ago, In English

Is my approach correct? can anyone have more optimised approach?

my code:


#include <iostream>
#include <vector>

using namespace std;

int main() {
    int signal_size;
    cin >> signal_size;

    vector<int> signals(signal_size);
    for (int i = 0; i < signal_size; ++i) {
        cin >> signals[i];
    }

    int filter_A_sum = 0;
    int filter_B_sum = 0;

    int left = 0, right = signal_size - 1;

    bool is_A_turn = true;

    while (left <= right) {
        if (is_A_turn) {
            if (signals[left] > signals[right]) {
                filter_A_sum += signals[left];
                ++left;
            } else {
                filter_A_sum += signals[right];
                --right;
            }
        } else {
            if (signals[left] > signals[right]) {
                filter_B_sum += signals[left];
                ++left;
            } else {
                filter_B_sum += signals[right];
                --right;
            }
        }

        is_A_turn = !is_A_turn;
    }

    cout << filter_A_sum << endl;

    return 0;
}
  • Vote: I like it
  • -13
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

your approach is wrong as well as sample test 2 is also incorrect. we can do this problem using O(n^2) dp.

code
→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Guess what! You will get TLE.

    WHY?
    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i know but the best i could get is this. i still have to think about the optimal soln

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks for the approach, if you figured out the optimal approach you are thinking about then do share.

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yes, can you share the problem link

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i don't have any link, it was asked in offline competition in my university.

            → Reply
»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This problem is solvable in $$$\Theta(N)$$$ via a greedy algorithm.

Spoiler
→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate it a bit more

    → Reply