Codevita Challenge, 6 Interesting Questions.

Anonymous User

1451

Post is slightly long. sorry for that, I have included every possible detail I could.

1 ) Walls

Problem Description -

A company manufactures walls which can be directly implanted at the site. The company uses small square bricks of material C and material D which have similar looks but have huge difference in quality. The company manufactures walls of square shapes only to optimize their costs.

A novice employee created a square wall using bricks of material C and D. However, the client had asked the wall to be made of only high-quality material - material C.

To solve this problem, they will place the wall in a special furnace and heat it such that the material D melts and only material C remains. Material C brick will move down due to gravity if a material D brick below it melts. The new empty space created will be filled by new material C square walls. They also want to use biggest possible C square wall while building the final wall. For this they will position the wall in the furnace in an optimal way i.e. rotate by 90-degrees any number of times, if required, such that the biggest space possible for new material C wall is created. No rotations are possible when the furnace starts heating.

Given the structure of the original wall created by the novice employee, you need to find out the size of the new C square wall which can be fitted in the final wall which will be delivered to the client.

Constraints :
1 < N < 100

Input :

First Line will provide the size of the original wall N.

Next N lines will provide the type of material (C and D) used for each brick by the novice employee.

Output :
Size of the biggest possible C square wall which can be fitted in the final wall.

Examples :

Example 1

Input -

4

C D C D

C C D C

D D D D

C D D D

Output

3

Explanation

If the wall is placed with its left side at the bottom, space for a new C wall of size 2x2 can be created. This can be visualized as follows

D C D D

C D D D

D C D D

C C D C

The melted bricks can be visualized as follows


- - - -

- C - -

C C - -

C C - C

Hence, the maximum wall size that can be replaced is 2x2.

If the wall is placed as it is with its original bottom side at the bottom, space for a new C wall of size 3x3 can be created. Post melting, this can be visualized as follows.

- - - -

C - - -

C - - -

C C C C

Hence, the maximum wall size that can be replaced is 3x3 in this approach.

Since no rotations followed by heating is going to a yield a space greater than 3x3, the output is 3.

Example 2

Input

7

C D D C D D D

C D D C D D D

D D D D D D C

D C D C D D D

D D D C D C D

C D D C D C C

C D C D C C C

Output -

5

Explanation

If the wall is placed with its left side at the bottom, a space for new C wall of size 5x5 can be created. This can be visualized as follows

D D C D D C C

D D D D C C C

D D D D D D C

C C D C C C D

D D D D D D C

D D D C D D D

C C D D D C C

When this orientation of the wall is heated, a space for new C wall of size 5x5 is created after the D bricks melt

_ _ _ _ _ _ _

_ _ _ _ _ _ _

_ _ _ _ _ _C

_ _ _ _ _ _ C

_ _ _ _ _ C C

C C _ C C C C

C C C C C C C

Whereas, if the rotation was not done, the wall formed after the D bricks melt will be as follows

_ _ _ _ _ _ _

_ _ _ _ _ _ _

_ _ _ C _ _ _

C _ _ C _ _ _

C _ _ C _ _ C

C _ _ C _ C C

C C C C C C C

When this orientation of the wall is heated, a space for new C wall of size 3x3 only is created after the D bricks melt

Hence rotation is important and correct answer is 5x5

Since no rotations followed by heating is going to a yield a space greater than 5x5, the output is 5.

2) Factor of 3

Problem Description
Given an array arr, of size N, find whether it is possible to rearrange the elements of array such that sum of no two adjacent elements is divisible by 3.

Constraints

1 <= T <= 10

2 <= N <= 10^5

1 <= arr[i] <= 10^5

Input

First line contains integer T denoting the number of testcases.

Each test cases consists of 2 lines as follows-

First line contains integer N denoting the size of the array.

Second line contains N space separated integers.

Output
For each test case print either "Yes" or "No" (without quotes) on new line.

Examples :
Example 1

Input

**Output
**
Yes

Explanation

Some of the rearrangements can be {2,1,3,3}, {3,3,1,2}, {2,3,3,1}, {1,3,3,2},...

We can see that there exist at least 1 combination {3,2,3,1} where sum of 2 adjacent number is not divisible by 3. Other combinations can be {1,3,2,3}, {2,3,1,3}.

Hence the output is Yes.

Example 2

Input

Output

No

Explanation

All possible combination of {3,6,1,9} are

{1,3,6,9}, {1,3,9,6}, {1,6,9,3}, {1,6,3,9}, {1,9,3,6}, {1,9,6,3},

{6,1,3,9}, {6,1, 9,3}, {6,3,1,9}, {6,3,9,1}, {6,9,1,3}, {6,9,3,1},

{3,1,6,9}, {3,1,9,6}, {3,9,1,6}, {3,9,6,1}, {3,6,1,9}, {3,6,9,1},

{9,1,3,6}, {9,1,6,3}, {9,3,1,6}, {9,3,6,1}, {9,6,1,3}, {9,6,3,1}.

Since none of these combinations satisfy the condition, the output is No.

3 ) Even Odd

Problem Description
Given a range [low, high] (both inclusive), select K numbers from the range (a number can be chosen multiple times) such that sum of those K numbers is even.

Calculate the number of all such permutations.

As this number can be large, print it modulo (1e9 +7).

Constraints

0 <= low <= high <= 10^9

K <= 10^6.

Input

First line contains two space separated integers denoting low and high respectively

Second line contains a single integer K.

Output

Print a single integer denoting the number of all such permutations

Examples

Example 1

Input

4 5

3

Output

4

Explanation

There are 4 valid permutations viz. {4, 4, 4}, {4, 5, 5}, {5, 4, 5} and {5, 5, 4} which sum up to an even number

Example 2

Input

1 10

2

Output

50

Explanation

There are 50 valid permutations viz. {1,1}, {1, 3},.. {1, 9} {2,2}, {2, 4},... {2, 10} . . . {10, 2}, {10, 4},... {10, 10}. These 50 permutations, each sum up to an even number.

4 ) Unlocker

Problem Description
A locker is comprised of one or more layers. Each layer can be rotated only in one direction. Odd numbered layers rotate in anti-clockwise direction (left to right), and even numbered layers rotate in clockwise direction (right to left).

You are given a locker, in the form of a matrix. The matrix will be rectangular in shape. The outer most layer of this matrix is layer1. In context of the diagram below, the numbers painted in red are layer1 and the inner numbers constitute layer2. Bigger matrices will have more layers.

One rotation defined as a given number moving in the neighbouring spot i.e. one spot left for clockwise rotation and one spot right for anti-clockwise rotation.

Number of rotations for each layer required to unlock the locker will be provided as input. Print the final unlocked matrix as output.

Constraints

1 < M, N <= 300

0 <= Numbers in matrix < 100

1 <= Number of rotations <= 10^9

M%2=0 && N%2=0

Input

First line contains two space separated integer M and N which denotes the number of rows and number of columns, respectively

Next M lines contain N space separated integers depicting the locked matrix

Last line contains L space separated integers, where L is the number of layers. Each number on this line denotes the number of rotations for every layer from 1 to L

Output

Print unlocked matrix

Examples
Example 1

Input

Output

4 3

2 1

Explanation:

There is only one layer. So, we have to rotate it in anti-clockwise direction with 2 rotations.

**Example 2
**
Input

Output

Explanation:

Here we have to rotate layer1 in anti-clockwise direction with 2 rotations, and layer2 clockwise with 2 rotations.

5 ) Particles

Problem Description

There is a cube of height H, and there are 4 moving particles on the vertical edges of the cube. Initially particles are at some height A, B, C and D respectively. These particles are moving in different direction (Only upward or downward, no sideways movement) with different speed.

If the particle is moving upward or downward reaches the tip of the cube then it remain at the tip only and will not move further. If other particles have not reach the tip they continue to move along their respective edges in their respective direction till the last particle reaches the tip.

These 4 particles will make two triangles in a 3-D plane. Since the particles are moving, sum of the area of these two triangles will change every moment.

Find out the maximum and minimum of the sum of the areas of these two triangles.

Refer the Examples section for better understanding.

Constraints

1 <= H <= 100

0 <= A, B, C, D <= H

0 <= V1, V2, V3, V4 <= 100

Input

First line contains an integer H which denotes the length of the side of cube.

Second line contains 4 space separated integers denoting the initial position of all 4 particles on the 4 vertical edges, say A, B, C and D respectively.

Third line contains 4 space separated integers denoting the speed of all particles, say V1, V2, V3, and V4 per time unit respectively.

Fourth line contains 4 space separated characters U or D denoting the direction of movement of particles. U denotes the upward direction and D denotes the downward direction.

Output

Print 2 space separated integers which denote the value

[4 * [Max (sum of area of triangle ABC and area of triangle ADC)]2] and

[4 * [Min (sum of area of triangle ABC and area of triangle ADC)]2]

respectively. If the above values are decimal value round them off to nearest integer.

Examples
Example 1

Input

Output

80000 40000

Explanation

Note: Within a state the area of sum of triangle ABC and triangle ADC is constant. The MAXAREA and MINAREA terms used in the diagrams above are used to keep a track of maximum area and minimum area achieved until that point in time.

MAXAREA = [4 * [Max (sum of area of triangle ABC and area of triangle ADC)]2]

MINAREA = [4 * [Min (sum of area of triangle ABC and area of triangle ADC)]2]

Example 2

Input

5 5 5 5

1 2 1 2

D U U D

Output

80000 40000

Explanation

The movement per time unit is depicted as shown in the diagrams below.

// Sorry I don't have image for this question.

MAXAREA = [4 * [Max (sum of area of triangle ABC and area of triangle ADC)]2

MINAREA = [4 * [Min (sum of area of triangle ABC and area of triangle ADC)]2]

Example 3

Input

Output

120000 40000

Explanation

MAXAREA = [4 * [Max (sum of area of triangle ABC and area of triangle ADC)]2]

MINAREA = [4 * [Min (sum of area of triangle ABC and area of triangle ADC)]2]

6 ) Tennis Score

Problem Description
A game of tennis (singles) is played. Regions of the court are named as shown in the image.

The running score of each game is described in the manner: "0", "15", "30", and "40". If at least three points have been scored by each side and a player has one more point than his opponent, the score of the game is advantage ("Advantage") for the player in the lead. (source: Wikipedia)

A set consists of a sequence of games played with service alternating between games, ending when a player wins a set by winning at least six games and at least two games more than the opponent. If one player has won six games and the opponent five, an additional game is played. If the leading player wins that game, the player wins the set 7-5. If the trailing player wins the game (tying the set 6-6) a tie-break is played. A tie-break, allows one player to win one more game and thus the set, to give a final set score of 7-6 or 6-7.(source: Wikipedia)

Aim is to toss the ball on the green part of the other side of the court. A set of strings will be provided signifying where the tennis ball has been tossed on the court. Assume that no player will hit the ball directly (i.e. without the ball being tossed on his (green) side of the court).

For Example, a string Q4 Q1 Q3 O1 will mean that server serves and the ball hits the area Q4. Receiver returns and ball hits ground in area Q1, server hits back again to area Q3 and then the receiver hits 'long' to area O1 and loses a point. So the set output is 0-0 and the current game output will be 15-0.

Following are the rules of the game:

Game always starts with Server on H1 side (lower side in the image)

Serve changes after every game is won

On 'Serve' ball should hit on any 'Q' part of the other side. Hitting on 'H' part will be considered a fault

While serving, if the server makes a double fault (ball should fall on his side or outside region twice), the server loses one point

Points scored by the current server are mentioned first, for example if server wins the first point score will be 15-0

At the end of a set, a changeover happens i.e. players change sides of the court.

In case of game score 40-40, display "Deuce". In case of Server's Advantage, display "Advantage Server".

In case of Receiver's Advantage, display "Advantage Receiver"

Number of sets played may not exceed 5

In case a set is complete a set score of 7-5 will be denoted as:

7 0 (first player set score)

5 0 (second player set score)

Since the second set is about to start, a score of 0 0 is displayed. Please read these scores vertically.

When a new game is about to start, display 0 - 0 for new game. For example:

0 0 (current game score)

Departure from Tennis rule:

In real game of tennis a server is required to serve cross court. However, in this problem the server can serve in any court {Q3, Q4} for server 1 and {Q1, Q2} for server 2
In real game of tennis a tie-break is counted in scores of 1, 2, 3, 4 instead of 15, 30, 40 etc. However, in this problem a tie-break is won according to regular rule i.e. by scoring points like in a regular game. For example, lets say the score is 6-6. In regular tennis a tie break would follow, but in this problem the 13th game will be played and scored using the same rules applied for first 12 games. Whoever wins the 13th game, wins the set i.e. either 7-6 or 6-7

In a real game of tennis, a changeover (players switching court sides) happens at the end of a set or after the first game is played in a new set. However, in this problem changeover happens at the end of the set

Constraints
Number of space separated strings in input < 500

Input
One line containing a string representing the sequence where the ball drops, separated by space

Output

First line containing the set score of all the sets of the Server (starting from first and separated by space)

Second line containing the set score of all the sets of the Receiver (starting from first and separated by space)

Third line containing the game score of the current game (separated by space) or "Deuce" or "Advantage Receiver" or "Advantage Server", as may be the case.

Examples

Example 1

**Input **

Q1 Q1

Output

0
0
0 15

Explanation

Server serves and ball hits area Q1. He will not lose point because he is serving. Again he serves and ball hits area Q1. Since, this is a double fault he loses one point. Hence the game score is 0-15.

Example 2

Input

Q1 Q1 Q3 Q3 Q1 Q1 Q3 Q3 Q1 Q1 Q3 Q3

Output

0
0
Deuce

Explanation

· String Q1 Q1 indicates a double fault. The score becomes 0-15

· Next String Q3 indicates a valid serve. The second Q3 indicates that the Receiver could not return the serve because it fell into his own half. This makes the score 15-15.

· Similar sequence repeats for two more times, making the score 30-30, then 40-40 which is Deuce.

Example 3

Input

Q1 Q1 Q2 Q3 O1 H2 H2 Q1 Q1 Q1 Q2

Output

1
0
0 0

Explanation

· Except points Q2 Q3 O1 all other string indicates a double fault on part of the server

· Q2 Q3 O1 earns the server one point

· Overall the server loses the game

· Now a new game begins and the current server becomes receiver and vice versa

· The score is printed after the new game begins and the score is 0 0. Hence, server score is 1 whereas the receiver score is 0

I found these questions interesting and though if we could discuss optimal approach it would be benifitial for all of us. Thank You.

Comments (2)