Ryuma_7810's blog

Can you optimse my code for the given problem even further ?
By Ryuma_7810, history, 7 months ago, In English

Problem: https://codeforces.net/contest/1937/problem/B (Binary path)

int n;  cin>>n;
string s,t; cin>>s>>t;

int count=1;
string path= s[0] + t;
string min_str= path;

for(int i=1; i<n; i++)
{
    path[i]= s[i];

    if(path < min_str){
        count=1;
        min_str= path;
    }
    else if(path == min_str)
            count++;

}

cout<<min_str<<endl;
cout<<count<<endl;

I have written this coder sample for the above problem, but it keeps on getting TLE on Test 4. I can't seem to understand it because the time complexity for this is O(n) and n<=2.10^5 Can you explain in which part of my code is there an issue ? I want to use this current approach.

Tags c++
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

String comparison has O(n) complexity, therefore your solution has O($$$n^2$$$) complexity, not O(n).

If you really want to keep the current approach, then make an observation about the condition when one string is smaller than other, and use hashing for the comparison of their equality, but I recommend thinking about something else.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

no

→ Reply