You are not logged in. Please login at to post your questions!



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?

asked 26 May '17, 12:26

sm1dash's gravatar image

accept rate: 0%

converted to question 26 May '17, 12:32

vijju123's gravatar image

5★vijju123 ♦♦

Link to the problem statement-

(26 May '17, 12:33) vijju123 ♦♦5★

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])
while m <= n:
    oc=max(oc, sum(d[j][l:m]))
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 : or watch this awesome video : )

My code:

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.


answered 26 May '17, 14:00

divyansh_gaba7's gravatar image

accept rate: 23%

edited 26 May '17, 14:40

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.


answered 26 May '17, 13:10

vishesh_345's gravatar image

accept rate: 8%

Can anyone suggest me problem in this solution I am not able to post question I am using hashmap to make it work in O(n) Any suggestion


answered 26 May '17, 14:50

ST7's gravatar image

accept rate: 0%

edited 26 May '17, 14:51

@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 :(

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);

answered 26 May '17, 16:14

divyansh_gaba7's gravatar image

accept rate: 23%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 26 May '17, 12:26

question was seen: 421 times

last updated: 26 May '17, 16:14