SPOJ 12323. Minimum Knight Moves!!!

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

 There are lots of ways to solve this, BFS recursion, DFS dynamic. I suggest using thee BFS (If you need more info on BFS go here) approach, it is simpler to understand but harder to implement. Just keep a queue and push the coordinates of the first cell to it, every time you take out an element check all of the 8 neighbors that cell has and add them to the queue , also don't forget to mark all the visited cells so that you won't have to visit them again and again.Check out the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1419. A Game with Numbers

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

This problem is a very interesting one. For solving the tasks like this we need to determine what actually means " the best strategy". So here is what I am telling you, if there is one digit present on the board the winner is the first player for sure, because he will just subtract that digit fro itself and get 0. If the current number is 10 and it is now the turn of the second player the first player would still win right? So if we want to win we need to make a situation where the number 10 will be on the board and it will be the second player's turn,  consider the number 11,12,13,14,15,16,17,18,19 in all of those cases the first player would take out the last digit leaving the number 10 to the second player which is a complete defeat. The same goes for every number, to conclude the best strategy is to subtract the last digit from the number so that we can leave a number which is divisible by 10 to the other player and when he makes a move (he can't turn the number divisible by 10 into another number divisible by 10 because the maximum number ho might be able to subtract is 9) and we will do it again and again until he will be down to the number 10 which is a lose. And of course it is clear that if we have a number divisible by 10 from the beginning that means that we will lose it.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1841. Prime Path

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

   We will solve this with BFS( if you need some more info about BFS go here). First of all we need to find all the prime numbers up to 10000 we can do this easily with the sieve of Eratostenes( for more info about the sieve of Eratostenes go here). We will keep a queue where we will add the number which we have already created , the numbers are always 4 digit which makes our job easier. Now we need to replace all the digits with a different digit from 0 to 9 (be careful while replacing the first digit you might end up replacing the first digit with 0 :) ). Every time when we take out the current number from our queue we need to separate his 4 digits and then keep replacing and combing the digits back to form other numbers, then with the help of the found prime numbers we can check if the number is prime or not, and also don't forget to mark every number you get so that your program won't process the same numbers all over again. Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3934. Recaman’s Sequence

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

This task can be solved easily with the help of C++ STL map (for more info about using map go here). The problem could have been done easier if there wasn't the requirement for the numbers being distinct we could have solved it easily but we need to keep the numbers distinct, this is where C++ STL map template helps us, in every step when we are calculating the current element we need to push it in the map and mark it as true. It is impossible to do with the old fashioned method, keeping a big boolean array and mark every number in it because the numbers are very big no computer would be able to hold an array of elements that big.

       DOWNLOAD THE FULL SOURCE CODE

1706. Queens, Knights and Pawns

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

 This task is a good task of implementation, there is not much to explain here you need to keep an array fill the given figures and then loop over the array, whenever you find a figure in there you need to check all the cells that figure can attack, for knight its simple you need to check only 8 cells , for the queen I suggest writing a recursive function which will start from a certain cell and move in a certain direction. Here is how it will look like
void rec( int x, int y, int px, int py)
where px and py show the number which we after being added to x and y will give you the position of the next cell for example px=1 and py=1 will lead you to south east. Check the source code for a better understanding

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1710. Two Ends

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

   For solving this task have a look at this tutorial where you will find the full explanation and also the source code.

       DOWNLOAD THE FULL SOURCE CODE

game 1: 2 players second player takes the maximum of 2 ends

The Problem

  

   We have a line of things to take. Each thing has a value , 2 players are playing each of them is taking either the first element or the last , we are the first one, the second player takes the maximum of the first and last. How many points we can score if we play the best way?

Solution

   We will solve this using the dynamic programming. We have an array A[N][N] where A[i][j] shows the answer for a segment of the given items from i to j. Suppose the name of the given array is a. So initially A[i][i]=a[i] because form i to i there is only one element and we will take that and end the game. Then, every A[i][i+1] equals to max(a[i], and a[i+1]) because when there are 2 elements we would rather take the biggest and then the second one will take the last and the game will end. Now, suppose we have an answer for A[i][j] and we want to find A[i][j+1] in other words when we have already found for a segment from i to j now when the j+1th element is added what will the answer be? When the new element a[j+1] is added we have 2 options

1. Take the new added element and then the second player will take the biggest from a[i] and a[j] and we will have to play our best for either for a segment i+1 to j or for a segment i to j-1 both we have calculated previously.

2. We can take the i the element and then the second player will take the bigger from a[i+1] and a[j+1] and then like in the previous option we will add already calculated answer.

There is a task on SPOJ which requires the knowledge of this, you might want to try this and here is  the full source code.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1798. Assistance Required

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

 I suggest solving this task with precomputation. We can write a simple solution which can find the numbers for us and write those numbers in am output file in the way so that we can use them in our source file. Here is my solution with C++ with the process of counting the numbers and also the main source code.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1027. Fool The Police

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

This task is an exact duplicate of the task FISHER
http://www.spoj.com/problems/FISHER/
If you want to see the explanation and the solution go here where you will find the solution and explanation for FISHER and the full source code.

       DOWNLOAD THE FULL SOURCE CODE 

SPOJ 101. Fishmonger

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

 This task is possible to solve with both dynamic and recursive approach. Here I will present you the recursive one. We can have an obvious DFS(you can find more info about DFS here approach, start with the 1st and take every single path, I am not sure whether the simple DG We can use some optimizations to reduce the time. Our DFS should have 3 parameters: N,M,T. N shows the node we are currently in , T shows the time it took us to reach the current node, and M shows the money we paid so far. Here are some optimizations you should do. We also have 2 parameters ansT and ansM which show the answer ansT stands for time and ansM stands for money.
1. Marking the node we already visited, (of course don't forget to unmark it after the recursive call).  
2. If the current money we have already paid is bigger then the answer we have got previously then here is no need in continuing our recursion because we are not going to get a better answer.
3. If the time which we have spent is greater then the given maximum time we need to break our recursion immediately.
 Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 9861. Hotels Along the Croatian Coast

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

Here is an O(n) algorithm for you. Let us keep 3 variables P , Q and S. P and Q will show us an interval which we are considering at the moment and S will show the sum of the current interval. Initially P and Q are 1 and S is A[1]. Suppose he variable which shows the maximum purchase is called M. So now, if currently our S is smaller than M which means that there is still a chance that we might buy the next one as well, we increment Q by 1 meaning that we will be considering now the hotels between P and Q+1. If S is more then M which means that by taking the latest hotel we passed the limit so we increment P by 1 meaning that we are not taking the leftmost hotel. And also don't forget to update the answer in any step.

       DOWNLOAD THE FULL SOURCE CODE 

SPOJ 18713. Can You Make It Empty (Easy)

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

This task is the easy version of the task EMTY2. Check out my tutorial on the more difficult task which has a fast solution and works for this one as well (you will find the full source code as well) by going here,

SPOJ 18714. Can You Make It Empty

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

I suggest using C++ STL stack for this one. If you need more info on stack go here. Here is how we will do it. We loop over our string, if the current element is '1' then we add it to our stack, if not then we need to check for the last 2 elements, if the last 2 elements are 1 and 0 ( in other words the last two and the current one are forming 100) then we pop those elements otherwise we push the current '0' to our stack. In the end we check if there are any elements left in the stack if there are then the answer is 'no' otherwise is 'yes'.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 5449. Seinfeld

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

This is a problem of finding the minimum number of operations to form a correct bracket expression. Go here to check that tutorial out. Also check the full source code.

       DOWNLOAD THE FULL SOURCE CODE

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.

C++ Stack

Stack is another C++ STL container.

Stack is a dynamic array where you can add elements form the end and remove elements again from the end.
It is declared like this. The stack is just alike dish stacking one on another. When you put some plates on one another then when you need them you need to take them out from the top.
....
#include <stack>
.........
...........
..........
stack<type> s;
type is the data type you want your array to hold.

Here are the main functions of stack.
suppose we have
stack<int> a;

a.empty()
This is a boolean function which returns "true" if the stack is completely empty and "false" otherwise.

a.pop()
This function removes the element which is at the end of the stack.

a.push(int x);
This function will add the element x form the back of our stack.

a.top()
This function returns the value of the last element of stack.

SPOJ 4557. Musical Chairs

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

This is a basic task of a problem called "Josephus Problem". You can find info about Josephus Problem here.Also check the full source code.

       DOWNLOAD THE FULL SOURCE CODE

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.

SPOJ 4452. Simple Arithmetics II

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

This is another great implementation task. There is not much to say but I will try to give a few tips. First of all I suggest finding the numbers first and storing them somewhere then proceed to the operations. Here is how we do that, we loop over the string, whenever we see a digit we make another loop until we see the end of that number, then we turn the found area into an integer and store it somewhere. After making those steps no its time to loop over the string again this time looking for the arithmetic operations. Check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3440. Enormous Input and Output Test

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

This is another input output based task. The same as a task ITEST. You need to know the programming language you use well so that you can solve it, as for C++ I can say that scanf and printf function cover this task completely. If you need more info about input/output function of C++ go here.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 450. Enormous Input Test

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

This task is very simple, for solving it you need to observe the programming language you use. I can say that C++ scanf function covers everything. If you need information on C++ input function go here.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 3885. Coins Game

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

We need to solve this  problem dynamically meaning building the solution for A[i] based on the previous findings. Let us have an array A where A[i] shows the answer for i coins. The array is a boolean array where "true" means that the first player won and "false" means that the second player won. Initially a[1]=true becasue if there is only 1 coin then the winner is the first one for sure and let us have a[0]=false meaning that second one wins when there are no coins at all because the first one can't make a move. Now for every next I if A[i-1] is false then for sure a[i] is going to be true. (because if there are B coins and the winner is the second that means that when there are B+1, B+L, or B+K coins the winner will be the first because we are kind of adding one more move to the total game which changes the outcome).

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 526. Divisors

The problem statement

We need to find the number of divisors of numbers from 1 to 10^6 and then check if that number is a multiplication of 2 distinct primes or not. Fir of all we need to get all the prime numbers, we will use the sieve or Eratosphen. We need to do one more thing in our process of finding the prime numbers. Let us have an array named A[] where A[i] shows the number of divisors of i. Now Initially all the elements of A have a value of 1.(we consider that we had already taken the number 1 as a divisor of every number). Now when we are doing our prime search we need to do the divisor count as well. Here is how prime search worked, when we had a number which was not marked we considered it as prime and then we looped over all the numbers which are divisible to that number and marked them as primes. While doing that we also need to increase the current number of divisors with 1. Here is an example
we are now on number 2 which sis a prime that means that we must loop over the number 4,6,8,10...1000000 and mark them as not primes, also we will increase A[4],A[6],A[8].....,A[1000000] with 1 by saying that all these numbers are divisible on 2.
After calculating the primes and the number of divisors of 1 million numbers we can move on to the second step by checking if the elements in the array A have the form of A[i]=p*q (p and q are distinct primes). First of all we need to keep the prime numbers in some array. Then for every number in the array A[i] we need to do a brute force loop. We need to loop over all the primes numbers starting from the lowest and check for the condition.
Check out the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 13738. Happy Valentine Day (Valentine Maze Game)

The problem statement

So, this task really requires a good approach. First of all a simple brute force approach won't pass for sure , for n=5 and m=5 it already gives a time limit exceeded error. So here is how we will do it.
Let's look on this example so that it can be easier to understand
3 6
C#C###
OTOV#
######
Its a little bit different then the example in spoj , but I wrote it this way so that it can be an understandable table, in here "T" is the starting point, "V" is the ending point , "O" is a simple walkable area and # is the wall. we are going to use BFS and DFS . First of all we need to know every distance between the cells which we need ( cells which are "C , "V" or "T") . We need to find the distances between every pair and then make a special graph. OK, so here is the main thing, we need a BFS function which will count the distance between the given cell and all other "important" cells. (We call a cell "important' if it is either a chocolate or a stating or ending point). Let us give the starting point the index of 1 in our graph and the ending point the index 12 in our graph and all the chocolates from indexes 2 to 11. So, in the example I showed above we will have the graph below.

As you can see in the picture, I wrote the coordinate of the node which comes from the initial array (for example the starting point which we gave an index of 1 has a coordinate in the given array of (2,2 ) ). The red numbers are the distances between the 2 pairs (for example the distance between the starting point and the chocolate in the cell (1,3) is 2). Here is another NOTE , if on our BFS we weren't able to get to at least one "important" cell that means that the answer is "Mission Failed!".
Now, after we built out graph we need to find the best way. Here we can just do a recursive brute force (taking every single possibility)  which passes over all the chocolates and pick the best answer.
 Here is a little optimization which got me accepted as I was getting a TLE without it. We need to keep the answer in some variable, let's call it ANS. Initially ANS equals to a large number. Whenever we have passed over all the nodes we need to update our answer. So here is the optimization, If at some point in the middle of our recursion our already passed distance is larger then the ans and we still didn't get to the end we can brake that recursion because there is no way we are going to get a better answer. Make sure to check teh source code for other little details and overall understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 11063. AP - Complete The Series (Easy)

problem statement

This problem requires dealing with formulas. We will call the series A,we have A[3] and A[N-2] and S. We don't know N yet. We know the formula for the sum which is ((A[1]+A[N])/2)*N it is the same as we replace A[1] with A[3]-2*D and a[N] with A[N-2]+2D which gives (A[3]-2D+A[n-2]+2D)/2*N whic equals to (A[3]+A[n-2])/2 * N =S where the N is the only unknown element so N=2*S/(A[3]+A[N-2])
After finding N we need to find D. so
A[3]=A[1]+2*D
A[n-2]=A[1]+(n-3)*d;
If we subtract the 2 equations above we will get the following
A[n-2]-A[3]=(n-5)*d where d=(A[n-2]-A[3])/(N-5)

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 2157. Anti-Blot System

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

This task is a simple implementation task. We have that the way of representation is num+num = num so we don't have any problems with many variables or different math operators its only a + operator. I suggest using C++ string because it will cover the difficulty of the input because the string reads up to the first space, so we need to read only 3 numbers (one of them is not a number) and check for the "non number" element , we will also need a function for turning a string into a number. So we have 3 elements n1,n2,n3. We don't have to worry if the "non number" element has some digits with him or not . If n1 is not a number then we transform the other 2 into numbers and n1=n3-n2 the same we do for n2 and n3. Make sure to check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

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.

SPOJ 1437. Longest path in a tree

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

This task is solved with 2 BFSs. (If you need more info about BFS go here). Here is how its done. First of all we need to start a BFS from any node we want and find the furthest node from the starting node. But wait, the path we just found isn't the longest, the node we just found is the starting point for our real longest path. Now we need to find the furthest node from the node we just found, that will be our answer.
So , for summarizing, we need 2 BFS, the first one starts with any node and ends on some node X.Xis the furthest form the starting node. Then the second BFS finds the furthest node from X. and the path is the path between those 2 nodes. Check my source code for a better understanding..

       DOWNLOAD THE FULL SOURCE CODE