[CSES][Sorting and Searching] Sum of Three Values

[kaihong]

Brilliant!! I hope I can be as wise as you!!

[Gurrari]

Broo... you've made the solutions of the most standard where many might face conceptual error and Most Important problems of CSES...thanks Alot :)

[ishmam]

Thanks a lot, bro, really great explanation as always

[navitabatra]

can we use binary search for finding 3rd value, o(n^2 log n) soln? and great idea.

[sdmfslkdm]

can't we do something like use two nested loop for two values, and for 3rd value we use binary search ? will that work .
I tried it but i am struggling to use binary search, when mid can be one of the nos already taken ? simply adding the if statement is not working for all cases !
I think simple if condition won't work, i should use set and delete the two previously taken element and then apply binary Search ?

[ariyudopertama]

O(n²) using two loops and hashmap gives TLE :(

[adelina__]

teacher i wrote it but it didnt help. can you help pls
#include <bits/stdc++.h>
using namespace std;
#define ln '\n';
typedef long long ll;
int main()
{
int n, x;
cin>>n>>x;
vector<pair<ll, int>>a(n);
for(int i=0;i<n;i++){
cin>>a[i].first;
a[i].second=i+1;
}
sort(a.begin(), a.end());
for(int i=0;i<n;i++)
{
ll x2= x- a[i].first;
for(int j=i+1, k=n-1;j<k;j++)
{
while(a[j].first + a[k].first>x2)
k--;
if(j<k && a[j].first+a[k].first==x2)
{
cout<<a[i].second<<" "<<a[j].second<<" "<<a[k].second;
return 0;
}
}
}
cout<<"IMPOSSIBLE"<<endl;
}

[siddharthgahalot]

O(n^2) using two and hashmap tle ?


#include <iostream>
#include <bits/stdc++.h>
#include <numeric>
#define lli long long int
#define lld long long double
#define FOR(i, n, a) for(int i=0;i<n;i=i+a)
#define all(x) x.begin(), x.end()
#define pb push_back()
using namespace std;

void solve() {
lli n;cin>>n;
lli sum;cin>>sum;

unordered_map<lli, lli>mp;

vector<lli>vec(n);

for(int i=0;i<n;i++)
{
cin>>vec[i];
mp[vec[i]]=i+1;
}

for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
lli f=sum-(vec[i]+vec[j]);
if(mp.find(f)!=mp.end())
{

&& mp[f]!=(j+1))

"<<j+1<<" "<<mp[f]<<endl;
;

}
}
}

cout<<"IMPOSSIBLE"<<endl;
return ;



}

int main() {

solve();
}