PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Naman Jain
Tester: Rahul Dugar
Editorialist: Ritesh Gupta
DIFFICULTY:
Easy
PREREQUISITES:
Two-Pointer
PROBLEM:
You are given a sequence of N integers. You want to reverse a subsequence of a given sequence, exactly once such that maximum sum subarray is maximum possible.
QUICK EXPLANATION:
- By applying the operation mentioned in the problem, it is always possible to separate out non-negative and negative numbers such that all negative numbers appear in start and all non-negative numbers appear in the end or vice versa.
- So, the maximum sum-subarray in all possible possibilities is equal to the sum of all positive numbers and the subsequence which needs to be revered can be found using two pointer technique.
EXPLANATION:
Lemma: It is always possible to select a subsequence and reverse it such that the resulting sequence has all the negative numbers in the first part and rest non-negative numbers in the second part or vice versa.
Proof: As there are two states for any number i.e. negative and non-negative, So, we can say that it is always possible to divide a sequence into two continuous parts such that either count of negative numbers in first part is equal to the count of non-negative numbers in second part or vice-versa. If this is possible then we can select a subsequence containing either negative numbers from the first part and non-negative numbers from the second part or vice-versa.
Now, To find such a subsequence which suffice our use case, can be found using two pointer approach. In a two pointer approach we keep two pointers, one for non-positive numbers which scan the sequence from start and another for negative numbers which scan the sequence from back.
The implementation details can be found in solutions.
TIME COMPLEXITY:
TIME: O(N)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.first << "," << P.second << ")";}
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector< pii >
#define I insert
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define mp make_pair
#define endl "\n"
void solve(){
int N; cin>>N;
ll ans = 0; int num = 0;
vi v(N);
for(int i=0;i<N;i++){
cin>>v[i];
tie(ans, num) = v[i]>0 ? mp(ans+v[i], num+1) : mp(ans, num) ;
}
cout<<ans<<"\n";
vi seq;
for(int i=0;i<N;i++){
if(i<num && v[i]<=0) seq.pb(i);
else if(i>=num && v[i]>0) seq.pb(i);
}
cout<<seq.size()<<" "; for(auto z:seq) cout<<z+1<<" ";
cout<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
int T; cin>>T;
while(T--){
solve();
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sum_n=0;
int a[100005];
void solve() {
int n;
cin>>n;
// int n=readIntLn(2,100000);
// sum_n+=n;
// assert(sum_n<=2000000);
int ans=0,cntr=0;
vi index;
fr(i,1,n) {
cin>>a[i];
// if(i!=n)
// a[i]=readIntSp(-1000000000,1000000000);
// else
// a[i]=readIntLn(-1000000000,1000000000);
// assert(a[i]);
if(a[i]>0) {
ans+=a[i];
cntr++;
index.pb(i);
}
}
vi rev;
fr(i,1,cntr) {
if(a[i]<0) {
rev.pb(i);
rev.pb(index.back());
index.pop_back();
}
}
sort(all(rev));
cout<<ans<<endl;
cout<<sz(rev);
for(int i:rev)
cout<<" "<<i;
cout<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
// int t=readIntLn(1,2000);
int t=1;
cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector <int> v;
int cnt = 0;
int sum = 0;
for(int i=0;i<n;i++) {
int x;
cin >> x;
if(x < 0) {
cnt++;
} else {
sum += x;
}
v.push_back(x);
}
cout << sum << endl;
if(cnt == 0 || cnt == n) {
cout << 0 << endl;
continue;
}
vector <int> l,r;
int l1, r1;
l1 = 0;
r1 = n-1;
while(l1 < r1) {
while(l1 < n && v[l1] < 0)
l1++;
while(r1 >= 0 && v[r1] > 0)
r1--;
if(l1 < r1) {
l.push_back(l1);
r.push_back(r1);
l1++;
r1--;
}
}
reverse(r.begin(), r.end());
cout << l.size() + r.size() << " ";
for(int i:l) {
cout << i+1 << " ";
}
for(int i:r) {
cout << i+1 << " ";
}
cout << endl;
}
}
for video editorial, very clear subtitles and audio quality 
