5 weeks ago

John 910

Hyderabad

Question1

There are a series of n connected mountains whose heights are represented in an array arr[]. A person is initially at zero height. The energy required for a person to climb up a mountain is the distance between the height of that mountain and the person’s current height. No energy is needed to go down any mountain of any height. Calculate the total energy required by a person to climb all the mountains.

Constraints:

• 1 ≤ n ≤ 10^6
• 0 ≤ arr[i] ≤ 10^9

Input Format:

• The first line contains n representing the size of the array.
• The second line contains n space-separated integers arr[].

Output Format:

Print the single integer representing the total energy required by the person to climb all the mountains.

Sample Testcase #0

Testcase input

7

2 3 5 11 4 7 10

Explanation 

Size of array = 7

arr [ ] = {2, 3, 5, 11, 4, 7, 10}

The person is initially at height = 0.

To climb the first mountain of height = 2, he requires (2-0) = 2 units of energy. 

To go to the next hill of height = 3, he requires (3-2) = 1 unit of energy.

For the 3rd and the 4th hill, he requires (5-3) = 2 units and (11-5) = 6 units of energy resp. 

Now, to get to the 5th hill, he doesn’t require any energy as he is already at a height greater than 5th hill.

And, for the 6th and 7th hill, he requires (7-4) = 3 units and (10-7) 3 units of energy resp.

Total energy required = 2+1+2+6+0+3+3=17

Question 2

Problem Statement

You can jump from A to B, if and only if B % (B - A) = 0, where % is the modulo operator.

You are given an integer N, find the number of ways to reach N, if you can only use the above jumps and start from 1.

Since the answer can be large, find the answer modulo 109 + 7.

Input Format

The first line contains a single integer T - number of test cases.

The first line of each test case contains a single integer N.

• 1 ≤ T ≤ 10000

• 1 ≤ N ≤ 105

Output Format

Print the answer modulo 109 + 7 for each test case in a single line

Sample Testcase #0

Testcase Input

5

1

2

5

10

1337

Testcase Output 

1

1

2

31

37318587

Question 3

Problem Statement

X and Y were in an election battle in their city. This city consists of N towns,and each town has M1 number of people who will vote for Y and M2 number of people who will not take part in the election. X after seeing the lack of his supporters, decided to campaign.

If X does a campaign in town T, both M1 and M2 number of people in this town be come his supporters.

Your task is to calculate the least number of towns in which X has to campaign to win the election.

Note: It is always possible for X to win the election.

Input Format

The first line contains N:

• I <= N<= 200000

The next N number of lines contains pair (M1,M2)

• 1 <= M1,M2<= 1000000000

Output Format

Output a single integer - the least number of towns in which X has to campaign to win the election

Sample Testcase #0

Testcase Input

4

2 1

2 2

5 1

1 3

Testcase Output

1

Explanation

For 1st sample:

If X campaigns in town-3, total number of X supporters will become (5+1=6) while total number of Y supporters will become (2+2+1=5), and clearly X will win.

Sample Testcase #1

Testcase Input

2

2 2

2 2

Testcase Output

1

Explanation

For 2nd sample:

In this case, If X campaigns in town-1, total number of X supporters will become (2+2=4) while total number of Y supporters will become 2, and clearly X will win.

Question 4

Problem Statement

You are given a list P which contains N numbers.

The elements in P are a permutation of numbers from 1 to N.

Your task is to calculate the number of elements Pi(1< i < N) that satisfy the following condition such that Pi is the second smallest number among the three numbers Pi-1, Pi and Pi+1.

Input Format

The first line contains a single integer N.

Next line contains integers Pi.

• 3 ≤ N ≤ 50

Output Format

Print the number of elements that satisfies the condition.

Sample Testcase #0

Testcase input

5 

1 3 5 4 2

Testcase Output

2

Explanation

Sample test 1 :

P2 = 3 is the second smallest number among P1=1, P2=3, and P3=5. Also, P4=4 is the second smallest number among P3=5, P4=4, and P5=2. These two elements satisfy the condition.

Sample Testcase #1

Testcase input

7

6 3 2 5 7 4 1

Testcase Output

3

20 months ago

Yash Sahijwani 940

Solution to Question 2

Analysis

In the problem it is mentioned that we can jump from A to B, where A and B are two integers, only if B%(B-A)=0. Using this, we need to find the number of ways to reach N, starting from 1. Firstly, we can see that if B=A, then B-A is 0, and B%(B-A) is not defined. Hence, B can't be equal to A. So we can't just stay at the same point, we need to jump to some other point. We also need to clear the fact that B should be greater than A, because if both B < A and B > A are possible, then the total number of ways become infinite. This is because, in such a case, you can jump between A and B an infinite number of times. So we establish that B > A always.

Now, we need to find the number of ways we can reach N starting from 1. This can be thought of as a recursive problem with memoization, which becomes a dynamic programming problem. Say you are at the index i, and can jump to indices j, k and l. Then the number of ways to reach N from index i (consider this to be dp[i]) can be written as dp[i] = dp[j]+dp[k]+dp[i].

So, we will have to calculate dp[i] from i=1 to N, and dp[1] would be our answer. However, at every index, we will have to sum up over the points to which we can jump. To calculate that, we need to evaluate the expression B%(B-A)=0. Here we see that B is completely divisible by B-A. So, we can rewrite this as, B = k(B-A), where k is a non negative integer. This can further be written as B = kB - kA which implies, kA = kB - B, so, B = kA/(k-1). So from this we know that the points we can jump to (i.e. B), given that we know A, can be given using this relation. Also since B is an integer, we want that k-1 should be a divisor of kA, so that it completely divides it. Now since k and k-1 differ by only 1, they are coprime (except for k=2, since k-1 would be 1). So k-1 can't be a divisor of k, and their G.C.D would also be 1. So because of this k-1 needs to be a divisor of A. So we calculate all divisors of A, and then for each divisor of A (let the divisor be y), we can write B as B = ((y+1)*A)/y.

Now the total number of times we would be summing in the recursive dp relation is sum of the total number of divisors from 1 to N. For large numbers of the order of 10^9, the maximum number of divisors for each number is n^(1/3). However, here we are dealing with N upto 10^5. So we should check the sum of the total number of divisors from 1 to 100000. This can be done by simply calculating the total number of divisors for each number from 1 to N in O(logN) leading to O(NlogN) time complexity.

int n = 100000;
int ans = 0;
for(int i=1;i < = n;i++)
{
    for(int j=1;j < = sqrt(i);j++)
    {
        if(i%j==0)
            ans+=2;
    }
}
cout<<ans<<'\n';

Running this code gives us 1167066, which is of the order of 10^6. So in the total the summation in dp across all indices will run 10^6 times, so our time complexity becomes O(10^6) which is fast enough for the problem.

We can calculate the divisors for each number in O(NlogN) which comes out to O(10^6). After that we move from i=N to 1, where dp[N] = 1, and for other indices we sum up over the points it can jump to.

Implementation for finding divisors

vector < vector < ll > > divisors(100001);
void find_divisors()
{
   ll n = 100000;
   for(ll i=1;i < = n;i++)
       for(ll j=i;j < = n;j+=i)
          divisors[j].pb(i);
   return;
 }

Implementation for Dynamic Programming Part

dp[n] = 1;
for(ll i=n-1;i > = 1;i--)
{
    ll ans = 0;
    for(ll j=0;j < (ll)divisors[i].size();j++)
    {
        ll b = ((divisors[i][j]+1)*i)/divisors[i][j];
        if(b<=n)
            ans = (ans%mod + dp[b]%mod)%mod;
    }
    dp[i] = ans;
}
ll final_ans = dp[1];

Note: The constraints in the question seem to be 10^5 for N, (sum across all test cases) and modulo is 10^9+7.

7 months ago

Shikhar Mehrotra 480

Chennai

Q1) It can be implemented just by doing what is been said in the question by iterating from left to right :

     1. Increase energy when climbing to greater height   by its difference  
     2. No change in energy when climbing to lesser height  
     3. Update the initial height to current mountain height.

i=0;
initial_height=0;
energy=0;
while(i < n)
{
if(initial_height < =mountain_height[i]){
    energy=energy+mountain_height[i]-initial_height; //more energy is required
}
initial_height=mountain_height[i];
i++;
}

energy is our final answer.

7 months ago

Akshay Sharma 990

Chandigarh

Question 4

Overview

• We are given an array of N integers.
• We have to find the for every P[i] ranging from i 0 to n the total number of the second smallest element among the three elements that are P[i-1] , P[i] and P[i+1].

Solution

• The solution is quite straight forward we have to choose the second smallest element among the three elements.
  • we can start integrating our for loop from 1 to N-1 and make a checker function that will check if the current ith element is the second smallest element among the tree or not it can be done using the if statement and increasing the answer by 1 every time when the function returns true.
  • The constraints are quite small and the time complexity of this solution is O(N)` and it will also run when the value of N is 10^6.

7 months ago

Akshay Sharma 990

Chandigarh

Question 3

Overview

• In question, it's stated that person 1 and person 2 are standing in an election and votes are carried out in N cities
• Each of N cities has some X and Y type of persons, X are those people whole support 1st person and Y are those persons who didn't participate in the Election means there are not going to vote for any of the candidates.
• It's stated that person 2 wants to win the election so for winning the election he needs to carry out some campaigns in any of N cities, If person 2 carries out the campaign in any city then the total voters who are supporting the 1st person change their mind and vote to 2nd person and also those who are not interested in voting also give a vote to 2nd person. This means the total vote that person 2 gets from the ith city is X+Y;
  • We need to find how many minimum cities a person 2 needs to do campaigns so he could win the election.

Solution

• We can solve this question using the greedy technique which is first we are going to store all the X and Y types of person in pairs of array and also make a variable totalX=0 that will store the count of the total number of citizens who are going to vote for X.
• Also we make another array of pairs call that pair<int, int>sum[n] that will gonna store the total count of citizens in the ith city and the city they belong to sum[i]={X[i]+Y[i],i);.
• After this, we can sort the pairs of arrays based on the sum of 1st values in the reverse order so at the top we get the city that has more citizens.
• Finally, we can create two more variables that are answered and Count which will store the minimum number of cities to visit and the sum of votes we get after doing campaigns.
• Then we finally iterate from 0 to n and check if the Count is greater totalX or not. If yes we will break our loop else we add the Count+=sum[i].first and also don't forget to remove these votes from the totalX so we will be going to subtract only votes of that candidate who is actually going to vote that is ToalX-=X[i] and increase our answer.
• Finally print or answer -Time complexity :O(NlogN)

24 months ago

Abhishek • 0

Question 2 Solution

    void solve() {
    int mod = 1e9 + 7;
    vector<ll> dp((int)1e5 + 1, 0);
    dp[1] = 1;
    for (int i = 1; i <= 1e5; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j)continue;
            (dp[i] += dp[i - j]) %= mod;
            if (j * j != i)(dp[i] += dp[i - i / j]) %= mod;
        }
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << dp[n] << endl;
    }
}