Egg Dropping Algorithm

// TABULATION IMPLEMENTATION
// Ref: https://www.youtube.com/watch?v=UvksR0hR9nA&list=PL-Jc9J83PIiEZvXCn-c5UIBvfT8dA-8EG&index=43

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define F first
#define S second
#define PI 3.1415926535897932384626
#define sz(x) ((int)(x).size())

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vull> vvull;
typedef vector<vb> vvb;
typedef vector<vc> vvc;

/************************************************** DEBUGGER *******************************************************************************************************/

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(ld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(vector <vector<T>> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }

/*******************************************************************************************************************************************************************/

mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}

const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;

ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
                         while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }

ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }

/******************************************************************************************************************************/

int egg_drop(int floors, int eggs) {
    vvi dp(eggs + 1, vi(floors + 1));

    // initialisation of dp matrix

    // if eggs = 0, then no answer
    // if eggs = 1, then ans = #floors
    for(int j = 0; j <= floors; j++) dp[0][j] = -1, dp[1][j] = j;

    // if floors = 0, then ans = 0
    // if floors = 1, then ans = 1
    for(int i = 2; i <= eggs; i++) dp[i][0] = 0, dp[i][1] = 1;

    for(int i = 2; i <= eggs; i++) {
        for(int j = 2; j <= floors; j++) {
            int res = INT_MAX;

            for(int rj = j - 1, lj = 0; rj >= 0 and lj < j; rj--, lj++) {
                int tmp = 1 + max(dp[i][rj], dp[i-1][lj]);
                res = min(res, tmp);
            }

            dp[i][j] = res;
        }
    }

    return dp[eggs][floors];
}

void solve()
{
    int floors, eggs;
    cin >> floors >> eggs;

    if(eggs == 0 and floors != 0) cout << -1 << "\n";
    else cout << egg_drop(floors, eggs) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif

    // #ifndef ONLINE_JUDGE
    //      freopen("error.txt", "w", stderr);
    // #endif

    int t = 1;
    // int test = 1;
    // cin >> t;
    while(t--) {
        // cout << "Case #" << test++ << ": ";
        solve();
    }

    return 0;
}

/* NOTE: The 3rd for() loop in the function egg_drop() can also be used in this manner:--->

   for(int k = 1; k <= j; k++) {
       int tmp = 1 + max(dp[i - 1][k - 1], dp[i][j - k]);
       res = min(res, tmp);
   }
*/


// dp[][] is a 2 D global matrix/vector of vectors, with size (eggs + 1) x (floors + 1)

// Time Complexity: O(floors^2 x eggs)
// Auxiliary Space : O(floors x eggs)