HACKWITHINFY ROUND 1 QUESTION

general
1

You are given an array of N Integers. You are also given two integers A ad and B (A>B).

In one operation you can select any element from the array and subtract A from it and the rest of the elements will be subtracted by B.

Your task is to find the minimum number of such operations to make all the elements non-positive.

CONSTRAINTS:
1 <=N <= 10^5
1 <= arr[i] <= 10^9
2 <= A <= 10^5
2 <= B <= 10^5

INPUT
n=> 4
arr=> 4 5 8 10
a, b=> 5 3

OUTPUT
3

INPUT
n=> 2
arr=> 20 20
a, b=> 10 4

OUTPUT
4

Can anyone explain how to solve this question.

INPUT
n=> 4
arr=> 1000000000 1000000000 1000000000 1000000000 1000000000
a, b=> 3 2

OUTPUT
454545455

1 Like
2

wil greedy approch work

3

As A>B, Find the maximum element of the array and subtract A from that and subtract B from rest of the elements, continue this process until all elements become non positive.

4

It will be better if u could tell the constraints as well.

6

constraints are high

CONSTRAINTS:
1 <=N <= 10^5
1 <= arr[i] <= 10^9
2 <= A <= 10^5
2 <= B <= 10^5

1 Like
7

CONSTRAINTS:
1 <=N <= 10^5
1 <= arr[i] <= 10^9
2 <= A <= 10^5
2 <= B <= 10^5

8

void test(){
//cout<<“Hello World”<<"\n";
int n,a,b;
cin>>n>>a>>b;
int r[n];
for(int i=0;i<n;i++)
cin>>r[i];
sort(r,r+n);// sort the array
int op1=0,op2=0;
while(r[n-1]>=0){
r[n-1]-=a;
op1++;
}
r[n-2]=r[n-2]-(op1*b);
while(r[n-2]>=0)
{
r[n-2]-=a;
op2++;
}
cout<<op1+op2<<’\n’;

}

9

yeah that is giving me wrong answer
my output is 444444445

10

did u try the last test case given by the author for ur code??

11

yeah that is giving me wrong answer
my output is 444444445

12
Code 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin>>n;
  vector<ll> v(n);
  for(auto&u:v) cin>>u;
  ll a,b;
  cin>>a>>b;
  priority_queue<ll> pq;
  for(auto&u:v) pq.push(u);
  ll cnt=0;
  while(true)
  {
    ll f=0;
    priority_queue<ll> q;
    ll t=pq.top();
    pq.pop();
    t-=a; 
    if(t<0) f++;
    while(!pq.empty())
    {
      ll k=pq.top();
      pq.pop();
      k-=b;
      if(k<0) f++;
      q.push(k);
    }
    q.push(t);
    pq=q;
    cnt++;
    if(f==n) break;
  }
  cout<<cnt<<endl;
  return 0;```

I have come with this code up but this will work only for small constraints. Most probably will TLE for very high differences in value of A,B and the elements. If I am able to find a better solution will surely post here.

13

can u tell ur approach

14

yeah so the thing why they have given A>B is to justify the fact that the number that needs to be subtracted by A must the greatest number out of the all present elements in the array. The rest will be subtracted by B.

15

Btw check the last test case. For n=4 u have given 5 (1e9) and also check whether output u have mentioned is correct or not.

16

I have a solution that should work in O(N.log^2a[i]_{max})

Code 
import java.io.*;
class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int n=Integer.parseInt(bu.readLine());
        String s[]=bu.readLine().split(" ");
        int i,c[]=new int[n],l=1,r=1,mid,ans;
        for(i=0;i<n;i++)
        {
            c[i]=Integer.parseInt(s[i]);
            r=Math.max(r,c[i]);
        }
        s=bu.readLine().split(" ");
        int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]);

        ans=r;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(possible(c,mid,a,b))
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        System.out.println(ans);
    }

    static boolean possible(int c[],int k,int a,int b)
    {
        int rem=k,i,n=c.length;
        for(i=0;i<n;i++)
        {
            long v=1l*rem*a+1l*(k-rem)*b;
            if(v<c[i]) return false;
            int l=0,r=rem,mid,ans=r;
            while(l<=r)
            {
                mid=(l+r)>>1;
                v=1l*mid*a+1l*(k-mid)*b;
                if(v>=c[i])
                {
                    ans=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            rem-=ans;
        }
        return true;
    }
}

So what I have done here is binary searched the answer, and for any value k, checked if it is possible to make the non positive using x a’s and k-x b’s. Ultimately, what we need is to optimally divide the a’s, so this is what I tried to do.

We need the smallest number of moves for which we can make the entire array non positive
Now suppose we have m moves. This means that \sum_{i=1}^{n}x_i \leq m where x_i is the number of times we are removing a from any index. Now, for any index, we have to find the minimum value of x_i, which can be found by binary search too. If the minimum index is greater than remaining moves(rem), the answer m is not possible, otherwise, we make rem=rem-x_i
Now for this binary search of x_i, suppose we select a number k, which means we are removing a from array element k times. Therefore the total value removed will be a.k+(m-k).b. If this is \geq array element, then k is a valid choice, otherwise its not.

It passes the cases given in the blog(for the last case N=5), but there may be cases where it fails. If anyone can provide such corner cases, or a link where I can submit the code, I would be grateful.

3 Likes
17

Can u explain ur code in a bit more in detail about ur code??
This code will surely pass all test cases.
Someone else also suggested for binary search but I couldn’t get the idea as to how to approach it.

18

done, edited the comment!

1 Like
19

Wow great approach there.
I know it’s most probably not feasible but is it possible to solve the question by simulating it??
Like I initially tried using priority_queue and that won’t work for bigger test cases like the last one.

20

It was a proctored contest and its over so we cannot submit and test the code.

21

I was asked this problem to which I was able to write n3 dp solution but not n2.

Given a number line from 1 to n, you start from pos x and a jump strength of atmost z and can jump exactly k times. Find the number of distinct paths that can be made.

example: n = 5, z = 1, k = 3, x = 2
paths could be 2 → 1 → 2, 2 → 3 → 2, 2 → 3 → 4. So output is 3. you can have path like 2 → 2 → 2 or 2 → 1 → 1

Can someone help me with a n2 approach