atlasworld's blog

How to solve this problem ? SOLVED()
By atlasworld, history, 6 years ago, In English

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.
    }
};
  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

i think this problem can be solved by using binary search on answer.
try to think this way.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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()).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it may lead to TLE if constraint of B is large and array element is very small.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right, binary search is a better solution :)

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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!

→ Reply