P3506 [POI 2010] MOT-Monotonicity 2

This task is a harder version of task Monotonicity from the third stage of 17th Polish OI. It wasn't used in the contest itself. For an integer sequence  we define its monotonicity scheme as the sequence  of symbols ,  or . The symbol  represents the relation between  and . For example, the monotonicity scheme of the sequence  is . We say that an integer sequence  with monotonicity scheme , realizes another monotonicity scheme  if for every  it holds that . In other words, the sequence  can be obtained by repeating the sequence  and removing appropriate suffix from that repetition. For example, the sequence  realizes each and every one of the following schemes:     as well as many others. An integer sequence  and a monotonicity scheme  are given. Your task is to find the longest subsequence  () of the former that realizes the latter.

N/A

N/A