We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

The description would be clearer if it read "L is the amount of luck that can be gained by losing the contest." She believes that luck is spent on wins and earned from losses.

## Luck Balance

You are viewing a single comment's thread. Return to all comments →

The description would be clearer if it read "L is the amount of luck that can be gained by

losingthe contest." She believes that luck is spent on wins and earned from losses.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.

i think you're right on this although you received downvotes

## C# Code

The complexity above is o(nlogn) because of the sort.

I have a solution with complecity of O(kn) which actually O(n):

We need to fill a matrix of 2D. Lines are contests and columns are the number of remaining imprortant contest failures:

## 0 1 2 3 ... K

## 0

## 1

## :

if this is a non-important contest then:

m[contest][k_left] = m[contest-1][k_left] + contest's luck

Otherwise we need to choose between failing or not failing the content (if we have remaining failures):

m[contest][k_left] = max ( m[contest-1][k_left] - contest's luck, m[contest-1][k_left+1] + contest's luck)

The 1st is a win, thus not changing the remaining failures.

The 2nd is a failure, thus we decreased the number of remaining failures from previous contest (k_left+1 --> k_left)

As for the last column, it means that we do decide not to fail at all.

Worse happens to your algorithm as k approaches n?

Shorter version:

totalLuckBalance -= 2 * tempList[j];

what is the reason for the 2*tempList[j]? Why do you need to subtract twice the value?

C++ solution :

## Java Solution

## PASSES 100% OF TEST CASES ✅

## O(N) TIME COMPLEXITY ✅

## SHORTEST CODE YOU CAN FIND IN JAVA! 🔥

Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element.

Not sure why this has so many down votes. This is an efficient solution in Java 8

Wonderful code

Hello can you tell me when we should go for priority queues...