Luck Balance


Problem Statement :


Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. Initially, her luck balance is 0. She believes in "saving luck", and wants to check her theory. Each contest is described by two integers, L[ i ] and T[ i ]:

L[ i ] is the amount of luck associated with a contest. If Lena wins the contest, her luck balance will decrease by ; if she loses it, her luck balance will increase by L[ i ].
T[ i ] denotes the contest's importance rating. It's equal to 1 if the contest is important, and it's equal to 0 if it's unimportant.

If Lena loses no more than k important contests, what is the maximum amount of luck she can have after competing in all the preliminary contests? This value may be negative.


Function Description

Complete the luckBalance function in the editor below.

luckBalance has the following parameter(s):

int k: the number of important contests Lena can lose
int contests[n][2]: a 2D array of integers where each contests[ i ] contains two integers that represent the luck balance and importance of the ith contest
Returns

int: the maximum luck balance achievable

Input Format

The first line contains two space-separated integers n and k, the number of preliminary contests and the maximum number of important contests Lena can lose.
Each of the next n lines contains two space-separated integers, L[ i ] and T[ i ], the contest's luck balance and its importance rating.


Sample Input

STDIN       Function
-----       --------
6 3         n = 6, k = 3
5 1         contests = [[5, 1], [2, 1], [1, 1], [8, 1], [10, 0], [5, 0]]
2 1
1 1
8 1
10 0
5 0

Sample Output

29


Solution :



title-img


                            Solution in C :

In C :






#include<stdio.h>
 long int sort(int a[] ,int size,int k){
	
	int i,min,j,sum=0,t; 
	for(i=0;i<k;i++){
		min=i;
		
		for(j=i+1;j<size;j++){
			if(a[min]>a[j])
			min=j;
		}
		if(i!=min){
			t=a[i];
			a[i]=a[min];
			a[min]=t;
		}
		//printf("a[%d]=%d\n",i,a[i]);
	sum+=a[i];	
	}
	//printf("sum=%d\n",sum);
return sum;	
	
}
int main(){
	int n,k,i,t;
	long int l,sum1=0,sum2;
	int ar[100],arc=0;
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		
		scanf("%ld %d",&l,&t);
		
		if(t==1)
		ar[arc++]=l;
		
		
		sum1+=l;
	}
	sum2=sort(ar,arc,arc-k);
	//	printf("sum1=%d\n",sum1);
	printf("%ld",(sum1- 2*(sum2)));
	
	return 0;
}
                        

                        Solution in C++ :

In  C  ++  :






#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;



int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	int ans = 0;
	vi w;
	REP(i, n) {
		int a, b;
		scanf("%d%d", &a, &b);
		if(b == 0) ans += a;
		else w.pb(a);
	}
	sort(w.rbegin(), w.rend());
	REP(i, (int) w.size()) {
		if(i < k) ans += w[i];
		else ans -= w[i];
	}
	printf("%d\n", ans);
	return 0;
}
                    

                        Solution in Java :

In  Java :






import java.util.Arrays;
import java.util.Scanner;
public class LuckBalance {

    static class Contest implements Comparable<Contest> {
        int l,t;

        @Override
        public int compareTo(Contest o) {
            if(t == o.t) {
                return (this.l - o.l);
            }else {
                return -(this.t - o.t);
            }
        }
    }
    public static void main(String[] args) {
        int N, K;
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();

        int total = 0;
        int t,l;
        Contest[] contests = new Contest[N];
        int importCnt = 0;
        for (int i = 0; i < N; i++) {

            l = scanner.nextInt();
            t = scanner.nextInt();
            total += l;
            if(t == 1) {
                importCnt++;
            }
            Contest contest = new Contest();
            contest.l = l;
            contest.t = t;

            contests[i] = contest;
        }

        Arrays.sort(contests);

        int winCnt = importCnt - K;
        if(winCnt <= 0) {
            System.out.println(total);
            return;
        }

        for (int i = 0; i < winCnt; i++) {
            total -= 2 * contests[i].l;
        }
        System.out.println(total);



    }
}
                    

                        Solution in Python : 
                            
In  Python3 :






N, K = map(int, input().strip().split())

luck = 0
important = []

for i in range(N):
    L, T = list(map(int, input().strip().split()))
    if T == 0:
        luck += L
    else:
        important.append(L)
        
for i in sorted(important, reverse=True):
    if K > 0:
        luck += i
        K -= 1
    else:
        luck -= i

print(luck)
                    

View More Similar Problems

Array-DS

An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3

View Solution →

2D Array-DS

Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t

View Solution →

Dynamic Array

Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.

View Solution →

Left Rotation

A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d

View Solution →

Sparse Arrays

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun

View Solution →

Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu

View Solution →