# Trilogy Innovations(CodeNation) Coding Round, 5th March In today’s post, I am going to share Trilogy Innovations(CodeNation) Coding Round, 5th March. I have collected a few questions and wrote their answers for you guys.

## Trilogy Innovations(CodeNation) Coding Round, 5th March Questions

#### Question 1 – Find The Evil Monsters

Given an array A of N elements representing the monsters and an array B of Q elements representing the heros.
The i-th type of monster is represented by A[i], A[i] and A[i] which means a monster of the i-th type is present at each integer co-ordinate from A[i] to A[i] and having a strength of A[i].
The i-th type of hero is represented by B[i] and B[i] which means a hero of strength B[i] will appear at the integer point B[i] after i seconds. When the i-th hero appears it will destroy each and every monster present at B[i] and having a strength less than B[i].
For each i you have to determine the number of monsters left after the i-th hero has completed their task.

Problem Constraints

• 1 <= N <= 105
• 1 <= Q <= 105
• 1 <= A[i] <= A[i] <= 105
• 1 <= B[i] <= 105
• 1 <= A[i] <= 109
• 1 <= B[i] <= 109

#### Question 2 – Minimize Travel Tax

There are A cities connected by A-1 bi-directional roads such that all the cities are connected.
Roads are given by array 2D array B where ith road connects B[i] city to B[i].

You go on C trips where on the i-th trip you travel from C[i] city to C[i] city. All the trips are independent of each other.
You have to pay a tax on D[i] on entering or leaving the i-th city. If you pay the tax while entering then you don’t need to pay at the time of leaving.

You can choose some non-adjacent cities and make their tax half.
What can be the minimum sum of taxes you pay for all the C trips? Since the answer can be large, return the remainder after dividing it by 109+7.

Problem Constraints

• 2 <= A <= 105
• 1 <= B[i], B[i] <= A
• 1 <= C <= 105
• 1 <= C[i],C[i] <= A
• C[i] != C[i]
• 1 <= D[i] <= 105
• D= A and D[i] % 2 = 0

#### Question 3 – Expected Path Length III

You have A natural number from 1 to A, each occuring exactly once. Now, you choose any of the A (each number being equally likely) numbers and do the following procedures:
1. Initialize a variable step = 0.
2. Let X be the current number you have.
3. Randomly choose any divisor of X (each divisor being equally likely). Let it be Y, now replace X by X/Y. Also, increment step by 1.
4. If X is not equal to 1, repeat from 2nd step.

Let expected value of step be represented in the form of a irreducible fraction x/y. Return xy-1 mod (109+7), where y-1 is the modulo multiplicative inverse of y modulo (109 + 7).

NOTE: You only have to consider positive values of Y.

Problem Constraints

• 1 <= A <= 105