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