Optimise solution for MATTEG

help
, ,
1

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/16655060
1 Like
2

I 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.

2 Likes
3

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ā€¦

4

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.

5

HashMap internally use hashing and give amorrized O(1) time complexity, not O(logN).

1 Like
6

Though i guess i have to implement a hash myself this tymā€¦

7

Didnā€™t knew about this thing of Hashmap,I use maps in C++ which takes log factor time.

8

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.

9

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

3 Likes
10

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ā€¦

11

@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.

12

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 https://www.codechef.com/viewsolution/16635385

13

Not sure about the TLE, but pretty sure the WA is because you forgot to initialize ans to dp[0].

14

Thanks @meooow. Silly mistake on my part.

Can anyone tell reason of that TLE???

15

@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?

1 Like
16

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. :frowning: (Though donā€™t even want to, usually).

17

Time to change input class. :smiley:

18

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 (āŠ™.ā˜‰)

19

I too want to know such behavior reason.

PS: Sorry for late reply, was inactive.