Chef Likes Good Sequences Codechef October Lunchtime Problem solution -
First of all do not confuse with subarray and subsequence.
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A subarray will always be contiguous but a subsequence need not be contiguous.
- Case 1 : () and (), then answer will increase by as it will make segment into segments.
- Case 2 : () and (), then the answer will increase by as earlier and will introduce an extra segment. If then we will reduce the answer by as earlier we added as changing to increased the segment count but now it will be merged with previous segment. Example : let and , so If answer will increase by , and if then there will no change to the answer.
- Case 3 : () and (), similar to above case, we will increase the answer by . if then we will reduce the answer by .
- Case 4 : () and (), then if we will reduce answer by . if we will reduce answer by .(Note that you might reduce the answer by when ).