MISS03-Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: [Vivek Kumar Mishra(vkm41101 | CodeChef User Profile for Vivek Kumar Mishra | CodeChef)
Tester: Vivek Kumar Mishra
Editorialist: Harshit Pandey

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Binary Search

PROBLEM:

To find the Maximum Length L that would give the desired Length of wire

QUICK EXPLANATION:

Binary Search the desired Value.

EXPLANATION:

It is clear that there will be a threshold Value of L beyond which sufficient Length of wire cannot be procured. This Threshold Value can be binary searched easily.

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

using namespace std;

#define nln ‘\n’
#define fr(i, l, h, s) for (long long i = l; i < h; i += s)
#define inp(x,arr) for(auto& x:arr) cin >> x
#define ll long long
const ll M = 998244353;

/===================================================================/

ll intfromstring(string s)
{
int n=s.length();
ll num=0;
fr(i,0,n,1) num=num*10+(s[i]-‘0’);
return num;
}

ll factn(ll n)
{
ll prod=1;
if(n==0) return 1;
fr(i,1,n+1,1)prod*=i;
return prod;
}

ll factlogn(ll lo, ll hi)
{
if(hi-lo==1) return hilo;
if(hi-lo==2) return hi
(hi-1)*(lo);
int mid=(hi+lo)/2;
return factlogn(lo,mid) * factlogn(mid+1,hi);
}

ll binarySearch(ll arr[], ll lo, ll hi, ll x)
{
if(hi-lo>1)
{
ll mid=(lo+hi)/2;
if(arr[mid]==x) return mid;
if(arr[mid] > x) return binarySearch(arr, lo, mid-1, x);
if(arr[mid] < x) return binarySearch(arr, mid+1, hi, x);
}
return -1;
}

ll firstOccurence(ll arr[], ll lo, ll hi, ll x)
{
if (hi - lo > 1)
{
ll mid = (lo + hi) / 2;
if (arr[mid] == x)
return firstOccurence(arr, lo, mid, x);
if (arr[mid] < x)
return firstOccurence(arr, mid + 1, hi, x);
if (arr[mid] > x)
return firstOccurence(arr, lo, mid - 1, x);
}
if (arr[lo] == x)
return lo;
if (arr[hi] == x)
return hi;
return -1;
}

ll lastOccurence(ll arr[], ll lo, ll hi, ll x)
{
if (hi - lo > 1)
{
ll mid = (lo + hi) / 2;
if (arr[mid] == x)
return lastOccurence(arr, mid, hi, x);
if (arr[mid] < x)
return lastOccurence(arr, mid + 1, hi, x);
if (arr[mid] > x)
return lastOccurence(arr, lo, mid - 1, x);
}
if (arr[hi] == x)
return hi;
if (arr[lo] == x)
return lo;
return -1;
}

ll count(ll arr[], ll n, ll x)
{
return lastOccurence(arr, 0, n - 1, x) - firstOccurence(arr, 0, n - 1, x) + 1;
}

long long int maxl(long long int a, long long int b)
{
if (a > b)
return a;
return b;
}

long long int minl(long long int a, long long int b)
{
if (a < b) return a;
return b;
}

long long int absl(long long int a)
{
if(a<0)return -a;
return a;
}
ll powb(int base, int po)
{
base%=M;
if(base==1 || po==0) return 1;
if(po==1) return base%M;
if (po&1)
{
ll x=powb(base, po/2)%M;
return (((x*x)%M)base)%M;
}
ll x = powb(base, po / 2)%M;
return (x
x)%M;
}

/====================================================================/

bool getm(ll arr[],ll n, ll m, ll cut)
{
ll get=0;
fr(i,0,n,1) get+=maxl(0, arr[i]-cut);
if (get >= m) return true;
return false;
}

void testCase()
{
ll n,m;
cin >> n >> m;
ll lo=0, hi=2e9;
ll arr[n];
inp(x,arr);

while(hi-lo>1)
{
    ll mid=(hi+lo)/2;\
    if(getm(arr,n,m, mid)) lo=mid;
    else hi=mid-1; 
}
if (getm(arr, n, m, hi))
{
    cout << hi << nln;
    return;
}
else{
    cout << lo << nln;
    return;
}
return;

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int t = 1;
// cin >> t;
while (t–)
{
testCase();
}
return 0;
}