MVAL - Editorial

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

Video Editorial

16 Likes

I thought that we can extract out positive and negative number as a partition but the proof is still unclear to me!

3 Likes

Iterate from left to right. Skip non-negative numbers and add negative numbers to an output vector. Whenever the size of vector becomes equal to the number of positive elements to the right of current index, just get the indices of the positive numbers and add them to the vector. We just need to handle the corner case where answer is 0. Refer this

2 Likes

I had totally read the problem statement wrong I thought that we have to print the subsequence after reversing the subsequence instead we have to print the indexes :pensive:

7 Likes

Its tagged as easy. How?

10 Likes

If there are p positive elements in the array, print the indices of the -ve values in the first p elements of the array, and the +ve elements not in the first p values of the array.
https://www.codechef.com/viewsolution/38078989

The number of -ve elements in the first p elements will be equal to the number of +ve elements not in the first p elements.

Reversing them is akin to putting the first half outside the array, and the second half inside the array.

3 Likes

Like :heart: for video editorial, very clear subtitles and audio quality :clap: :+1:

6 Likes

I have also done the same as given in Editorial but still, I’m getting WA. Can you tell me where I’m going wrong?

https://www.codechef.com/viewsolution/38074027

Video editorial into text format -

Given array A contains some positive and some negative element , let denote positive with + sign and negative with - sign

Now take an example => N = 9 [ + , - , - , + , + , - , - , + , - ]

so total positves (denote with p ) = 4

Now divide array into two part first part contains P (4) elements and other part contain 5 element

means -> [+ , - , - , +] $$ [ + , - , - , + , - ]

what we want , we want to place all + together right ?

see in first part if we replace 2 -ve’s with 2 +ve’s from second part our question is solved.

means take all -ve’s from first part and all +ve’s from second part and reverse them , u will surely get all +ve’s together

Proof : How many + ve’s we have P right ?

Now in first part there is some positive numbers (+) and some negative numbers(-) , let count all +ve’s in first part be X , so how many -ve’s in first part remaining ?
P - X right ? , Now in second part How many +ve’s remaining obviously P - X , why ( as in first part total +ve’s are X and in total we count +ve’s as P so in remaining part +ve’s will be P - X ) .

Now what we want we want all -ve’s from first part will be replaced with all +ve’s from second part right ? ( as -ve’s in part 1 = (P-X) , +ve’s in part 2 also = (P-X) )

so our problem is solved

  1. count all +ve numbers and sum of positive numbers = > p , sum
  2. store all -ve number indexes from 1 to p in list
  3. store all +ve number indexes from p+1 to n in list
  4. print sum (sum of all +ve numbers in list)
  5. print size and content of above index list

My solution : “https://www.codechef.com/viewsolution/38080042

9 Likes

Great Explanation!

1 Like

Can someone find the bug in this I am not getting what I am missing

https://www.codechef.com/viewsolution/38080335

Problem was not tough, but why do you write statements so bad? it took me 30 mins to under which subsequence meant which sub sequence and i still don’t how was out put expected.
someone tell me whats wrong in this : https://www.codechef.com/viewsolution/38060604

i keep my self free whole day and at the end this is really sad.

5 Likes

(Since nobody helped so) I think you made a mistake you should write in place of
if(sum == 0||count==n){
cout<<0<<endl;
cout<<0<<endl;
}

this

“if(sum == 0||count==n){
cout<<sum<<endl;
cout<<0<<endl;
}”

https://www.codechef.com/viewsolution/38081440

My solution O(n) time:


please look at this …@admin

think in terms of hoare’s partition algorithm and realise that we can always separate the
numbers greater than 0 than the numbers which are less than zero(just like we used to do
In quick sort)
Hope it helps!!!

1 Like

Try this case:
12
1 1 1 -1 -1 1 -1 1 -1 -1 0 0
Your output:
5
6 4 5 6 8 11 12
Sum is undoubtedly correct but with that sequence it is unachievable.
Reason is while counting pos you didn’t count zeroes but while swapping you are!

My solution is correct.
The final sequence will be:
1 1 1 0 0 1 1 -1 -1 -1 -1 -1 -1
so sum of first 7 elements is 5.

Please cross check once.

How 7th element has turned to 1?
It was -1 in test case i provided and sequence to be reversed according to output from https://www.codechef.com/viewsolution/38081887 : 4 5 6 8 11 12. Which means, final array: 1 1 1 0 0 1 -1 1 -1 -1 -1 -1.

Brother you are make a mistake while reversing the sequence .
Please check once again.
My solution is correct!.