SPOJ 15506. Helping Igor (IGOR)

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

   First of all we need to have a good look at constraints. Firstly, The value of the query can be up to 10^9 which tells us that we can't have a brute force solution passed. Secondly, the length of the given line is not going to be more than 14 so here is what I suggest. We can calculate all the possible lines, (they will be no more than 2^14) and then output the result. Then, just because there are 2^14 maximum possibilities and queries up to 10^9 we can say for sure that the sequence of +s and -s is going to repeat itself at some point, so we have to calculate the sequences first and stop the calculations until we reach a point where the new sequence we have got has already been gotten earlier. So how do we know which sequence we calculated fast?   We can turn the sequence of +s and -s into a sequence of 1s and 0s and considering it us a binary number turn it into a decimal number and mark it as "visited". We will also need to keep the "time" , "time" tells us the time. Whenever we reached a number which was marked previously we stop our calculations . Here is what we will get in the end.

N1,N2,N3,N4,. . . . . . . .Nm
starting from a certain number R the number are going to repeat themselves, which means our sequence will have this look
N1,N2,...  Nr, N(r+1)....Nm, Nr,N(r+1).....Nm and so on.
All that is left is to input the query time and find the right one and output it. Check the source code for some other details and better understanding.

SPOJ 7188. Escape the Jail (ESJAIL)

   Here is what we will basically do. We need to use BFS and check, every time whenever we are checking a node we need to look over it's neighbors and see if there is one neighbor which we were not able to visit because it is locked we need to push that same node again to the end of the queue so that after our search it is possible that we can unlock the door which we weren't able to visit from the beginning. And we will need some optimizations, we can keep a double element queue where the first element shows the node and the second one shows the "time", whenever the time becomes too much we can exit the process and say that we can'r reach our destination. (in our case too much time can mean that time is more than 2*M). Also we can keep a boolean array which shows the elements we have double pushed to the array because there was a closed neighbor so that we won't have to push the same node many times. Check the source code for a better understanding.

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 14543. Range Sum (RANGESUM)

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

  For solving this you need to know how to use segment trees for finding the sum of a  given range in O(logN) time. For learning the segment trees go here. So, we keep an array which represents our tree of length of a number bigger than N which is a power of two. First of all we will increase that size, we will have the size which is a power of 2 and bigger than 2*N so that we can have more "free" leaves. (In our case free means that it has a value of 0). We will fill our array starting from the leftmost leaf (a leaf which has a smaller index) in reverse order so that whenever we will have to add an element to the beginning of the array we can use the "free" leaves for that. Then the rest is a simple segment tree implementation. 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 16121. MODIFY SEQUENCE (NITK06)

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

   Here is how we need to approach this problem. Suppose there are 2 numbers, for finding the answer we need to check if the two are equal numbers or no. When there are 3, here is what we will need to do, we need to find the smaller of the elements in the ends (first and last) and decrease it to 0 and see and after that we can ignore him and the only thing which is left to check is the equality of the remaining 2 elements, this way we need to deal with all the cases, by checking every three, picking the smallest if it is on the end (first or last) and by making it 0 check the rest, overall this is the same as giving negative signs to the elements with the elements with the index divisible on 2 and counting the total sum, if the sum is 0 then the answer is "YES" otherwise the answer is "NO".

       DOWNLOAD THE FULL SOURCE CODE

 

SPOJ 9380. Connecting Three Towns (THREETWN)

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

  I got around 92% of the total score by solving it this way. If you take the arithmetic mean of 3 coordinates you will get a very good answer if not the best answer.
X=(X1+X2+X3)/3
Y=(Y1+Y2+Y3)/3

       DOWNLOAD THE FULL SOURCE CODE

SPOH 7405. Delicious Pancakes (PANCAKES)

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

  This is a very good implementation task where the implementation is not very hard but we need to be extra careful while doing it. First of all there is a case where the needed ingredients are more than the ones we have, in that case the answer is 1 0 which means by taking the first recipe we weren't able to cook any pancakes. Then , for doing the calculations I recommend avoiding floats do it with integers, Initially while reading the input data increase the given ingredients which have have 10 times so that when it comes to dividing the ingredients on one another for finding the number of pancakes the problem with that 10 will be solved. Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 6828. Lineup (LINEUP)

http://www.spoj.com/problems/LINEUP/
 By looking at the constraints I can tell that it is enough to just look over all the possible configurations and pick the best one, the hardest problem is the implementation. We can do it recursively with backtracking which means every time we try something we keep our steps so that we can return to some point and continue with other configuration. Check the source code for a good understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 12880. Sheep (KOZE)

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

  We will solve this using BFS or DFS  We need to keep a boolean array called MARK[N][M] where MARK[i][j] shows whether we visited that cell or no. Thu function of our BFS or DFS is to cover all the cells of the current sector and also keeping track of the number of sheep and wolves . When the BFS\DFS is  done with covering the sectors we  will check the conditions and see if the sheep defeated the wolves or they lost or none of them. The way we are going to cover our sectors is the following. We need to loop over our MARK array and see if there is a cell which we haven;t visited and that cell is not a fence then we should start our function which will cover all the cells in that sector. also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 15965. PLAY WITH NUMBERS (ENIGMATH)

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

Here we need to notice that if A*x - B*y =0 then for A=y and B=x the equation is true. We could have just printed the numbers and finish but the problem asks for the minimum number and for example for this case 2*x-4*y=0 the minimum answer is not 4 and 2 but 2 and 1 :). So here is what we should notice the right formula is x=B/GCD(A,B) and y=A/GCD(A,B)  where GCD means the greatest common divisor of numbers A and B. You can find more info about calculating GCD fast here.

       DOWNLOAD THE FULL SOURCE CODE

Greatest common divisor of 2 numbers.Euclid's algorithm

Here I will explain quickly how to find the greatest common divisor of 2 numbers very fast. First of all Euclid;s algorithm states that GCD(x,y)  equals GCD(x-y,y) which is true for x>y.  But we can improve the performance significantly when replacing the operator "-" with operator % (reminder ) which means GCD(x,y)=GCD(x%y,y) where x>y.

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