Author |
Topic: count the valid blocks (Read 1039 times) |
|
inexorable
Full Member
Posts: 211
|
 |
count the valid blocks
« on: Jun 10th, 2010, 3:13pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
|
Re: count the valid blocks
« Reply #1 on: Jun 11th, 2010, 6:01am » |
Quote Modify
|
You cannot in O(n log n) find result of size \Omega(n^2).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: count the valid blocks
« Reply #2 on: Jun 11th, 2010, 7:42am » |
Quote Modify
|
on Jun 11th, 2010, 6:01am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print