[Haskell-cafe] Open Kattis Problem Srednji: Hints to improve my algorithm

[Viktor Dukhovni]

On Wed, Sep 23, 2020 at 09:15:40AM +0200, Dominik Bollmann wrote:

> Check out https://open.kattis.com/problems/srednji for the details.

Which gives a more precise statement of the problem.

> My Haskell solution below tries to find the number of odd sub-sequences
> by first locating the median and then repeatedly moving left and right
> from that median to find larger and larger sub-sequence candidates. Each
> found candidate is checked to have B in the middle when sorted in order
> to become a solution. Moreover, I also extend each such candidate
> further to the left (and to the right, respectively) to determine
> whether these leftward or rightward extensions are solutions, too.
> 
> I think with this approach I systematically enumerate all solutions.
> Unfortunately, though, this approach is too slow and times out on the
> 11th hidden test cases.
> 
> I'd therefore be thankful for hints about different approaches to
> solving this problem more efficiently.

This is not really a programming problem, writing the code is the easy
part.  Rather, this is an *algorithm* problem.  An efficient solution
uses a better algorithm, not a different implementation of the same
algorithm.  Your algorithm is not efficient.  Forget Haskell for the
moment, can you think of a better algorithm.  The above algorithm is
subtantially slower than optimal.

The best algorithm that comes to mind runs in linear time in the length
of the list, and requires linear (2N) additional space.  No sorting
(that would not be linear) or complex testing of candidates is required,
just some counting and O(N) book-keeping.

-- 
    Viktor.