You are not logged in. Please login at www.codechef.com to post your questions!

×

Need a Better Method or a Direct Algo

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

asked 24 Oct '13, 16:02

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

edited 24 Oct '13, 16:14

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! :D

(24 Oct '13, 16:35) kcahdog3★
1

lol...gimme ur code na..wanna see what u did...:P

(24 Oct '13, 17:13) kunal3614★
1

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...:P

(24 Oct '13, 17:47) kunal3614★
1

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

(24 Oct '13, 18:34) kcahdog3★

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!

link

answered 24 Oct '13, 23:56

ivan100sic's gravatar image

6★ivan100sic
10514
accept rate: 0%

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

(25 Oct '13, 00:13) kcahdog3★

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(P) for each prefix P of S. You can try to see for yourself how this can be done.

(25 Oct '13, 04:48) ivan100sic6★

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)

(25 Oct '13, 04:52) ivan100sic6★

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.

(25 Oct '13, 04:57) ivan100sic6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×1,112
×356
×11
×3

question asked: 24 Oct '13, 16:02

question was seen: 1,448 times

last updated: 25 Oct '13, 04:57