Skip to main content

SPOJ 95 - STPAR - Street Parade

Problem Statement

Heuristics: 
Let, N be the number which is next in fixed order.
Take an input X, if it is equal to N then next number will be n++. If not, then search for N in the side lane and after finishing the search, put X in the side lane.
After all X is processed but N is not found in either X or side lane, then the order is not possible.
Solution:

Labels:

Comments

Post a Comment

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left
14 comments
Read more