Блог пользователя Ryuma_7810

Автор Ryuma_7810, история, 4 недели назад, По-английски

Problem: https://mirror.codeforces.com/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.

Теги c++
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 недели назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

no