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

Vaishnav and Factorials

Problem

Idea : Given an integer N . You have to do the following tasks-

1 . Calculate the factorial of  N .

2 . Count how many 4 or 7 are in N!

To do the first task -

You have to calculate N! . Very simple . Wait , the range of N from 1 to 250 . Using built in data type , you can calculate factorial up to 20 . Then ?

Now , you have to think something new . To face this situation , we can use array . In an array , we will keep a value . In every cell of the array , we will keep every digit of the value . Now think about calculating factorial as below -

                                         factorial = 1 ;
                                         for(int i=1;i<=N;i++)
                                         factorial*=i ;        // Multiplication to calculate factorial

For an array , we will multiply with array cell start from starting .

Initially we assign array[0] = 1 , and carry = 0 . Then for every value comes in the loop , we will multiply with every cell and add carry . Then the last digit of the value will remain in current position of the array . The carry is value/10 . After multiplying , we keep the carry infront of the array . Thus , if we iterate till N . We will get factorial in the array .

To do the second task -

Iterate from the starting of the array to the last and increase counter if array[i]==4 or array[i]==7 .

Then print the value of counter .

My Solution

Composite Numbers Having 7

Problem

Idea : Given two integer M and N where M<=N and the value of N would be up to 1000000 .

You have to do the following tasks -

1 . Find out the composite number C where M<=C<=N .

2 . Count the composite number containing digit 7 .

3 . If there is no composite number that contains 7 , print -1 else print the number of composite number that contains 7  . 

To do the first one , you can use sieve method to indicate the composite numbers .

Then for the second one , cheak every composite number . Whether it contains 7 or not .

If yes , increase counter .

And for the last one , if the value of counter is 0 , print -1 else print the counter .

My Solution

Small factorials

Problem

Idea : Given an integer n . You have to calculate n! . Very simple . Wait , the range of n from 1 to 100 . Using built in data type , you can calculate factorial up to 20 . Then ?

Now , you have to think something new . To face this situation , we can use array . In an array , we will keep a value . In every cell of the array , we will keep every digit of the value . Now think about calculating factorial as below -

                                         factorial = 1 ;
                                         for(int i=1;i<=n;i++)
                                         factorial*=i ;        // Multiplication to calculate factorial

For an array , we will multiply with array cell start from starting .

Initially we assign array[0] = 1 , and carry = 0 . Then for every value comes in the loop , we will multiply with every cell and add carry . Then the last digit of the value will remain in current position of the array . The carry is value/10 . After multiplying , we keep the carry infront of the array . Thus , if we iterate till n . We will get factorial in the array .


My Solution

Holes in the text

Problem

Idea : Given a string composed of uppercase letters .You have to count the hole in the string , specifically ,  an alphabet B contains 2 hole , A contains 1 etc .

Look , only alphabet B contains 2 hole . Alphabet A , D , O , P , Q and R are have 1 . Other have no hole . The summation of hole containing each alphabet in the given string is our answer .

My Solution

Factorial

Problem

Idea : Given an integer n , you have to find out number of zeros at the end of n! .

There are one zero at the end of a number x . What is its meaning ? That means , x can be expressed as multiple of 10(5*2) . Similarly , There are two zero at the end of a number x . What is its meaning ? That means , x can be expressed as multiple of 10(5*2)*10(5*2) . If we want to count the number of zero , we should count the number of 5*2 appears in the number . The number of zero is equal to the number of 5*2 .

To do so , we first look up at 5 and 2 . How many 5 and 2 is in the number .

As example , if n=10

Number of 5 = 10/5 = 2
Number of 2 = 10/2 = 5

We see that , the number of 2 > the number of 5 .

So , cheaking 5 is enough .

In an integer n , number of 5 is n/5 .

Some numbers have two , three or more munber of 5 as 25 , 50 , 75 , 100

So , we can cheak in n the total occurance of 5 by -

Single 5 = n/5
Double 5 = n/25
Triple 5 = n/75 and so on......

The total number of 5 = The total number of 5*2 = The total number of zero .


 My Solution

Enormous Input Test

Problem

Idea : Take input two integer n and k . Then again take input n long integer . Count the number of value those are divisible by k .

My Solution

ATM

Problem

Idea : It is an easy problem . Take input an integer x and a floating value Y . If the integer x is multiple of 5 and x+0.5 if less than or equal Y , print Y-(x+0.5) . Else print Y .

My Solution

Life, the Universe, and Everything

Problem

Idea : It is a very easy problem . Just for cheaking I/O knowledge .
Take integer as input and print that . When 42 is arrive , Stop .

My Solution

EmoticonsDiv2

Problem

Idea : Given emoticon number N and one emoticon . You have to make N emoticon by copy pasting the given emoticon . You have to determine the smallest number of action to reach N .

To do so , we think a function that gives minimum number of action for N .  Now see , we can copy paste only those imoticon whoose number are proper divisor of N . If  N = 1 , then we need 0 action to reach N . Because we have 1 emoticon given . It can be base case . For every divisor of N . We calculate the action number and take the minimum one .

My Solution

ChooseTheBestOne

Problem

Idea : Given a circle of people each having a t-shirt numbered from 1 to N . You have to find out the person with which t-shirt remain alive after playing  the discussed game in problem .

In this problem , we have to find out one , out of N . So , N-1 turn needed to eliminate N-1 people . In each turn t , people having t^3 called by shiny eliminate . After one elimination , we starts from the next person who was the next person of immediately eliminated . So , we need to start from the position . Each turn calling starts from 1 . So a person who is t^3 far from the current position will eliminate . So for every turn , we can find out the eliminated position by the formula :

                                E_Position = Current_position+t^3-1

The peoples are in circle and the counting may overlap . So , the formula will be :
                               
                                E_Position = ( Current_position+t^3-1 ) % Number_of_remaining_people .

My Solution

NumbersChallenge

Problem

Idea : You are given a number sequence and you have to find out the smallest number that can not be formed by the adding some combination of given integers .

To do so , we can evaluate all combination produced value . If the amount of given integer is N . Then 2^N combination is possible . We can use bitmask to make the values that produce the given integer sequence .

 We calculate those value and give true result for those values in a boolean array . Then iterating from first , we can easily find out the required value . 

My Solution

Monkey Banana Problem

Problem

Idea : Given a diamond shaped 2D array . You have to find out the maximum summation of weight of those cells of which cells form a road to upper cell to lower cell .

To do so , we consider the upper single cell . For this cell , the maximum summation is itself .
For the next two cell , calculate the maximum summation . From which cells , we can visit the cell , we take the maximum of those . Then we do so for next rows . That means , every cell has its maximum summation that is required as above . So , our result is at the last cell .

My Solution

Ciel and Map

Problem Link : http://www.codechef.com/problems/CIELMAP/

Idea : Given some point N . You have to find out the larger side of a quadrilateral that can be formed by 4 out of N point . The boundary of the quadrilateral may not be crossed by itself .

If N>4 , our answer is the distance between the farthest couple of points .
It can be determined using loop .

If N=4 , then we have to face the calculation for possible all quadrilateral .
For possible all permutation , we have to calculate two thing -

1. Whether the quadrilateral cross its own boundary or not .
2. If yes , skip this quadrilateral .
   Else , take the maximum side for count .

We can easily find out 1st requirment using the concept of vector cross product .

If points are A,B,C and D.

If the sign of AB*AC and AC*AD are same , that means all points are consecutively clockwise or anti-clockwise and a valid quadrilateral is possible . Then calculate AB , BC , CD , AD and take the maximum value of side for counting .

My Solution

Lights

Problem Link : http://www.codechef.com/problems/LIGHT/

Idea : In this problem , we have to find out the maximum height where a plane can run totaly in light. The height must be remain among the 0 and 1000 , as problem statement says .  So we can easily find out the height doing binary search within the range of h=0 and h=1000 .
For each value , we have to cheak whether in that height the plane can run or not .
At first , we calculate the cut point of the line at a height , along with which line , the plane can run by each light . Given the half of an angle of each triangle . This is the way we can calculate the cut point with the help of trigonometric ratio of tangent .
Now we want to see that which points are consecutive .

if given L and R are in a region where the cut points are consecutive , our answer is true and otherwise not.

Following this formulation , we can find out the maximum height .

My Solution

Snape and Ladder

Problem Link : http://www.codechef.com/problems/SNAPE/

Idea : If B is the base , L is the left side and R is the right side of a triangle ;
Given B and L . You have to calculate the minimum and maximum value for R .
The value of R will be minimum , if the angle between  B and R is 90 degree .
Then it is a right angle triangle and we can easily calculate the value of R by pythagoras theorem .

 So  ,  R min = sqrt(L*L-B*B)

The value of R will be maximum , if the angle between  B and L is 90 degree .
Then it is a right angle triangle and we can easily calculate the value of R by pythagoras theorem .

 So  ,  R max = sqrt(L*L+B*B)

My Solution

Chef and the Cake I

Problem Link : http://www.codechef.com/problems/CAKE1AM/

Idea : We have to calculate the area that covers by two rectangle . Given the co-ordinate in 2D space . Our answer is the summation of the area of the two rectangle minus the area that they intersect , that also a rectangle . If we analyze some case , we can easily understand that their intersection rectangle's lower left corner is the maximum x co-ordinate and the maximum y co-ordinate of all the lower left points as wll as its upper right corner is the minimum x co-ordinate and the minimum y co-ordinate of all the upper right points . Tf the two point makes a rectangle , that means the two rectangle intersects . The two point makes a rectangle if the x and y co-ordinate of second point is larger than first .
Take input for co-ordinate of 4 points .

Add result the area made by the two rectangle . As shown below -

result+=(x2-x1)*(y2-y1)+(x4-x3)*(y4-y3)

If the rectangle intersects , subtract the area made by intersection rectangle from result . Show output .

My solution

Chef and The Right Triangles

Problem Link : http://www.codechef.com/problems/RIGHTRI/

Idea : Given co-ordinate of three vertex of a triangle in 2D space . You have to determine whether it is right triangle or not . If yes , Increase counter , because there are N triangle . A triangle is right triangle if and only if it satisfies the pythagoras theorem . If its largest side is c and other are a and b . Then the relation holds for all right triangle.
                c*c=a*a+b*b

Take input and calculate its sides . Find out its largest side and cheak the above condition and increase the counter if it is right triangle . One thing is important that , the sides are given by distance formula -

                Distance = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))

Here we do the sqrt operation and in condition cheaking part we are squaring it . It may occur floating point error . For that we calculate side by -

Distance = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)

And our cheaking condition will be -

c=a+b.

The number of right triange is our answer .

My solution : http://pastebin.com/n6HhaFca

Circle of death

Problem Link : http://www.codechef.com/problems/CIRKILL/

Idea : Given N points , you have to take three points so that a unique circle can be formed . For other point , you have to count these point that is inside the circle or at the perimeter.
First take an int int pair to take point . Take input and store in a vector . Now there are how many ways to choose three point fron given N point ??? Obviously we can find out it with the help of loop . Now we should cheak whether a unique circle can be formed throw the three point or not . To do so , we can cheak the area of the triangle formed by the three points.
The formula to calculate area is-

             Area=x1*(y2-y3)+x2*(y3-y1)+x3(y1-y2)

If the area is not zero , that means a circle can be formed.

Now for other points , we have to count these point that is  inside the circle or at the perimeter. Now a determinant -

| (x² + y²)  x   y  1 |

| (x₁²+y₁²)  x₁  y₁  1 | = 0

| (x₂²+y₂²)  x₂  y₂  1 |

| (x₃²+y₃²)  x₃  y₃  1 |

given by the general circle equation of the three points and another point that we want to find out.

Now for all cases , solve the determinant . If its value is zero , that means the point is at perimeter of the circle and if the sign of the velue of the determinant is opposite to the area of the triangle , the point is inside the circle . So we got the number of occurning . Now the probablity of the number to all possible cases is our answer .

My Solution : http://pastebin.com/Sqw5PWpW

Closest Points

Problem Link : http://www.codechef.com/problems/CLOSEST

Although my solution for this problem is not good,i would like to share it with you.

Idea: Given N points as 3D for BTPD help center and Q points for banks.The problem want at least one correct solution fer accept :).In my solution,i calculate for first bank.Take input for N points in an array.Then take input for Q banks.Calculate distance from each help center to first bank.Find out the minimum one.Save the number of that help center that is closest to first bank.
Then show the same result for Q banks :)
My solution : http://pastebin.com/bUe1YDNS

Triangle From Centroid

Problem Link : http://www.spoj.com/problems/TRICENTR/

Idea: If distances from centroid to side a,b and c are ga,gb and gc respectively.
The height of the triangle is 3*ga , 3*gb and 3*gc. So we can calculate the area of the triangle easily by this formula-
           Area=a*ga*3/2                where,base is a and height is ga*3   
Now we have to calculate side b and c.
Look,we know the area of the triangle,the height of the triangle.It is quite simple to calculate side b and c.
            Area=b*gb*3/2.               where,base is b and height is gb*3
         So, b=(2*Area)/(3*gb)
 Similarly,  c=(2*Area)/(3*gc)
Now the radius of circumcircle is
R= (a*b*c)/(4*Area)
Distance from Orthocenter of the triangle to the center of the circumcircle of the triangle HO is-
HO=sqrt(9*R*R-a*a-b*b-c*c)
We know that,the distance from Orthocenter of the triangle to the centroid of the triangle HG is-
HG=2*HO/3

Our answer is Area and HG :)

My Solution : http://pastebin.com/mUyePC2u

Calculate the Area

 Problem Link : http://www.spoj.com/problems/CALCAREA/

 Idea: Given N points and we have to deduce the area of polygon made of given  points. First triangulate the polygon taking 3 points at a time.If the polygon is convex,  the summation of area of those triangles is the answer.Otherwise the answer is  the summation of area of those triangles whose points are convex in respect of the polygon minus summation of area of those triangles whose points are concave in respect of the polygon.
Take a vector of int int pair. Store the co-ordinate of given points in pair and push the pair in vector.Now,assume fixed the first point and make vector from first point to other point.Calculate the cross product taking couple of vector from first to other with the formula-
                  A*B=x1*y2-x2*y1.
So area of the triangle is A*B/2.
and add them.
You oppose that,all triangle are not part of the polygon,that means we should subtruct the area of concave triangles.See more specifically,if the triangle is concave to the polygon,the area given by the formula is positive else it is negative.Our convex area are negative and concave are positive.If we add them,we should get the required area.Of course take its absolute value.

My Solution:  http://pastebin.com/L9rgPBHB

Helping Lira

Problem Link : http://www.codechef.com/problems/HELPLIRA

Idea: For N triangle,Given the co-ordinates of three point for each.First calculate the area of each triangle and push in a vector.Take another vector and push in it the values of first vector. Sort second vector.Now we have minimum value at V2[0] and maximum value at V2[size-1].Our answers are the indexes of minimum value and maximum value in first vector.If there are multiple maximum or minimum value,we have to result for the last.For that,search maximum(Contained in V2[size-1]) and minimum (Contained in V2[0]) value in first vector from the last.If one if found,keep continue for another one.Then show output.

My Solution: http://pastebin.com/GFpyevR1