ACM 1073. Square Country / Квадратная страна

 We will keep an array of answers DP[N] where DP[i] shows the answer for i. We also would like to keep a list of squares up to 60000. The algorithm pretty much looks like the algorithm of the knapsack problem except here we keep the number of elements. Initially all the numbers equal to infinity (to a very big number) now starting form 0, if we are on a current element I then we need to check for all the I+ squares and check if we can update the answers, in other words DP[I+squares]=min(DP[i+square], DP[i]+1);

       FULL SOURCE CODE 

SPOJ 15259. Large Knapsack (LKS)

http://www.spoj.com/problems/LKS/
 
  For solving this read the optimizing tips for knapsack problem. Also check the source code below.

Optimizing the knapsack problem.

 I suppose that you know the knapsack problem with 2 parameters. So here is how we are going to optimize it. You know that we are keeping an array C where C[i] shows the best value we have got by using i weight. Every time we loop over this array and if we find an element which is not 0( has been used previously) we check if by adding the new weight and a new value we can get a better value of not. Every time we loop we check many elements which are 0 (which we haven't used yet), it would be much better if we just looped over the elements which have a value greater than 0 to save time right?, Here is how we will do it, we will need to keep another array suppose D where D[i] shows the next index which is not 0. Initially D[1]=1 and size of D is 1 because there is only one element which we used from the beginning. Then instead of looping over array C we will loop over array D and check, if by using a new weight we got into a cell which is 0 we need to add that to our array D so that next time we loop over that spot as well. Now about adding element to array D, If in the task we have a limited numbed of elements (meaning that we cannot choose infinite number of elements, we can choose only one) then in the slow approach we were looping over array C from the end so that we won't count the same number more than once, in here we need to keep our array D sorted in increasing order so that we will not lose the right answer, there are 2 ways of doing that either sorting the entire array D or using binary search for finding the appropriate spot of the new element and insert it in the middle of our array D.

SPOJ 16046. Help Professor (HPPROF)

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

   We will solve this with dynamic programming. Let us have an array A where we will keep our answers, elements A[i] shows the number of possibilities from the beginning of the string to the i th element. Initially A[1] is 1 because with one digit we can make only one possible combination. Let us also have A[0] equal to 1. For element I there are 2 possibilities either the element I is considered as a separate number or the elements I-1 and I be considered as one.  Now for every element I the answer equals to A[i-1] at least, also we need to check if the elements I and I-1 form an 2 digit number which is smaller than 21 and there are no leading zeroes then the answer would be A[i-1]+A[i-2] .
Here is the short pseudo code
 first a[i]=a[i-1]
if ( a[i-1] and a[i] make a  number smaller than 20 and a[i-1] is not zero)
   a[i]=a[i]+a[i-2];
Check the source code for a better understanding.

SPOJ 7217. Training for final (TRIKA)

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

  We will solve this task using dynamic programming. Let us have an array A where A[i][j] shows the maximum points we will have left for reaching the cell (i,j). Initially all the elements of array A are equal to -1 which means that we haven't visited it yet. Our starting point will be equal to the value we have form the beginning. Then we need to loop over array maximum N*M times and whenever we find a spot which is not -1 we check all it's neighbors and update the values of array A. Check the source code for a better understanding.

SPOJ 13745. Crack the Safe

http://adf.ly/joZ9p

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

   We will solve this task using dynamic programming. Let us have an array A of size 100000x10 where A[i][j] shows the number of codes which have the length i and end with a digit j. Initially all the elemenets of A[1] are 1 because there are 10 codes of length 1 and each of them ends with a separate digit. Now we need build the next lines. We can tell what digits can come after any digit for example if the code which has a length of M ends in digit 1 that means we can make 2 times more codes of length M+1 where we will add the digits 2 and 4 (the neighbors of digit 1) and form new codes ending with digits 2 and 4. I also suggest keeping the sum of elements in every 10th element on every row so that we can make our code easier. Check the source code for a better understanding.

SPOJ 8442. Problem 3

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

   We can solve this task using dynamic programming. Let us have an array A[11][26] where the element A[I][J] shows the number of valid sequences of length I  where the last present letter is the Jth letter. Let's look on an example
for 1 there is one sequence "a"
for 2 there are 2 sequences "ab" "aa"
for 3 there are 5 sequences "aaa" "aab" "aba" "abb" "abc"
So, A[3][2] will be 3 because there are 3 sequences which have a length of 3 and their "biggest" letter is b. A[3][3] will be 1 because there is only 1 sequence of length 3 which has the "biggest" letter of 'c'.
So here is how our dynamic approach will look like
for every A[i][j]
we can add all the letters to form the i+1 length from 1 to J+1 the letter, for every letter added if that letter is smaller than J => the "biggest" letter will still be J.
This is the formula
for A[i][j]
A[i+1][j]=A[i+1][j]+j*A[i][j];
A[i+1][j+1]=A[i][j];

       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 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 3923. Philosophers Stone

Here is the problem statement .

We will solve this problem with dynamic approach mening that we will get the solution for current cell (X,Y) with the help of (X-1,Y) (X-1,Y-1),(X-1,Y+1). We will call teh given array A. We will also keep another array B where B[i][j] will show that maximum number of stones we can collect . INitially every element of the first row of the array B equals to every element of the first row of array A, the others have a value of 0. Now we need to loop over array B and for every coordinate (X,Y) we need to see if we can update B[X+1][Y] , B[X+1][Y-1] or B[X+1][Y+1]. Then we need to find the maximum of the last row of the array B and print it out.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 39. Piggy-Bank

Here is the problem statement.

This is another classic problem of dynamic programming called Knapsack problem with 2 parameters. Read about knapsack probelm with 2 parameters here.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 97. Party Schedule

Here is the problem statement.

This problem is a classic problem of knapsack with 2 parameters. Check for teh algo Knapsack with 2 parameters here.

       DOWNLOAD THE FULL SOURCE CODE

Knapsack problem with 2 parameters

The knapsack problem with 2 parameters is very close to the knapsack probelm with 1 parameter.
The problem is as follows
 We have a bag which can carry up to M kilos. We have N items where each item has a cost and has a weight. We need to fill our bag in a way that we can have the maximum cost and the overall weight must not exceed M.
 Just like in Knapsack with 1 parameter where we kept an array of trues and falses we will keep an array but this time an array of integers not booleans. Suppose the name of that array is A. The value of A[K] shows the maximum cost of the items which have a weigh K together.
Here is a pseudocode
   Suppose we have 2 arrays
   COST[N]
   WEIGHT[N]
    and our array of answers A.
for(i=1;i<=N;i++)
    for(j=m;j>0;j++) //we start from the end because in this task the number of items of each type is 1 , if there were infinite items we were going to start form the beginning
     {
              if( j+WEIGHT[i] <=m //checking if the combination is possible AKA smaller than M// and A[j+WEIGHT[i]]<A[J]+COST[I]   // If the new combination is better than the one previously collected//)
                   A[j+WIEGHT[i]]=A[k]+COST[i]; ///update the new combination
    }

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 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

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