Consider This Catharsis

Pages

AuthorTopic: Consider This Catharsis
Nuke and Pave
Member # 24
Profile Homepage #25
Aran, congratulations with finding a polynomial time algorithm.

While trying to understand your solution, I found one that works in O(N^3):

When filling out your matrix, put 2, instead of 1 on all non-diagonals, to represent pairs.

Now go through each column from right to left, and let the value of each point be the sum of its original value and highest value along the edges of rectangle to the right and top of it.

In pseudo-code:

Let value(i,j) =
1 if i=j
2 if letter(i) = letter(j) (and i>j)
0 otherwise

for i = (N-1) to 1
..for j = 2 to i
....let best(i,j) = value(i,j) + MAX of best(i+1,l) for l = 1 to (j-1) and best(k, j-1) for k = (i+1) to N

result = MAX of best(i,j) for i = 1 to N, j = (i-1) to i

Here is an example:
String = abca

Matrix of values:
a.b.c.a
1.0.0.2
-.1.0.0
-.-.1.0
-.-.-.1

Matrix of bests:
a.b.c.a
1.0.0.2
-.3.2.0
-.-.3.0
-.-.-.1

result: 3 (either aba, or aca)

The reason I look at two diagonals to find result is for a case like aab (where the central pair has no single letters in the middle):
a.a.b
1.2.0
-.1.0
-.-.1

--------------------
Be careful with a word, as you would with a sword,
For it too has the power to kill.
However well placed word, unlike a well placed sword,
Can also have the power to heal.
Posts: 2649 | Registered: Wednesday, October 3 2001 07:00
Electric Sheep One
Member # 3431
Profile #26
Indeed, quantum computation is not non-deterministic Turing machines. A quantum computer is parallel and capable of exploring multiple inputs in a single run, but it does so within the tight constraints of quantum mechanics, which is not simply arbitrary parallelism. It has its own rules, and exploring just what those are is an interesting new angle on understanding quantum mechanics in general. It is also of some interest as an extension of classical computer science. It is far from clear that quantum computers will ever replace classical computers wholesale, but it is quite likely that quantum engines will be available as oracles for specific types of problem within our lifetimes.

Which is why people have been doing advanced research on quantum computation theory for quite a few years now, mostly in physics departments, sometimes in computer science departments, and in a few cases at large companies (IBM and Microsoft are the ones I know).

Basic research always looks far ahead. It also looks wide to the sides, considering things that don't seem at all likely bets for application in the foreseeable future. That's what you have to do, or the human race is just stumbling blindly into the future, hoping things will work out. And there are billions of us, after all. Throwing a few hundred thousand humans into basic research, around the world, is a smart investment. Most of their research never really pays off in practical terms. But a tiny fraction of the ideas they generate are the biggest practical payoffs humanity ever gets. Basic research is like a lottery where the tickets are expensive and the odds of winning are low, but the prize is disproportionately enormous. It pays to keep playing.

--------------------
We're not doing cool. We're doing pretty.
Posts: 3335 | Registered: Thursday, September 4 2003 07:00
Law Bringer
Member # 2984
Profile Homepage #27
Zeviz: Brilliant! I had to look at it a while before I saw it was n^3, but since you're replacing the triangle search (squared) with a search of one row and one column (linear), you've dropped one power. :)

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Shaper
Member # 32
Profile #28
I suspect that Zeviz's solution is probably as optimal as one can get, unless there's some obscure language theory solution. However, I'm not going to bother looking for it.

Time to move on to a new project?

EDIT:Sphere Online Judge

[ Thursday, October 25, 2007 04:47: Message edited by: Lt. Sullust ]

--------------------
Lt. Sullust
Quaere verum
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Law Bringer
Member # 2984
Profile Homepage #29
Zeviz: I probably have it imlemented faultily, but I keep getting different results than with my other implementation on long texts. This occurs after about 20-30 characters, and the result the O(n^3) algorithm returns is slightly under double that which O(n^4) returns.

My PHP code is here:

function largest_palindrome($text)
{
$begin = explode(" ",microtime());
$matrix = array();

// build match matrix.
// Note: matrix[i][j] is COLUMN i, ROW j.

for ($i = 0; $i < strlen($text); $i++) // each column
{
$matrix[$i] = array();
for ($j = 0; $j <= $i; $j++) // each cell down to the diagonal
$matrix[$i][$j] = $text[$i]==$text[$j] ? ($j<$i ? 2 : 1) : 0;
}

// Go through each column from right to left
for ($i = strlen($text)-1; $i >= 0; $i--)
{
// Go through each cell down to the diagonal
for ($j = 0; $j <= $i; $j++)
{
$max = 0;
// Find the maximum in the horizontal row above and to the right
for ($k = $i+1; $k < strlen($text); $k++)
$max = max($max, $matrix[$k][$j-1]);
// Find the maximum in the vertical row above and to the right
for ($k = 0; $k < $j; $k++)
$max = max($max, $matrix[$i+1][$k]);
// Add this maximum to the current cell.
$matrix[$i][$j] += $max;
}
}

$max = 0;
// Find largest value in the matrix
foreach ($matrix as $column)
foreach ($column as $cell)
$max = max($max, $cell);
$end = explode(" ", microtime());
print "Calculated result in ". ($end[0]+$end[1]-$begin[0]-$begin[1]) ."seconds \n";
return $max;
}


[ Thursday, October 25, 2007 05:13: Message edited by: Xian ]

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Shaper
Member # 32
Profile #30
Well some time could be saved if the program was adjusted so as to only check the two diagonals that Zeviz mentions, when looking for the largest value. But that alone can't account for that much of a difference.

Also when you begin, your boundary is i >= 0. Shouldn't that be i > 0.

[ Thursday, October 25, 2007 07:37: Message edited by: Lt. Sullust ]

--------------------
Lt. Sullust
Quaere verum
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Law Bringer
Member # 2984
Profile Homepage #31
I'm not sure if I misunderstood or you did. But by "difference in results" I mean that the actual maximum length found is different, not the time. ;)

The difference between i>0 and i>=0 is negligible: The left-most column contains only a single field that can only have the value 1.

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Shaper
Member # 32
Profile #32
I'm not completely familiar with php. But when i = 0, we are evaluating matrix[k][-1] for k from 1 to (N-1). I imagine evaluating this is going to cause issues.

--------------------
Lt. Sullust
Quaere verum
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Law Bringer
Member # 2984
Profile Homepage #33
i+1, actually. The point where the array boundary is broken is on the right edge, not the left one.

In PHP, array boundaries are more what you'd call guidelines than actual rules. Since we're looking only for the maximum, and out of boundary values are 0, this is negligible - as long as we check the correct rows and columns.

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Shaper
Member # 32
Profile #34
Could you give an example of a string (preferably shorter) where it is different.

--------------------
Lt. Sullust
Quaere verum
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Law Bringer
Member # 2984
Profile Homepage #35
quote:
In PHP, array boundaries are more what you'd call guidelines than actual rules. Since we're looking only for the maximum, and out of boundary values are 0... unless Zeviz had a specific boundary case in mind other than the value 0, this shouldn't be a problem.
My algorithm: Length 55, 22 seconds.
Zeviz: Length 99, 14.45 seconds.

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Shaper
Member # 32
Profile #36
I coded it up in C++ and ran it. I also got 99. But I got it in .48 seconds :P .

--------------------
Lt. Sullust
Quaere verum
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Nuke and Pave
Member # 24
Profile Homepage #37
You can check correctness of my algorithm by modifying it to return the actual palindrome, rather than just a number:

1. Save a copy of original matrix that you are overwriting.

2. When you are looking for a max, keep track of coordinates of the point where max value was found:
if ($matrix[$k][$j-1] > $max) {
..$max = $matrix[$k][$j-1];
..$max_x[$i][$j] = $k;
..$max_y[$i][$j] = $j-1;
}
(Use similar block of code for the $matrix[$i+1][$k] comparisons.)

3. When going through the matrix of results looking for largest value, keep track of its coordinates.

4. After largest value is determined, look up its coordinates in @max_x and @max_y, to find the coordinates of the previous point. Then look up the previous point, etc.

5. Finally, go through your list of points, reporting x-coordinates of the ones that are non-zero in the original matrix. (If I am not mistaken, the y-coordinates correspond to coordinates of matching letters from the first part of the string. However, I am at work now, so I don't have time to think this through.)

PS When you implement this, it might be easier to check correctness of answer with a shorter string.

--------------------
Be careful with a word, as you would with a sword,
For it too has the power to kill.
However well placed word, unlike a well placed sword,
Can also have the power to heal.
Posts: 2649 | Registered: Wednesday, October 3 2001 07:00
Shaper
Member # 32
Profile #38
In order to simplify it a bit, I set it to only print the second half of the palindrome. This is the solution it gives me for the palindrome:

.. unless Zeviz had a specific boundary case in minNote: Since the palindrome has odd length the first period is the center. I'll wait to see what Aran gets before making adjustment to my code.

--------------------
Lt. Sullust
Quaere verum
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Law Bringer
Member # 2984
Profile Homepage #39
Heh. It's possible that my own algorithm could be flawed (or at least its implementation).

Oh wait. I'm only checking for half of the palindrome. Did I even remember to multiply by two?

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Guardian
Member # 6670
Profile Homepage #40
Homework load little less now - still a lot, but at least I can breathe now. Anyhoo, just popped in to say that O(n^2) is possible (use the dynamic programming, Luke!). Just 'cause, y'know, if I have to do homework tonight, so does everyone else.

That, and I was wrong before when I said P=NP => NPC=NP-P. Actually, NPC would be a subset of NP-P, perhaps even a proper subset.

--------------------
Fatty, you with your thick face have hurt my instep.
- Hong Kong subtitle
Posts: 1509 | Registered: Tuesday, January 10 2006 08:00
Law Bringer
Member # 2984
Profile Homepage #41
quote:
Originally written by Dintiradan:

O(n^2) is possible (use the dynamic programming, Luke!).
Pseudocode or leave. :P

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
By Committee
Member # 4233
Profile #42
quote:
Originally written by Xian:

quote:
Originally written by Dintiradan:

O(n^2) is possible (use the dynamic programming, Luke!).
Pseudocode or leave. :P

sudu don't be so mean, Aran! :D

--------------------
In today’s America, there are more World of Warcraft players than farmers.
Posts: 2242 | Registered: Saturday, April 10 2004 07:00
Guardian
Member # 6670
Profile Homepage #43
Wimps.

Define a subsequence of array X[1..m] as an array Z[1..k], where each element of Z is an element of X. The elements do not have to be adjacent, but must be in order.

A common subsequence of arrays X[1..m] and Y[1..n] is array Z[1..k] if Z is a subsequence of both X and Y.

For arrays X[1..m] and Y[1..n], consider the longest common subsequence Z[1..k]. Note the following:

* X[m]=Y[n] => Z[k]=X[m]=Y[n] and Z[1..k-1] is a longest common subsequence of X[1..m-1] and Y[1..n-1]
(If Z[k]!=X[m], append X[m] to Z to make a longer common subsequence.)

* X[m]!=Y[n] and Z[k]!=X[m] => Z[1..k] is a longest common subsequence of X[1..m-1] and Y[1..n]

* X[m]!=Y[n] and Z[k]!=Y[n] => Z[1..k] is a longest common subsequence of X[1..m] and Y[1..n-1]

Since the problem has optimal substructure, we can make a m x n matrix to store the intermediate values. Let matrix entry c[i, j] be the length of the longest common subsequence of X[1..i] and Y[1..j]. Use the following recurrence equation:

c[i, j] =

* 0 : i = 0 or j = 0
(The size of the longest common subsequence cannot be longer than either array.)

* c[i-1, j-1] + 1 : i, j > 0 and X[i] = Y[i]

* max(c[i, j-1], c[i-1, j]) : i, j > 0 and X[i] != Y[j]

--------------------
"Can we use ad hominem attacks now?"
Posts: 1509 | Registered: Tuesday, January 10 2006 08:00
Law Bringer
Member # 2984
Profile Homepage #44
*bows down*

Oh Dread Lord of the Algorithm, I am not worthy.

(Being pwned like that isn't exactly pleasant for the average programmer. :P )

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Guardian
Member # 6670
Profile Homepage #45
Bloody hell, I didn't come up with it.

--------------------
But I'll pwn you nonetheless.
Posts: 1509 | Registered: Tuesday, January 10 2006 08:00
Law Bringer
Member # 2984
Profile Homepage #46
But you do understand it?

Meh, perhaps I'm just tired. Let's see...

# uptime

Arancaytar has been up 20 hours 24 minutes and 2 seconds.
Oh gah.

--------------------
The Noble and Ancient Order of Polaris - We're Not Yet Dead.
EncyclopediaArchivesStatsRSS (This Topic / Forum) • BlogNaNoWriMo
Did-chat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.'
Decorum deserves a whole line of my signature, and an entry in your bookmarks.
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Agent
Member # 5814
Profile #47
quote:
Originally written by Xian:

But you do understand it?

Meh, perhaps I'm just tired. Let's see...

# uptime

Arancaytar has been up 20 hours 24 minutes and 2 seconds.
Oh gah.

I've had 12 hours of actual sleep over the past 3 days, although I've also rested my body without actually sleeping, have had massive amounts of caffeine, and haven't had to do any serious thinking.

--------------------
It's only an eye, my lord.
Posts: 1115 | Registered: Sunday, May 15 2005 07:00
By Committee
Member # 4233
Profile #48
I sometimes do that when my wife is out of town and I get sucked into the black hole of gaming. It always seems like a good idea at the time, but then I'm always grateful when she returns and life is returned to moderately more productive and much more restful order. :)

--------------------
In today’s America, there are more World of Warcraft players than farmers.
Posts: 2242 | Registered: Saturday, April 10 2004 07:00
Nuke and Pave
Member # 24
Profile Homepage #49
After thinking a little more about it, my solution can run in O(n^2) if I use some memorization of intermediate results:

1. Start as before by building a matrix where value(x,y) =
1 if x = y
2 if letter(x) = letter(y) and x > y
0 otherwise

example:
a.b.c.a
1.0.0.2
0.1.0.0
0.0.1.0
0.0.0.1

2. Go through columns finding best values, but remember previous bests instead of recalculating them every time. (By "best value" I mean the best value from the edge of rectangle to the right and top of current point plus the value of the current point. You can see the explanation of this method in Aran's original description of his algorithm.)

for i = n to 1
..for j = 1 to i

....best_vertical(i,j) = max(best_vertical(i,j-1), best(i+1, j-1))
(meaning that best value along the vertical of inner rectangle is either the best value of smaller rectangle, or it's in the corner)

....best_horizontal(i,j) = max(best_horizontal(i+1,j), best(i-1, j-1))
(same as above, but looking along the horizontal edge of the inner rectangle)

....best(i,j) = value(i,j) + max(best_vertical(i,j), best_horizontal(i,j))
(now we get the best value for the point itself)

3. Now go through the two diagonals looking for the largest best value. That is your answer.

for i = 1 to n
..for j = i-1 to i
....result = max(result, best(i,j))

This is equivalent to my original algorithm, but runs in O(n^2).

Could somebody who read Dintiradan's solution (or Dintiradan himself) tell me if my solution is as good as his, or if I need to work more on space and/or time efficiency. (I don't want to read the solution myself, because I am still hoping to be able to find it on my own.)

--------------------
Be careful with a word, as you would with a sword,
For it too has the power to kill.
However well placed word, unlike a well placed sword,
Can also have the power to heal.
Posts: 2649 | Registered: Wednesday, October 3 2001 07:00

Pages