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
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;
}```
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
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:
When no repeation answer is 0.
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)
You have to maximize length of A. How it can be done ? Answer is simple minimise the (middlepart)
" 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.
#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";
}
}
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) .
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?
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
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:
Use ios_base::sync_with_stdio(false); cin.tie(0); if you want to use cin, cout. otherwise use scanf, printf.
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";
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 .
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 .
and enjoy the green AC.