SPOJ 16793. Statistics applied

Here is the problem statement
http://www.spoj.com/problems/EC_ESTA/

We have a long sequence and every time it is asked we need to print the median of it. ( The median is the middle number of a sorted sequence, if the length of the sequence is an even number => it has 2 medians fo the real median is the sum of those middle elements divided on 2). For solving it we will divide the sequence into 2 parts. We need to keep each part in a priority queue. (For more information about priority queue go here). The elements of the second priority queue will be stored with a - (minus) sign so that every timew we call for the largest ellement we get the smallest element in the second sequence which wil be the biggest element in priority queue when multiplied with -1.As we can get the biggest element of the first queue (which might be the middle element) and the biggest element (which also might be the middle element) if the total size is even number than we take this 2 values and sum them and print the result divided on 2 if not then we just output the biggest number of the first queue. (PAY a very close attention when you are adding the element, you need to add it to the appropriate place or else this strategy won't work). Make sure to check the source code for better understanding.

       DOWNLAOD THE FULL SOURCE CODE

       

STL priority queue

The STL priority queue is similar to the standard STL queue but tehre are some differences.

As you can see, as in teh standard queue, in priority queue you can push elements to the queue but when you are taking out the frint element you will get the biggest element. That is why it is called PRIORITY queue.
 Prirority queue is being declared like this

priority_queue<int> q;

Functions of priority queue

q.empty()
This boolean function will return you the boolea value "true" if the queue has no elements otherwise it will return the boolean value "false".

q.pop()
This function removes the biggest element in queue in O( log(N) times here N is the size of the queue.

q.push( int X)
This function will add the elmene X to teh queue.

q.size()
This function return the length of the queue AKA the size.

q.top()
This function return the biggest element in the queue in O(logN) time where N is the size of the queue.

SPOJ 13043. The Mirror of Galadriel

Here is the problem statement.
http://www.spoj.com/problems/AMR12D/

The problem is very simple if observed correctly. You only need to check if the given string is palindrome or not. Here is why. The palindrome is a string which if reversed will be the same string. Let's try to prove the reversed point. If the string contains all the reversed substrings of his own that eans that he is a palindrome. which is very easy to prove by just taking the string himself as a substring :D . The reversed of himself can exist in himself if he reads from the left and right the same way .

       DOWNLOAD THE FREE SOURCE CODE 

C++ (intermediate) STL queue

One of the most important classes in C++ STL( standard template library) is queue. Queue is a dynamic array. You can add elements from the back of the queue and remove elements from the beginning of the queue. The functions are called push and pop. Push stands for pushing an element from the back of the queue and pop stands for popping (taking out) the element from the beginning of the queue.

Queue is being defined like this

queue< data type> name_of_the_queue;

Here is the list of functions of queue.

push

is written like this q.push(a);

This command will add element a to the end of our queue. 

pop

   is written like this q,pop();

  This function has no parameters. It is just removing the first element of our queue.

front

 is written like this a=q,front();

this function is not a void type function it returns the value of the first element (returns not removes).

empty

is written like this q.empty(); 

This is a boolean function. It returns one of 2 values. It returns "true" if the queue is completely empty(no elements are present in the queue) and it returns "false" if there is at least one element present in the queue.

IF YOU HAVE ANY QUESTIONS LEAVE THEM IN COMMENTS. NO QUESTION WILL BE UNANSWERED