I got lost on that statement, too. I ignored it and focused on the example.

Actually the description is intentionally made complex for increasing its value.

very nice and elegant solution

in the statement int result = total - 2*luckToFlip; why have you put 2*luckToFlip insted of just luckToFlip?

very nice solution

Unfortunately, the "Collections.sort" method degrades the performance to O(n*log(n)). Besides, the "List" collection uses an additional O(n) amount of memory. An optiomal solution should run in O(n*log(k)) time and use O(k) space.

exactly same as mine.

Very nice! Based on this i wrote it in c#

var temp = Console.ReadLine().Split(' ');
var arr = Array.ConvertAll(temp, Int32.Parse);
var N = arr[0];
var K = arr[1];
List<Tuple<int, int>> luckBalance = new List<Tuple<int, int>>();
for (var contest = 0; contest < N ; contest++){
    var ln_temp = Console.ReadLine().Split(' ');
    var ln = Array.ConvertAll(ln_temp, Int32.Parse);
    var luck = ln[0];
    var importance = ln[1];
    luckBalance.Add(Tuple.Create(luck, importance));
}
var importanContests = luckBalance.Where(u => u.Item2 == 1).Select(u => u.Item1).OrderBy(u=>u).ToList();
var luckSum = luckBalance.Select(u => u.Item1).Sum();
int luckToFlip = 0;
int mustWinImprCount = importanContests.Count() - K;
for (int i = 0; i < mustWinImprCount; i++)
{
    luckToFlip += importanContests[i];
}
int result = luckSum - 2 * luckToFlip;        
Console.Write(result);

Hi. Nice solution. For a challenge, try using quickselect to improve runtime like in this O(n) average runtime solution.

HackerRank solutions.

thanks man

would it improve the performance if we replace the last part with

Iterator<Integer> iter = list.iterator();
while(list.size() > k) {
	totalLuck -= 2*iter.next();
	k++;
}
return totalLuck;

?

for a test case n == k wont the line

int mustWinImprCount = importantContests.size() - k;

cause a problem, Since Arraylist size is less than n, the variable mustWinImprCount will be initialized with negative value causing the for loop to cease in the beginning?

Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation:

   // Complete the luckBalance function below.
    static int luckBalance(int k, int[][] contests) {
        int numLuck = 0;
        int totalImportant = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer obj1, Integer obj2){
                return obj1 - obj2;
            }
        });
        for(int[] contest : contests){
            numLuck += contest[0];
            if(contest[1] == 1){
                minHeap.offer(contest[0]);
                totalImportant++;
            }
        }
        for(int i = 0; i < totalImportant - k; i++){
            numLuck -= 2 * minHeap.poll();
        }
        return numLuck;
    }

Just completed this problem and this solution is eerily similar to mine:

static int luckBalance(int k, int[][] contests) {
    List<Integer> important = new ArrayList<Integer>();
    int totalLuck = 0;
    for(int i = 0; i < contests.length; i++){
         if(contests[i][1] == 1){
             important.add(contests[i][0]);
         }
        totalLuck += contests[i][0];
    }
    int canWin = important.size() - k, score = 0;
    Collections.sort(important);
    for(int i = 0; i < canWin; i++){
        score += 2 * important.get(i);
    }

    return totalLuck - score;
}

Great minds think alike? haha

I haven't used C++ in over a decade but this implementation certainly makes sense. Would I have caught it right away - probably not!

Had same problem. Was getting segmentation fault. Thanks buddy.

int n,k;
cin >> n >> k;

vector <int> impt;
int impt_sum=0;
int unimpt_sum=0;

for (int i=0;i<n;i++) {
    int luck,type;
    cin >> luck >> type;

    if (type) {
        impt.push_back(luck);
        impt_sum+=luck;
    }    
    else 
        unimpt_sum+=luck;
}

sort(impt.begin(),impt.end());
int isize=impt.size();

if (k<=isize) for (int i=isize-k-1;i>=0;i--) impt_sum-=(2*impt[i]);

cout << impt_sum+unimpt_sum;

then what changes u did ?

then how did u solved the thing ??

thx buddy..

More specifically which events should she lose (if any) of the ones that she is allowed to lose based on the value of k.

same idea, but your solution is much clearer and more concise

def luck_balance(k, contests):
    # group important and unimportant contests
    sorted_contests = sorted(contests, key=itemgetter(1))
    groups = tuple(list(g) for k, g in it.groupby(sorted_contests, key=itemgetter(1)))
    if len(groups) > 1:
        unimportant, important = groups
    elif groups[0][0][1] == 0:
        unimportant, important = groups[0], []
    else:
        unimportant, important = [], groups[0]

    # calculate how many matches we need to throw

    throws = len(important) - k
        
    if throws < 1:
        return sum(luck for luck, _ in important + unimportant)

    # start by sorting important contests to throw the smallest in terms of luck
    sorted_important = sorted(important)
    # group wins and losses
    losses, wins = sorted_important[:throws], sorted_important[throws:]
    # do math
    total = sum(luck for luck, _ in wins + unimportant)
    net = total - sum(luck for luck, _ in losses)
    return net

While selecting competition to win you pick competition which is important and has least luck cost. Your solution is optimal at that instant that's why it is greedy.

As a long LINQ one liner for fun:

static int luckBalance(int k, int[][] contests)
 {       
    return contests.Select(contest => new { Luck = contest[0], Importance = contest[1] }).OrderByDescending(contest => contest.Luck).Select(contest => (contest.Importance == 1 && k-- <= 0) ? -contest.Luck : contest.Luck).Sum();
}

Me too have encountered the same problem,I didn't know why,but I too have same problem,can someone just help us out?

you have not taken into consideration the cases when number of unimportant cases are more than or equal to important cases

you have initialized the value of x=imp-k; but as we can assign any value to k,therefore if k>imp :- then x will be negative and after that you have used that x in the for loop also , in which when you have used c[i] where i=x;i

Test Case 7 is working for me but test case 8 is failing even though my answere are correct.

Put the condition if k is more than important then return total count. Here is the snippet and with this condition all test cases are passing (PS: without this condition, test case 7 and 8 were failing). I am not posting the whole code :)

int luckBalance(int k, vector> contests) { sort(contests.begin(), contests.end(), [](vector&a, vector&b){return a[0]=important) return total; ....... //your rest of the logic ....... // goes ........ // here }