SPOJ 3934. Recaman’s Sequence

http://www.spoj.com/problems/MRECAMAN/

This task can be solved easily with the help of C++ STL map (for more info about using map go here). The problem could have been done easier if there wasn't the requirement for the numbers being distinct we could have solved it easily but we need to keep the numbers distinct, this is where C++ STL map template helps us, in every step when we are calculating the current element we need to push it in the map and mark it as true. It is impossible to do with the old fashioned method, keeping a big boolean array and mark every number in it because the numbers are very big no computer would be able to hold an array of elements that big.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 18713. Can You Make It Empty (Easy)

http://www.spoj.com/problems/EMTY/

This task is the easy version of the task EMTY2. Check out my tutorial on the more difficult task which has a fast solution and works for this one as well (you will find the full source code as well) by going here,

SPOJ 18714. Can You Make It Empty

http://www.spoj.com/problems/EMTY2/

I suggest using C++ STL stack for this one. If you need more info on stack go here. Here is how we will do it. We loop over our string, if the current element is '1' then we add it to our stack, if not then we need to check for the last 2 elements, if the last 2 elements are 1 and 0 ( in other words the last two and the current one are forming 100) then we pop those elements otherwise we push the current '0' to our stack. In the end we check if there are any elements left in the stack if there are then the answer is 'no' otherwise is 'yes'.

       DOWNLOAD THE FULL SOURCE CODE

C++ Stack

Stack is another C++ STL container.

Stack is a dynamic array where you can add elements form the end and remove elements again from the end.
It is declared like this. The stack is just alike dish stacking one on another. When you put some plates on one another then when you need them you need to take them out from the top.
....
#include <stack>
.........
...........
..........
stack<type> s;
type is the data type you want your array to hold.

Here are the main functions of stack.
suppose we have
stack<int> a;

a.empty()
This is a boolean function which returns "true" if the stack is completely empty and "false" otherwise.

a.pop()
This function removes the element which is at the end of the stack.

a.push(int x);
This function will add the element x form the back of our stack.

a.top()
This function returns the value of the last element of stack.

SPOJ 9734. Hacking the random number generator

http://www.spoj.com/problems/HACKRNDM/

Of course this type fo probelms can be used with a simple approach. We need to keep and array named B, (we will call the input array A) and B[I] will shows the number of elements from the array A which have the value of I. Then we will check and add to our answer elements B[A[i]+k] . This might work but we are not sure about the constraints. There might be negative numbers where we can't keep negative numbers as an array index. So, STL map covers this problem because with the help of STL map we can keep every type of an index we want. (If you need info about STL map go here).

       DOWNLOAD THE FULL SOURCE CODE

STL map

Map is another STL container and is aother good way of keeping data. We declare map like this.
map<type1 , type2> m;
Basically this map means that we keep data of type 2 with indexses of data type1. This sounds complicated but I will try to be more clear. For example we want to keep a list of names and surnames. We can do that with map.
If we assign map<string,string> m;
this emans that the following expression is legal m["Smith"]="John"; We can consider the first data type we assign to map as the index data type. So in our example "Smith" is the index and "John" is the value. When we are declaring an ordinary array int a[10000]. then we can use the following expression a[10],a[1] but not a[-25] because the indexing starts with 0. You can imagin map as a little more enhanced version of array. So , one more time map<type1 /*index data type*/ , type2 /*value data type*/> m;
examples
map<string,int> m;
m["John"]=0;

map<int, int > m;
m[-10000]=902;

map<unsigend int,int> m;
m[10]=34; //Note that map<unsigend int,int> m has the same effect as the regular array because the indexing starts with non negative numbers

And one more important question, the memory usage. When we first declare the map it is using almost no memory. When the first value is attached, ( for example we have map<string,string> m; and we write m["John"]="Smith") some memoryis being taken only for storing one elment and somehow keep its index. When we assign another value , it checks if the index we use has already been used he just replaces already taken memory with anotehr value if its new than he take memory again. Example
map<string,string> m;
m["John"]="Smith";
takes memory for storing the value "Smith" under the index "John";
m["Johny"]="Smith";
Takes memory because the index "Jonhy" was unused.
m["John"]="Brown";
Already has a memory for the idnex "John" so just replaces the value "Smith" with teh value "Brown";

Looping over maps is being done with iterators.
Now some important functions

m.begin()
return the value for iterator which shows the beginning of the map. IMPORTANT map always starts looping from teh lowest index to the highest.

m.clear()
clears the map completely.

b.empty()
boolean function which returns true if the map is empty and false if it is not.

m.end()
returns the end of the map for iterator.
Looping over map is accomplished like this.
map<type1,type2> m;
........................
........................
........................
map<type1,type2>::iterator it;
for(it=m.begin();it!=m.end();it++)
{
}
m.erase()
This function ca be used in more than 1 ways. If you give a single iterator to it it will remove the element which has that iterator. If you give 2 iterators it will remove all teh elements between these 2 iterators.

m.find( value)
retuns and iterator, needs a value to find it.

m.size()
returns the size of the map= the number of elements in the map.

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++ STL deque

Another STL template is deque. Deque is a lot like queue. The main difference between queue and deque is that you can push/pop element from the beginning of the sequence.

It is defined like this

deque<data type> name;

Suppose we have 

deque<int> q;

 Here are the main functions of deque.

q.at(int i);

Unlike queue, you can access all the elements of deque. This function returns you the element with index i.[] operator can also be used for calling an element.

q.begin()

This function returns an iterator  of the first element of the deque.

q.back();

This function returns the last element in the queue.(the one who is on rightmost position)

q.clear();

This function clears the deque. After this function is used the deque becomes completely empty.

q.empty();

This boolean finction checks if the deque is empty or no. You will get "true" if there is at least one element in the queue and "false" otherwise. 

q.end();

This function return an iterator  of the last element of the deque.

q.erase( .....)

1. 

q.erase( deque<int>::iterator it);

      This function is used to erase elements from different parts of the deque. Note that this function reciveses and iterator. 

2.

q.erase(deque<int>::iterator from , deque<int>::iterator to)

  This function recivese 2 iterators and erases all the elements between this 2 elements.

q.front()

This function returns the first element of the deque. (The leftmost element)

q.insert(deque<int>::iterator i, int x)

This function will insert the number x between the posotions of  i and i+1.

q.pop_back()

This function will remove the last element of the deque(the rightmost element).

q.push_back(int x)

this function  adds the element x to our deque from the end.

q.pop_front()

This function removes the first element of the deque. (The leftmost element).

q.push_front(int x)

This function adds the element x from the beginning of the deque.

q.size()

This function returns the size of the deque. (The length of the deque).

IF YOU HAVE ANY QUESTIONS LEAVE THEM IN COMMENTS, NO QUESTION WILL STAY UNANSWERED

C++ STL vector

Vector is another component of C++ STL (standard template library). Vector is also a dynamic array just like queue but with some differences.

This data structure is different from the data structure stack because vector is often use to keep data not to process and it leave it alone. We define vector like this
vector< data type> name_of_the_vector;
(don't forget to include vector class in the beginning of your code #include <vector> )

Suppose we have vector<int> v;

Above you can find the use of vector's functions.

v.at( int I);

This function calls the element with index I. When we have a static array we use [ ] operator to call for an element , in here we use .at function.
(NOTE [] operator can also be used when we use vector but it is a little bit unsafe.)

v.begin()     v.end()
The functions v.begin() and v.end() return the iterator which shows the beginning of the vector and the end of the vector accordingly. You can learn about iterators here.

v.clear()

This function clears the vector completely. After this function the vector is becoming empty.

v.empty()

This is a boolean function. It returns TRUE if there is at least 1 element in vector or false when the vector is completely empty.

v.erase( vector<int>::iterator iter);

This function deletes an element from the given point of our vector. NOTE this function recieves an iterator as a parameter not an integer.

v.insert( vector<int>::iterator iter,int x);

This function inserts the element x in the position of iter. NOTE this function just like the previous one recieves an iterator as a parameter not an integer.

v.pop_back();

This function pops(removes) the last element of the vector.

 v.push_back(int x);

This function adds an element from the back of the vector .

v.size();

This function returns an integer; the number of elements present in the vector.

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

 

 

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