Dealing with extremely big numbers.

Suppose we need to calculate the sum of 2 numbers. Seems pretty easy task but when we are han\ving a look at the constraints whichs say "both numbers are integers up to 10^1000", the task becomes difficult.
   For dealing with big numbers we need to use the knowledge from our 1st grade when teacxhers showed us how to sum up numbers . We need to write them one under another and sum up the digits, if we are getting a number bigger than 9 then we subtract 10 from that number and we keep 1 in mind and then we add that 1 to the second suming of digits.
        12344
     + 56666
     = 69010
So now a little bit about implementation,. We need to use arrays to solve this. We have to keep arrays where every element is a single digit of a given number and then , using a simple loops, we iterate over our array summing up the digit and keeping some numbers for suming up on next turn if necessary.         

SPOJ 130. Rent your airplane and make money

Here is the problem statament

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

2 thigs we will use in this task 1. Dynamic Programming 2. Binary search

First of all we sort our array by the start time. 

Suppose this is our array

s1 e1 c1 (start, end, cost)

s2 e2 c2 

...

...

sn en cn

Then we will keep our array for dynamic programming approach, we call it dp. As we all know, for dynamic programming we need to build our current solution based on the ones we got from our previous operations. We need to loop from back of the sorted array. When we are on I th element. We need to find the leftmost element which is on the right side of I ( index is grater than I) and the start time of that element is more than the end time of our current element( AKA we can take the Ith order and the order which we found with this step). That will be element with the index J. So we are sure that the orders from J-1 to I+1 can't be taken If we take teh order I. So does it worth it? That makes our dp[I]= max (dp[I-1], dp[J]+cost[I])  (AKA we either reject this order and take the profit we already collected ,or we reject all the orders from I+1 to J-1 to take the order I).  Make sure to check the source code for a better understanding ,

       DOWNLOAD THE FULL SOURCE CODE 

SPOJ 7733. Happy Numbers I

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

This task is a task of implementation with a little bit of care. We can always calculate the sum of the squares of digits of a number. We will keep doing this until our number reaches 1 or it reaches a number which we already processed before . For keeping track of numbers we already processed we will keep a boolean array called mark and we will mark the indexes of this array as true if we process a number. Example
we are on number N. we write mark[N]=true   And we constantly check if mark[N] is true (AKA we have already processed it) that means that thegiven number is ont "happy number". We don't need to keep a boolean array of 2,147,483,647  because of the following. There are 10 digits in this number. Even if all of them were 9s (maximum value) the second number was going to be 81*10=810 so tha mark array of size 900 is completely enough.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 902. Hangover

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

 Just because the constraints are 5.2>N>0.02 this task can be solved with a simplem implementation. Just loop from 2 and add to our current legth the 1/i (i is our current loop value)/ If we reached the value print the index and exit.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 7424. Girls and Boys

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

We nned to pick the smaller number form the two given numbers, let's assume its the number of boys which is smaller. We take the boys and distribute them in a girl sequence in a way so that the repetition can be minimum. Lets look at an example
bbb
ggggggg
We have 7 girls and 3 boys. It is possibleto ditribute the boys in a way so that there will always be at  2 consequetive girls at best. Example
ggbggbggbg

The formula for this is
answer= ceil( max(a,b)/(min(a,b)+1)) (ceil means divided and rounded up)

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 4408. Build a Fence

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

It is obvious that we can obtain the biggest area with formaing a half cyrcle.

As shown in the picture, the yellow part is the area we get and the black part is the wall.
The formula for calculating the area of a cyrcle is pi*r*r. Just because its a half cyccle we need to calculate (pi*r*r)/2

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 11. Factorial

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

 N!=1*2*3*4*...*N
If we factorize N we can be sure that there are more factors 2 than factors 5*5=10 (ends in 0 ) so in other words we need to find the number of factors 5 in N!. The obvious approach is looping over number from 1 to N and every time we meet a number which is divisible on 5 we calculate the number of 5 factors and add them to our answer. Unfortunately it won't pass the time limit.
Let's have a look at  a few numbers.
N=27;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
I suggest that the amount of numbers divisible on 5 is N/5 ( / means divided without taking the remainder) 27/5=5 and which is true.
I suggest that the amount of numbers divisible on 25 is N/25.   27/25=1 and which is also true. So our final formula will look like this
ans= ans+ N divided to all powers of 5 which are less than N)

       DOWNLOAD THE FULL SOURCE CODE 

1025. Fashion Shows

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

Obviously we will get the maximum answer if we put the bests together, the maximum with the maximum and the minimum with the minimum. Only thing we need is to sort both arrays and start multiplying all the pairs with the same indexes.

       DOWNLOAD THE FULL SOURCE CODE

    

SPOJ 9788. Friends of Friends

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

Some commets that you can use STL set to solve, of course its a good choice but we can do it in a simpler way(without using STL). Just because the numbers are 4 digit numbers , we can just keep a boolean array , and every time we read a number A (the number of a friend's friend) we mark Mark[A] as true. Then at the end we loop from 1000 to 9999 and calculate the number of marked spots. Its is shorter when you are using STL but this way is safer :) .

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 9655. Elevator Trouble

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

This task is solved witha  simple BFS implementation. (For more information about BFS go here). Just keep the list of already visited floors and check if you reached the needed floor stop the BFS else look at all of the neighbours of the current floor( The neighbours are the floors which can be visited from the current floor. NOTE Every floor can't have more than 2 neighbours).

       DOWNLOAD THE FULL SOURCE CODE

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 1688. A Very Easy Problem!

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

I am posting tutorials about spoj tasks which will give hints and help the reader to figure out himself vut on this task I can't give anything but the correct answer, If you already triedmany times and you want to know the answer then keep on reading.

The 2(...) means the power of 2. This is all you need to know. The rest is up to you

   There is no source code this time :)

SPOJ 10509. Cards

Here is the problem statament
http://www.spoj.com/problems/CRDS/

The pyramid of  level N is being build in this way

/\ /\ /\ /\ /\ (N /\ s)
then between every pair we put one more card on theit tops and then we put n-1 /\ s and again and again until we reach the final level .
Here is a picture

As we can see easily we need n-1+n-2+n-3....+1 cards for building the "floor" (cards that we put on pairs to form a floor the horizontal cards) and 2*(n+n-1+n-2+....+1 ) cards to build the /\ pairs. The formula for calculating the sum of numbers from 1 to k is ( k*(k+1) )/2 .
Be certain that you do the division first because the numbers are too big you might get a wrong answer.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 6818. Capital City

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

The graph is directed. (If you need information about directed/indirected graphs go here)/ As you can see from constraints we need to figure out a N*LogN solution or something close to that. The first thing we wanna do is keeping a second graph with reversed edges. We need to loop over all the nodes and run a BFS in the following way. (We are looping over the graph with reversed edges). Initially we keep a mark array for the reversed graph. If the current node is unmarked we start a wave (BFS) from that node (in a reversed graph). If we reached all the edges that means that the current node can be a capital city and we need to launch another wave (BFS) in the initial graph and add all the nodes which are reachable from the current node to the asnwer list. We do the exact opposite( mark it as not capital) if on the reversed graph cannot reach all the nodes.  MAKE SURE TO CHECK THE SOURCE CODE FOR OTHER IMPORTANT DETAILS

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 2149. Baised Standings

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

Th task is a simple calculation. We need to get only the numbers. (We can ignore the names, they are just made to ruin our code and fill them with strings :D ) . Now we get all the numbers and sort them. And then calculate the difference between the I th element and I  and add it to our answer. This way the so called "badnes" will be minimal.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 96. Shopping

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

I suggest a way which is not fast enough( you won't be the first in the best solutions field :) ) but works great. This is done by a simple BFS ( you can find information about BFS here) but in a different way (without queue). Initially we keep an array which we will call ans (the array of answers) and the field ans[x][y] will show the minimum cost of getting to the point (x,y) . Initially all the elements are equal to infinity ( to a very larg number which we will call INF). We give our start point the value of 0. Then we loop over our array N*M times ( this is the worst case) and every time we loop we check if the current point we are on is not equal to INF we check its neighbours and update the value if necessary. Then we output the value of ans[x2][y2] where (x2,y2) is the destination point).

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 2727. Army Strength

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

This task is very simple. We need to understand one simple fact. No matter how many monsters there are on the field at each teams the winner team will be the team which has the strongest monster because even if the strongest monster is left alone, every step he will kill the opposing monsters until the battle is over. (If you need information about finding maximum/minimum in an array, go here.

       DOWNLOAD THE FULL SOURCE CODE

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 

SPOJ 10232. Distinct Primes

This task can be done using a simple implementation . Just find all the primes, for numbers buy multiplying 3 primes and then for each numbed found , multpily it again with the same primes we used from the beginning, and then when we got a list, we can sort it and we are ready to read the input and output the asnwer right away. But first for doing this we need to make sure that for n=1000 the number needed won't be too great. 

The primes are 2,3,5,7,11,13,17,19,23,29,31,37.41 Our initial numebrs are going to be made by multiplying 3 different primes. It is not hard to notice that the 1000 th number is not going to be formed with a greater number then 41. So we can be sure that a simple  brute force solution will pas the time limit easily.

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 10565. Alice Sieve

Just take a piece of paper and a pan and try to do that on a few examples. Its is not hard to notice that for even Ns the answer is N/2 and for odd Ns the answer is (N+1)/2.

TRICK FOR  SOLVING THIS TYPE OF TASKS

If the task has a very little input (one or two numbers) and has a little output and the constraints are very high, it is simple to understand that there is a special trick for that,we need to input the numbers and by using a formulas or some relationsships output the result right away. 

 The trick is the following.Write a simple bruto force solution and output the asnwer for N from 1 to 100 or 1000 ( choose the amount appropriately) and they you will be able to notice the special trick.

    DOWNLOAD THE FULL SOURCE CODE

  

BFS (Breadth First Search)

 The BFS is used to find a shortest path between 2 points of the graph. The C++ STL  queue. Consider these steps for the BFS algorithm. Suppose we want to find the distance between nodes X and Y.
We need to use a pair, the first element will show the current node and the second element will show the distance between the nodes X and the node we are currently in.
Step 1 . Add the first pait to the queue . The first element of the pair is X and the second element of the pair is 0. (The distance between X and X is 0 : ) ).
Step 2 On every step check all the nodes which are neghbours with node X . If the node we are checking is not visited ( every time we add a node to our queue , we mark it as visited so that we won't have to visist it again) we add that node to the queue and the distance equals to the distance which is required to reach teh neghbour of that node + 1.
Step.3 Do the second step until you reach the node Y (note that whenever you reach the node Y you should stop the process because the found distance is the shortest).

The pseudocde
Suppose we have queue q;

q.push(x,0);
while( q is not empty)
{
        take the first element of the queue.
         node=the first elemnet of q.top()
       distnace = the second element of the q.top()
       for(i=0; i< neighboursnumberl i++)
               If ( neighbour is not visited )
                   q. add element( neighbour, distance+1)
      remove the first element of queue
}

And also check if you reached the Y node or not. If you reached it there is not point in continuing our loop,