Guys, can anyone help me optimize solution of [MATTEG][1], which is getting TLE only in one file, rest all AC.
Link to my
[2].
EDIT:Can anyone tell me the resaon for [this][3] TLE?
[1]: http://codechef.com/problems/MATTEG
[2]: https://www.codechef.com/viewsolution/16621409
[3]: https://www.codechef.com/viewsolution/16655060I have solved same problem few days. TLE is happening because of log factor added as you are using Hashmap. See the editorial of this problem where the it is discussed why TLE happens. To overcome this you need to use hashing or you need to use tester’s approach where he used log_5 mask which is more easy and interesting approach.
@taran_1407 I looked into your code and honestly I’m quite confused now.
At first I thought your input method was too slow, so I just replaced it with my reader class and it was accepted: 16690821
But then I saw that your previous partially correct code uses the same input method but it works just fine for subtask 1!
Do you have any idea what’s going on?
I am already using HashMap, and yes, i have referred the editorial and know how to do this using tester’s idea, but i wanna know how this approach can be optimized…
TLE is occuring because of the fact that you used Hashmap and every time you search for last result it occurs in log factor time. You can use array so access occurs in O(1) time but it will exceed space limit because of the constraints so you need to do “Hashing” so that access of previous results occur in O(1) time, and solve collisions using Linear probing or any other technique.
HashMap internally use hashing and give amorrized O(1) time complexity, not O(logN).
Though i guess i have to implement a hash myself this tym…
Didn’t knew about this thing of Hashmap,I use maps in C++ which takes log factor time.
HashMap in java is same as C++ unordered map, which use hashing and gives amortized time complexity O(1).
The simple map u are using presently, is ordered map in c++ and TreeMap in java, which use tree internally and give O(logN) time complexity.
Hashmap give amortised cost of O(1) but it is not guaranteed always. Rehashing occurs when size of Hahsmap exceeds cetain limit, like in vectors size of internally doubles (known as capacity of vector) when half of the vector is filled. This rehahsing is O(N) and if it occurs many times, this increases the complexity of your code. Hence, TLE. You can avoid this with only your own written hash table. (Brief part of this was also added in the editorial).
Thanks for your reply @likecs.
I know Hashmap rehash every time it reavh a certain size of capacity (0.75 default for Hashmap java) and its an O(N), but i haven’t ever implemented a custom hash table (not counting once when my hash table gave worse time complexity than a treemap).
Would be glad if u could help me with implementing a custom has table. I tried reading CLRS, but i guess ot was too complicated for me…
@taran_1407, I recommend you to go through the author’s solution for that problem. His implementation is very clear and neat according to me.
Yeah…
I would go through setters solution.
PS: I tried testers approach. I have understood the approach and underlying idea, but my solution is gjving TLE for subtask 1 while AC in all other subtask, except WA in 1 file.
Here’s that submission CodeChef: Practical coding for everyone
Not sure about the TLE, but pretty sure the WA is because you forgot to initialize ans to dp[0].
I have a guess.
Maybe the formatting of test case of that particular input is different which my IO class ignore and get TLE, because of expecting further input.
Only a guess, because we can’t see test cases. 
(Though don’t even want to, usually).
Time to change input class. 
You can do that, but that is not at the heart of the issue. See these 2 solutions: 16693704 and 16693711. The only difference is that in the first one the inner loop has 2 iterations and in the second one it has 3. The first takes 0.23 sec and the second takes more than 2 secs!
I really want to know the reason for this strange behaviour (⊙.☉)
I too want to know such behavior reason.
PS: Sorry for late reply, was inactive.