# HACKWITHINFY ROUND 1 QUESTION

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

wil greedy approch work

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.

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

constraints are high

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

1 Like

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

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’;

}

yeah that is giving me wrong answer
my output is 444444445

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

yeah that is giving me wrong answer
my output is 444444445

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.

can u tell ur approach

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.

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.

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
{
StringBuilder sb=new StringBuilder();
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]);
}
int a=Integer.parseInt(s),b=Integer.parseInt(s);

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

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.

done, edited the comment!

1 Like

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.

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

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