Skip to content

Instantly share code, notes, and snippets.

@alivesay
Created May 20, 2021 16:01
Show Gist options
  • Save alivesay/92a0d0c65fd13cea267a98e303d78045 to your computer and use it in GitHub Desktop.
Save alivesay/92a0d0c65fd13cea267a98e303d78045 to your computer and use it in GitHub Desktop.
template <typename T>
T worstCase(T p_psxCount, T p_floorCount) {
Cache<T> cache;
auto min = [](T a, T b) { return (a < b) ? a : b; };
auto max = [](T a, T b) { return (a > b) ? a : b; };
auto memo_W = [&cache](T n, T k, auto &&W) {
return (cache.count({n,k}) > 0) ? cache[{n,k}] : cache[{n,k}] = W(n,k,W);
};
// https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle
// W(n,k) = 1 + min{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k }
auto W = [&](T n, T k, auto&& W)->T {
T L = 1, R = k, x, least = std::numeric_limits<T>::max();
if (k == 0) return 0; // W(n, 0) = 0
if (n == 1) return k; // W(1, k) = k
while (L <= R) { // Binary Search
x = (L+R) >> 1;
T n1 = memo_W(n - 1, x - 1, W); // W(n − 1, x − 1) -> BROKEN
T n2 = memo_W(n, k - x, W); // W(n, k - x) -> NOT BROKEN
if (n1 > n2) {
R = x - 1;
least = min(least, n1);
} else {
L = x + 1;
least = min(least, n2);
}
}
return 1 + least; // W(n,k) = 1 + ...
};
return W(p_psxCount, p_floorCount, W);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment