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.

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.