Tiles of Tetris, Not!

Problem

Tags : GCD , LCM

Idea : Given the height H and width W of a tiles . You have to find out the minimum number of tiles to make a square .

If H and W are equal , we can make a square by one tiles .

If H is greater than W , then

                 - If W is a divisor of H ,  then we can make a square by H/W tiles .
                 - Else we  can make a square by lcm ( W , H ) tiles .

If W is greater than H , then

                 -If H is a divisor of W ,  then we make a square by W/H tiles .
                 - Else we  can make a square by lcm ( W , H ) tiles .  

My Solution

Guess the Number

Problem

Tags : GCD , LCM .

Idea : This is a simple problem . Just need to know gcd and lcm evaluation .

Given a string consisting Y and N .

First , you have to calculate the lcm of the position index of Y in the string .

If the lcm is divisible by any position index of N in the string, print -1 else print the lcm .

If there is no Y in the string , lcm is 1 .

My Solution

Euler Totient Function

Problem

Idea : The problem in very easy . Just straight forward approach if Euler Totient Function is needed .

You can learn Euler Totient Function from wiki .

Just take the input n and call phi function to calculate phi(n) . Then print it .

My Solution

Prince and Princess

Problem

Idea : Given two number sequence . You have to find out the LCS of the two . But you can not use the normal LCS finding algorithm .

You have to find out LCS using LIS . You can learn LIS from here

For a single sequence of number , we can calculate LIS as below -

Push the first element in a vector . Then , if the number is greater then the top element of the vector , push it also , else find out its position of the vector using binary search . Then put it in the position .

Then the LIS is the size of vector .

But for two sequence ?

We only take the element that are present in both sequence . To maintain increasing sequence , we may indexing the first sequence from 1 .

Then in second sequenec , we cheak whether it whether it present in first sequence or not . If it is not present , skip it . The first value that is present in both sequence , push it in a vector . Then if the index of next element is greater than the index of the last element of vector , push it . Else , find out the position of the index in the vector and put it .

Finally , the size of vector is our answer .

My Solution

Divide the Land

Problem

Idea : Given a trapezium . You have to divide the trapezium in two equal part of area . You have to draw a parallel line with the parallel line of the trapezium .

Consider the above trapezium . Given AB  ,CD , AD and BC . You have to find out AE and BF so that we can draw the parallel line joining E and F . Given trapeziums are as above . Where AB || CD and AB>CD .

Here , the area of ABFE = the area of CDEF = the area of trapezium ABCD / 2 .

The area of trapezium ABCD = ( AB + CD ) * h / 2 ------------------------ (1)

Here h is height and it is unknown .

We can draw a triangle combining the triangle AmD and BnC . The new triangle is pqr . We know its sides . pq = AB - CD , pr = AD and qr = BC . So we can calculate its area . Say it is triangleArea .
We know , area of triangle pqr , triangleArea  = pq * h / 2 .

                                              or , h= 2 * triangleArea / pq .

Putting the value of h in equation (1) , we may get the area of trapezium ABCD . Say it is trapeziumArea .

So , the area of ABFE = the area of CDEF = trapeziumArea / 2 .

Or , the area of CDEF = trapeziumArea / 2 = CD * n + triangle rst .
Or ,  CD * n +  b * n / 2 = A  .        --------------- (2)        Let , A =  trapeziumArea / 2 .

In the triangle pqr , rst and pqr are simillar triangle .

So , b / pq = n / h
So , b = n * pq / h

Putting the value of b in equation (2) ,

we get , CD * n + ( n * pq / h ) * n / 2 = A
       Or,  CD * n + pq * n * n / 2h = A
      Or , pq * n * n + 2h * CD * n - 2 * h * A = 0

So , n = ( -2h * CD + sqrt(( 2h * CD ) * ( 2h * CD) - 4 * pq * ( - 2A * h ) ) ) / ( 2 *pq )

In triangle AmD , n / h = DE / AD
                   So , DE = AD * n /h .
                   So , AE = AD - DE .

Similarly , in triangle MnC ,
                 n / h = CF / BC
            So , CF = BC * n / h
            So , BF = BC - CF .

And our answer is AE and BF .

My Solution

Vaishnav and Pizzas

Problem

Idea : Given an integer N . You have to find out the nuber of P/Q where gcd(P,Q) = 1 ,  P/Q<1 and P,Q can be up to N .

To do so , if we iterate P , Q up to N and try to cheak gcd , it must get TLE . Because N can be up to 10000 and the complexity is 10000*10000 will not pass within the given time limit . 

So , we need the help of Euler's Totient Function . You can learn Euler's Totient Function from wiki .
Euler's Totient Function gives the number of integer i(<n) that are co-prime to n . That means their gcd = 1 .

Euler's Totient Function gives output 1 for input 1 . But 1/1 = 1 .So we can avoid this . We can make P/Q by any co-prime/n(<1) . So for every value throw 2 to N returned by Euler's Totient Function is the possible couple of number . We can add these and our answer is this .

My Solution

Little Vaishnavi and plywood

Problem

Idea : For this problem , given the position of damaged wood m and the number of jump k that the damaged wood can tollarate over it .You have to count the number of jump until the damaged wood break down .

Here we have to handle the following cases-

1 . m = 1 and k = 0 or k>0
2 . m = 5 and k = 0 or k>0
3 . 1<m<5 and k is even or k is odd.

1 . If m = 1 , that means the damaged wood is in first position .
For that ,
If the value of k = 0 , we can not make any jump .
If the value of k is other than 0 ,
For this situation ,
If k=1 , Number of jump = 8
If k=2 , Number of jump =16
If k=n , Number of jump =8*n


2 . If m = 5 , that means the damaged wood is in last position .

For that ,
If the value of k = 0 , we can make 4 jumps .
If the value of k is other than 0 ,
For this situation ,
If k=1 , Number of jump =12
If k=2 , Number of jump =20
If k=n , Number of jump =8*n +4

3 .  If the value of m is not 1 and not 5 .

If k is even ,the number of jump is 4*k+(m-1)
If k is odd , the number of jump is 4*k+(5-m)

My Solution