# Open Kattis Problem Srednji: Hints to improve my algorithm

6 messages
Open this post in threaded view
|

## Open Kattis Problem Srednji: Hints to improve my algorithm

Open this post in threaded view
|

## Re: Open Kattis Problem Srednji: Hints to improve my algorithm

 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. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: Open Kattis Problem Srednji: Hints to improve my algorithm

Open this post in threaded view
|

## Re: Open Kattis Problem Srednji: Hints to improve my algorithm

 In reply to this post by Viktor Dukhovni On Wed, Sep 23, 2020 at 03:57:33AM -0400, Viktor Dukhovni wrote: > 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. On my machine the constant factor seems to be about 0.7 seconds for a randomly "desorted" list of length 10 million numbers, in which choosing the desired median to be 5 million yields 9,979,641,307 possible combinations of sequences:     9979641307        2,160,167,416 bytes allocated in the heap              106,240 bytes copied during GC           80,053,184 bytes maximum residency (2 sample(s))              744,512 bytes maximum slop                   80 MiB total memory in use (0 MB lost due to fragmentation)                                          Tot time (elapsed)  Avg pause  Max pause       Gen  0       960 colls,     0 par    0.005s   0.005s     0.0000s    0.0001s       Gen  1         2 colls,     0 par    0.005s   0.005s     0.0026s    0.0050s       INIT    time    0.000s  (  0.000s elapsed)       MUT     time    0.652s  (  0.698s elapsed)       GC      time    0.010s  (  0.010s elapsed)       EXIT    time    0.000s  (  0.000s elapsed)       Total   time    0.663s  (  0.708s elapsed)       %GC     time       0.0%  (0.0% elapsed)       Alloc rate    3,311,613,717 bytes per MUT second       Productivity  98.4% of total user, 98.5% of total elapsed The tuned up algorithm uses 1*N+constant space, which for 10 million 64-bit Ints in an Unboxed Vector works out to the reported 80 MB. Most of the CPU time (and heap allocaton) is likely spent reading and converting the input stream of decimal integers.  The actual CPU time spent solving the problem is likely a fraction of that cost. The RTS stats for 100M numbers confirm the linear scaling in time and space (this time 103,749,385,441 ways to place the median):     103749385441       21,701,903,208 bytes allocated in the heap              935,496 bytes copied during GC          800,053,240 bytes maximum residency (2 sample(s))               67,592 bytes maximum slop                  766 MiB total memory in use (0 MB lost due to fragmentation)                                          Tot time (elapsed)  Avg pause  Max pause       Gen  0      9610 colls,     0 par    0.052s   0.052s     0.0000s    0.0001s       Gen  1         2 colls,     0 par    0.049s   0.049s     0.0247s    0.0491s       INIT    time    0.000s  (  0.000s elapsed)       MUT     time    6.811s  (  7.297s elapsed)       GC      time    0.101s  (  0.102s elapsed)       EXIT    time    0.000s  (  0.000s elapsed)       Total   time    6.912s  (  7.399s elapsed)       %GC     time       0.0%  (0.0% elapsed)       Alloc rate    3,186,237,035 bytes per MUT second       Productivity  98.5% of total user, 98.6% of total elapsed --     Viktor. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.