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

| Write comment?
 » 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 Y`s 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!