say_yas's blog

Codeforces Round #481 (Div. 3) C. Letters (Unable to get around tle)
By say_yas, history, 4 years 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

Comments Comments (1)
| Write comment?
»
4 years 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.

→ Reply