Consider This Catharsis
Pages
Author  Topic: Consider This Catharsis 

Nuke and Pave
Member # 24

written Wednesday, October 24 2007 20:46
Profile
Homepage
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 nondiagonals, 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 pseudocode: Let value(i,j) = 1 if i=j 2 if letter(i) = letter(j) (and i>j) 0 otherwise for i = (N1) to 1 ..for j = 2 to i ....let best(i,j) = value(i,j) + MAX of best(i+1,l) for l = 1 to (j1) and best(k, j1) for k = (i+1) to N result = MAX of best(i,j) for i = 1 to N, j = (i1) 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

written Wednesday, October 24 2007 22:15
Profile
Indeed, quantum computation is not nondeterministic 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

written Thursday, October 25 2007 00:57
Profile
Homepage
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. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Thursday, October 25 2007 04:42
Profile
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

written Thursday, October 25 2007 05:07
Profile
Homepage
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 2030 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: [ Thursday, October 25, 2007 05:13: Message edited by: Xian ]  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Thursday, October 25 2007 07:30
Profile
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

written Thursday, October 25 2007 07:44
Profile
Homepage
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 leftmost 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. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Thursday, October 25 2007 08:03
Profile
I'm not completely familiar with php. But when i = 0, we are evaluating matrix[k][1] for k from 1 to (N1). 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

written Thursday, October 25 2007 08:43
Profile
Homepage
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. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Thursday, October 25 2007 09:09
Profile
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

written Thursday, October 25 2007 09:50
Profile
Homepage
quote:My algorithm: Length 55, 22 seconds. Zeviz: Length 99, 14.45 seconds.  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Thursday, October 25 2007 13:51
Profile
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

written Thursday, October 25 2007 15:47
Profile
Homepage
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][$j1] > $max) { ..$max = $matrix[$k][$j1]; ..$max_x[$i][$j] = $k; ..$max_y[$i][$j] = $j1; } (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 xcoordinates of the ones that are nonzero in the original matrix. (If I am not mistaken, the ycoordinates 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

written Thursday, October 25 2007 18:21
Profile
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 min Note: 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

written Thursday, October 25 2007 23:54
Profile
Homepage
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. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Tuesday, October 30 2007 19:25
Profile
Homepage
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=NPP. Actually, NPC would be a subset of NPP, 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

written Wednesday, October 31 2007 02:09
Profile
Homepage
quote:Pseudocode or leave. :P  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Wednesday, October 31 2007 06:17
Profile
quote: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

written Thursday, November 1 2007 16:24
Profile
Homepage
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..k1] is a longest common subsequence of X[1..m1] and Y[1..n1] (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..m1] 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..n1] 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[i1, j1] + 1 : i, j > 0 and X[i] = Y[i] * max(c[i, j1], c[i1, 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

written Thursday, November 1 2007 16:58
Profile
Homepage
*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. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Thursday, November 1 2007 17:47
Profile
Homepage
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

written Thursday, November 1 2007 18:54
Profile
Homepage
But you do understand it? Meh, perhaps I'm just tired. Let's see... Oh gah.  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat 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

written Sunday, November 4 2007 18:37
Profile
quote: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

written Sunday, November 4 2007 18:49
Profile
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

written Monday, November 5 2007 20:20
Profile
Homepage
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,j1), best(i+1, j1)) (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(i1, j1)) (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 = i1 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 