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, a₁,a₂,a₃ . . . a_N, and let the sorted sequence be b₁,b₂,b₃ . . . b_N. Suppose the numbers b_i,b_i+1,b_i+2. . . b_j are such that in sequence {a}_N, they appear in same order  (b_i+k occurs before b_i+k+1, but there can be other numbers apart from b_i to b_j 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(N²)

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: