Hi everyone,

I'm currently working on Problem D : Longest Max Min Subsequence from Codeforces Round 967 (Div. 2). You can find the problem here (https://codeforces.net/contest/2001/problem/D?mobile=true ).

I've been stuck with a "Wrong Answer" on test 5. You can check out my submission here (https://codeforces.net/contest/2001/submission/277865632).

The checker log says that the 18714th number is different than expected, with my code outputting '95' instead of the expected '140'.

My approach :- The solution to this problem involves several steps:

Unique Element Collection:

The first step is to identify unique elements in the array. This is done using a set sty and a stack st. The stack st is used to store indices of unique elements in reverse order (from the end of the array to the beginning). The stack is used because when constructing the subsequence, we need to process elements in reverse to preserve the lexicographical order when needed.

Two-Pointer Technique for Lexicographical Order:

The procedure function initializes two arrays gre and sme which represent flags for "greater" and "smaller" values respectively. gre[i] = 1 means that the element at index i is the maximum element from index i to the end of the segment. sme[i] = 1 means that the element at index i is the minimum element from index i to the end of the segment. This preprocessing helps in selecting elements based on their values to achieve the lexicographically smallest sequence.

Building the Result Sequence:

The main loop processes the elements by popping indices from the stack st. For each unique element: Determine the range [start, end] that needs to be processed. Within this range, based on whether the current position requires a "greater" or "smaller" value, the corresponding element is added to the result sequence ans. This choice between "greater" and "smaller" ensures that we minimize the lexicographical order. Alternate between picking maximums and minimums based on the lexicographical order requirement. The flag flag toggles between selecting maximums (if flag = true) or minimums (if flag = false).

Termination:

The process continues until the size of the answer sequence ans matches the number of unique elements in the original array. This ensures that the sequence contains all unique elements and is the longest possible.

Output:

Finally, the size of the sequence and the sequence itself is printed.

I would really appreciate any help or advice on what might be causing this issue. Has anyone else faced a similar problem or could provide insight into what I might be missing?

Thank you in advance for your time and help!