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

×

TLE in CHEFSUBA

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

asked 26 May '17, 12:26

sm1dash's gravatar image

2★sm1dash
102
accept rate: 0%

converted to question 26 May '17, 12:32

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

Link to the problem statement-

https://www.codechef.com/problems/CHEFSUBA/

(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])
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.

link

answered 26 May '17, 14:00

divyansh_gaba7's gravatar image

4★divyansh_gaba7
76818
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.

link

answered 26 May '17, 13:10

vishesh_345's gravatar image

1★vishesh_345
2567
accept rate: 8%

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

link

answered 26 May '17, 14:50

ST7's gravatar image

2★ST7
1
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);
            }
            System.out.println(res);
            }
link

answered 26 May '17, 16:14

divyansh_gaba7's gravatar image

4★divyansh_gaba7
76818
accept rate: 23%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×16

question asked: 26 May '17, 12:26

question was seen: 421 times

last updated: 26 May '17, 16:14