atlasworld's blog

By atlasworld, history, 2 months 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

»
2 months 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.

  • »
    »
    2 months 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.

»
2 months 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()).

  • »
    »
    2 months 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.

»
2 months 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!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, BS can also solve this problem along with priority queue. Thanks !

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

This will work.

int Solution::solve(vector<int> &a, int b)
{
    int n=a.size();
    //min heap
    priority_queue< pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > q;
 
   for(int i=0;i<n;i++)
   {
       pair<int,int> p = make_pair (2*a[i] , i);    
       q.push(p);
   }
 
   int ans=INT_MIN;
 
   vector < int > curr=a;
 
    while(b--)
    {
        pair<int,int> 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<curr.size();i++)  ans=max(ans,curr[i]);
 
    return ans;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.