Techniques for LightOJ 1233 - Coin Change (III)

1233 - Coin Change (III) Hints:

Category: Iterative Dynamic Programming

Techniques:

Hey!! I am suggesting you the procedure I've followed!! Hope, it helps!!

This problem can be solved in O(n*m) time. where n=number of coins, m=amount.

Suppose, I want to check the money between 1 to 6.
I have coins 2,3. 2 can be used for 2 times.

The moneys are 1,2,3,4,5,6,7,8,9.
Suppose I want to start with coin 2.
then I'll iterate through 2 to 9 to check which money I can make with this coin.
Initially, You set dp[0]=1.//base case.
 
So, for 2 ,
starting from i=2,
I can make 2 since dp[2-[present_coin]]==1, i.e, dp[0]=1.
then set dp[2]=present coin.//since number of coins are limited, u will need this to check.
now store 1 in an array since this is the 1st use of coin 2.
_cnt array will store how many times a particular coin has been used to make a amount.

so, dp[2]=2.
_cnt[2]=1.

now, for i=3,
I can't make 3 since dp[3-[present_coin]]==0,i.e, dp[1]=0 and I couldn't make 1.
then leave it.
dp[3]=0.
_cnt[2]=0.

for i=4,
I can make 4 since dp[4-present_coin]==2, i.e dp[2]=2.
Here is a matter, since dp[4-present_coin]==2 that means coin 2 has been made with a use of present coin. Since number of coins is limited so you have to check _cnt array to determine whether you can use present coin or you have already used max time.

since _cnt[2]=1 that means you have used present coin 1 time to make previous amount,2. and if you want to make 4 using present coin then you will used present coin for _cnt[2]+1=2 times.Since I can use coin 2 for max 2 times so, I can use present coin to make 4.
dp[4]=2.
_cnt[4]=_cnt[2]+1.//1 for using present coin another time.

Now, for i=5,
I can't make 5 since dp[5-[present_coin]]==0,i.e, dp[3]=0 and I couldn't make 5 using present coin since coin 3 has not been made yet;
then leave it.
dp[5]=0.
_cnt[5]=0.

For i=6,
I can make 6 since dp[6-present_coin]==2, i.e dp[4]=2.
Here is a matter, since dp[6-present_coin]==2 that means coin 4 has been made with a use of present coin. Since number of coins is limited so you have to check cnt array to determine whether you can use present coin or you have already used max time.
Since cnt[4]=4 that means you have used present coin 2 times to make previous amount,4. and if you want to make 6 using present coin then you will used present coin for _cnt[4]+1=3 times,which is not allowed.Since I can use coin 2 for max 2 times so, I can't use present coin to make 6.
dp[6]=0.
_cnt6]=0.

The last case, i=6, is very important to understand.




  

Dont forget to comment if you have any problem.

 

 

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.

 

 

Techniques and Solutions of Problems LightOJ - 1007 , LightOJ - 1014, LightOJ - 1024 , LightOJ - 1028 , LightOJ - 1035

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

1. LightOJ - 1007 Mathematically Hard
2. LightOJ - 1014 Ifter Party
3. LightOJ - 1024 Eid
4. LightOJ - 1028 Trailing Zeroes (I)
5. LightOJ - 1035 Intelligent Factorial Factorization

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

1. LightOJ - 1007 Mathematically Hard

 

Technique: This is an exact application of Prime Numbers. In this problem just one variance is used and this is called Euler Phi. If you have no idea about Euler phi then please learn the basic from here. you should see that there is an equation which can find the number of relative prime smaller than a particular number.Say the number is n, then the Phi of n is defined as the number of relative prime smaller then n.

OK. We have just got the equation in above picture. There, P1, P2,...Pm are the primes that divides the number(n) and e1,e2,...,em are the exponent or the number of times a particular prime divides the number(n).
Since we have to multiply n hence we would multiply every number in the array by that line:
for(i=2;i<=5000000;i++) res1[i]=i; 
 
To solve this,  You need to first generate primes till the desired number. Then there is a technique which will help you to skip the time limit exceed verdicts. For every prime you just calculate its part for the numbers it divides.

2. LightOJ - 1014 Ifter Party    

 

Technique: Read carefully, you'll notice that P-L number piaju's are left. When no contestant can eat any piaju's then the case will be "impossible".
Now for possible case: There's no restriction in contestant number. It means that contestant number can be any value. You have to find the number of piaju's each contestant ate. So, each contestant can ate any number of piaju's which divides the P-L value. Suppore, if P-L is 4, then contestant can ate 1,2 or 4 piaju's each since they divides 4. Contestant can't ate 3 piaju's since it doesn't divides 4. So, we can divide P-L by all value less then P-L to check which value divides it and the value must be greater then L since it has been told that L<Q . 
An optimization is square root the P-L since dividing by the value of one site of square root value we could get the value of other site.

3. LightOJ - 1024 Eid  

 

Technique: This is a very interesting problem . I am describing it in a very simple straightforward way. Listen, You are given some de-sec. You are told to find such a de-sec (EID) in which all the races eat together. So, what you have understood?? You are given some number. Find the number which is divisible by all of them. Are you getting any coincidence among them. Yes!! This is a LCM,i mean, Longest Common Multiple problem. But, the problem is here you have to find the longest common multiple of maximum approximately 1000 numbers. So, the resultant number could be very big and overflow the long long int too. So, You need to do array manipulation. Did you know the prime factorization mathod to find LCM? This is necessary here. You can check my code below to understand the LCM procedure. But, Try yourself.

4. LightOJ - 1028 Trailing Zeroes (I)

 

Technique: Have you any idea about the finding the number of divisors of a number? This problem is a of that type. Here, Since you are said to find such a base in which trailing zeros exist so it can be assumed that if we can find the number of divisor of that number then the problem can be solved easily. Have you any idea? 
Suppose n is a number and its prime factorization is n=P1^x * P2^y. Then the number of divisors of n is = (x+1)*(y+1).
Suppose n=6, then 6= 2^1*3^1. Now, Number of divisor = (1+1)*(1+1)=4.
So, After prime generation just do this work and this is the result.

5. LightOJ - 1035 Intelligent Factorial Factorization

 

Technique: I Think you should get the technique to solve this problem yourself. You could have implementation problem. However, I am helping you in both case here. In this problem since you have to do prime factorization till N! (1,2,3,..,N) So, what you need to do extra is memorize the prime factorization of a number and add it with the factorization of next number till 1 to N. In my code, I did this.


If you have any problem understanding then leave a comment.