SPOJ PLD

Link : PLD

Category : Hashing

Hint : Consider substrings of S of length k and substrings of Reverse(S) of length k. If the hash value of one substring of S matches with hash value of substring of Reverse(S), and second starts when first ends, there is a match!

Solution : Well, the hint says pretty much all of it, except for a good hash function. For hash value of substring Si to Sj, we better not take O(k) time (else program is O(N*K) and gets TLE), hence I used the polynomial hash function

Hash({S_i to S_j})=(S_ia⁰+S_i+1a¹+S_i+2a²...)%p
Where a and p were primes (p was because of good hash spread, a was for no good reason :D ). This hash function allows Hash({S_i to S_j}) to be computed from Hash({S_i-1 to S_j-1}) in O(1) time, giving the complexity of hashing all substrings of S of length k O(N).

To do the index match (S's substring ends where Reverse(S)'s starts), keep a sorted vector at all hash values, and so a binary search.

Code:

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:

Hello World!

Like all my recent ‘first’s, I’ll like to call this my “Hello World” post :D

And like all “Hello World”s, there’s nothing much to write, so I would like to end with my favourite quote:

  

“When a man is willing and eager, the Gods join in” – Aeschylus