SPOJ AMR12H

Link : AMR12H

Category : Maths, probability and expectation

Solution : If f(x) is the Random Distribution Function of a random variable X and g(x) is the RDF of RV Y then
RDF of min(X,Y) is f(x)*g(x)
RDF of max(X,Y) is f(x)+g(x)-f(x)*g(x)
Then the expected value of the expression formed is integral over [0,1]

Code:

UVA 12356 : Army Buddies

Link : UVA12356

Category : Data Structure

Solution : Simple segment tree data structure suffices. Each node of the tree has a boolean variable indicating if at all it is possible to find an alive soldier in this range of soldiers.

Code:

Codechef ARIGEOM

Link : ARIGEOM

Category : Pigeonhole principle

Solution : Consider the first three terms. Some two of them have to be in AP or both in GP, thus giving 6 possible cases. Eg, let a,b,and c be first three terms. If a and b form an AP, then common difference of the AP must be b-a. Now mark all elements falling in this AP as apmarked (remember, all elements must be present in this AP starting from a and ending at some end point within the array). Now for remaining elements, find the common ratio that would mark all remaining elements, and possibly some apmarked elements too. Similarly for other 5 cases too.

Code:

SPOJ DCEPC206

Link : DCEPC206

Category : Segment Tree

Code:

SPOJ SKYLINE

Link : SKYLINE

Category :Maths

Solution : Recurrence works out to be Catalan number.

Code:

SGU 355 : Numbers Painting

Link : sgu355

Category : Simple number theory

Solution :  For every M in 2 to N, let prime factorization of M be M=product(p_i^e_i). Then M will be colored by color number sum(e_i). Eg, 12=2²x3¹, then color 12 by color number (2+1)=3. Additionally, number 1 will require a totally different color, since it divides all other numbers.

Code:

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: