SPOJ 4141. Euler Totient Function

This task is a task about euler's function, you only need to know the Euler function to solve it. If you need information about Euler's function go here. Also, don't precalculate the values and store in array , count the answer after you read teh number so that you can avoid TLE.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3923. Philosophers Stone

Here is the problem statement .

We will solve this problem with dynamic approach mening that we will get the solution for current cell (X,Y) with the help of (X-1,Y) (X-1,Y-1),(X-1,Y+1). We will call teh given array A. We will also keep another array B where B[i][j] will show that maximum number of stones we can collect . INitially every element of the first row of the array B equals to every element of the first row of array A, the others have a value of 0. Now we need to loop over array B and for every coordinate (X,Y) we need to see if we can update B[X+1][Y] , B[X+1][Y-1] or B[X+1][Y+1]. Then we need to find the maximum of the last row of the array B and print it out.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 9948. Will it ever stop

Here is the problem statement.
In this problem we need to notice that it will stop if at some point n will be 2 and with teh first if statement it will turn 1 and the cycle will break. If N has divisors other than the powers of 2 => that the cycle is unbreakable. So we only need to check if the given nurmber is a power of 2 or not.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10798. Wachovia Bank

Here is the problem statement.

This is another classical dynamic programming problem called Knapsack Problem. If you need information about knapsack problem with 2 parameters go here

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1724. Counting Triangles

Here is the problem statement

This problem is one type of a problem which I can't explain. You just need to take pen and paper , draw a few examples and the solution will pump up on your brain. SO If you tried many times and very tired of it I can give you the formula.

Here is the formula

A[N]=  ( n*(2*n+1)*(n+2)   )/8

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1. Life, the Universe, and Everything

Here is the problem statement

There is nothing to say about this problem, you only need to now the basics of your favourite programming language to solve it. Here is my solution written in Pascal.

     

SPOJ 11573. A Famous ICPC Team

Here is the problem statement.

Just because the heights are the same, this task is a very simple one. Those are out numbers A1,A2,A3,A4. We need to sort them in increasing order, suppose we got B1,B2,B3, B4. Now if we take the needed side of a value B3+B4 we can absolutely be sure that all of them wu\ill be fit without overlapping.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3375. Stamps

Here is the problem statement

Obviously for bothering as less friends as possible we need to start taking from friends which offer the most so that we can reach our required amount as fast as possible.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3410. Feynman

Here is the problem statement

This problem needs noticing. We need to notice the following connection between the I and I+1 the papers.
For N=1 the answer is 1
for N=2 the answer is 5 , the 4 little squares and the big one.
We need to notice that the answer for N=3 is as follows 3*3  (the number of little squares) + A[N-2] (the number of the rest squares which are formed with more than 1 little square equals to the number of totalt squares of the previous answer).
In other words
A[I]=I*I+A[I-1]

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 39. Piggy-Bank

Here is the problem statement.

This is another classic problem of dynamic programming called Knapsack problem with 2 parameters. Read about knapsack probelm with 2 parameters here.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 97. Party Schedule

Here is the problem statement.

This problem is a classic problem of knapsack with 2 parameters. Check for teh algo Knapsack with 2 parameters here.

       DOWNLOAD THE FULL SOURCE CODE

Knapsack problem with 2 parameters

The knapsack problem with 2 parameters is very close to the knapsack probelm with 1 parameter.
The problem is as follows
 We have a bag which can carry up to M kilos. We have N items where each item has a cost and has a weight. We need to fill our bag in a way that we can have the maximum cost and the overall weight must not exceed M.
 Just like in Knapsack with 1 parameter where we kept an array of trues and falses we will keep an array but this time an array of integers not booleans. Suppose the name of that array is A. The value of A[K] shows the maximum cost of the items which have a weigh K together.
Here is a pseudocode
   Suppose we have 2 arrays
   COST[N]
   WEIGHT[N]
    and our array of answers A.
for(i=1;i<=N;i++)
    for(j=m;j>0;j++) //we start from the end because in this task the number of items of each type is 1 , if there were infinite items we were going to start form the beginning
     {
              if( j+WEIGHT[i] <=m //checking if the combination is possible AKA smaller than M// and A[j+WEIGHT[i]]<A[J]+COST[I]   // If the new combination is better than the one previously collected//)
                   A[j+WIEGHT[i]]=A[k]+COST[i]; ///update the new combination
    }

SPOJ 500. Turbo Sort

Here is the problem statement.

There is not much to say about this problem. The function "sort" in libriary <algorithm> in C++ covers this up. Nowadays the modern programming languages provide the opportunity to use already created sorting functions which are really fast working. You can look on internet and read about quick sort and merge sort , those are the quickest ones.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10186. Divisor Digits

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

In short, the problem wants us to find the number of digits which the given number is divisible by. The tasl is easy, you only need to check for all digits on by one with the divisibility rules you learnt in your early math grades.
1-The number is always divisible by 1
2-If the number ends with an even number the number is divisible by 2
3-If the sum of digits of the number is divisible on 3 then the number is divisible on 3 as well.
4-If the number formed with he last 2 digits of a given number is dvisible by 4 then the whole number is divisbly by 4
5- If the number ends eaitehr with a digit 0 or with a digit 5 its divisible by 5.
6- If the sum of the digits of teh numebr is divisible by 3 and the number is even that means that its divisble by 6
8- If the number formed from the last 3 digits of the given number is divisible by 8 , the given number is divisible by 8 as well.
9-If the sum of digits of the number is divisible on 9 then the number is divisible on 9 as well.
 I left 7 on purpose. The divisibility on 7 is very tricky, I think I can mess up If I try to explain it, I found a good explaination here.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 8725. Closest Point Pair

Here isthe problem statement
http://www.spoj.com/problems/CLOPPAIR/

The constraints are N<=50000. The most obvious approach is to use brute force in other words for every coordinated run over the others and update the answer if possible. This takes N^2 time which won't pass the time limit. Here is what I suggest. We will do just something like this but  with a little "saving". First lets sort our coordinates by x. Suppose we have a variable ANS where we store the minimum distance. Ok . Now we take the first coordinate in a sorted array . And we start comparing it to others. Here is the pseudocode

for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
     compare distance of coordinate i and corrdinate j and update the answer.

By just adding one more if statement we can get our code to work in way shorter time. As we know the distance between every pair of coordinates is sqrt (  sqr(x1-x2)+sqr(y1-y2) ). I recommend not using the sqrt function every time. We will use it in the end for outputing the answer, the sqrt function is slow and we might lose the correctness in it. So, back to our problem, we check if current distance between Xs of 2 corrdinates squared is gerater then the answer we have so far we brake the loop because the higher the index J becomes the higher X .
Here is how it looks
 for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
    {
         if( sqr( a[i].x-a[j].x) >ans)
             break;
     compare distance of coordinate i and corrdinate j and update the answer.
    }
This will save us significant amount of time, its enough to get the time limit passed. Check teh source code for clarification.

       DOWNLOAD THE FULL SOURCE CODE

Knapsack problem with 1 parameter

The probelm statement

We have a bag which can carry upto M kilograms of weight. We have N different items each with its own weight. We need to get out bag as full as possible. What is the maximum wieght we can carry?

 Sample

    5 20

   4 10 7 1 8

Here M is 20 and there are 5 elements to choose from . Here is the algorithm, we keep a  boolean array . The element I will show If we can collect the weight I . 

Initially all are marked as false. 

 for i=1 to N

mark[a[i]]=true;

because we can collect a weight equal to every element of the main array.

Then we need to loop over our mark array from back (If we can use one item multiple times then we need to loop from the beginning) and when we came to an element which has a value of true (suppose the index of that element is I) we need to loop over our given array and turn mark[I+a[j]] into true => If we can collect the value I we can also collect teh value I plus one more given element.Then we just need to find the biggest element which has a vlue of true in the mark array and is closest to M.  

SPOJ 7742. Onotole needs your help

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

This task is one of the best tasks in my opinion. At first its not what it looks like but we will need to use only the bitwise operator ^ (XOR). (If you need more information about XOR go here). I am givign you only on good hint. Notice the following , suppose we have 2 number X and Y . If we XOR X and Y we will get some number and when we XOR the new number with the number X we will get Y . Its like Y is being reversed and then reversed again. So if we XOR all the numbers we will get the one which was XORed only once :) .

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 2178. He is offside!

Here is tehe problem statement
http://www.spoj.com/problems/OFFSIDE/

This is another average implementation tasks. The constraints are low . Just find teh second maximum of the second array ,either by sorting or by using maxiumum finding algorithm 2 times and then compare that to all of the first array's elements.Check teh source code for more clarification.

      DOWNLOAD THE FULL SOURCE CODE

SPOJ 1112. Number Steps

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

This task is full of stuff that need to be noticed. Suppose the give coordinates are X amd Y. First of all notice that the the number exists only when x==y or x==y+2. Then you need to check for one more thing. Notice that if x is an even number the answer is x+y else its x+y-1

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10639. The Blind Passenger

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

This is yet another implementation task. SUppose we have the  number N. Obviously the number of the row is N/5.(don't forget to subtrac 1 just as soon as you read it because of the conductor's place :) ). Then we need to check if the numeration on our found row is from left to right or vice versa. On the rows with odd index the numeration is from left to right and on the even ones from right ot left.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 15208. Minimum Cost

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

The costs of removing element sometimes confuses the solver. What if I told you that the cost is not changing making it difficult? Its just a number made up by the task creator. Note that for making them equal we need to delete some amount of chars from both of them or from one of them but the point is that there is only one way of doing that. We need to calculate the LCS longest common subsequence of both of them . The counted LCS is the string which is going to remain after we remove some chas from both of the, The answer will be (If we consider the length of LCS L) ANS=(s1.size()-L)*15+(s2.size()-L)*30; If you need more information about LCS go here.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 7745. Bingo!

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

If we have a look on the constraints we can see that N<=90 and the number are in this interval as well. We just need to make a double loop and mark every number we can generate. Then can check if all the numbers are marked => we can get every single  number between 1 and N then we output "Y" else we output "N".

       DOWNLOAD THE FULL SOURCE CODE

       

SPOJ 6171. Majority

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

This task is another implementation task. It can be done using both arrays and maps. I prefer the first option because its easier to implement. The numbers are low so you can just read the input and somehow keep that you read that number once and then add up that number every time you come across to it again.
Make sure to check the source code for implementation details.

      DOWNLOAD THE FULL SOURCE CODE

SPOJ 5699. The last digit re-visited

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

This probelm is similar to the probelm The Last Digit (LASTDIG), here I wrote about it as well.
 For solving this task you need to know one thing, Have a look at teh table below

Number	1 power	2 power	3 power	4 power
1	1	1	1	1
2	2	4	8	6
3	3	9	7	1
4	4	6	4	6
5	5	5	5	5
6	6	6	6	6
7	7	9	3	1
8	8	4	2	6
9	9	1	9	1

As you can see, teh last digit of every number's power will be repeated every 4 powers at best. You just need to take the remainder of b divided on 4 and output the answer according to this table. 

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3442. The last Digit

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

For solving this task we need to notice one thing . Have a look at the table below

Number	1 power	2 power	3 power	4 power
1	1	1	1	1
2	2	4	8	6
3	3	9	7	1
4	4	6	4	6
5	5	5	5	5
6	6	6	6	6
7	7	9	3	1
8	8	4	2	6
9	9	1	9	1

The table above shows you teh last digits of numbers from 1 to 9 .For every number the last digit will be repeated after the 4 th power at best. So you just need to check the remainder when b divided on 4 and output the answer according to this table. 

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 13651. Check

The problem statement
http://www.spoj.com/problems/KNGCHECK/

This is another great task of implementation. We ned to loop all over the board and check for every single white figure and check all the cells that figure can attack and the output the answer accordingly. Make sure o check the source code for some details.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 12150. Just Next !!!

Here is the probelm statement
http://www.spoj.com/problems/JNEXT/

This probelm is a simple problem of finding next permutation. you can either use the function given by C++ mext_permutation or you ca implement your own next permutation algorithm. ( If you need information about next permutation algorithm go here

       DOWNLOAD THE FULL SOURCE CODE

Finding the next permutation of a sequence

In C++ there is an easy command for finding that. If you have an array of numbers. Just include the library called algorithm and use the function next_permutation( a+x,a+y); this means find the next permutation of elements in a sequence a from x to y. Vut if you wanna know the algorithm of this just keep on reading.

   Consider these numebrs 1 2 3 4 5 . This is the first permutation of number 1 2 3 4 5 . Here are the steps of for calculating next permutation. 

1. Loop over array backwards until you find the first element which is bigger than his neighbour. Suppose that element has an index of I. 

2. Swap the elements I and I-1.

3. Sort the number between indexes I+1 and N (N is the length of our sequence).

Example

 2 3 1 5 4

The first element which is greater than its neighbour is 5. Swap 5 and 1 . We will get the following sequence

2 3 5 1 4

Sort the number from 4 to 5 .

2 3 5 1 4

This is the next permutation of the sequence 2 3 1 5 4. 

SPOJ 2905. Not a Triangle

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

A triangle can be formed (including degenerate triangles) if sum of 2 sides is always biger or equal to the 3rd side. So , we will take pairs and for every pair we will find the number of the other sticks which are greater than the sum of our pair. For doing that fast the first thing is sorting. We need to sort our array . Then after that we need to consider every pair, for every pair find the leftmost element which is greater than the sum of that pair. Suppose that is the element with index I. So if our array is sorted and I is greater than the sum of our current pait, we can say for sure that the elements I+1,I+2,....N are also greater than the sum of our pair. To avoid TLE we will find that element with teh help of binary search,

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1436. Is it a tree

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

For checking if the graph is a tree we need to check those 3 things.
1. There are N nodes and N-1 edges. If the numebr of edges is different than N-1 than the graph is not a tree for sure,
2. We need to run a DFS , from any edge we want. If we meet a node which we already visited => the graph has cycles => the graph is not a tree. (  Every time we are on some node, we calculate the number of his neighbours which we already visited, the number must be less than 2 because for the cycles we shouldn't count the node which we were in our previous step. Check the source code for clarification).
3. If the previous 2 steps proved that our graph is a tree we need to check for one more thing. A tree must have only one component, there shouldn't be any otehr trees apart form our graph.

       DOWNLOAD THE FULL SOURCE CODE

DFS (depth first search)

DFS is another search algorithm in graphs. The absic use os this algorithm is finding the "first" way between to edges. It won't be the shortest like BFS. but it will find the first way betwwen 2 nodes. We implement DFS with the help of recursion.
void DFS(int X)
{
    for(i=0;i< number of neighbours of X ; i++)
  {  
     a=current neighbour;
     if( not marked a)
       {    
             DFS(a);
            a becomes marked;
       }
    }
}

        

SPOJ 394. Alphacode

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

We will solve this task with dynamic programming  (we will calculate the current answer with the help of already calculated answers). We will keep an array of answers A. We assume that A[I] shows the answer for the string fromt he begining to the element I. First a[0]=1; a[1]=1; now we loop over the rest fo the elements. For every digit I we check if the number containing the digits I and I-1 is less or equal to 26 we can conclude that the last 2 digits separetaly can be read in 2 ways, we will have our current a[I] equal to a[I-1]+a[I-2] ( we look at 2 different situations, if we look at the last 2 digits as separate letters that leaves us the asnwer of a[I-1] and If we look at them as they were one letter together that leaves us a[I-2])
. If the current digit is 0 or his neighbours are 0 or we can't make a 2 digit number with I and I-1 we assign a[I] tha value of a[I-1];

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 346. Bytelandian gold coins

Here is the problem statement

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

This is a probelm of recursion and memorization at teh same time. Here is the main question, suppose we decided to divide our coin of value N into N/2 N/3 and N/4. Now we have 3 coins, the main question says," Do I need to divide the new coins ito smaller ones for making a bigger profit?" This calls for recursion. For speeding up the time we wil also keep the solutions which we already found so that next time if we come across to the number we already calculate ,we can easily add already calculated answer. Checkthe source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 237. Sums in a Triangle

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

There is not much to say about this problem. The idea is simple , we just keep an array of answers , the we loop over it and update the current element with the best answer ( it would be max( a[i-1][j-1]+a[i][j],a[i-1][j]+a[i][j]) ) The drill ios the source limit. You need to preserver as much as possible . Avoid using many enters, spaces. Don't keep variables which you are not going to use. Make sure to check my source code. Its only 2 lines :D The first is #include <iostream> and the second on is full of operations. Its a long line :)

       FULL SOURCE CODE