Problem Link: Link
Author: Aman Singhal
Tester: Nishit Sharma
Editorialist: Aman Singhal
DIFFICULTY:
EASY - MEDIUM.
PREREQUISITES:
Basic- Maths.
Problem
To minimize the maximum value of candies in the array by passing candies only to the left.
Quick Explanation:
Tap to view
We start with the first element and then for each index we maintain the average of all candies upto that index and the maximum value upto that index.Let the current index be i then if the value a[i] is greater than the maximum value so far then we check if the average value is greater than the maximum value encountered so far if yes then we set the maximum value uptil the current index as average.
Explanation:
Tap to view
We are given N value of an array and since N cannot excedd 10**5 over all test cases we are sure that O(N) algorithm works.
We are given that every child can give his candies to its immediate left one. So, we will start with first child since he cannot give his candies to anyone and maximum till that point will be his value. Then we will start iterating the values of the array and check whether it exceeds the current maximum value or not. If it does than we have to distribute it to the previous child and recalculate the maximum value. It can be done by calculating the average till that point. For calculating average we will define a variable in the beginning itself and calculate the sum with each iteration or form a array which will store the average till that index.
Now we will recalculate the maximum value by distributing the candies and if exceed the current maximum value we will update it or continue with the same value.
Time complexity: O(N)
Solutions:
Editorialist's Solution
import math,sys
input=sys.stdin.readline
def vp(A):
mid,sv,mu=0,0,0
for i in range(len(A)):
sv=sv+A[i]
mid=(sv+i)//(i+1)
if (A[i]>mu):
mu=max(mu,mid)
return(mu)
T=int(input())
for _ in range(T):
N=int(input())
G=list(map(int,input().split()))
print(vp(G))
Tester's Solution
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int main()
{ quick;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll a[n];
fab(0,n,i)
cin>>a[i];
ll mid,sum=0,maxutil=0;
fab(0,n,i)
{
sum+=a[i];
mid=(sum+i)/((i+1));
if(a[i]>maxutil)
{
maxutil=max(maxutil,mid);
}
}
cout<<maxutil<<endl;
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}