sanjay6969's blog

By sanjay6969, 10 days 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

»
10 days 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
  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Guess what! You will get TLE.

    WHY?
    • »
      »
      »
      10 days 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

      • »
        »
        »
        »
        7 days 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.

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

          yes, can you share the problem link

          • »
            »
            »
            »
            »
            »
            7 days 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.

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

Spoiler
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate it a bit more