How to create time efficient code to avoid TLE?

In december long challenge there were few questions which i did and were partially correct as my code was not time efficient and TLE was executed. i want to know how to write codes to remove TLE and need help. any type of suggestion,advice is welcomed.
i am sharing my code of particular problem it is executing TLE due to 2 for loops inside while loop ,but i only know this .how to improve that i want to know

here is one problem(SUBSPLAY):- https://www.codechef.com/DEC19B/problems/SUBSPLAY

my solution:-


using namespace std;

int main()
{
	int t;
	
	//cout<<"enter total number of test cases ";
	cin>>t;
	
	while(t--)
	{
		int N;
	//	cout<<"enter string length ";
		cin>>N;
		
		string S;
	//	cout<<"enter string ";
		cin>>S;
		
		int i,j,c,K=0,d=0,min,found;
		
		min=N; //storing size of string in min
		
		
		
		
		for(i=0;i<S.length();++i)      //loop from start of string 1st character to end
		{ 
		    c=count(S.begin(),S.end(),S[i]);   //counting number of character similar to S[i]
		    
		    if(c==N)                   //if all charcters of string are same 
		    {
		        min=1;             
		    }
		    
		    if(c>1&&c!=N)              //if character is not unique and all charcters of string are not same
		    {  
		        for(j=i+1;j<N;j++)          //another loop from i+1 to N-1 for finding minimum difference of indices
		        {
		            if(S[i]==S[j])          //checking similar charcters 
		            {
		                d=j-i;              //difference of indices 
		                if(min>d)
		                { min=d;
		                 break;
		                }
		            }
		        }
		       
		            
		             
		             
		      }
		  }
	
	         
		   
	       
		//K will be length of string - minimum difference of indices of similar charcters

		K=N-min;
		
		cout<<K<<endl;
	}
	return 0;
}```

Use time efficient algorithms. Note the constraints of input and accordingly proceed with an appropriate algorithm. It takes practice and analysis.

1 Like

can you suggest somme sources which i can use in order to increase by knowledge about visualising algorithms for given probelm. i knew what to do in question but how to efficiently to i don’t.

I had the very same problem when i first joined codechef. Infact the first question in asked in discussion forums was how to get around TLEs. Noone answered because the simple answer is you don’t. Most of the time if you get TLE means that the approach you used is wrong, or the algorithm you are intended to use is was not used. If you go through the problems in the latest contest you’ll realize that almost all the question are very easy (even the last 2 in div1) if you use brute force, but guess what? You get TLE.
So basically what you do is, look at a problem, come up with a solution and visualize if the solution works before implementing it by carefully looking at the constrains.
heres a list of all cp algorithms : https://cp-algorithms.com/
and all the best :slight_smile:

3 Likes

Check all the constraint of the problem carefully and choose your algorithm accordingly. Let’s take this example problem link and solve it step by step.

Step 1:

Constraint analysis

Most of the problem’s solutions are hidden between constraints.According to all constraints value problem can be solved in O(N). So try to do something in O(N) use pen and paper to simplify the problem.

Step 2:

Reduce the problem to some standard problem by some observations if it possible using pen and paper.

Observation:

  1. When no repeation answer is 0.
  2. Now when repeation occurred string can be represented as follows:
    S=(rightpart)C(middlepart)C(lastpart)
    From here you can choose two subsequence
    A=(rightpart)firstC(lastpart)
    B=(rightpart)secondC(lastpart)
    As here index of C(same character index is different and and A=B)
  3. You have to maximize length of A. How it can be done ? Answer is simple minimise the (middlepart)
  4. " S contains only lowercase English letters"-
    so maximum length of (middlepart) of S can be 25.

Step 3:

After reducing the problem make a rough idea about implementation

Now you have reduced the whole problem to find minimum distance between two same char in O(N).
It can be done using backtracking ,try all possible distance 1 to 26.
Or use the following standard code from GeeksforGeeks after some modifications.

Now write the solution :upside_down_face: and enjoy the green AC.

Final step(write code)

check out this solution backtracking.
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main() {
    fastio;
	int t,n;
	cin>>t;
	while(t--)
	{ 
	    int ans=0;
	    string s;
	    cin>>n;
	    cin>>s;
            /*as all letters are small English alphabet worst case they may have 26 distance between them if repeated else break not possible of repeation */
            /*finding minimum distance between two same character */
	    for(int i=1;i<27;i++)
	    {
	        for(int j=0;j<n-i;j++)
	        {
	            if(s[j]==s[j+i])
	            {
	                ans=n-i;
	                break;
	            }
	        }
	        if(ans)
	        break;
	    }
	    cout<<ans<<"\n";
	}
	return 0;
}
without using nested loop unordered_map concept.
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

//function will return minimum distance between two same char
int calculate(string s,int len)
{
  unordered_map<char,int> lastoccurrence;
  int res=len;
  for(int i=0;i<len;i++)
  {
    if(lastoccurrence[s[i]]==0)
    {
      lastoccurrence[s[i]]=i+1;
      //first time char appear in s storing 1 base indexing
    }
    else //s[i] appears before this index previously
    {
      res=min(res,(i-lastoccurrence[s[i]]+1));
      //update last occurrence of s[i]
      lastoccurrence[s[i]]=i+1;
    }
  }
  return res;
}

int main() {
    fastio;
  int t,n;
  cin>>t;
  while(t--)
  { 
      int ans=0;
      string s;
      cin>>n;
      cin>>s;
      cout<<n-calculate(s,n)<<"\n";
      
   } 
    
} 
3 Likes

You need to use time-efficient algorithms.
For example, In a question you are given a sorted array of length n. Now you need to find 2 numbers whose product is equal to P.

The most common approach to this problem is using a nested for loop, but the constraints won’t allow you to do so. So in that case, you use two pointers. Keep a pointer on the extreme left and on the extreme right. If the product of these two numbers is greater than P, decrement the right pointer. If they are equal, you have your answer, else increment the left pointer.

Going on complexity analysis, the first solution would have taken O(n * n) time, which is bad. While, the second solution takes O(n) time.

NOTE: This is just a random question which came to my mind(kinda same like TwoSums) .

2 Likes

thank you so much bro…

it was very helpful bro ,I am lacking that ability to reduce problems to a particular algorithm .I want to develop that ability any useful and better way you can suggest please?

got your point bro ,chossing a write algorithm is my problem. i will learn more about them ,any source you can suggest for that?

Don’t get demotivated. In the initial stage everyone faces problem to figure out the problems. Use Codechef practice problem, GeeksforGeeks, leetcode problems and at first try to solve them if not able to solve don’t get demotivated. Most important thing read the editorials of that problem .There you will get the idea what they have done and where you need to improve. You will eventually learn to solve a problem efficiently. Keep practicing and keep learning. @pkpawan123

3 Likes

To avoid TLE, you need to do:

  1. Choose time efficient algorithm
  2. Code optimization

tl;dr

Tips to do so :

1. Proper Algorithm

To design a perfect algorithm, you need to learn some algorithm techniques, such as searching, sorting, hashing etc. You can use std::sort() but you should know how merge sort works, how divide and conquer works, recursive techniques, hashing etc.

After choosing an algorithm, you need to implement it using proper data structure. For that you need to learn some DS and their time complexity for different operation.
Their time complexity helps you to select proper DS by analyzing your algorithm needs (I mean which operation your algorithm need, and which DS process that operation efficiently). Some easy and useful DS are bitset, stack, queue, deque, priority_queue, set, map, unordered_set, unordered_map etc.

Practice makes a man perfect

2. Code Optimization

You should write optimized code, Some optimization example:

  1. Use ios_base::sync_with_stdio(false); cin.tie(0); if you want to use cin, cout. otherwise use scanf, printf.
  2. Avoid endl, instead use "\n" .
  3. Use register for loop veriable, for(register int i = 0, i<n, i++)
    Here is my register using experience
  4. Use custom hash function for unordered_map… AND SO ON…

Here is a pdf describing Tips for Optimizing C/C++ Code

2 Likes

You shouldn’t use nested loop. If you know, how to count frequencies of an array elements, then that techniques can be used… Here is my approach:

  int n, ans = 1e9;
  string s;
  cin >> n >> s;
  int a[27];
  memset(a, -1, sizeof a);
  for (register int i = 0, d; i < n; i++) {
    d = s[i] - 'a';
    if (a[d] != -1) ans = min(ans, (i - a[d]));
    a[d] = i;
  }
  cout << (ans == 1e9 ? 0 : n - ans) << "\n";
1 Like

i have heardabout frequency array by many guys but i don’t know much about it ,i will learn as soon as possible,thank you bro

ok bro. i use to solve practise problems but never watched editorials ,that i will be doing from now onwards

But yes, solve the problem for 4-5 hrs first and then look at the editorial. That is the process of learning.

2 Likes

I faced the same problem like you in start before December contest but later I understood how to do it>>
Whenever there is subtasks in question or time limit is less(close 1 seconds) >>gives you a hint that you have to write an optimised code)
STEP 1>In these questions do not write nested loops ex>>
for(i=0;i<n-1;i++){
for(j=i+1;j<n;j++){
but you can use one loop i,many times ;
STEP 2>Try to get a formula or search for a pattern (fit that formula or pattern in one loop i (only one loop ) and get answer or use different algorithm
watch editorials
STEP 3>If you cannot think see others solution .

STEP 4>Now to make you understand see two codes from same question
i GOT 30 points TLE>>https://www.codechef.com/viewsolution/28058640
Then I changed the code 100 points no TLE>>https://www.codechef.com/viewsolution/28271772

5>solve>> Smart Phone, Variation,Tournament from ZCO Practice Contest(or questions from decreasing order of submission easy to tough in ZCO pr contest) to develop understanding.
6>done now solve the December contest problem you were not able to solve .
7>You will see the difference .

1 Like