shreyas_24's blog

By shreyas_24, history, 3 weeks ago, In English

Hi, i tried to solved this problem Below is the code.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    int n,k;cin>>n>>k;
    vector<ll> a(n);
    cin>>a[0];
    for(int i=1;i<n;i++){cin>>a[i];a[i]+=a[i-1];}
    for(int i=0;i<k;i++){ll temp;cin>>temp;
        ll j=0;
        while(temp > a[j]){j++;}
        cout<<j+1<<" ";
        j==0?cout<<temp<<endl:cout<<temp-a[j-1]<<endl;
    }
         
} 

But i am getting TLE. I saw a similar approach(link to that solution) that got ac . Can anyone point out the difference between the two solutions. Also I saw the tag of binary search but i'm unable to figure out how to apply binary search on this. Can someone please discuss it.Thanks!!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Both these solutions are O(N^2). I guess that other solution could be optimized more by the compiler, so it ran in time, but still much higher than normal (about 1.5s).

If you inspect your code and see where the bulk of the computing time is going, it's that loop:

while(temp > a[j]){j++;}

You're finding the smallest index j such that it's at least temp. I'll leave you to figure out how you can optimize that part.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi thanks for the hint. I implemented binary search for finding the smallest index and the time reduced from 4000ms to 1500ms and got ac.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The different is your code run in $$$O(N*M)$$$ while AC solution run in $$$O(N+M)$$$. The different is your code find iterator $$$j$$$ every $$$i$$$, while AC solution use iterator $$$j$$$ from $$$i-1$$$ for count iterator $$$j$$$ for $$$i$$$.