SIGNFLIP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy

PROBLEM:

Given an array of N integers. You can multiply at most K elements by -1. Find the maximum possible sum, of a subsequence of the modified array.

EXPLANATION:

Claim: The optimal subsequence should only contain positive numbers present in the modified array.
(Proof is trivial and left to the reader as an exercise!)

Thus, It is optimal to multiply the negative numbers in the array by -1, making them positive (which can then be included in the optimal subsequence).

However, there might be more than K negative elements, all which we can’t multiply due to the given constraints.

Claim: It is optimal to multiply the K smallest negative numbers in the array, by -1.

Reasoning

If a < b, then -a > -b.
Thus, when a is negative, -a is positive and greater than -b, giving a larger sum when added to the subsequence.

Implementation

Sort the array. Iterate from smallest to largest numbers, multiplying the first K negative elements by -1. Finally, iterate over the array once more, adding all the positive terms together, to get the required answer.

TIME COMPLEXITY:

Sorting the array takes O(N\log N). Iterating over the array both times takes O(N) each. The total complexity is thus:

O(N\log N + N + N) \approx O(N\log N)

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

what’s wrong with this code?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin,x.end()
#define pb push_back
#define mp make_pair

void solve(){
    ll n,k;
    cin>>n>>k;
    
    set <ll> s1 ,s2;
    for (auto i = 0; i < n; i++){
        ll a;
        cin>>a;
        if (a >= 0){
            s1.insert(a);
        }
        else {
            s2.insert(a);
        }
    }    

    ll j = 0;
    for (auto i = s2.begin(); (i != s2.end()) && (j < k); i++,j++){
        s1.insert(abs(*i));
    }
    ll count = 0;
    for (auto i = s1.begin(); i != s1.end(); i++){
        count += (*i);
    }
    cout<<count;
}

int main(){
    ll t;
    cin>>t;
    while (t--){
        solve();
        cout<<'\n';
    }
}
3

This O(n) solution buts online judge showing incorrect, why?

#include <bits/stdc++.h>
using namespace std;
#define max(a, b) (a < b ? b : a) 
#define min(a, b) ((a > b) ? b : a) 
#define mod 1e9 + 7 
#define FOR(a, c) for (int(a) = 0; (a) < (c); (a)++) 
#define FORL(a, b, c) for (int(a) = (b); (a) <= (c); (a)++) 
#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); (a)--) 
#define INF 1000000000000000003 
typedef long long int ll; 
typedef vector<int> vi; 
typedef pair<int, int> pi; 
#define F first 
#define S second 
#define PB push_back 
#define POB pop_back 
#define MP make_pair 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    int t;
    cin >> t;
    while (t--) { 
        ll n,k;
        cin>>n>>k;
        vector<ll>arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        ll pos_sum = 0;
        set<ll>s;
        for(int i=0;i<n;i++){
            if(arr[i]>=0)
                pos_sum+=arr[i];
            else{
                s.insert(arr[i]);
            }
        }
        int j=0;
        for(auto it:s){
            if(j==k){
                break;
            }
            else{
                pos_sum+=abs(it);
                j++;
            }
        }
        cout<<pos_sum<<"\n";
    }
    return 0;
}
4

Give me some testcases where this code won’t work, or Is this approach Incorrect?

void solve()
{
	int n, k;
	std::cin >> n >> k;

	vector<int> num;

	ll pos = 0, neg = 0, sum_pos = 0, sum_neg = 0;

	for (int i = 0; i < n; i++)
	{
		int val;
		std::cin >> val;

		if (val >= 0)
		{
			pos++;
			sum_pos += val;
		}
		else
		{
			neg++;
			num.pb(abs(val));
		}
	}

	if (pos == n)
	{
		std::cout << sum_pos << '\n';
		return;
	}
	else if (neg == n)
	{
		std::cout << "0\n";
		return;
	}

	ll rest_sum = 0;
	sort(num.begin(), num.end(), greater<int>());
	for (int i = 0; i < k && i < num.size(); i++)
	{
		rest_sum += num[i];
	}

	std::cout << sum_pos + rest_sum << '\n';
}
5

Ahh! I got it [Now this question is for archives] :

1
6 5
-1 -1 -1 -1 -1 -1

or

1
6 6
-1 -1 -1 -1 -1 -1
6

Why does it shows TLE? The time complexity is O(k + n).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MaximiseTheSubsequenceSum
{
    class Program
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());

            while (t-- > 0)
            {
                string[] s = Console.ReadLine().Split(' ');
                int n = int.Parse(s[0]);
                int k = int.Parse(s[1]);

                int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
                List<int> sorted = arr.ToList();
                sorted.Sort();
                List<int> negative = new List<int>();
                int sum = 0;

                for (int i = 0; i < k; i++)
                {
                    if (sorted[i] < 0)
                        negative.Add(sorted[i]);

                    if (sorted[i] >= 0)
                        break;
                }

                for (int i = 0; i < n; i++)
                {
                    if (negative.Contains(arr[i]))
                        sum += (arr[i] * -1);

                    if (arr[i] > 0)
                        sum += arr[i];
                }

                Console.WriteLine(sum);
            }

            Console.Read();
        }
    }
}
7

how will you make sure that you are picking least k elements to your sum as elements in set need not to be sorted???

8

you are multiplying the fist k negative numbers from -1, but this isn’t optimal let me give you an example :
k = 2
neg numbers given in original order : -4 -1 -10
you are going to change -4 and -1 that will add 5 in answer
but the optimal choice would be : -4 and -10 that will add 14 in answer

9

can anyone tell me where am i wrong ?

#include <iostream>
#include<bits/stdc++.h>
using namespace std;


int main() {
	// your code goes here
	int t;
	cin>>t;
	
	
	while(t--){
	    int n,k;
	    cin>>n>>k;
	    int arr[n];
	    
	    for(int i=0; i<n; i++){
	        cin>>arr[i];
	    }
	    sort(arr, arr+n);
	    
	    int i=0;
	    int j=n-1;
	    int sum=0;
	    while(i<=j ){
	        if(abs(arr[i])>abs(arr[j]) ){
	            if(arr[i]<0 ){
	                if(k>0){
    	            sum += abs(arr[i++]);
    	            k--;
	                    
	                }
	            }
	            else{
	                sum += arr[i++];
	            }
	        }
	        
	        else if(abs(arr[i]) <= abs(arr[j])){
	            if(arr[j]<0){
	                if(k>0){
	                sum += abs(arr[j--]);
	                k--;
	                }
	            }
	            else{
	                sum += arr[j--];
	            }
	        }
	        
	        else{
	            break;
	        }
	        
	    }
	    
	    cout<<sum<<endl;
	    
	}
	return 0;
}