SIGNFLIP - Editorial

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

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

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

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

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

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