Join Us
Loading Similar Posts
Entering edit mode
Ques - 1 Single Lane Highway
- Problem Description
Certain number of cars are passing a single lane road. Speeds of all cars vary. It is easy to see, that depending on the speeds of the cars various groups will be
formed.
Being a single lane road passing/overtaking is not allowed. Given speeds of cars, calculate how many groups can be formed if all possible permutations are taken
into account. Refer example for better understanding.
Print number of groups divided by the number of permutations.
- Constraints
0 <= N < 10 ^ 5
0 <= speed of individual vehicle < 10 ^ 9
- Input
First line contains an integer N, which denotes the number of vehicles
Second line contains N space separated integers which denotes the speed of individual vehicle.
- Output
Print number of groups divided by the number of permutations rounded upto 6 decimal places.
- Time Limit
- Examples
Example 1
Input
10 20 30
Output
1.833333
Explanation:
So all possible permutations are:
{10 20 30}
(10 30 20)
{20) (10 30)
(20 30) (10)
(30} {10 20}
(30 20} (10)
So here there are total 6 permutations, and total number of groups are 11.
So, output is 11/6 = 1.833333
Example 2
Input
56 78 13 92
Output
2.083333
Explanation:
So here there are total 24 permutations,
For example:
(56 78 13 92)
(92) (13 78 56)
(56) (13 92 78)
So on and so forth. The total number of groups are 50
So, the output is 50/24 = 2.083333
Ques - 2 Path through Graph
Ques - 3 Fill the Cube
Ques - 4 Factor of 3
Ques - 5 Particles
Ques - 6 Tennis Score
Entering edit mode
Question 1Single Lane Highway[ Accepted ]
This is actually a math problem. Apart from N, inputs don't matter !
We can solve this using Linearity of Sieve.
Rephrasing original problem, it states find average number of expected groups! SimplerNow?
Now we can solve using linearty of expectation we get, required probability = 1 + 1/2 + 1/3 + ... + 1/n.
Just make sure you print upto 6 decimal places.
Here is the simple C++ implementation: https://ideone.com/fRzy1Y
This gave meAcceptedstatus!
Question 2Path Through Graph[ Accepted ]
There can be atmost O(log(N)) factors of a number, and finding an edge of a number-node takes atmost O(Sqrt(N)) time using usual factorization method.
This gives us O(log N x sqrt(N)) solution. This gave meAcceptedstatus!
Question 3 Fill the Cube[ Accepted ]
Note that N<100, so N2 algorithm will work. Try each rotation, and find the maximum wall that can be fitted in each rotation, the maximum of this will be the answer.
First create a new matrix for each rotation like this
- Let's say the original wall matrix is "wall" and wall[i][j] is the brick in row i and column j. Let's call the rotated matrix wall_rotated, wall_rotated[i][j] is the brick at row i, colun j.
- Left side at bottom - wall_rotated[j][n-i-1] = wall[i][j]
- Right side at bottom - wall_rotated[j][i] = wall[i][j]
- Top side at bottom - wall_rotated[n-i-1][j] = wall[i][j]
- Bottom side at bottom - wall_rotated[i][j] = wall[i][j]
For each roation we calculate the maximum wall that can be fitted in N2
- In an array, store the gap created in each column of wall when all 'D' type bricks melt. Gap in column i = No of bricks of type 'D' in column i.
- For each pair of i,j check the maximum square gap with end points at ith and jth columns. This is equal to = min(j-i+1,k)). k is the minimum gap in any column between i and j inclusive. Eg. Lets say there are three columns with gaps(calculated in step 1) = [3,2,5], then with i=0,j=2, k=min(3,2,5)=2.
- The maximum value calculated in step 2 for each pair, is the maximum size of square wall that can be inserted in this rotation
Question 4 Factor of 3[ Accepted ]
Idea is simple, replace every number by modulo 3, so every number now will be 0, 1 or 2.
If a 0 and 0 are adjacent or if 1 and 2 are adjacent only then will their sum be divisible by 3, so we want to avoid it.We can avoid it by:-
- If there are no '0' numbers and '1' and '2' are present then at some place we will get adjacent '1', '2'.
- if only '0' is present then too we get 0 and a 0 adjacent forcibly
- if number of 0s > number of 1s and 2s combined then again at some place two 0s will come together
Question 5 4-Particles[ Accepted ]
Note, constraints are integers all within 100. So one can simply bruteforce for each configuration and compute sum of two 3d triangles.
You can compute 3d Traingle's area using 3d_areaPolygon() in this site http://geomalgorithms.com/a01-_area.html
Code : C++ code
Question 6 Tennis Score
Simple bruteforce with tons of if-else.
Code will take time to cook.
