SBSTR - Editorial

general
, , , ,
2

In this problem some solution with complexity O(nn26) also passed.
link CodeChef: Practical coding for everyone and this CodeChef: Practical coding for everyone.

3

Why is this code leading to tle…(my code is easy to be read)… https://ideone.com/e.js/DugpK4

4

@vijju123 can you please tell why my O(N^2) getting TLE?
See this : CodeChef: Practical coding for everyone

5

Any Python Solution for 100 Points , i apply above both method but no one gives 100 Points .
@vijju123 .

6

Time limit is very strict. Dont know this solution is giving TLE

7

CHEF VIJJU’S CORNER:-

ans:-2 There are O(n^2) substrings in a string and we have to check every substring. So I think we cannot do better than O(n^2)

ans:-3 A computer does 10^8 computation/second on an average. So 2*10^4 is seems to good estimation,
Because of n^2=10^8 ==> n=10^4

@vijju123 am I right?

1 Like
8

Any cues on optimising it further in Python?
It would be of great help if someone could share their working code in Python.

Here is my implementation (Stuck at 40 points!) –
https://www.codechef.com/viewsolution/18676662

9

Can you tell where my code is going wrong? Code- CodeChef: Practical coding for everyone

10

For those asking, I solved this with Python (PYPY) for 100 points: CodeChef: Practical coding for everyone

Code could have been much more elegant (& more optimised) but a contest is always speed-coding.

11

Yes, I know. I described it in editorial, however, some other implementations (which used more expensive computations, or didnt optimize) failed as well.

1 Like
12

@vijju123 can u provide quick brief explanation for this:- SPOJ.com - Problem MMASS

plzz

13

Well that should not have happened. Why there is always some problem in codechef contest with weak test cases?

14

I wil @code_man , but first check the answer by @l_returns on it. I think it satisfies what you want.

@akash_321 - I disagree there. I feel since setter and tester’s solution themselves are O({N}^{2}), they shouldnt have even tried to stop the O(26*{N}^{2}) ones. When 2 solutions are asymtotically similar, then even constant and random optimizations matter.

1 Like
15

Your solution is O({N}^{2} LogN) in my opinion, which is worse than O(26*{N}^{2}). Map data structure has a LogN factor involved.

16

@vijju123 then what is point of n<=7000 why not n<=1000 , just an extra break statement?

17

i used unordered map…so it should be O(1) for insertion in my opinion…and for checking the second condition, I was iterating through this unordered map, which shall be less than 26 for many cases… @vijju123

18

The setter and tester did not intend that either, but they cannot indefinitely raise constraints or reduce TL, else some correct solutions will not pass. Ultimately they decided that, for second easiest problem of ltime, its ok if a few brute forces (optimized ones) pass. The tester himself made us aware by making such a solution. Its not that they were unaware of this, but its just that no correct solution should get TLE

19

link or didnt happen…xD

20

Hmm, true, but only provided that the test cases arent anti hash :stuck_out_tongue: . Still, I read somewhere that the constant for unordered map is a little high. The TL for problem is tight, so try to solve it without unordered map.

21

Ans2 - The reasoning is not correct. I can use the same reasoning to claim that “For sorting the numbers, we know that there are N! permutations. We need to try each and every one of them to see if that permutation is sorted or not. Hence, sorting takes O(N!) time.”

Ans 3- Yes, but 2*{10}^{4} isnt a very good estimate for TL of 1 second, as depending on implementations, it can take 0.4 - 4 seconds.