### sanjay6969's blog

By sanjay6969, 10 days ago,

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;
}

• -13

 » 10 days ago, # |   0 your approach is wrong as well as sample test 2 is also incorrect. we can do this problem using O(n^2) dp. code#include using namespace std; char nl = '\n'; using i64 = long long; void solve(int t) { // cout << "test #" << t << << nl; int n; cin >> n; vector A(n); for(auto& a : A) cin >> a; vector is_a(2); is_a[n & 1] = 1; vector dp(n); for(int len = 1; len <= n; len++) { // calculating dp values for subarray of length len vector new_dp(n); for(int front = len - 1; front < n; front++) { int back = front - len + 1; // dp[front] store the value of game played on subarray A[back + 1]..A[front] if(is_a[len & 1]) { // A's turn // A will try to maximize sum_a - sum_b; // 2 case possible // A choose back -> subarray reduces to A[back + 1]..A[front] // A choose front -> subarray reduces to A[back]..A[front - 1] new_dp[front] = max(A[back] + dp[front], A[front] + (front - 1 >= 0 ? dp[front - 1] : 0)); } else { // same as above but B will try to minimize sum_a - sum_b new_dp[front] = min(-A[back] + dp[front], -A[front] + (front - 1 >= 0 ? dp[front - 1] : 0)); } } dp = new_dp; } // dp[n - 1] is max value sum_a - sum_b // sum_a // sum_b = tot - sum_a // -> sum_a = (dp[n - 1] + tot) / 2 cout << (dp[n - 1] + accumulate(A.begin(), A.end(), 0LL)) / 2LL << nl; } int main() { int tt = 1; // cin >> tt; for(int t = 1; t <= tt; t++) solve(t); } 
•  » » 10 days ago, # ^ | ← Rev. 2 →   +2 Guess what! You will get TLE. WHY?See the range of N
•  » » » 10 days ago, # ^ |   0 i know but the best i could get is this. i still have to think about the optimal soln
•  » » » » 7 days ago, # ^ |   0 thanks for the approach, if you figured out the optimal approach you are thinking about then do share.
•  » » » » » 7 days ago, # ^ |   0 yes, can you share the problem link
•  » » » » » » 7 days ago, # ^ |   0 i don't have any link, it was asked in offline competition in my university.
 » 7 days ago, # |   +8 This problem is solvable in $\Theta(N)$ via a greedy algorithm. SpoilerLet $(a, b, c)$ be three consecutive signals, satisfying $a, c \leq b$. You can replace it with a single signal with value $a - b + c$. The case where the largest signal is on the edge can be solved greedily.Source: Algorithmic Engagements 2010, Termites.
•  » » 6 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } can you elaborate it a bit more