Can someone tell me why i am getting WA in this solution …I am getting correct answer when i do it in local editor…But getting WA when submitting here … I am new to programming so Plz help!
Link to the solution - CodeChef: Practical coding for everyone
You have used S.count() which takes another O(N) for every query. Try using frequency array(pre-computed count for every char) as mentioned in the editorial
@nisarg_140600. You are changing modifying the value of string s1 on every query and therefore your code fails. Try for
I/p:
1
4 2
aaab
0
1
Your o/p:
0
0
Expected o/p:
0
2
Also, your code is not optimized which will cause TLE for subtask 2.
@sahi1422 I am new to programming and I did not know about O(N) and frequency array till now(I googled it) but are there any resources which I can use to learn more about execution time and optimizing my code (any specific keyword I should use to search on Google)
Thank you so much for your reply but can u please little more explain regarding the part “modifying the value of string s1 on every query and therefore your code fails.” … that would be great
i get tle in last case but my approach is o(n) (correct me if I am wrong)
#include
using namespace std;
int main() {
// your code goes here
int t;
cin >> t;
while(t–)
{
int n,q;
cin >> n;
cin >> q;
string s;
cin >> s;
for(int j=0;j<q;j++)
{
int c;
cin >> c;
int a[26];
int i;
for(i=0;i<26;i++)
{
a[i]=0;
}
for(i=0;i<n;i++) // storing frequency of each character
{
int k=s[i]-97;
a[k]++;
}
int sum=0;
for(i=0;i<26;i++)
{
int r=a[i]-c;
if(r<0)
r=0;
sum=sum+r;
}
cout << sum << endl;
}
}
return 0;
}
link to my solution.
https://www.codechef.com/viewsolution/32882502
https://www.codechef.com/viewsolution/32623598
Can someone Please help to figure out why i am getting tle in #6 case.
Thank You.
can someone help me with this. what’s wrong in my code?
you are calculating frequency of letters every time you answer query in line 22-30.calculate frequency of letter only one time because string will not change.So there is no point in calculating frequency of same string Q times.
1 Like
Do not store frequency of each character every time you answer Query.you are calculating frequency of character of same string Q times. Calculate the frequency of character outside the loop .
1 Like
@tushar_wiz you will always see a constraint section in the problem statement which is used to figure out the time complexity of the solution. You can google for “Time Complexity of Algorithms”
1 Like
You are changing the value of given string S for every query. Only the no. of isolation centers change for every query and not the string S. Try debugging the sample input I gave u
Thank you so much for your reply!
stored string in a variable got frequency of each character stored in a string like- if string is aaaddbbc then first i sorted it alphabetically then my frequency string was 1223 then as per the query i used a loop 0 to c to decrease this string by 1111 then by 111 and so on until it either become 0 or loop ended then converted it to int and summed its digit to get the answer.
if u see u have declared globally map u have to keep clear the map freq after every test case or u can declare map in while (t–) loop
i have executed your code this is the output of your code
yes , got that