SPOJ 1021. Aibohphobia

This is the problem statement
http://www.spoj.com/problems/AIBOHP/

This problem is similar to the problem Palindrom 2000 (IOIPALIN). This task can be turned into another task. The number of insertions equals to the length of the string minus LCS(longest common subsequence) of the given string and the reversed string of the given string.
formula
answer=n - LCS( string, reversed string)

You can find information about LCS here.

DOWNLOAD FULL SOURCE CODE

SPOJ 7150. Palindrome 2000

Th statement of the task
http://www.spoj.com/problems/IOIPALIN/

his task can be solved by looking at it from different point of view. We can easily turn this task into a classic LCS (longest common subsequence algorithm). This will be the formula for finding out answer
answer= n- LCS(given string, reversed string of the given string)

You can find about finding the LCS here.

NOTE: I was getting TLE many times because of a simple problem. LCS has n^2 complexity, It is perfectly fine because 5000^2 will fit in 1 second but there is one problem. The LCS algorithm suggests to keep a matrix of NxN when the matrix gets full the processor runs slower that is why you may get TLE. For this you need to do a simple trick. We don't need to keep the whole 5000x5000 array. In every step. When we are at the row I, we use only the row I and I-1 . So instead of keeping 5000x5000 array we can keep only 2x2000 array and solve it there.

DOWNLOAD THE FULL SOURCE CODE

Minimum insertions to turn the string into palindrome

This task can be easily brought to another task of finding the length of the string minus the Longest Common subsequence of the given string and the reversed string of the given string.

In other words our answer will look like this

answer= n- LCS(s, reversed s);  ////n is the length of our string

Infomration about finding LCS can be found here

LCS(longest common subsequence)

As we all know dynamic programming works like this.
1. Divide the big problem into smaller subproblems.
2. Solve the current subproblem with the use of previously found solutions.

We have 2 arrays of char char s1[N],s2[N]; and we want to find the longest common subsequence of those strings.
For finding the longest common subsequence we will keep an 2 dimensional array (matrix) int a[N][N]
and a[i][j] will show us the length of the longest common subsequence of  sequences
s1[1],s1[2],....,s1[i]
                         and
s2[1],s2[2],....,s2[j]

This is the pseudocode of our algorithm

for i =from 1 to n    ////n is the length of the first sequence
for j =from 1 to m   ////m is the length of the second sequence
if(s1[i]==s2[j])
       a[i][j]=a[i-1][j-1]+1
else
       a[i][j]max(a[i-1][j],a[i][j-1]);
Example with explanation

	S	R	J	M
T	0	0	0	0
S	1	1	1	1
R	1	2	2	2
M	1	2	2	3

Suppose we have 2 strings s1="SRJM" and s2="TSRM"
a[1][1] shows the longest common subsequence for 2 strings "T" and "S", the string letter "T" is not equal to the letter "S" so we mark a[1][1] as 0. The same goes for the letters "R" "J" and "M"

lets get down to a[2][1]  . a[2][1] shows us the longest common subsequence of strings "TS" and "S"
as we can see we marked it as 1. The pseudocode says if s[i]==s[j] then a[i][j]=a[i-1][j-1]+1; =>
=>a[2][1]=a[1][0]+1 (All the elements are marked as 0 from the beginning)
Now we are at the cell a[2][2] which means that we need to look at 2 strings "TS" and "SR" . The letter "S" is not equal to letter "R" which means that we have to pick up the value of the longest common subsequence of either "T" and "SR" or "TS" and "S" . The second option has bigger value that is why we pick the second option which is a[i][j-1];

The full source code is also available for free download

DOWNLOAD THE SOURCE CODE 

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

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

iterators

Suppose we have a vector consisting of 4 elements. Suppose this is our computer's memory

******************************

******************************

******************************

******************************

******************************

******************************

* shows that at that spot of the memory some data exists.

When we declare a vector and give it 4 elements in memory it is not going to be in some special order. It may be like this

**********v[0]*******v[1]

**********************

***********************

v[3]*******************

********************v[4]

As we can see even if the creators wanted to avoid creating iterator and at the same time they tried to find  a way of calling the elements , they couldn't succeed because the way the elements are scattered in memory is not certain. 

The iterator itself returns you the position of the element we are looking for. It is not an integer, it is a separate data type. It is made in a special way. In our representation of computer memory suppose iterator is a pair of integers defining the row and the column of our element. the iterator for v[0] will be 1 and 12. (1st row and 12th column)

When we add 1 to our iterator (which is a legal move, adding an integer to iterator) the iterator will automatically jump from the 0th element to the 1st element and the new value will be  1 and 20(1st row and 20th column). 

Iterator is defined this way

Data_type_of_our_iterators_target::iterator name_of_iterator;

example

vector<int>::iterator it;

Example of using iterator

for(it=v.begin(); it!=v.end(); it++)

{

       cout<< * it<<endl; ( we wrote * because the iterator itself is a pointer)

}

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

As3. Setting up the enviroment

For coding in as3 you will need Adobe Flash Professional cs 4/5/5.5/6

Download Adobe Flash Professional CS 5.5 torrent file

Do the installation . It's very easy.

You will get a 30 day trial after installing it. Here is the list of serial keys for using in Adobe Flash professional installation 

Download the list of Serial keys for adobe flash cs 5.5

When you are done with installation proceed to next lesson.

IF YOU HAVE ANY QUESTIONS OR PROBLEMS LEAVE THEM IN COMMENTS, NO QUESTION WILL E UNANSWERED

finding all prime numbers in [1;N] for O(nlogn).the sieve of Eratostenes

Suppose we need to find all prime numbers between 1 and N. Usually we check if the number is prime by looking at the numbers from 1 to sqrt(K) (K is the number we want to check for). If we want to find all the prime numbers between 1 and N using this method we will have a time limit problem. It will take N*sqrt(N). There is a better way of finding the number in NlogN time. For this we will need a boolean array A[N]. A[i] will be false if the number i is prime otherwise it will be true.
 Here is the pseudocode of the sieve of Eratosfen.
    for(i=2;i<=N;i++)
    {
         if( a[i] is false)
         {
               mark all the divisors of i as true.
         }
    }
lets look at that on a small example
1 2 3 4 5 6 7 8 9 10
f  f  f  f  f  f  f  f  f   f
 number 1 is not prime but we will keep that as false.
Now our loop will continue until it meets a false value. It is the number 2.
2 is prime so our condition is met. Now we know that every number which is divisible on 2 is not a prime number . We go through the number form 2 to 10 and check if the current number is divisible on 2 we mark it as true ( not prime).
1 2 3 4 5 6 7 8 9 10
f  f  f  t  f  t  f  t  f   t
Next step is checking 3. 3 is false which means that 3 is prime so we do the same action again.
We loop through all the numbers and mark the numbers which are divisible on 3 (except 3 himself)
1 2 3 4 5 6 7 8 9 10
f  f  f  t  f  t  f  t  t   t
Now we are checking 4. 4 is true which means that we know that 4 is not prime.
We move to next step.
5 is false so we have to mark all the number which are divisible on 5
1 2 3 4 5 6 7 8 9 10
f  f  f  t  f  t  f  t  t   t
So, we got that 2,3,5,7 are primes in 5*log10


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

finding the greatest common divisor of 2 numbers in O(logn).Euclid's algorithm

We usually find the greatest common divisor of 2 number in this way. We find the prime factorization of two numbers.
a=p1^a1*p2^a2*....*pn^an
b=q1^b1*q2^b2*...*qn^bn
And we choose common prime factors and multiply them to find the greatest common divisor. There is a better approach to this problem.
   We will call the function of finding the greatest common divisor GCD(a,b).
   Euclid's algorithm suggests that GCD(a,b)=GCD(a%b,b) (When a is greater than b)
   Here is the code for finding GCD(a,b);
    int GCD(int a,int b)   // we consider that a is greater than b from the beginning
    {
          while(b>0)
          {
                a=a%b;
                swap(a,b);/// because we considered that a is always greater than b and it is clear that a%b<b)
          }
          return a;
     }

          

Calculate a^n (a power of n) in O(logn)

   We can always calculate A^N by multiplying A with A N times.

    ans=1;

    for(i=1;i<=n;i++)

    {

            ans=ans*a;

     }

This will take O(n) time. There is another way of calculating A^N in O(logn) time.

We can translate the code above in a different way.

    ans=1;   

    while(n>0)

    {

         ans=ans*a;

         n=n-1;

     }

The code above "means" subtract 1 from n until it reaches 0 and in the same time multiply the answer with a.

As we know from our math classes A^B*A^B=(A^B)^2= A^(2*B).  Using this we can cut our N into half (if it is an even number) and instead of multiplying our answer with a we will simply multiply our answer by itself. 

   ans=1;   

    while(n>0)

    {

         if(n%2==0)

         {

               ans=ans*ans;

               n=n/2;

         {

         else

         {

               ans=ans*a;

               n=n-1;

          }

     }

The code is generally right , but there is one problem. If n is divisible on 2 from the beginning we will get a wrong answer because of the following.

when ans=1  and n%2==0 ( n is divisible by 2) we will cut n into half but the answer won't change becuase 1*1=1

   So we better  begin with ans=a and n=n-1

    ans=a;

    n=n-1;  

    while(n>0)

    {

         if(n%2==0)

         {

               ans=ans*ans;

               n=n/2;

         {

         else

         {

               ans=ans*a;

               n=n-1;

          }

     } 

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

   

     

Euler function

Euler function

   Euler function is often called a function phi(n) shows the number of integers between 1 and n which are coprime with n. 

E(1)=1;

E(2)=2;

E(3)=3;

...

...

...

The Euler function can be calculated with prim factorization but here are some tips on calculating it faster.

1. If p is prime than E(p) = p-1 because every prime number is coprime with every number except itself.

2. If p is prime and a is an nteger than E(p^a) =p^a_ p^a-1   

3. If a and b are coprimes then E(a*b)=E(a)*E(b)

If  n=p1^a1*p2^a2*p3^a3*....*pn^an = (p1^a1-p1^(a1-1) ) * (p2^a2-p2^(a2-1)) * (pn^an - pn^(an-1)) = n * (1-1/p1) * (1-1/p2) * (1-1/p3) * ....* (1-1/pn)

Here is the function in C++ for calculating euler function

int phi (int n)
{
   int ans=n;
   for (int i=2; i*i<=n; ++i)
   if(n%i==0)
   {
while(n%i==0)
    n=n/i;
     ans=ans-ans/i;
   }
   if(n>1)
ans=ans-ans/n;
 return ans;
}

Binary search. checking for the existance of an element in O(logn)

Suppose we have an array of length N. All the elements are sorted in an ascending order. We have also another number M and we want to find that number in our array. We can use a simple linear search buy just looping from the first element to the last one and check if we can find the number M or no. This algorithm has a complexity N. An average computer can do 10^8 actions in one second so if our N=10^11 we will wait for 1000 seconds until we get our result.

    If we use binary search for the same purpose we will have to wait log(1000) seconds which is nothing compared to 1000. The binary search algorithm suggests to divide the array into half every step. We declare to variables showing from where to where we are searching. To make it more clear initially we have 2 variables P and Q. P will show the left border while Q will show the right border. Initially P=1 and Q=N; now we take the middle element which has an index of (P+Q)/2.  We compare that middle element to our element M. If we get as a result that M is grater than the middle element we don’t need to search on the first half anymore. So we update the value of P and make it the middle index and we do the same actions for the new updated P and Q until P equals to Q or, P and  Q are different only by 1. Lest do it on an example.

We need to check if the number 5 exist in our set of elements or no.

Note

We will determine “the first half” as the first half  of the elements between P and Q and the “second half” as the second half of the elements between P and Q.

Step 1

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q	P								Q

Now we take the middle element which is (1+9)/2 = 5

The 5^th element is 20 . Now we can say that 20 is grater than 5. Note that the elements are sorted in ascending order which means that we don’t need the second half any more.  We just found out that our element is not on the first half in only one step. We update the value of Q giving it a value of (P+Q)/2 .

Step 2

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q	P				Q

Now we again need to check the middle element between P and Q which is the third element. The third element is 7. 7 is greater than 5 so we don’t need the second half again. We update the value of Q giving it a value of (P+Q)/2 .

Step 3

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q	P		Q

And again the same way. We take the middle element and compare to 5. Now its less than 5 so this time we don’t need the first half. We update the value of P .

Step 4

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q		P	Q

Now we can see that there are no more numbers between P and Q. So we can say for sure that there is no element which is equal to 5.

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