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