SPOJ PRATA

The problem : www.spoj.com/problems/PRATA/

Solution: There are many solutions one can use binary search which is straight forward if you understand the concept of binary search . Use the link to find a binary search based implementation

http://spoj-solutions.blogspot.in/2014/10/prata-roti-prata.html

I used a min-heap based solution. The algorithm is to find the the cook who will next become free and assign him a prata, as simple as that.

My solution is O(p*L) which got accepted. You can find the code through following link
https://github.com/kanirudh/spoj/blob/master/prata.cpp

Comment below in case of queries.

A list of algorithms for Competitive Programming

Solving problems on SPOJ, I realised I used to forget the algorithms which I had previously used. For this fallacy of mine I am listing the algorithms and the corresponding SPOJ problems. There may be better resources on net similar to this but this is my effort. You can also find solutions to these problems on my github page http://www.github.com/kanirudh/SPOJ/

1. Sorting:
     Using the library function for sorting usually does the trick. You need to know how to define a comparator function for sorting user-defined structure arrays.
   
     http://www.spoj.com/problems/DOTAA/

2. String Algorithms
 
     Patten Matching
     a) KMP Algorithm
     http://www.spoj.com/problems/NHAY/
     b) Rabin Karp 

3. Dynamic Programming Algorithms
   
     a) 0/1 Knapsack
     http://www.spoj.com/problems/LKS/
   
     b) Longest Increasing Subsequence
     http://www.spoj.com/problems/XMEN/

     c) Longest Common Subsequence
     http://www.spoj.com/problems/LCS/
     http://www.spoj.com/problems/TRIP/

4. Divide And Conquer
     a) Closest Pair of Points
     http://www.spoj.com/problems/CLOPPAIR/

     b) Binary Search
     http://www.spoj.com/problems/PIE/
     http://www.spoj.com/problems/EKO/
     http://www.spoj.com/problems/OPCPIZZA/
 

5. Graph Algorithms
    ( DFS, BFS, Djisktra, Floyd-Warshall, Bellman-Ford, kruskal)
    http://www.spoj.com/problems/PARADOX/

6. Maths
    Gaussian Elimination
    http://www.spoj.com/problems/XMAX/






 

SPOJ:Insertion Sort

The problem asks us to find the number of swaps an insertion sorts does, which in a way is a measure of efficiency of the sort.

The basic logic is answer is the sum of ( for each element the number of elements greater than itself occuring before it .)

One way to implement it is Employ merge sort on it and during each merge operations if you are copying an element from the right array (swaps +=no. of elements in the left array) .

A novice mistake which I made what that I dynamically allocating and de-allocating a temporary array during each merge operation, BEWARE this is a very costly operation and should not be used. Allocate memory once and pass that array .