can anyone help me find the correct approach to solve this problem . I’ve tried using naive approach and also tried using priority queues to get the kth smallest element from the given matrice but both the solutions are fetching me runtime error for few TestCases/partially correct because of big constraints.
Do share your approach . Thankyou in adv
I don’t have a clever solution for matrix problem but you can always binary search the answer though.
#include "bits/stdc++.h"
using namespace std ;
#define int long long
signed main(){
int n,k ;
cin >> n >> k ;--k;
auto ok = [&](int x)->int{
int c=0 ;
for(int i=1;i<=n;i++)
c+=min(x/i,n) ;
return c<=k ;
} ;
int lb = 1,rb=n*n ;
while(lb<rb){
int mb=(lb+rb)/2 ;
if(ok(mb))
lb =mb+1 ;
else
rb=mb ;
}
cout << lb ;
}
I’ve discussed my solution in this thread, feel free to ping me if you don’t get it.
2 Likes
Thankyou so much senior .
but i’m afraid i am not able to understand this part of code .
auto ok = [&](int x)->int{
int c=0 ;
for(int i=1;i<=n;i++)
c+=min(x/i,n) ;
return c<=k ;
} ;
Are you familiar with lambda functions? or you didn’t get the logic itself ?
3 Likes
#include "bits/stdc++.h"
using namespace std ;
#define int long long
bool ok(int x , int n){
int c=0 ;
for(int i=1;i<=n;i++)
c+=min(x/i,n) ;
return (c<=k);
}
signed main(){
int n,k ;
cin >> n >> k ;--k;
int lb = 1,rb=n*n ;
while(lb<rb){
int mb=(lb+rb)/2 ;
if(ok(mb,n))
lb =mb+1 ;
else
rb=mb ;
}
cout << lb ;
}
If u don’t know lambda function then : " Lambda expression in C++ - GeeksforGeeks "
2 Likes
i didn’t get the logic behind choosing the minimum between (x/i, n) and adding up them to compare with k.
See you if I give you a number x then you can check whether it’s the kth number or not by counting the total number of elements which are less than x but are present in the matrix. You can do so by going to each ith row and adding \displaystyle\frac{x}{i} as it’s contribution. And rest is trivial binary search.
Alright if you observe the matrix for any N it’d look like.
1 \ 2 \ 3 \ 4 \ \ 5 \dots\
2 \ 4 \ 6 \ 8 \ 10 \dots
3 \ 6 \ 9 \ 12 \ 15 \dots
\vdots
It is clearly evident that the ith row contains multiples of i.
Second thing to note is the following question.
How many multiples of i do we have which are less than a given number x.
If you scribble it on paper you can observe that it is exactly \displaystyle\frac{x}{i}. And we can also see it intuitively that why is this the c…
Have you checked these already? if you still don’t get it do let me know
2 Likes
Thankyou @cubefreak777 for this perfect explaination. Now i’ve understood it .
1 Like