Th statement of the task
http://www.spoj.com/problems/IOIPALIN/
his task can be solved by looking at it from different point of view. We can easily turn this task into a classic LCS (longest common subsequence algorithm). This will be the formula for finding out answer
answer= n- LCS(given string, reversed string of the given string)
You can find about finding the LCS here.
NOTE: I was getting TLE many times because of a simple problem. LCS has n^2 complexity, It is perfectly fine because 5000^2 will fit in 1 second but there is one problem. The LCS algorithm suggests to keep a matrix of NxN when the matrix gets full the processor runs slower that is why you may get TLE. For this you need to do a simple trick. We don't need to keep the whole 5000x5000 array. In every step. When we are at the row I, we use only the row I and I-1 . So instead of keeping 5000x5000 array we can keep only 2x2000 array and solve it there.
DOWNLOAD THE FULL SOURCE CODE
http://www.spoj.com/problems/IOIPALIN/
his task can be solved by looking at it from different point of view. We can easily turn this task into a classic LCS (longest common subsequence algorithm). This will be the formula for finding out answer
answer= n- LCS(given string, reversed string of the given string)
You can find about finding the LCS here.
NOTE: I was getting TLE many times because of a simple problem. LCS has n^2 complexity, It is perfectly fine because 5000^2 will fit in 1 second but there is one problem. The LCS algorithm suggests to keep a matrix of NxN when the matrix gets full the processor runs slower that is why you may get TLE. For this you need to do a simple trick. We don't need to keep the whole 5000x5000 array. In every step. When we are at the row I, we use only the row I and I-1 . So instead of keeping 5000x5000 array we can keep only 2x2000 array and solve it there.
DOWNLOAD THE FULL SOURCE CODE
cant download the source code
ReplyDelete