TLE in CHEFSUBA

general
1

my solution to the problem CHEFSUBA why is showing TLE for original constaints whereas its execution time is very less almost 0.01 in the sub tasks.I also read the editorial but can you please help me in improving my approaches?

https://www.codechef.com/viewsolution/13640241

https://www.codechef.com/viewsolution/13788254

2

Link to the problem statement-

3

I guess you are calculating either query ‘?’ or query '!'in O(n) time. Since string length and number of queries are both of order 1e5 you cannot afford an algorithm of O(n2). Either reduce one of them to O(logN) or O(1) :). That you can understand through tutorial, explained clearly.

4

Ok, First lets see why your approach doesn’t work even when 1st subtask gets solved in almost no time!

Calculating Time complexity of your program : (What is time complexity and how to calculate it? why do we need it? read here and here)

Your solution is precomputing the answer in this block

for j in range(n):
d.insert(j, ac[-j:]+ac[:-j])
l=0
oc=0
m=k
while m <= n:
    oc=max(oc, sum(d[j][l:m]))
    l+=1
    m+=1
c.insert(j, oc)

This is of O(n^2) Complexity as we have two nested loops each of which can go upto n.
Also ac[-j:] aka slice operator and sum(d[j][l:m]) aka sum of list is also of O(n) complexity. Source

So, in subtask 1 we range of N in order of 10^3, so O(n^2) is roughly 10^6 operations.

Codechef compilers allow around 1.6 x 10^8 operations per second, we have 0.5 seconds for this problem.
Which means we get around 0.8 x 10^8 operations for test file.

And clearly, 10^6 is very small compared to 10^8, hence so little time in first subtask.

But in second subtask, N is of range 10^6. Which means N^2 = 10^12 operations! thats 10000 times more than we are allowed!

To solve this we would need something which can solve this in O(N logN), log10^6 = 20, so that gives us 20 x10^6 = 2 x 10^7 operations.

To solve this problem, you will need to use Segment trees. ( What are those? read here : http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ or watch this awesome video : https://www.youtube.com/watch?v=ZBHKZF5w4YU )

My code: https://www.codechef.com/viewsolution/13459049

Give this all a thought, if you still don’t get it after 1~2 days, comment below, i (or maybe someone else) will help :).

Happy Coding.

1 Like
5

Can anyone suggest me problem in this solution
https://www.codechef.com/viewsolution/13621651
I am not able to post question
I am using hashmap to make it work in O(n)
Any suggestion

6

@ST7, Although lookups in Hashmaps are O(1) , but you are looking up in-worst case n elements for every query.

that brings your program to O(QN), since Q and N are of both order 10^6, it unfortunately times out as well :frowning:

I am referring to this part of your code :

			for (i = k; i < arr.length; i++) {

				if (hM.get(arr[i - k]) != null) {
					int count = hM.get(arr[i - k]);
					if (count == 0)
						count = 1;
					hM.put(arr[i - k], count - 1);
				}
				if (hM.get(arr[i]) != null) {

					int count = hM.get(arr[i]);
					hM.put(arr[i], count + 1);
				} else {
					hM.put(arr[i], 1);
				}
				if (res < hM.get(1))
					res = hM.get(1);
			}
			System.out.println(res);
			}