I have written my solution to this problem in JAVA and I am getting a TLE error in the second sub-task. I know my code is not the most efficient nor the most optimised way to do so. I have tried understanding the concept by looking at other people’s code but couldn’t decipher it. Can someone explain to me how it is done. I am new in competitive coding and not very well versed with binary search.
Code in Java -
//written by Lord_of_Codes
import java.util.*;
class ZCO13003
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
long sum =0;
for(int i=0; i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
long d=a[i]+a[j];
if(d<k)
{
sum++;
}
}
}
System.out.println(sum);
}
}
What you have done is called a brute force approach -
To solve this problem you need to know binary search which you said are not well versed with.
I recommend you to watch some videos of it on youtube and also I am providing some links -
I tried to solve it using Fenwick Tree.
for every element in the hardness array i am counting how many are less than the current element.
but i am getting WA for few TC. can someone pls tell me the flaw in the logic?
ll int n,k;
long long int bit[1000000+7];
long long bit_q(ll int bt[], ll int j)
{
long long sum=0ll; //its 0LL
while(j>0){
sum+=bt[j];
j -= (j & (j*-1)); //parent finding
}
return sum;
}
void bit_up(ll int bt[], ll int n, int i,ll int diff) // bit update
{
while(i<=n){
bt[i] += diff;
i += (i & (i*-1)); //next index in BITree
}
}
int main() {
int t=1; // readint(t);
while(t--){
cin>>n>>k;
vector<ll int> q;
for(int i=0;i<n;i++){
ll int a;
cin>>a;
if(a<k) q.push_back(a);
}
sort(q.begin(),q.end());
n=q.size();
ll int c = 0;
for(ll int i=0; i<n; i++){
c+= bit_q(bit, k-(q[i]) );
bit_up(bit, n, q[i]+1 ,1);
}
cout<<c;
}
return 0;
}