9 weeks ago

John 910

Hyderabad

Question 1

Amaru and Kapkan were playing Rainbow 6 Siege in which Kapkan strategically placed N bombs all over the map.

Each bomb has 3 numbers associated to it X, L and R and can only be defused by finding the maximum value of (X ⊕ Y) where ⊕ represents the bitwise xor operation and Y can be any number in the interval [L,R].

Amaru is a dumb player who only rushes in, so can you help her in winning by finding the maximum value of (X ⊕ Y) for all the N bombs?

Constraints:

1 <= N <= 5000

1 <= L <= R <= 1019

1 <= X <= 10^9

•[execution time limit] 1 seconds (cpp)

•[input] integer n

•[input] array.integer x

•[input] array.integer I

•[input] array.integer r

•[output] array.integer

Question 2

Zasho is a popular genie. Being a genie, he's in the business of granting wishes, and a lot of people ask him for help. However, his power is limited - currently it is p units.

To grant the i-th wish, Zasho needs to have at least x units of power. After a wish is granted, his rating changes by y (y can be positive or negative). Of course, his power should not dip below zero - otherwise he won't be able to grant any wishes. He can choose to grant wishes in any order.

Zasho wants to grant the maximum number of wishes possible so that he remains popular. Can you help him figure out how many wishes he should grant?

In other words, find the maximum possible size of the subset of wishes so that Zasho has enough power before starting each, and has non-negative power after completing each wish.

Constraints:

• 1 ≤ n ≤ 100, 1 ≤ p ≤ 30000

• The next n lines contain the wishes, one per line. The i-th wish is represented as a pair of integers x and y (1 ≤ x ≤ 30000, -300 ≤ y ≤ 300)

Example:

If the input is

3  5

4 -5

4 -2

1  3

The output is 3 because a possible order <2, 3, 1> exists for Zasho to fulfill every wish.

•[execution time limit] 1 seconds (cp) 

•[input] integer p 

•[input] array.integer x 

•[input] array.integer y 

•[output] integer 

[C++] Syntax Tips

4 months ago

Ujjwal Srivastava 320

Bengaluru

Question 1

Overview

• We have N queries of forms X, L, and R.
• We have to find the maximum value of X^Y where Y belongs to [L,R].

Solution

• We basically need to find a suitable value of Y that results in a maximum value of X^Y.
• We need Y to have complementary bits to that of X to have the maximum value.

• We will iterate from the largest set bit in R to the lowest (0th Bit). The following two cases can arise for each bit:

  • If the bit is not set, i.e. 0 in X, we will try to set it in Y. If setting this bit to 1 results in Y exceeding R, then we will not set it.

  • If the bit is set, i.e. 1 in X, then we will try not to set it in Y.

  • If the current value of Y is already greater than or equal to L, then we can ignore the bit i.e not set the bit in Y.
  • In the other case, we will check if setting all of the next bits is enough to keep Y >= L. If not, then we are required to set the current bit.
• At last, when we have iterated over all the bits, we will have our required value of Y hence the maximum value of X^Y.

Code

ll n;
cin >> n;
for (ll i = 0; i < n; i++)
{
    ll x, l, r;
    cin >> x >> l >> r;
    ll y = 0;
    for (ll j = 30; j >= 0; j--)// iterate from largest to smallest bit
    {
        ll val = (1ll << j);
        if (x & val)// if the current bit is set in x
        {
            if (y + val - 1 < l)// Even if after setting all the next bits, the value of y remains less than r than we have to set the current bit
            {
                y += val;// we have to forcefully set the current bit
            }
        }
        else// if the current bit is not set in x
        {
            if (y + val <= r)// if setting the current bit doesn't exceeds r
            {
                y += val;// set the current bit
            }
        }
    }
    cout << (x ^ y) << endl;
}
return;

2.0 years ago

HARDIK • 40

Question 2

Overview

We are given n wishes (x,y), and an initial power p. We can give the wish If x <= p and p-y>=0. p changes to p-y after giving a wish.

Find maximum size of subset of the wishes we can give.

Solution

• Main idea is to give the wishes with maximum y first, so that our p increases, or decreases the least.
• Hence, we maintain a set where x <= p condition is satisfied, and y is stored in the set in decreasing order.
• We take the maximum y, and if p-y>=0, we give this wish and change p to p-y.
• If at any point, p-y<0 for max y, we can't give any more wishes.

Complexity : O(n^2*log(n))

Code

int solve(int n,int p,vector<pair<int,int>> a)
{
    set<pair<int,int>,greater<pair<int,int>>> s;
    vector<int> done(n);
    for(int i = 0;i < n;i++) 
    {
        if(a[i].first<=p)
            s.insert({a[i].second,i});
    }
    int ans=0;
    while(!s.empty())
    {
        auto x=*s.begin();
        s.erase(x);
        if(p-x.first<0)
        {
            break;
        }

        p+=x.first;
        done[x.second]=1;
        ans++;
        for(int i = 0;i < n;i++)
        {
            if(done[i])
                continue;
            if(a[i].first<=p)
                s.insert({a[i].second,i});
        }
    }
    return ans;
}