Wednesday, November 28, 2012

SPOJ GONESORT


Link : GONESORT

Category : Sequences, ad-hoc


Hint : What are the books that need not be moved. Try to find maximum set of such numbers.


Solution : Let the sequence be of N numbers, a1,a2,a3 . . . aN, and let the sorted sequence be b1,b2,b3 . . . bN. Suppose the numbers bi,bi+1,bi+2. . . bj are such that in sequence {a}N, they appear in same order  (bi+k occurs before bi+k+1, but there can be other numbers apart from bi to bj in between them). In this case, all numbers apart from this subsequence can be put to order in N-(j-i+1) steps.

Now the problem is to find maximum contiguous increasing sequence in given set (maximum length sequence such that it appears continuously in sequence {b}N and appears in increasing order in {a}N  It can be easily done in O(N2)

Code:

SPOJ PARADOX

Link : PARADOX

Category : Graphs


Hint : constructed an appropriate graph and do a depth-first traversal.


Solution : Consider this as a directed graph, with edge from vertex A to vertex B if statement A tells about statement B. Make list of incoming and outgoing edges for each vertex, and then do simple depth-first traversal on both, incoming and outgoing edges. If a statement claims opposite of the truth value assigned to an already visited node, then there is a paradox.


Note that for the traversal, the starting vertex can be anyone, and its truth value can be anything (true or false, because if truth value of one statement is changed, then truth value of all nodes reachable by it via directed/directing edges also gets flipped, hence preserving the PARADOX or NOT PARADOX answer.


Code: