Love and Chef Solution

Problem

Simulation is quite an undervalued skill at coding. Often, given a description of a problem where we have to follow a set of rules or satisfy the properties, simulation comes to our mind for getting a general picture of the solution. However, two questions must be considered - How accurate is it? And how feasible is it to write the complex code for that?

Hence, simulation alone is useful only in some narrow cases. Nevertheless, combining it with various paradigms can potentially yield powerful results.

###Statement: In a far away Galaxy of Tilky Way, there was a planet Tarth where the sport of Tompetitive Toding was very popular. According to legends, there lived a setter known for understanding the pain of his friends in love.

The HR and the Team leader, Tanuj and Tanup, were quite distraught with their employees recently. Too many of them were asking for leaves, wanting to go home early to spend some time with their loved ones, and what not! All these extraneous things were keeping them away from their one true purpose - to work at office 24/7.

Hence, they come up with the following policy, that each and every man at Todechef shall henceforth follow eternal bachelorhood and maintain everlasting innocence.

Now, who can control love? Poor Urjan was way much smitten by his lover, and can't help but think of her at work. He wants to get off from work early.

You are given the amount of work that Urjan has, over the next $N$ days, in the form of an array. Urjan can shift some of the work of his current day to next day (and MUST complete them by the next day). However, if he shifts more than $K$ amount of work on any single day, Tanup and Tanuj will know something is fishy. He wants to shift the work, in such a way that the maximum amount of work that he has to do on any single day is minimized, so that he can go home early and meet his lover everyday. In other words, if you take the maximum work that he does over the $N$ days, this maximum should be minimized and this minimum value should be outputted. Since you are his friend, you must help him.

###Input:

• First line will contain $T$, number of test cases. Then the test cases follow.
• First line of each test case constraints 2 integers, $N$ and $K$.
• Next line contains $N$ space separated integers which represent the amount of work that he has over the next $N$ days.

###Output: For each test case, output the minimized maximum work that he has to do on any single day.

###Constraints

• $1 \leq T \leq 10^4$
• $1 \leq N \leq 10^5$
• $0 \leq K \leq 10^{18}$
• $0 \leq A_i \leq 10^{18}$
• Sum of $N$ over all test cases is $\leq 10^6$

###Subtasks

• 5% points - The input array is sorted.
• 5% points - $K=0$
• 10% points - $1 \leq N \leq 10$ and $0 \leq A_i \leq 10^6$
• 15% points - $1 \leq N \leq 10^5$ and $0 \leq A_i \leq 10^{6}$
• 20% points - $1 \leq N \leq 10^5$ and $0 \leq A_i \leq 10^9$
• 45% points - Original Constraints.

###Sample Input:

1
5 1000
5 4 3 2 1

###Sample Output:

3

###EXPLANATION: Recall that Urjan MUST do the work which he shifted to next day. One possible way of achieving the said answer is-

• Day 1 has 5 units of work. Shift 2 (units of work) to day 2.
• Day 2 now has 6 units of work. Shift 3 to next day. Note that even though 5 $\leq$ 1000, you cannot shift 5 units of work from Day 2 to Day 3, because the two units of work shifted from Day 1 have to be finished on Day 2 itself. They cannot be shifted forward to Day 3.
• Day 3 now has 6 units of work, shift 3 to next day.
• Day 4 now has 5 units of work, shift 2 to last day
• Day 5 has 3 units of work.

Notice that the amount of work shifted each day is $\leq K$, and hence this is valid.

Program :

 #include <bits/stdc++.h>

using namespace std;

#define ll long long

#define MOD 1000000007

#define ln '\n'

bool check_work(vector<ll> &v, ll k, ll max_Work)

{

    ll previous_Work = 0;

    for (ll i = 0; i < v.size(); i++)

    {

        if (previous_Work > k || previous_Work > max_Work)

            return false;

        ll rem = max_Work - previous_Work;

        previous_Work = max(v[i] - rem, 0ll);

    }

    return (previous_Work == 0);

}

pair<ll, ll> minimum_maximum(vector<ll> &v)

{

    pair<ll, ll> result = make_pair(LONG_MAX, LONG_MIN);

    for (auto el : v)

    {

        result.first = min(result.first, el);

        result.second = max(result.second, el);

    }

    return result;

}

void solve()

{

    ll n, k;

    cin >> n >> k;

    std::vector<ll> v(n);

    for (auto &i : v)

        cin >> i;

    pair<ll, ll> range = minimum_maximum(v);

    ll l = range.first, r = range.second;

    ll ans = r;

    while (l <= r)

    {

        ll mid = l + (r - l) / 2;

        if (check_work(v, k, mid))

        {

            ans = mid;

            r = mid - 1;

        }

        else

        {

            l = mid + 1;

        }

    }

    cout << ans << ln;

}

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    ll test_cases = 1;

    cin >> test_cases;

    while (test_cases--)

        solve();

    return 0;

}