➤ Problem Link : 607A. Chain Reaction
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; #define ll long long int ll bin_search(ll i,pair<ll,ll> arr[]) { ll low=0,high=i-1,mid; ll val=arr[i].second; while(low<high) { mid=low+(high-low+1)/2; if(arr[mid].first < arr[i].first - arr[i].second) low=mid; else high=mid-1; } return high; } int main() { ll n,ind; cin>>n; pair<ll,ll> arr[n+1]; for(int i=1;i<=n;i++) cin>>arr[i].first>>arr[i].second; arr[0]=make_pair(-1,-1); sort(arr,arr+n+1); ll dp[n+1]; ll ans; dp[0]=0; dp[1]=0; ans=n-1; for(ll i=2;i<=n;i++) { ind = bin_search(i,arr); dp[i]=i-ind-1 + dp[ind]; ans=min(ans,dp[i]+(n-i)); } cout<<ans; }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
➤ Problem Link : 607A. Chain Reaction
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; #define ll long long int ll bin_search(ll i,pair<ll,ll> arr[]) { ll low=0,high=i-1,mid; ll val=arr[i].second; while(low<high) { mid=low+(high-low+1)/2; if(arr[mid].first < arr[i].first - arr[i].second) low=mid; else high=mid-1; } return high; } int main() { ll n,ind; cin>>n; pair<ll,ll> arr[n+1]; for(int i=1;i<=n;i++) cin>>arr[i].first>>arr[i].second; arr[0]=make_pair(-1,-1); sort(arr,arr+n+1); ll dp[n+1]; ll ans; dp[0]=0; dp[1]=0; ans=n-1; for(ll i=2;i<=n;i++) { ind = bin_search(i,arr); dp[i]=i-ind-1 + dp[ind]; ans=min(ans,dp[i]+(n-i)); } cout<<ans; }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!