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,




                     

SPOJ 1028. Hubulullu

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

The words " 2 guys are playing a game"  confuses the reader and sometimes reader thinks that this is a difficult task which is solved with a special game theory techniques. But its not like that. You don't need to know game theories. Let's have a look at a time when one wins. Now let's imagine that after a few moves its the move if the second guy and no matter what move he will make , the first guy will win on the next turn. This means that there must be 2 bunch of numbers (when I am saying bunch I mean one number and all its divisors ). If you look a bit deeper you will find out that the started always can make that position so that no matter what the opponent chooses the advantage is always at the starters side. So we only need to write a few lines of code, if the starter is Airborne output Airborne otherwise output the name of the other guy.

   DOWNLAOD THE FULL SOURCE CODE

       

Directed and indirected graphs.

Let's have a look at 2 graphs which are almost the same.

The two graphs are almost the same. But there is one difference. The cities of the first graph are connected with simple lines while the cities of the second graph are connected with vectors.
   There are 2 types of graphs. They are called directed and indirected. As the name suggests indirected means without directions. The first graph is indirected. If we can go from the city A to city B and we can get back from city B to city A that means that the road connecting the cities A and B is not directed. In  the second graph, the arrow means that we can go from A to B but we can't get back. We can only move with the direction of an arrow. 

what are graphs?

We can imagine a graph as a bunch of different cities which are connected to each other with roads. 

The picture above is a simple graph. Here we have cities A,B,E,G,H,F,K,M and the roads which are connecting them. The cities are called nodes (sometimes vertexes) and the roads are called edges. So if we want to get from the city G to the city K as fast as possible We can go to the city H then go to K or we can go to the city M and then go to K. We treat all the roads equally. There is a type of a graph when the roads have , let's say length. The lengths of cities are sometimes called weights. 

The graph above is the same as the previous one but the roads of this graph have wights (lengths). So if we want to get from the city G to the city k as fast as possible we better go to the city M and then to K (by doing so we will pass 13+34=47 distance not 4+47 (If we went to H then to K) ).. 

Examples of graphs from our daily life

 1.  The cities and roads.

 2.  Airport network

3.  Firneds of friends network

   You have a friend. And your friend has another friend whom you don't know so you are connected to your friend and you friend is connected to his friend.

4. Internet network 

 Your computer is connected to a modem. The modem is connected to the ISP (internet service provider).ISP is connected to the different sattelites which connect the whole internet together and so...

...

....

....

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 

Bitwise operator ^ (XOR)

The bitwise operator ^ (XOR) which is also called exclusive or, is used as shown in the chart.

^   0   1

0   1   0

1   0   1

So as we can see the bit1^bit2 equals to 1 if bit1=bit2 else it equals to 0.

Bitwise operator | (OR)

Just like we discussed bitwise operator &, we will discuss this operator with the help of statement if.

Statement if for || (OR)

     condition 1       condition 2     result
          false                   false           false
            true                   false           true
          false                   true             true
         true                     true              true

So, just like the if statement , the operator | t\does the same but with bits.

example
000001110100
|
000000011100
=
000001111110

Bitwise operator & (and)

The operator & is another bitwise operator int C++. For making let's call the bits names. 0-false and 1 -true.
First let's look at an example
000000011100
&
000000000101
Let's remember the logical operator if. Just like the && (and) operator in if , the bitwise operator & (and) has the same meaning. When we had a conditional operator if and 2 conditions in it .
Let's have a loot at this chart
for operator && in if statement
    condition 1   condition 2     result
          false            false           false
          true             false           false
          false            true            false
          true             true            true
So basically , if both of the conditions are true => the if statement is true otherwise its false. Just like && the operator & does the same but with bits.

for bitwise operator &
      bit1    bit2    result
         0       0         0
         1       0         0
         0       1         0
         1       1         1

Remember that 0 stands for false and 1 stands for true
 So in our example from the beginning , when we perform the operator & we get

000000011100
&
000000000101
=
000000000100

bitwise poerators << and >>

Bit is a digit of a binary representation of a number. In C++ there are operators referring to bits.

 One of those operators are the operators >> and <<. If we try to translate the operator << into english we would get this definition move the current bits to the right. And the >> stands for move the bits to the left. The operator is mostly used for multiplying the number with the power of 2.  Now we will use an example to make it clear. 

Image somewhere in our memory we have the decimal number 3 which is 11 in binary.

1 2 3 4 5 6 7 8

0 0 0 0 0 1 1 0

The start point is the position 6 and the endpoint is 7.  Now if apply 3<<2 (means move 2 bits to the left)

we will get this

1 2 3 4 5 6 7 8

0 0 0 1 1 0 0 0

NOTE that the endpoint is going to stay the same . Its 7 but the start point moved to position 4. We sure know that binary 1100 is 12 which is 3*4.

So    n<<m=n*2^m

and   n>>m=n/2^m

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 8104. Friendly Knights

This is the task statement
http://www.spoj.com/problems/KFRIENDS/

We need to notice one very important fact. The answer can't exceed 8 because the knight on a chess board can have maximum 8 neighbours. When for example one knight has 8 neighbours he will wear 8 different color straps . Now let's consider on of his neighbours which is already wearing one strap. He also can have 8 neighbours at best but one of them is already considered (the first one) so we understood that the answer cannot be greater than 8. For calculating our answer we will need to calculate the number of neighbours of every knight and then pick the maximum.  Just because the coordinates are 100 at most we can keep a 2 dimensional array (matrix) and loop over it once and find the number of neighbours of every knight. Pick the maximum of the found values and print.

DOWNLOAD THE FULL SOURCE CODE
  

SPOJ 7974. What’s Next

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

The task itself is a very easy task. A very simple implementation just check if the difference between the first two equals to the difference between the second two elements. There is a little part to take care of. when one element equals to 0 we might end up dividing on 0 when we are checking if the progression is geometrical. Use this pseudocode

if(a2-a1==a3-a2)
print "arithemitc"
else
print "gemoetric"
Don't check for geometric progression

       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

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.