×

TLE in CHEFSUBA

 0 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 2★sm1dash 10●2 accept rate: 0% 15.5k●1●20●66 Link to the problem statement- https://www.codechef.com/problems/CHEFSUBA/ (26 May '17, 12:33)

 1 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 ) 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 768●1●8 accept rate: 23%
 0 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 256●7 accept rate: 8%
 0 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 answered 26 May '17, 14:50 2★ST7 1 accept rate: 0%
 0 @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); }  answered 26 May '17, 16:14 768●1●8 accept rate: 23%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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