My reasoning was to break the sequence up into blocks of "one or more Ys followed by an N", and "one or more Ns followed by a Y" (any remaining Ys or Ns treat as a special case), and then show that in the first case an optimal sequence for that block is all Ys, and similarly therefore for the second case an optimal sequence is all Ns. Since you've ended with a different letter, you are free to choose the first letter for the next block, so it should be possible to treat the blocks independently. Though I may have missed something or made some assumptions.
The only time an alternative solution is possible if the block is either NY or YN - we can try YY or NN, but that constrains us to keep the same letter for the next choice ... So it can be seen that a block of NYY can have YYY as a solution instead of NNY (and similarly YNN can have NNN instead of YYN). I think that shevek's solution is the greedy solution except with these two substitutions made.
I'm not sure how to prove that these are the only possible substitutions. If they are, then it ought to be possible to find all possible solutions by spotting sequences of NYY and YNN and writing all possible combinations with each of these sequences having either of the two solutions?
So for NYYNYNN, the best would be NNYYYYN (score 4). There is 1 sequence of NYY and 1 of YNN given 3 other solutions: YYYYYYN, NNYYNNN and YYYYNNN.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2005-11-03 12:12 pm (UTC)My reasoning was to break the sequence up into blocks of "one or more Ys followed by an N", and "one or more Ns followed by a Y" (any remaining Ys or Ns treat as a special case), and then show that in the first case an optimal sequence for that block is all Ys, and similarly therefore for the second case an optimal sequence is all Ns. Since you've ended with a different letter, you are free to choose the first letter for the next block, so it should be possible to treat the blocks independently. Though I may have missed something or made some assumptions.
The only time an alternative solution is possible if the block is either NY or YN - we can try YY or NN, but that constrains us to keep the same letter for the next choice ... So it can be seen that a block of NYY can have YYY as a solution instead of NNY (and similarly YNN can have NNN instead of YYN). I think that
I'm not sure how to prove that these are the only possible substitutions. If they are, then it ought to be possible to find all possible solutions by spotting sequences of NYY and YNN and writing all possible combinations with each of these sequences having either of the two solutions?
So for NYYNYNN, the best would be NNYYYYN (score 4). There is 1 sequence of NYY and 1 of YNN given 3 other solutions: YYYYYYN, NNYYNNN and YYYYNNN.
And you were looking very beautiful at Whitby!