COCR106 - Editorial

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;
}
4 Likes

Can somebody please explain how to solve this problem with binary search ?

Assume that you are given a value ‘x’ and you want to check if it is a candidate for the final answer. For this start from the end of the array, if arr[i] <= x then just continue to previous index, else remove the extra candies from the current person and transfer it to the previous person. If in the end, the first person has <= x candies then ‘x’ is a possible candidate, else you need to increase ‘x’ i.e. distribute more candies to other people.

My AC solution: CodeChef: Practical coding for everyone

5 Likes

Thanks buddy ! it really helped

please somebody Explain why we are taking mid=(sum+i)/(i+1) in Editorialist’s Solution. why this formula is not working mid =(sum)/(i+1);

As of here you are dividing the sum to all the i+1 elements ,But you are ignoring the extra decimal value .
for example 1 2 3 gives sum=1+2+3=6,we distribute them as 6/3=2 for each element.
But in 1 2 3 4 gives sum 1+2+3+4=10,we distribute them as 10/4=2 is the wrong assumption.The write one is : 2 2 3 3.
So the final code is:
mid=(sum)/(i+1);
if(sum%(i+1))
mid++;
Hope you understand it .

1 Like

Your formula should be mid=ceil(sum/(i+1)). The counter example and the explanation of using (sum+i) is clearly explained by @gowtham516 . Hope you understood the point.

3 Likes

Thanks man ,it is clear now. but it is giving WA now.
solution link

In line 23 while you are taking mod of sum with (i+1), your condition should be not equal to zero instead of equal to 1. It is because if your mod is greater than zero then surely its ceil will be 1 plus than current value.
Say sum=12 and i=4
then mid=ceil(12/5)=3
But your solution will give 2.

2 Likes

Thanks man

Can you please tell me where am I wrong?

https://www.codechef.com/viewsolution/34559314

@anon97806351 you have to use long long int for the large input values. Updating the int with long long int will correct your code.

2 Likes

Thanks a lot.