Greatest common divisor of 2 numbers.Euclid's algorithm

Here I will explain quickly how to find the greatest common divisor of 2 numbers very fast. First of all Euclid;s algorithm states that GCD(x,y)  equals GCD(x-y,y) which is true for x>y.  But we can improve the performance significantly when replacing the operator "-" with operator % (reminder ) which means GCD(x,y)=GCD(x%y,y) where x>y.

Minimum operations to form a correct bracket expression

The Problem

   We have an expression which consists of opening and closing brackets '('  and ')'. We have 1 operation. We can change any bracket into its reversed one (aka changing this  ')' to this '(' and vice versa). We need to perform the minimum number of operations which can turn it into a correct expression. 

The Solution

 We can solve this using simple Stack of C++ STL. (You can find more info on stack go here). The first thing we need to do is to remove every single correct bracket expression from our given expression. 

For example

1 2 3 4 5 6

} { } { } }

The 2nd and 3rd form a correct expression so we don't need them, that means we can remove them, the same goes for the elements 4 and 5. We will be down to 2 brackets ) ). 

Here is how we will do that

Obviously we can consider a expression correct if there are 2 brackets '( '  and ') ' following one another. For example

 ( ( ) )

When we remove the middle 2 brackets we will be down to an expression ( ) which is also correct.

So here is how stack will help us. We loop over our given string, if the current element is ')' and the top element of the stack is '(' that means that those 2 are correct and we don't need them, otherwise we push teh current element to the stack.

for( i from 0 to the size )

 if(s[i] is ')' and stack.top()=='(')

        continue;

   else

       stack.push(s[i]);

Now we down to a wrong expression which we need to change with minimum number of operations.

I can guarantee that it has this form )))))((((((((( or in other words there are some of this brackets ' )' and after there are some brackets '('. Suppose there are N brackets ')' and M brackets '('. First of all we all understand that the given string must have an even number of elements and the string we just got must have even number of elements as well. Here are 2 things possible If both N and M are even. IN this case we need (N+M)/ operations (by turning the half of those brackets '(' into ')' and turning the half of those ')' brackets into this '(' this, example ))))(( we cant switch the first 2 brackets thus removing the first 4 elements as correct expressions and then change the last element and we get a total correct expression in (N+M)/2 steps. If N and M are both odd ( there is no other case they both either have to be even or odd). Example )))((( then we should switch the middle elements so that we can remove both of them and we will be down to the case were N and M are both even. The total number of operations in this case would be (N+M-2)/2 + 2.

There is a good task in SPOJ which has the same question as this problem.

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

If you want the full source code of this go here.

Josephus Problem

The problem

Imagine that you are in a situation where you and your soldiers are trapped and soon the enemy is going to get you, so you decide that you would rather die than fall to the hands of the enemy. Now you and your soldiers formed a cyrcle and you pick 2 integers D and K. Starting from the Dth spot you count up to K and every time the count reaches K that person standing on the current spot commits suicide. You need to figure out where should you stand so that you will be the last person standing. 

This is a true story which happened in the first century.

Implemetnation

First first of all we need to try the link between the problems A[n][k] and the previous ones. For doing that let's calculate the answer by hand for the first integers. Here is a list of the answers for integers form 1 to 6.

N              K	1	2	3	4	5	6
1	1	1	1	1	1	1
2	2	1	2	1	2	1
3	3	3	2	2	1	1
4	4	1	1	2	2	3
5	5	3	4	1	2	4
6	6	5	1	5	1	4

here we can notice and interesting link

when N is 1 for every K the answer is also 1.

A[I][J]=(A[I-1][J]+j-1)%n+1

Or if we want to turn it into a recursive code here is how it will look like

int rec(int n, int k)

{

       if(n==1)

                 return 1; (because for every K when N is 1 the answer is also 1)

       else

                return  (rec(n-1,k) + k - 1 ) %n +1;

}

Note that the smallest index is 1 not 0.

And here is another non recursive apporach

int ans=0;

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

      ans=(ans+k)%i;

return ans+1;

There is a task in spoj which requires the knowledge of this problem , you can practice what you learnt there. 

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

And here is the link for getting the full source code for the task above if you want to.

finding the longest path in a tree

There is a very good task in spoj which requires finding the longest path in a tree.
Go here to find the link to the task, the explanation and teh full source code for this task.

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
    }

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,




                     

SPOJ 2148. Candy III

This is the problem statement

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

This problem is increadibly easy. You may think that this is a big integer problem (where you have to calculate the sum of numbers using arrays because the numbers won;t fit in the 64 bit integer) but don't worry C++ 's long long (__int64) can hold the answer. We need to calculate the sum of all elements and check if it is divisible on N or no. I am pretty sure that the input can be kept in 64 bit integer and we don't need to calculate the actual sum of numbers. Instead we can calculate the sum of remainders which we get when dividing the current element of N.If the final number is divisible on N output "YES" else output "NO"

   

   

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 2123. CANDY I

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

The answer is -1 when the sum of all candies is not divisible on N. We know that every pack must contain sum/N which means that we need to loop over every pack and check for the difference between sum/N and the current number of candies in the current pack. But after this we will get answer 2 times more because of this . Consider a simple test case of N=2 and a[1]=1 and a[2]=7
so every pack must contain (1+7)/2 =4  our program will calculate the number of candies which will be removed from the second pack and added to the first and also the number of candies that the 1 st pack must get which gives a total of answer which is 2 times more than the actual answer,

   DOWNLOAD THE FULL SOURCE CODE

prime factorization

Prime factorization is a representation of a number as a multiplication of prime numbers.

If the problem you are solving has many test cases you better use the method 1 otherwise use the method 2.

Method 1 slow but useful when you need to factorize many numbers

Generate all the prime numbers in the needed range using the sieve of Eratosphen (which takes O(NlogN) ).
Now loop over the array of found primes until the number gets smaller than the current prime and check if the number is divisible on the current prime. If yes then divide the number into the found prime until it becomes non-divisible on that prime.
Here is the pseudocode

suppose we have the array of found primes called prime[10000]
and our number is N
for(  i=1 continue until a[i]<N)
{
        if( N is divisible on a[i])
        {
             divide N on a[i] until N becomes non divisible on N and keep track of the number of divisions
         }
}


method 2

Loop over numbers from 1, and our loop will end until our N becomes 1. If we found a number on which is divisible on and divide N on that number until it becomes non-divisible to that number. This method works the  same way as the previous method does. Of course the first number which we will find will be prime and other numbers won't be divisible on already found numbers.
 Use the method 1 if you have a problem which requires to factorize many numbers, if you have one big number you better use the second method.




              

SPOJ 11736. Prime Time

Here is the problem statement
http://www.spoj.com/problems/PTIME/
 Let's have a look at constraints. N<=1000

N!=1*2*3*4*5*6*...*N

We can just loop over numbers from 1 to N and factorize them, then sum the found powers of prime factors and output them in the right order which is. The factorization takes O(sqrt(N)) time. You can find information about prime factorization here.

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 1786. In Danger

Task statement

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

First of all this task requires a very special approach. If the task usually has one input and one output and the constraints are very high, you should understand that the solution is a simple formula or something close to it. I recommend writing a simple brute force solution for the first 1000 , print them one after another and you will easily notice the drill. 

For making it clear , you can find the answer for the first 100 elements below. 

1---1

2---1

3---3

4---1

5---3

6---5

7---7

8---1

9---3

10---5

11---7

12---9

13---11

14---13

15---15

16---1

17---3

18---5

19---7

20---9

21---11

22---13

23---15

24---17

25---19

26---21

27---23

28---25

29---27

30---29

31---31

32---1

33---3

34---5

35---7

36---9

37---11

38---13

39---15

40---17

41---19

42---21

43---23

44---25

45---27

46---29

47---31

48---33

49---35

50---37

51---39

52---41

53---43

54---45

55---47

56---49

57---51

58---53

59---55

60---57

61---59

62---61

63---63

64---1

65---3

66---5

67---7

68---9

69---11

70---13

71---15

72---17

73---19

74---21

75---23

76---25

77---27

78---29

79---31

80---33

81---35

82---37

83---39

84---41

85---43

86---45

87---47

88---49

89---51

90---53

91---55

92---57

93---59

94---61

95---63

96---65

97---67

98---69

99---71

100---73

Pay a close attention to the numbers which are powers of 2 (2,4,8,16). They are equal to 1, after every power of two , the next answer equals to the previous answer +2.

2^n          1

2^n+1      3

2^n+2      5

2^(n+1)    1

.....

.....

So , the only thing which is left is to take care of the input then find the biggest power of two which is smaller than the given number and calculate. 

Here is the formula

answer=1+(n-P)*2;  (P is the biggest number which is a power of 2 and is smaller than n)

DOWNLOAD THE FULL SOURCE CODE 

SPOJ 14138. Amazing Factor Sequence

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

This problem is very tricky. let's have a look at constraints
n<=1000000
t<=100

This task will take a lot of time even if we tried calculating the answer for N=1000000 even if used powerful math. And the number of test cases makes it worse. For dealing with test cases we need to make precalculations. Remember the sieve of Eratosfen? We looped over our array and checked if we have one prime number we mark all the numbers which are divisible to the found number as not prime. We will use almost the same approach but with the divisors ;). The problem defines some function f(n) which is equal to sum of divisors of n. We will keep an array . The I th element will show the f(I) . Now we loop over our array. Suppose we are now at the spot I. We are sure that the numbers 2*I , 3*I , 4*I, 5*I ..... all will have the divisor I so we can add the value I to the elements a[2*I], a[3*I], a[4*I]......   using this method we found all the values of function f with the speed of a little bit more than NlogN Now we need to keep an array of answers and to keep the answers up to1000000. This can be done easily in O(N) time. Now for the test cases. Now that we have calculated all the values, we are ready to read the input and output the answer right away.

   DOWNLOAD THE FULL SOURCE CODE   

SPOJ 4300 Rectangles

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

Note that the constraints are N<=10000 which means that N^2 probably won't pass. The task ask us to find the number of rectangles which we can build using up to N cubes. I mentioned "up to" because we can have some cubes unused. We can describe the task i a different way.Find the number of distinct pairs i and j the multiplication of which is less or equal than N. Now we can loop through N elements in a double loop and check if the multiplication is less or equal than N and also check if we have already seen that answer. The clever way of doing this is using 2 loops in this way.
for( i=1;i<=N;i++)
   for(j=1;j<=N/i;j++)
(because we know that if we have the first side of our rectangle the second side must be less than N/side1.

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 7875. Miles and kilometers

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

This problem is a little bit tricky. Let's have a look at constraints. There are 10000 test cases and every test case is less or equal to 10^15. The first thing we will have to do is generating all the Fibonacci numbers which are less or equal to 10^15. Be sure that that number won't exceed 80 so we generate the Fibonacci numbers and keep them. Now we need to find the right combination of Fibonacci numbers. The task says that the numbers must be as big as possible.Basically we need to complete this steps in order to get our answer.

1. Find the smallest Fibonacci number which is bigger than the given number.
2. Add the found number to our answer and subtract the previous Fibonacci number of the current Fibonacci number from our given number .
3. Go back to step 1 if our number is still greater than  0.

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 10239 Between the Mountains

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

This task is a very simple task. The constraints are enough to write a simple brute force solution and get accepted. Just loop over both of arrays , calculate the distance between every pair and update the answer.

   DOWNLOAD THE FULL SOURCE CODE 

SPOJ 7975. Tri Graphs

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

  This task can be solved with creating a graph out of our array and use BFS to solve it but there is a better way. We can use dynamic programming to solve this. Create an 2 dimensional array. Let's name that array b.
b[i][j] will show the minimum number of points we will have to collect in order to reach i-th row and j-th column. We now that b[1][1]=a[1][1]. Now we can just loop over our input array and for every element a[i][j] we update the value of b[i+1][j],b[i+1][j+1],b[i][j+1]. (All the values of array b equal to infinty from the beginning).

   DOWNLOAD THE FULL SOURCE CODE

SPOJ 42. Adding Reversed Numbers

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

This task is a simple implementation task. Juts keep the number in an array digit by digit so that you can calculate the reversed number easily. The numbers are small so this means that we won't have to do the long number sum.

DOWNLOAD THE FULL SOURCE CODE

SPOJ 10676. 0110SS

Here is the problem statement.

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

For solving this kind of problems we need  to have a bit of noticing skills. Try to calculate the answer for n=1,2,3,4 by hand and you will easily notice the drill in here.Create a simple tree which will show the answer.

The tree shows the ways of creating numbers

When the length is 1 we can have 0 and 1 on our first position. When we are trying to form the sequence of length 2 we need to use the sequences we had already created and add 1 or 0 (if possible) to the end of the sequence. Obviously this is a problem of dynamic programming. Here is the table of answers from 1 to 4

1-2

2-3

3-5

4-8

We can easily notice that a[n]=a[n-1]+a[n-2]

The only problem we have in our task is the problem of constraints. N<=10000 obviously for N=10000 our answer will not fit in int64 I can say more the answer for N=10000 s 2009 digits long. We need to implement the long arithmetics. You can find information about that here.

DOWNLOAD THE FULL SOURCE CODE

SPOJ 10639. The Blind Passenger

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

This task requires a little bit of logic to solve.
RowNo Left   Right  
      W  A   A  M  W 
                  
      01 
1     02 03  04 05 06 
2     11 10  09 08 07 
3     12 13  14 15 16
4     21 20  19 18 17
5     22 ............ 
This is the structure of the bus. Calculating the row will be very easy .
Here is the pseudocode of calculating the position of the row.

n=n-1;(To consider numeration from 1 )
row=n/5;
n=n-row*5;
if(n>0)
       row++;

Then we need to check every single remainder when n is divided on 5.
Let's have a look at a table where we write only the remainder of n divided on 5
2 3 4 0 1
1 0 4 3 2
..............
................
and so on. If the number of row is not divisible on 2 then we should consider 2,3,4,0,1 else 1,0,4,3,2

DOWNLOAD THE FULL SOURCE CODE

SPOJ 8351. KOSARK

This task is a simple implementation task. You only need to keep track of the events and check which team is on lead and add you answer accordingly. The only challenge here might be the input and the output because we are getting the input in MM:SS format and we should output in this format as well. In C++ the input will be easy to read. cin>>int>>int>>char>>int; will give us what we need. If we read the number in format 02 C++ will understand it as 2 and 00 as 0. The other part is very easy. Just keep the current time and check if at the current event one team has more points than the other add to the answer the time of event minus current time.

DOWNLOAD THE FULL SOURCE CODE