HackerRank Luck Balance

This is the solution for the HackerRank Luck balance problem, in python. Luck Balance is a problem in the Interview Preparation Kit > Greedy Algorithms and is considered easy.

The main idea is that someone believes in the balance of luck. She needs to loose some contests to win on others. But the requirements are more complex:

• There are two types of contests: important and unimportant.
• The person can only lose a maximum of k important contests.
• If the person loses a contest, its points of luck are added to their luck balance.
• If the person wins a contest, the luck points are removed from their luck balance.
• The person can choose which contests to lose.

To solve the problem, we can use the following greedy algorithm:

1. Sort the contests in descending order of their luck points.
2. For each contest:
   • If the contest is important and the person has not yet lost k important contests, lose the contest.
   • Otherwise, win the contest.

The catch here is to choose what to loose. For that, the person must sort the contests array in descending order. So, she will loose first the ones with more points.

For example, having

k = 3
contests = [[5, 1], [2, 1], [1, 1], [8, 1], [10, 0], [5, 0]]

she has 4 important contests (and 2 unimportant), but can loose only 3 of them. If she sort in reverse order, she will traverse first the most valuables first:

constests.sort(reverse=True)
print(contests)
# [[10, 0], [8, 1], [5, 1], [5, 0], [2, 1], [1, 1]]

Here is the complete solution in python:

def luckBalance(k, contests):
    contests.sort(reverse=True)
    balance = 0
    lost_important = 0

    for contest in contests:
        if contest[1] == 1:
            if lost_important < k:
                balance += contest[0]
                lost_important += 1
            else:
                balance -= contest[0]
        else:
            balance += contest[0]
    return balance