Techniques to solve Problem LightOJ 1057 - Collecting Gold

LightOJ 1057 - Collecting Gold 

Category: This problem is a dynamic programming problem. Particularly this problem can be solved by bitmask dynamic programming technique.This problem can also be solved by using breath first search.

Techniques: When I have solved this problem then I was tried it by recursive dynamic programming technique. Your sample test cases may pass by these techniques but in case of mine I have defeat my code by a critical test case of mine. Then I thought it from different angle and I have solved it by the technique of bit-mask dynamic programming. 
It is little hard to model the problem in bitmasking. If you don't have any idea about bit-masking then please learn it from internet. There are available resources. I did the same. 

In the problem it has been told that the problem could have at best 15 gold. When the input size of a DP problem is less than 16 then this problem could be a bit-mask DP. 

The gold has 15 pieces and a initial location(x) together makes 16. I think now you have got the clue. 

At first please keep the locations of all gold pieces in a separate array of two dimension by index starting from 1. Now, use the zero index to store the location of initial position.
Now, calculate the distance of every gold pieces to each other including the initial position.
Suppose, Array to store locations is 'a' and array to store the distances is 'b'. My code was:
      repc(i,0,m-1)
      repc(j,0,n-1)
      {
          if(s[i][j]=='x'){ a[0][1]=i;a[0][2]=j;}
          else if(s[i][j]=='g') {a[++c][1]=i;a[c][2]=j;}
      }
      repc(i,0,c)
      repc(j,i+1,c)
      {
        b[i][j]=b[j][i]=max(abs(a[i][1]-a[j][1]),abs(a[i][2]-a[j]  [2]));
      }
I am not describing the code. You can try if you are willing to do so. The following part is interesting in code: "max(abs(a[i][1]-a[j][1]),abs(a[i][2]-a[j][2]))" 
Isn't it?
This is the distance from one coordinate to another coordinate if you can move in all 8 direction. For four direction this equation could be failed!! 
Please put two coordinates in your paper and try to figure out what's going on in this equation.

Now, everything is ready. You can start bit-masking procedure recursively. The memory you can use is at best 16*2^16. 
If you have learn the bit-mask DP technique already then it shouldn't be a problem for you at all. If you don't then comment for further help. I shall try in shaa Allah.
Test Cases:
Input:
3
3 4
x..g
...g
g.gg

3 4
x..g
...g
gggg

20 20
....................
....................
.g...g..............
.............g......
....................
....g...............
..........g.........
g...................
.........x....g.....
....................
....................
...g................
....................
.....g......g.......
....................
..g.................
...........g...g....
....................
....................
g..................g

Output:
10
10
71

Techniques to solve Problem LightOJ 1013 - Love Calculator

Techniques of LightOJ 1013 - Love Calculator 

Category: This problem is mainly a Longest Common Subsequence Problem. 

Techniques: If you read carefully the problem statements then you should already know that this problem can be solved in two parts. 
In the first part what you need is to find the "The length of the shortest string that contains the names as subsequence" and in the second part what you need is that "Total number of unique shortest strings which contain the names as subsequence.". We are doing these in two parts too. 

First Part: Here, we are going to find the length of the shortest string that contains the names as subsequence. We can do this job in two ways as below.

1. A way could be to find the longest common subsequence of the two given string and subtract it from the addition of the length of two given string.
   How does it work?
   We have to find the length of shortest string. So, We actually don't need to take a letter twice which is available in both the given string.
   Suppose, A=bac and B=mct. The the resultant shortest subsequence will be C=bamct.
   How? Answer: Since ba and c are not common at all so we have to take them all. now, next character c is common.Hence we can only take one. And at last t can be taken as the last character.
   I think you know how to find the lcs of two string. If don't then learn it.
2. Another way two find the 1st part could be a modified version of
   longest common subsequence. In this process you don't need to subtract anything rather you do all the job in procedure lcs(). What you need here extra is that in the base case of recursive call, if any of the string got empty then you take the remaining letters in count. 

Second Part:  
The first part of this problem is relatively easy.  But the second part is a little bit thinking.
Since you know the length of the shortest string from first part, it is very helpful and necessary here. 
The function I have defined to do the work has three parameters. First is the present index of first string, second is the present index of second string and third is the number of characters we have taken till now.  
Case are:
If the two characters are same then proceed to the next characters by unique(i+1,j+1,num+1).
If two characters are not same then proceed by calling like follow:
ret=unique(i+1,j,num+1)+unique(i,j+1,num+1).

The base case is more important in my technique:

If any of the string got finished then what you will do?
My answer is, in common you add all the remaining letters from given strings with the num value from paremeter. If it is equal to length from first part then return 1(right approach:) ) else return 0(wrong approach :().


Comment if you have any Question.
 

Useful Techniques to solve Problems LightOJ - 1054

I am here to describe some techniques which can help you solve the following problems:

1. LightOJ - 1054 - Efficient Pseudo Code 
2. LightOJ - 1098 - A New Function
3. LightOJ - 1215 - Finding LCM

Please follow the above sequences one by one to get your desired problem. 

1. LightOJ - 1054 - Efficient Pseudo Code 

Technique:  

     

Techniques to solve Problems LightOJ - 1045 , LightOJ - 1067 , LightOJ - 1090

In this article I am writing some of my techniques in describe which I have used to solved the following problems:

1. LightOJ - 1045 - Digits of Factorial
2. LightOJ - 1067 - Combinations
3. LightOJ - 1090 - Trailing Zeroes (II)

Please follow the above sequences one by one to get your desired problem.

1. LightOJ - 1045 - Digits of Factorial  

Technique: You know about finding the factorial of a number. If you don't know, then don't worry. I am here to help you on this. Suppose, I have to find the factorial of n which is denoted by n! . The law to calculate the factorial is,
n!= n* (n-1) * (n-2) * (n-3)...*1 .
For n=4 , n!=4!=4*3*2*1=24. 
I am forwarding to the solution but before it I am going to give you some basic on this so that my blog become helpful to the readers who are new at programming. If you know then skip them and go to the starred section. 
In this problem you are said to find the number of digits. In C++, you can at most use long long int data type which can store value upto approximately 10^18. But here , the number is at most 1000000. The factorial of that number is impossible to store in long long int data type. What should we do now??

Yes!! There is a way to handle this situation and this is the array manipulation. In this method you at first declare an array and every time store the multiplication result in the array. And multiply the number with the elements of the array. Google this topics to be clear. 

*** If we follow the above procedure, the inefficient implementation can leads you to the TLE verdict. Besides there is a factor of base conversion. One way could be that you calculate the factorial in decimal base then convert it to the desired base. But this work is teddy and inefficient implementation can leads to another TLE verdict. 
To handle this situation shortly there's an formula exist.

Q. How to find the number of digits in factorial of n of base b? 
Answer: 

1. At first Precalculate the logarithms of number 1 to n and add them all in an array, say, sum[n].
   sum[n]=log(1)+log(2)+....+log(n).
2. Now divide sum[n] by the log of b: log(b).
3. result= sum/log(b).
4. Add 1 to the result for final result.
5. Ans= result+1;
6. For any value of n you just need to divide sum[n] and you can get the result at O(1).

2. LightOJ - 1067 - Combinations 

 

Technique: This is a straight forward combination problem. The formula for calculating the combination is,
C(n,r)=n!/(r!*(n-r)!); --- (1)
Optimization can be done by another formula C(n,r)=C(n,n-r); 
   
So at the initial part of the problem solving we shall reduce the value of r to n-r. It is your choice or you can keep it. Now, What we have to do is precomputation to avoid time limit exceeded verdict. Since the resultant number could be very big!! So we have to mod this number every time we perform a multiplication. You can check my code at the bottom of this post for see how it works!
As sample, if we multiply a and b and perform mod on them then we can writ as below:
(a*b)%m = =(a%m * b%m)%m.
It is not that tough. After precomputation of all factorial of all number then we have got the value of n!,r! and (n-r)!. we can multiply r! & (n-r)!.
Now this is an important part. Suppose a=n! and b=r!*(n-r)!. Since the result could be very big so you have to perform mod operation on them which would be like (a/b)%m.

 We can perform modular multiplication, addition and subtraction easily but we can't perform modular division in the same way. So, We have to bring a new term Modular Multiplicative Inverse. That means we have find the modular multiplicative inverse of b with respect to m.  Let N is the modular multiplicative inverse of b with respect to m.

Then (a/b)%m would be like,
(a*N)%m = (a%m * N%m)%m.
Isn't is easy? 
OK. then try your self and if any problem then let me know.
     

3. LightOJ - 1090 - Trailing Zeroes (II)  

 

Technique: The problem is very interesting if you can enjoy. In this problem you are said to find the number of  trailing zeroes. You probably be known that multiplication of 2 & 5 can produce a zero. Multiplication by olny 2 or only 5 never can increase the number of zero.

For example, 
2*5=10.
6*2=12.
9*5=45.

Remember, if I multiply 12 by 5 then we can get a zero. This is because 12 can be written as the multiplication of 2 and hence there's 2 exist there. And 2 and 5 have produced  a zero.

For Example, 12*5=2*2*3*5=60 (a Zero).
So, If we check a number that how many times it is divided by 2 and 5 in common then, we easily can find the number of zeroes in that number.

Here, Given C(n,r)*p^q. Since the input number is very big so if we calculate the necessary calculation in every test case then we could get time limit exceeded verdict. What's the necessary of it? Let's bypass it. A way could be that we can precalculate the necessary calculation before and can use them after in every test cases. The result could be found in O(1). 

When finding the factorial of a number then to find how many zeroes could be present  in the result, you need to sum all the numbers of two and five you have got from 1 to that number. In my code at the bottom, you would see that I have stored them in pp[i][0] and pp[i][1]. 
I used these data when calculates C(n,r).
For p^q, you don't need any previous number instead of present number of two and five. So, I kept them simply in pp[i][2] and pp[i][3]. When using them, to handle the power q, I just have multiplied q with pp[i][2] and pp[i][3].

After performing above operations the final number of zeroes can be found.

Don't hesitate to comment.