Codeforced Round #624 (Div. 3) Problem C O(n) solution TLEs

Problem Link :- https://codeforces.com/contest/1311/problem/C
Submission Link :- https://codeforces.com/contest/1311/submission/71801841

This is my code. It runs in O(n) but still gets TLE (it shouldn’t). So if anyone can check why my code TLEs that would be great.

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	//cout.tie(NULL);
	int t;
	int siz = (2 * 1e5) + 20;
	cin >> t;
	while (t--)
	{
		int n, m;

		cin >> n >> m;
		//scanf("%d %d", &n, &m);
		vector<int> k(siz, 0);
		string s;
		cin >> s;
		//scanf("%s", &s);
		for (int i = 0; i < m; i++)
		{
			int x;
			cin >> x;
			//scanf("%d", &x);
			k[x]++;
		}

		vector<long long int> h(26, 0);
		//vector<int> p(n, 0);

		long long int count = 1;

		for (int i = n - 1; i >= 0; i--)
		{
			//p[i] += count;
			h[s[i] - 97] += count;
			count += k[i];
		}

		for (int i = 0; i < 26; i++)
		{
			cout << h[i] << " ";
			//printf("%d ", h[i]);
		}
		cout << endl;
	}
}

I stored the values of p in a map and ran a loop starting from the end of the string.
Then i increased the value of occurrence of that character by count. Then i incremented the value of count by the value of k[i] where k is the map which stores the amount of times the letters before index i are typed.

You are declaring vector of 210^5 and initializing it to 0 for each test case which will make it’s to complexity (210^5)*(10^4) .

You just need to create vector of size n.

4 Likes

In the constraints it is mentioned that sum of n overall testcases will not exceed 2*10^5.

Thanks!

I made the exact same mistake of declaring a vector with size 210^5.
@gourav_987 could you please elaborate how the time complexity becomes (2
10^5)*10^4 :slightly_smiling_face:

I think, Initializing vector with 0 value will take O(n) time complexity.

Shouldn’t be getting TLE for O(n) complexity then, should we?:neutral_face:

Read the output line carefully sum of all test cases doesn’t exceed 2 * 10^5.
If you keep creating an array of size 2 * 10^5 repeatedly
And since number of test cases are 10^4 it will TLE.
If you want to work globally simply declare resize array to n only not siz

Complexity for initializing is O(n) and in your case n=210^5 for each test case which will become O(nt).

n=2*10^5
t=10^4.