wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> count the valid blocks
        
(Message started by: inexorable on Jun 10^th, 2010, 3:13pm)

Title: count the valid blocks
Post by inexorable on Jun 10^th, 2010, 3:13pm

Given an array A which holds a permutation of 1,2,...,n. A sub-block A[i..j]
of an array A is called a valid block if all the numbers appearing in A[i..j]
are consecutive numbers (may not be in order）.

Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5],
[3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]

Give an O( n log n) algorithm to count the number of valid blocks.

Title: Re: count the valid blocks
Post by Hippo on Jun 11^th, 2010, 6:01am

You cannot in O(n log n) find result of size \Omega(n^2).

Title: Re: count the valid blocks
Post by towr on Jun 11^th, 2010, 7:42am

on 06/11/10 at 06:01:53, Hippo wrote:

You cannot in O(n log n) find result of size \Omega(n^2).

You only have to give the count, not the blocks.

Title: Re: count the valid blocks
Post by inexorable on Jul 28^th, 2010, 1:13pm

A solution is posted at
http://stackoverflow.com/questions/1824388/finding-sorted-sub-sequences-in-a-permutation
:o

could someone please explain it?