11 weeks ago

John 910

Hyderabad

Question 1

Anwar has an array A containing N integers on which he performs M operations.

In the jth operation he will perform one of the following tasks:

• If Tj=1, then add F(Ai) to Ai for each i in the interval [Lj,Rj], where (1<=Lj<=Rj<=N).
• If Tj=2, then do all operations of the first type from the Lj operation to the Rj operation again in their order, where (1 <= Lj <= Rj < j).

F(x) is defined as the largest power of 2 that divides x. For example, F(4)=4, F(5)=1.

Find the final values in A after performing all operations. Since the answer may be very large return the elements of A modulo 10^9+7.

Question 2

A farmer has a tree with N nodes. He wants to trim the tree using an operation T(0 <= T <= N-1).

In one operation he will choose any edge and delete it. From the resulting two connected components(i.e. trees) keep one and discard the other.

Additionally, the farmer has an array A which gives the score of each node of a certain degree present in the tree. The farmer wants to apply the operation such that the total score of the tree left is maximum.

The total score of the tree left is defined as the sum of values of A as per degree of each node left in the tree. This means that a node of degree 1 left in the final tree will contribute A1 to the total score.

Find maximum possible score for the tree left.

Question 3

You have N types of ingredients. Additionally, you have 3 units of each ingredient.

Additionally you have M cake recipes where each recipe is represented by a binary string of length N. if the ith character in a cake recipe is 1, the you need to use 1 unit of the ith ingredient for making a cake using the recipe.

You will be given an array P where P[i] denotes the recipe of a cake made using the ith cake recipe. You can use each recipe atmost once.

You will make cakes (possibly 0 to 1) using the ingredients available such that you obtain the maximum possible sum of prices R for the cakes made by you.

Find the value of R.

Question 4

Problem Statement

You are given an array Arr of size N. You are also given Q queries where each query is described by two values, start and jump.

For each query you will perform the following operations:

• Begin at the index i = start and add the element Arr_i to the value of sum.
•  Set i = i+jump and add Arr_i+jump to sum till i+jump <= N.

The answer to each query is the value of sum after performing the above operations.

Find the sum of answers to all Q queries. Since the output can be large, return it modulo 10^9+7.

Notes:

• Arr follows 0-based indexing.

• It is given that the value of sum for each query is computed independent of the other queries.

Question 5

Problem Statement

You are given an array A consisting of N queries and an empty array B of size 10^5. It is given that each of the N queries consists of three integers T, X and Y.

You want to perform N queries on B such that,

• If T=1, increase the value of B[X] by Y.

• If T=2, compute the sum of B[i] for all i in the range[1, 100000] such that i%X=Y. Then, insert the sum at the back of a new a array C

Find the value of array C after performing N queries.

Notes:

•If T=2, then 0 <= Y < X <= N.

• The arrays A and B follow 1-based indexing.

Input Format

The first line contains an integer. N, denoting the size of A

Question 6

Problem Statement

Alex loves listening to music. He has N songs on his phone such that the ith (0<=i<N) song has a coefficient equal to A[i]. His phone has a volume coefficient which is a positive integer which will be chosen by Alex. If he chooses volume coefficient to be V then he will listen the ¡th song with volume 

A[i] *V.

Moreover, he has two constraints, X and Y. (X <= Y and Y-X+1 >= maximum element of A). If the volume of the music (i.e. A[i] * V) is strictly smaller than X, he will not be able to listen it as it is too low. On the other hand, the volume is strictly greater than Y, it will be too noisy and may be harmful for his ears. So volume should be between X and Y, inclusive.

Alex can change the volume coefficient V several times, but he wants to minimize the number of

changes while being able to listen to all his songs.

Find the minimum possible number of changes of the volume coefficient needed.

22 months ago

Yash Sahijwani 940

Solution for Question 1

Analysis

Firstly, though it is not mentioned in the question, we assume that the integers in the array can be in the range [1, 10^9]. Now, we are given 2 types of queries. In query 1, we are given a range and for each element in that range we are supposed to add F(A[i]) to A[i] where F(A[i]) is the maximum power of 2, which is a divisor of A[i]. In the second type of query, we are given a range and we are supposed to carry out all operations of type 1 in the given range.

We can break down the problem into two parts:

1. Calculating for each index i in the range [1, n], the number of operations to be carried out. Let us call this ops[i], meaning that after taking into account all queries, we need to apply an operation of type 1 query on the index i, ops[i] number of times.
2. Applying ops[i] operations on a[i].

Calculating ops[i]: We create an array ops of length n. This will store the final number of operations required for each index. We also create an array query_freq of length m, which will store the number of times each query is to be executed. (Though we'll be calculating this for all indices, it will only matter for queries which are of type 1). Then we start taking queries as input. Say we input the query i, i.e. the ith query, then we know that the frequency of this query is 1 right now, so we do the following operation, query_freq[i] + = 1, query_freq[i+1] - = 1.

We do this because this an easy method to calculate the frequency of indices, given a large number of ranges. In the end, for each index i, query_freq[i] = query_freq[i] + query_freq[i-1] + .... + query_freq[1], so for the ith query, the frequency will increase by 1 due to this, but for the i+1th query, and for all subsequent queries, this will have no effect, since we are subtracting 1 as well at the i+1 th position.

This was for when we encounter queries of type 1. In case we encounter queries of type 2, we do the following operation, query_freq[l[i]] + = 1, query_freq[r[i] + 1] -=1. Hence, this operation, increases the frequency of all queries in the range from l[i] to r[i] by 1.

Then at the end, after processing all queries, we do the following operation for all indices from 1 to n, query_freq[i] = query_freq[i] + query+freq[i-1]. This will give us the final query_freq array.

Now, that we have the number of times each query has to be processed, we start updating the ops[i] array. For each i from 1 to m, if the ith query was a query of type 1, we do the following operation : ops[l[i]] + = query_freq[i], ops[r[i]+1] -= query_freq[i]. So this for all indices from l[i] to r[i], this operation will increase the number of times the operation is to be carried out by query_freq[i].

In the end, we do similarly, ops[i] = ops[i-1] + ops[i]. This will give us the final array ops.

Applying ops[i] number of operations: Let us look at this using binary representation of a[i]. Let us say a[i] = 52, then its binary representation is 110100. So the rightmost 1, denotes what is F(a[i]). Here since the rightmost 1 is at the 2nd position (starting from 0), 2^2 = 4, is the largest divisor of a[i]. Now, if we add F(a[i]) to a[i], the rightmost 1, will become 0, and the 1 will be carry forwarded. Now a[i] will be 111000. If we do it again, F(a[i]) = 8, adding it will carry over the 1, and now since there are consecutive 1s, a[i] will become 1000000. Hence, we are basically at each operation adding 1 to the rightmost set bit of the binary representation.

Now, since we have assumed that a[i] will be less than 10^9, the number of bits in the binary representation will be at max 31. So, if ops[i] is greater than 31, the after applying those 31 operations (or we might reach this earlier as well, possibly after a single operation, or maybe no operation at all) we'll have something like 1000...000. i.e. there would only be a single 1 in the binary representation of the number. After this adding F(a[i]) is basically multiplying by 2. So, say we have rem[i] operations remaining, then we need to multiply a[i] by pow(2, rem[i]), which can be calculated in O(logN) using binary exponentiation. We can do this for all indices, and hence the overall time complexity will be O(nlogn).

Implementation

ll n;
cin > > n;
vector < ll > a(n+1, 0);
for(ll i=1;i < = n;i++)
    cin > > a[i];
ll m;
cin > > m;
vector < vector < ll > > queries(m+1, vector<ll>(3, 0));
vector< ll > ops(n+2, 0);
vector< ll > query_freq(m+2, 0);
for(ll i=1;i < = m;i++)
{
    ll type;
    ll l, r;
    cin > > type > > l > > r;
    queries[i][0] = type;
    queries[i][1] = l;
    queries[i][2] = r;
    if(type==1)
    {
        query_freq[i]+=1;
        query_freq[i+1]-=1;
    }
    else if(type==2)
    {
        query_freq[l] += 1;
        query_freq[r+1] -= 1;
    }
}
for(ll i=1;i < = m;i++)
    query_freq[i] += query_freq[i-1];
for(ll i=1;i < = m;i++)
{
    if(queries[i][0]==2)
        continue;
    ll l = queries[i][1];
    ll r = queries[i][2];
    ops[l] += query_freq[i];
    ops[r+1] -= query_freq[i];
}
for(ll i=1;i < = n;i++)
    ops[i] += ops[i-1];
for(ll i=1;i < = n;i++)
{
    ll best_divisor = 1;
    while(__builtin_popcountll(a[i]) > 1 && ops[i] > 0)
    {
        if((a[i] & best_divisor) == best_divisor)
        {
            a[i] = a[i] + best_divisor;
            ops[i]--;
        }
        best_divisor *= 2;
    }
    ll rem = ops[i];
    ll additional = binExp(2, rem);
    a[i] = (a[i] * additional)%mod;
}

4 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to problem 4

Analysis

We only want to determine the sum of answers to all the queries. So instead of trying to find the answer for each query, we can rather determine the number of queries for which an element at index i needs to be added. Thus if we can find out such number for all indices, we can find the total sum of answers for all queries.

How to determine the number of times an element at index i needs to be added ?

Lets distinguish the queries by the value of jump.

• if jump > √N, we can notice that we only need to add atmost √N elements for this query. Hence we can trivially add those elements in a complexity of √N. The complexity is thus O(Q√N)
• otherwise jump ≤ √N and thus an element at index i needs to be added for some query if and only if start ≡ i (modulo jump). So, we can use prefix sums to optimally add the contribution of such queries. Let's maintain an array of length a for each a ≤ √N, say pre such that pre[a][rem] denotes the number of queries discovered so far with start%a = rem. Now sort all the queries with the start value and start iterating through the array in increasing order. As soon as you reach index i, update the pre array by iterating through all the queries with start == i. Now iterate from 1 to √N and add arr[i]*pre[a][i%a] to your answer (As explained, we need to add element at index i only for queries with start ≡ i (modulo jump). So we maintain the prefix sum for the number of queries for each value from 1 to √N and then add the contribution for each index accordingly). Since at each index, we perform O(√N) operations, the complexity is O(Q + N√N).

Thus we separated the queries as per the value of the jump and obtained the answer in a total complexity of O((Q+N)√N).