You are viewing a single comment's thread. Return to all comments →
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:
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.
Seems like cookies are disabled on this browser, please enable them to open this website
Luck Balance
You are viewing a single comment's thread. Return to all comments →
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.