TAP2015I - Invading aliens

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

In the novel "A for Andromeda", by Fred Hoyle and John Elliot, a civilization from a planet in orbit around a star in the constellation of Andromeda, 200 light years away from our Solar System, decides to colonize the galaxy. To avoid the long and costly interstellar travels, this civilization decides to perform the colonization at a distance, by sending a signal instead of ships (this signal contains instructions on how to build a supercomputer with an artificial intelligence capable of taking over the world of the unfortunate civilizations who build it, but that is not our problem for the moment).

One of the issues humans have to overcome in order to construct the supercomputer is the decoding of the signal. As it happens, the aliens send two messages in two different frequencies, repeating endlessly in each of them a code with N characters. For example, if N = 3 and one of the codes is "abc", the alien message in the corresponding frequency will be "...cabcabcabcab...", where the ellipsis mean that the code is repeated infinitely both backwards and forwards. For this reason, the terrestrial stations receiving the signal are incapable of telling what the emitted code actually is, as there can be more than one code that is compatible with a given message. In our example, knowing that N = 3 they could interpret that the code is any of three possibilities "abc", "bca" and "cab".

Complicating matters even further, although both messages are composed solely of characters from the alphabet 'a' through 'z', because they are transmitted in different frequencies there exists an ambiguity in the identification of the characters between them. Thus, if we let the characters be named c1 = 'a', c2 = 'b', and so on until c26 = 'z', it is possible that every occurrence of the character ci in one of the messages is replaced by the character cσ(i) in the other message, where σ(i) is an arbitrary permutation of the numbers from 1 to 26. For instance, if we have σ(1) = 24, σ(2) = 25 and σ(3) = 26 the code "abc" in one of the frequencies will be turned in the other into "xyz", so that the corresponding message will be "...zxyzxyzxyzxy...".

You've been put in charge of decoding the alien signal, and your task is to determine the maximum length of a common substring that two codes compatible with the received messages can have. This is, you should find the maximum value K such that one of the messages is compatible with the code a1 a2 ... aN and the other is compatible with the code b1 b2... bN, and there exist i and j with 0 ≤ i, j ≤ N-K such that ai+k = bj+k for k = 1, ..., K up to a permutation of the alphabet.



There are multiple test cases in the input file. For each test case, the first line contains an integer N representing the length of the codes emitted by the aliens (1 ≤ N ≤ 1000). Each of the two following lines contains the description of the message received in a different frequency, in the form of a string of N characters from 'a' to 'z'. The received message is obtained repeating endlessly the corresponding string.



For each test case, print one line containing an integer representing the maximum length of a common substring two codes which are compatible with the received messages can have.





hide comments
[Rampage] Blue.Mary: 2016-01-07 05:07:06

I've added many constant optimization to get AC. The time complexity of desired solution is O(n^2), but even this solution with a little bit large constant will get TLE.

facug91: 2015-11-17 01:26:37

The same solution I've used in BOCA, it's now giving me TLE here. Even that I've optimized it. Could be something wrong with the uploaded file? Thanks in advance!

Added by:Fidel Schaposnik
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Argentinian Programming Tournament 2015