Problem 1004

[henrig]

I would like to confirm that I correctly understand what is meant by "longest non-strictly increasing subsequence". It seems "strictly" relates to excluding equal digits and it does not relate to consecutive digits.

Is 85377429 balanced or not? Is the longest strictly decreasing subsequence the digits 8742 and the longest non-strictly increasing subsequence 5779?

If strictly relates to consecutive digits then 8565327017 would be a balanced number of length four - 6532 versus 5577? Similarly, is 63209789 balanced with length four (6320 versus many possibilities including 789 as the last three digits)? Lastly, according to me 363209789 is not balanced since "longest non-strictly increasing subsequence" is five by using 33789.

[henrig]

Is the following rather extreme number balanced with length six: 44444333933222872261151114?
The longest strictly decreasing subsequence is 987654 while there are multiple longest non-strictly increasing subsequences of length six - including 444444, 333338, 333335, 222226 and 1111114.

[skoczian]

I would like to confirm that I correctly understand what is meant by "longest non-strictly increasing subsequence". It seems "strictly" relates to excluding equal digits and it does not relate to consecutive digits.

I think you are right and the example is clear enough:
"For example, the number 77429 is balanced, because both its longest strictly decreasing subsequence (742) and its longest non-strictly increasing subsequence (779) have length 3."

The subsequence 742 consists of consecutive digits, 779 does not.

[drakempham]

I would like to confirm that I correctly understand what is meant by "longest non-strictly increasing subsequence". It seems "strictly" relates to excluding equal digits and it does not relate to consecutive digits.

Is 85377429 balanced or not? Is the longest strictly decreasing subsequence the digits 8742 and the longest non-strictly increasing subsequence 5779?

If strictly relates to consecutive digits then 8565327017 would be a balanced number of length four - 6532 versus 5577? Similarly, is 63209789 balanced with length four (6320 versus many possibilities including 789 as the last three digits)? Lastly, according to me 363209789 is not balanced since "longest non-strictly increasing subsequence" is five by using 33789.

Yes, your understanding is correct. A subsequence does not have to be consecutive, but need to preserve original order of character in string.
So:

• 85377429 is balanced. Its longest strictly decreasing subsequence has length 4, for example.

• 8742, and its longest non-strictly increasing subsequence also has length 4, for example 5779.