Need a Better Method or a Direct Algo

general
, , ,
1

This is a ques from yesterday’s ICPC Amritapuri OnLine Round(Contest is over…:P)…LINK…seeing the constraints i tried a n^6 soln and it got AC…but if ne1 has a better method with lesser time complexity or a direct algo then pls do comment…MY_CODE…thanks in advance…:slight_smile:

2

I am pretty sure the algorithm cannot be optimized further than O(n^6) for this problem. Our O(n^8) algorithm got an AC! :smiley:

3

lol…gimme ur code na…wanna see what u did…:stuck_out_tongue:

4

some1 has written editorials…http://machlearner.blogspot.in/2013/10/icpc-amritapuri-online-contest-2013.html . It also uses a n^6 algo(i.e. (n*m)^3)…hehe…:stuck_out_tongue:

1 Like
5

@kunal361 My team mate had coded that one so i dont have the code.It was basically just 8 for loops one inside another!! Really surprised it got AC. and thanks for the editorial links.

1 Like
6

You can do it with a matrix hashing algorithm running in O(n^4 log n), it’s quite simple too. I’m also quite sure this can be improved further to O(n^3 log^2 n) by using binary searches. If anyone wants me to elaborate please reply!

1 Like
7

Could you elaborate a bit more. Do you mean we hash the entire matrix and then search for it?

8

Have you heard of the Rabin-Karp algorithm?
We can use the so called polynomial hash function:
Let S be a string S[0],S[1],…,S[N-1], where N is the length of the string. We can interpret every letter in our string as a number, for example, ‘a’ = 1 …
let H(S) = ( S[0]*p^0 + S[1]*p^1 + S[2]*p^2 + … + S[N-1]*p^N-1 ) mod Q
where p,Q are positive integers.
What’s so great about this function is that we can quickly compute H(T), where T is a substring of S, provided that we already computed H§ for each prefix P of S. You can try to see for yourself how this can be done.

9

By using this hashing algorithm, we can solve the one-dimensional version of stated problem easily in time O(n^2 log n): for every possible length L<=N, we compute the hash values of all substrings of length L, sort them and look for matches. We can generalise this hashing algorithm to work on matrices of letters, instead of strings. Since there are O(n^2) possible submatrix sizes and it takes us O(n^2 log n) to look for matches in one such size, the overall complexity is O(n^4 log n)

10

We can further optimize this approach starting form the one-dimensional version: Note that if no two substrings of length L match, there cannot possibly be a match between any two substrings of length greater than L - meaning that we can do a binary search for L - reducing the complexity to O(n log^2 n). Similarly, we can reduce the complexity for the two-dimensional case to O(n^3 log^2 n) - for a fixed submatrix width, we do a binary search for the submatrix height.