SPOJ 11931. AMZ Word

The problem statement

We can solve this task using dynamic programming. Suppose we have the number of words which end with zero, one and two. Lets make arrays zero[N], one[N], two[N] where zero[I], one[I], two[I] each will show the number of words with length I ending with 0, 1 and 2 respectively. The task says to find the number of words which have a neighboring digit difference at most 1 which means that numbers 0 and 2 can't be neighbors. zero[I] shows the number of words which have length I and end with 0. So I can say that when it comes to calculating the words with length I+1 there will be at least zero[I] words which will end in 0 and zero[I] words which will end 1 because after 0 only the digits 0 and 1 can come. So here is a general formula
suppose we have the answer for the length I ,
the formula for I+1 would be
zero[i]=zero[i-1]+one[i-1]; (Because we can add 0 and 1 to 0)
one[i]=zero[i-1]+one[i-1]+two[i-1]; (because we can add 0 1 and 2 to 1)
two[i]=one[i-1]+two[i-1]; (because we can add 1 and 2 to 2)

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 13046. The Glittering Caves of Aglarond

The problem statement

here is one statement which will make this task a lot easier. Every time we are required to click on switch, I say we should click a row which has the minimum number of on turned lights. Why?

because if there number of ON switches is less then the half of the row then we will "win" a few more lights (by saying win I mean get a better number) , if the number of ON turned switches is more then the half we will have the minimum "lose" note that every time we click a switch the OFF turned lights become ON and the rest ON turned lights become of, in other words if we have on ON lights and off OFF lights then after switching them on=N-on, off=N-off. So every time we can just sort them sort them by the number of OFF turned switches and take the minimum one and switch it , this way we will minimize the "loss" and maximize the "profit".

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10471. Aliens at the train, again!

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

  We will name the given arrays A and B. We will solve this with a dynamic programming (building every step based on the previous one). Let us keep 2 additional arrays , we will call them AA and BB. AA[I] shows the minimum number of people which must be seen in order to reach the station I on train A, similarly the element BB[I] shows the minimum number to be seen to reach to station I on train B. Suppose we have the answers AA[1],BB[1],AA[2],BB[2]....,AA[i-1],BB[i-1]. We need to calculate the AA[i] and BB[i]. There are 2 ways we need to compare to get to AA[i] , we can get there directly from station I-1 in sector A or we can be in the station I-1 in B sector then go to the station I in B sector and then go to the station I in A sector. The same refers to BB[i] but in reversed order. The basic formula is this

BB[i]=min ( AA[i-1]+AA[i]+BB[i] ,  BB[i-1]+BB[i]);

AA[i]=min (BB[i-1]+BB[i]+AA[i] , AA[i-1]+AA[i] );

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10401. Aliens at the train

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

By looking at the constraints we can assume that our solution must be O(NlogN) a worst. but here is a solution with O(N) complexity. First of all we will keep 3 variable which will show us the current answer.  we will cal them P and Q and S Let us call them ans1 and ans2 (ans1 stands for the number of people seen and ans2 for the number of stations passed). Our variables P,Q and S show the left and right ends of the interval we are now in and the sum of those numbers. So , every time we need to check if S is smaller than Bt (the maximum number) then we increment Q by 1 and S by A[Q]( we want to check that is it possible to take the next element or not). If at some point we came across a situation where our S (the number of seen people) >Bt (meaning that we took an invalid interval) we are increasing P by 1 and decreasing S by A[P] .

Also at every step we update the values of ans1 and ans2. Also, check the source code for a better understanding.  

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 15454. How to Handle the Fans

The problem statement

This task is a classic task of segment trees . Learn about segment trees and implementation of segment trees here. . Also check the source code for a good understanding.

       DOWNLOAD THE FULL SOURCE CODE

Segment Tree. Finding the sum of a given range in O (logN). Implementation of segment tree

 We have the following task. We are given an array of integers. There are 2 types of operations we need to perform. 1st update x,y. Change the xth element to y. 2. query x-y  find the sum of elements in range [x;y].
Of course the first way which pops up in mind is the simple brute force solution. That can work only if the constraints are low but here we are going to discuss a solution which will work for big constraints (in other words every query will work in O(logN) time not O (N)).
    We will do that with the help of segment trees. Segment tree ( sometimes called interval tree) is a very special way of data representation. Segment tree is a tree which is fully binary.I think It would be better If we discuss it on an example.
Suppose we have this simple example
N=5
1 2 3 4 5
We have 5 elements. Ok . Now have a look at the segment tree of our data set and we will continue discussing.

I am sorry for the bad picture, I am not good at this sort of stuff but anyway I hope you can understand it.
Here are a few things to notice for the beginning.
1. Every node in this tree shows the required information (in our case it is the sum) of a specific range. The numbers of nodes are written in green, the interval of every node is written in dark brown. For example the node 4 represents the sum of elements between 1 and 2.
2. The leaves are initial elements of the array.
3.  For having a fully binary tree we need to add up some elements which won't affect our answer to the closest power of 2. In our case we have 5 elements and we need to add 3 more elements so that we can have a fully binary tree. I marked the extra added elements with red X. So in our case we need to add 3 0s because when we sum 0 with other numbers the numbers are not changing.
4. If the current node which has the index of I shows the sum of elements in interval X and Y then
    his 2 children will have the index 2*I and 2*I+1 and , the 2*I the node will show the sum of elements between X and (X+Y)/2 and the 2*I+1 the node will show the sum of element between (X+Y)/2+1 and Y. So, basically we are cutting
  Implementation
We will need to make 3 functions.
1. Building the tree.
2. Updating the tree
3. Querying the tree

1. Building tree
let M be the closest element to N which is not smaller than N and it is a power of 2.
Our tree will have 2*M-1 elements. So our initial elements will be from M to 2*M-1 which will be our given elements from 1 to N and also the extra elements we will add to form a number which is a power of 2. For that we will keep a linear array name Tree. Tree I will be one node of a tree which will have 2 children with indexes 2*I and 2*I+1. So tree[I]=tree[2*I]+tree[2*I+1];
  for(i=m;i<=2*m-1;i++)
tree[i]=a[i-m+1]; (Note that the indexing starts with 1 in array A and in array Tree).
For the rest we need to loop back and every element Tree[i]=Tree[2*i]+Tree[2*i+1];
               for(i=m-1;i>=1;i--)
tree[i]=tree[2*i]+tree[2*i+1];
2. Update tree
   Updating is easy. We are getting an index of an array as an updating parameter. We need to find which node represents the given element of an array and update the tree by cutting the index of that node to half until we reach 2. (Note that the children of node I are 2*I and 2*I+1 , both of this number will give the result I when divided on 2).  This can be done recursively.
void update_tree(int x,int y)
{
tree[x]=tree[x]+y;
if(x==1)
return;
update_tree(x/2,y);
}
Also NOTE that when we receive a parameter I which tells us to update the value in A[I] our function must receive a index of a node not an index of array in our case we will give our function the index m+I-1.
3. Querying
  So, this one is a little bit complicated so I will try to be as clear as possible. Our function is going to have 5 parameters.
int query_tree(int node, int x, int y, int qx, int qy)
1. node-  node shows the current node we are observing
2. x,y - those 2 show the current interval which the node is representing
3. qx, qy,  - those 2 represent the interval which sis being queried.
SO, the node which has an interval of x to y has 2 children . The first child has an index of 2*node and the second child has an index of 2*node+1. The first child shows the answer for an interval X and (X+Y)/2 and the second child shows the answer for interval (X+Y)/2+1 and Y. our function is recursive. Now we need to check for 3 things.
If the queried interval and the current interval of current node are the same we need to return the answer on the current node.
If the previous condition is not true we need to check for 2 more things. If the queried interval belongs to the interval of node*2 (in other words qx and qy are between X and (X+Y)/2) then we need to call this function again but with new parameters ( query_tree( node*2 , X, (X+Y)/2, qx , qy)) .
If the queried interval belongs to the second child of the current node (in otehr words if the qx and qy are between (X+Y)/2+1 and Y then we need to call this function again similar to the previous call. ( query_tree( node*2+1, (X+Y)/2+1, Y, qx, qy) .  
If the 2 conditions below are not met that means that the queried interval has 2 parts where the first part belongs to the first child and the second part belongs to the second child. This calls for 2 recursive functions
query_tree(2*node,x,mid,qx,mid)+query_tree(node*2+1,mid+1,y,mid+1,qy); (mid is (X+Y)/2) , as we can see we divided our qx to qy into 2 different queries , teh first one is from qx to mid and the second one is from mid+1 to qy.
 For having a better understanding check this task from spoj.com and the source code for this task can be found in this site in the section "SPOJ tutorials". 

SPOJ 9921. ABC Path

The problem statement

 This task can be solved easily with BFS. (Here is some more information about BFS). Just add the current position to the queue and every time check for it's neighbors, if there are any which are the next letter on our current position then add that cell to the queue as well. We have a problem with marking here. We can'r mark a cell as visited and forget about it because there might be another path which is being made with teh help of that cell . If we leave everything unmarked and don't use marking at all we will sure get a time limit exceeded error even with optimized input / output. We can just keep the number of times we visited one cell. And every cell has a total of 8 neighbors then we need to keep the number of times we visit the same cell and make sure that it won't exceed 8. See the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 181. Scuba diver

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

We can call this task a "Knapsack probelm with 3 parameters". For solving this we will need a knowledge of "knapsack problem with 2 parameters".
 We use a linear array in "knapsack with 2 parameters" where A[I] shows the maxmum value we can get which has a mass of I. In our case we will keep a matrix where A[I][J] shows the minimum mass of cylinders which have I oxygen and J nytrogen. Have a look at the constraints the limits of oxygen and nytrogen are not high which means that keeping a matrix and looping over it won't be much of a problem. Check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 9734. Hacking the random number generator

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

Of course this type fo probelms can be used with a simple approach. We need to keep and array named B, (we will call the input array A) and B[I] will shows the number of elements from the array A which have the value of I. Then we will check and add to our answer elements B[A[i]+k] . This might work but we are not sure about the constraints. There might be negative numbers where we can't keep negative numbers as an array index. So, STL map covers this problem because with the help of STL map we can keep every type of an index we want. (If you need info about STL map go here).

       DOWNLOAD THE FULL SOURCE CODE

STL map

Map is another STL container and is aother good way of keeping data. We declare map like this.
map<type1 , type2> m;
Basically this map means that we keep data of type 2 with indexses of data type1. This sounds complicated but I will try to be more clear. For example we want to keep a list of names and surnames. We can do that with map.
If we assign map<string,string> m;
this emans that the following expression is legal m["Smith"]="John"; We can consider the first data type we assign to map as the index data type. So in our example "Smith" is the index and "John" is the value. When we are declaring an ordinary array int a[10000]. then we can use the following expression a[10],a[1] but not a[-25] because the indexing starts with 0. You can imagin map as a little more enhanced version of array. So , one more time map<type1 /*index data type*/ , type2 /*value data type*/> m;
examples
map<string,int> m;
m["John"]=0;

map<int, int > m;
m[-10000]=902;

map<unsigend int,int> m;
m[10]=34; //Note that map<unsigend int,int> m has the same effect as the regular array because the indexing starts with non negative numbers

And one more important question, the memory usage. When we first declare the map it is using almost no memory. When the first value is attached, ( for example we have map<string,string> m; and we write m["John"]="Smith") some memoryis being taken only for storing one elment and somehow keep its index. When we assign another value , it checks if the index we use has already been used he just replaces already taken memory with anotehr value if its new than he take memory again. Example
map<string,string> m;
m["John"]="Smith";
takes memory for storing the value "Smith" under the index "John";
m["Johny"]="Smith";
Takes memory because the index "Jonhy" was unused.
m["John"]="Brown";
Already has a memory for the idnex "John" so just replaces the value "Smith" with teh value "Brown";

Looping over maps is being done with iterators.
Now some important functions

m.begin()
return the value for iterator which shows the beginning of the map. IMPORTANT map always starts looping from teh lowest index to the highest.

m.clear()
clears the map completely.

b.empty()
boolean function which returns true if the map is empty and false if it is not.

m.end()
returns the end of the map for iterator.
Looping over map is accomplished like this.
map<type1,type2> m;
........................
........................
........................
map<type1,type2>::iterator it;
for(it=m.begin();it!=m.end();it++)
{
}
m.erase()
This function ca be used in more than 1 ways. If you give a single iterator to it it will remove the element which has that iterator. If you give 2 iterators it will remove all teh elements between these 2 iterators.

m.find( value)
retuns and iterator, needs a value to find it.

m.size()
returns the size of the map= the number of elements in the map.

SPOJ 8611. Non-Decreasing Digits

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

This task can be solved eaither with math calculaions or with DP (dynamic programming). I will suggest a solution with DP. So we will keep an 2 dimensional array. A[I][J] will show the number of non-decreasing numbers of lenght I which starts with teh digit J. Initialy a[1][0],a[1][1],a[1][2].....a[1][9] are equal to 0. Now we need to count others. For the lenght 2 if the number starts with 0 then after it we can have any number which we made i a previous step . If the number starts with 1 that means that after that we can have all 1 digit numbers which start with a digit greater or equal to 1. The genertal formula will be like this
a[i][j]=a[i-1][j]+a[i-1][j+1]+.....+a[i-1][9]. And I also suggest to keep the sum of the row in the 10the element so that you can be able to output the answer just after reading teh input. Also check teh source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 16246. Trener

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

This task is another implementation task. I think the best way is to sort teh array then start looking from the beginning , we need to calculate the numebr of consecuetive elements which start with teh same letter, if the number of those elements is greater than 4 that means that we can add that letter to the answer. This might not be the fastest algorithm but it passes in 0.01 wiht using slow intput output.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 13002. For Loops Challenge

The problem statement

This task is an implementation task and the biggest challange is the output format. But anyway I will explain how to solve it in case you need an explaination. I think the best way would be getting all the elements in one array and sort them . Then we need to loop and with that we will keep 2 numbers p and q, which shows the interval which is going to be printed. If the difference between teh current element and the next element equals to 1 then we increment q with 1 if not then we write the output which tells that the number between A[p] and A[q] are printed then we turn the values p and q to the next index. Check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

13753. Amazing Prime Sequence

The problem statement

This task is all based on precomputations. Do you remember how we were getting all the prime numbers in na given range with the sieve of Eratoshpen? We will do something like that here. Let us have an array of size 10^7 where the element A[I] shows the smallest prime factor for I. Here is what I am saying, for the number 2 the smallest prime factor is 2, and of course for all the numbers divisible by 2 the answer is the same right?. So, when in sieve of Eratosphen we were just marking the numbers as primes, in here we will give all the numbers which are factors of another prime numbers the value of that prime number if that place hasn't been marked yet. Because there is a case, for 2 in A[14] we write the number 2. Then, when we consider the number 7 the asnwer for A[14] shouldn't be changed to 7. Check teh source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10500. Haybale Stacking

The problem statement

For getting the answer somehow we need to have all the values , and we need to figure out a way to get those values in a special way because the most obvious approach is too slow in this case. So , Instead of looping and increasing every element in the given range we can keep do it in other way. We can keep an array with the name A , every element A[I] shows the difference between elements I and I-1 or in other words A[I]-A[I-1]. When we read an interval suppose it says from a to b. We add 1 to A[a] and subtract 1 from B[b+1]  this way we can easily get the values.Now for getting the exact values of the elements we need to loop over and keep a variable num, num is 0 initially. for Calculate NUMBER[I], we add A[I] to num and NUMBER[I]=num.  Then we need to use a fast sorting to sort them and output n/2+1 th element.Check the source code for a better udnerstanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 10286. DOTA HEROES

problem statement

This task is a very easy one if you look carefully. I suggest looking on the explainatin of the sample test. It suggests a way of crossing a tower, He says that one guy comes and gets a shot and then the rest can pass. So, we only need to send somebody who won't die after one shot and the tower can be considered as crossed, so IN other words if tehre is a hero who can take one hit and stay alive that means that you can pass one barrier. So we ned to calculate the total numebr of shots which all the heroes can take without dying and compare it to the number of towers.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 8612. Penney Game

The probelm statement.

This task is a task of implementation. The constraints are very low so the simple brute force will pass easily. ust take every 3 letter string and start checking for that in the given string. And every time you find one  increment the asnwer with 1. Here is a checking method I suggest. ust because the strings are of length 3 we can loop over the given string and check if the current character and the next to are equal the the first , second and thirdf characters of the short string.
Check the cource code for a beter understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 9032. Cube Free Numbers

The problem statement

This task is a pure precomputation task. Remember how we were finding all prime numbers in O(NlogN) time? Yes, the Sieve of Eratosphen.(If you need info about the sieve of eratosphen go here). We will do the same type of thing here but instead of marking the prime numbers we will mark all the NOT Cube free numbers. Of course the first NOT cube free number is 2*2*2=8 then all the numbers which are divisible on 8 are also NOT cube free so we mark them as well. Then it comes to 3, 3*3*3=27 we mark all the number which are divisibly by 27 , we do this to the number 100 because 100*100*100=10^6 which is the maximum value which can be in teh input. Then we need to numerate all the numbers and the solution is ready. Check the source code for more clarification.

       DOWNLOAD THE FULL SOURCE CODE