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.