### atlasworld's blog

By atlasworld, history, 3 years ago,

Given an array A of N numbers, you have to perform B operations. In each operation, you have to pick any one of the N elements and add original value(value stored at index before we did any operations) to it's current value. You can choose any of the N elements in each operation.

Perform B operations in such a way that the largest element of the modified array(after B operations) is minimised. Return an integer corresponding to the minimum possible largest element after K operations.

Example:

Input : A = [1, 2, 3, 4] B = 3

Output : 4

Explanation : After the 1st operation the array would change to [2, 2, 3, 4] After the 2nd operation the array would change to [3, 2, 3, 4] After the 3rd operation the array would change to [4, 2, 3, 4]

A : [ 8, 6, 4, 2 ] B : 8 The expected returned value : 12

Thanks : the problem is solved, one more way to solve this problem is to use min heap priority queue with the following comparator

struct op
{
bool operator()(const pll &a , const pll &b)
{
return a.fi + a.se > b.fi + b.se; /// greater than bcoz min and max works reverse in comparator, what i observed till now.
}
};


• -2

 » 3 years ago, # |   +1 i think this problem can be solved by using binary search on answer. try to think this way.
•  » » 3 years ago, # ^ |   0 Yes I think binary search should work in the range [orginal_max , original_max*(b+1)]. Now to check whether an answer(call it x) is possible or not, greedily start incrementing the value in increasing order such that it is <=x. If you end up such that operations are remaining and can't increment an element anymore then it's not possible.
 » 3 years ago, # | ← Rev. 2 →   0 I'm not sure about this, but I think it's correct. In each operation, do the operation on the number that will be minimal after it's modified. You can do this using set (for each i from 1 to N, you keep modified_array[i] + original_array[i] in the set) and in each operation you just modify the "best" number (number from set.begin()).
•  » » 3 years ago, # ^ |   0 it may lead to TLE if constraint of B is large and array element is very small.
•  » » » 3 years ago, # ^ |   0 You're right, binary search is a better solution :)
 » 3 years ago, # | ← Rev. 3 →   +1 The ideia I found correct is: Guess the answer to be X. To check if it is possible to find X as a maximum value you have to use at least B operations. The check function is: go from 1 to N and find the Y value that array[i]*Y <= X and Y is the maximum possible number. Then, if the sum of Ys over all the array is greater then or equal to B, X is a possible answer. So, try to decrease the answer. Otherwise, try to increase the answer. To guess the answer, the fastest way is using binary search! Hope it helps you!
•  » » 3 years ago, # ^ |   0 yes, BS can also solve this problem along with priority queue. Thanks !
 » 3 years ago, # | ← Rev. 4 →   0 This will work. `int Solution::solve(vector &a, int b) { int n=a.size(); //min heap priority_queue< pair , vector >, greater > > q; for(int i=0;i p = make_pair (2*a[i] , i); q.push(p); } int ans=INT_MIN; vector < int > curr=a; while(b--) { pair p=q.top(); int i=p.second; curr[i]+=a[i]; q.pop(); p=make_pair(curr[i]+a[i],i); q.push(p); } for(int i=0;i
•  » » 3 years ago, # ^ |   0 I don't want to be mean. But there's a reason why some people remain gray/green/cyan. It is because they dump unreadable code with masqueraded logic (worse still, some post unformatted code). For God's sake, humans are not compilers. Describe key points of your logic and post minimal and clear code samples.
•  » » » 3 years ago, # ^ |   0 chill bro Below is the approach. After reading the approach go through my code, you will get it.Let’s keep a state array to keep track of the value of every element in the array after K operations. Maintain a state array, which tells about the state of the array after every operation. Initially, state array will be the same as the initial array. We need to consider the next state of every element in the array. Consider a min heap. And initially push the next state of every element in the heap. Note that you need to keep track of the indices of every element in the heap, present in the initial array. Pick the top element, and change the state of that element, in the state array. Pop this element and push the next state in the heap. At every operation we are choosing the element whose next state is minimum, hence there are only two possibilities: 1) Either the maximum element remains the same, and we return that element directly. 2) The next state of the popped element is the maximum. We made sure changing the state of this element is the best option, as the next state of this element is the minimum. Hence the maximum will be the least using this approach.