Question: Media.NET OA | Fractional Knapsack | XOR Subsequence | Hungry Policemen | IIIT Vadodara | FTE | 27th July 2023
13
Entering edit mode

## Problem Description

You are given an array A, you have to create an array B which is a subsequence of A.
An array B is called valid if it satisfies both the conditions

1. B[i] < B[i+1] where 1 <= i<|B|.
2. bit_count( B[1] ^. ^ B[i-1] ^ B[i]) <= bit_count(B[i+1]) where 1 <= i < |B|.
.........
Let X be the Bitwise XOR of all the elements in valid array B.
You need to find the number of different values of X that can be formed.
Note: bit_count(t) is the number of set bits present in the binary representation of t

1 <= IAl <= 10^5
1 <= A[i] <= 100

## Input Format

The first argument is an integer array A

## Output Format

Return an integer denoting the number of different values of X that can be formed

# Fractional Knapsack

Problem Description
You are inside Gringotts Gold Bank with a Knapsack that can hold B weight of Gold coins.
In the Gringotts bank, gold coins have some unique properties:
1. Each Gold coin has a weight equal to some non-negative power of 2.
2. Each Gold Coin can be further divided into two gold coins of equal weight.
There are N gold coins in the Bank, given by array A. where Ali] is the weight of the it gold coin.
You have to fill the knapsack completely, by making minimum number of divisions of the gold coins.
Calculate the minimum number of divisions needed to fill the knapsack completely.
Note: In case it is impossible to fill the knapsack completely, output -1.
Problem Constraints

1 <= N <= 10^5
1 <= B <= 10^18
1 <= A[i] <= 10^9

### Input Format

The first argument given is an array. A
The second argument given is an integer, B.

### Output Format

Return an integer denoting the minimum number of division that are required to fill the knapsack completely.
Example Input
Input 1:
A - [16, 1, 4, 1]
B = 23
Input 2:
A = [1, 32, 1]
B = 10

Output 1

-1

Output2

2

Example Explanation
Explanation 1:

It is impossible to fill the knapsack of weight 23

Explanation 2:
You can convert cold coin of weight 32 into gold coin of weight 8 with 2 divisions.
1.e. 32 -> 16 ÷ 16
16 -> 8 + 8.
And Now to fill the knapsack with weight 10
three gold coins with weight 1, 1

Question 3.

Hungry Policemen

You are given a graph G of N nodes and M edges and each edge has some time associated with it.

There is a policeman standing on each node except Node N.

All of them get a report that there is thief on Node N and the policemen start moving towards it, but all of them have been hungry for days, so they are looking to visit a few restaurants as well, before reaching the node N.

There are K restaurants present on some nodes, and each restaurant has some satisfaction. Now, a policeman will only go to a restaurant if and only if the satisfaction he receives by reaching the restaurant is greater than the time he has invested in reaching there and then going to the Node N.

Find and return the number of policemen who will have a meal at a restaurant.

Input Format:

The first argument contains an integer A, representing the number of nodes.

The second argument of input contains a 2 d matrix of size M x 3, B, where Node B[i][0] and Node B[i][1] are bidirectionally connected with an edge that takes B[1][2] time to go through it.

The third argument of input contains a 2-d matrix of size K x 2, C, where Node C[i][0] has a restaurant that has C[i][1] satisfaction.

Output Format: Return an integer representing the number of people who will have a dinner at the restaurant.

Constraints:

2 <- N <- 50000

1 <= M <= 100000

Output Format:

Return an integer representing the number of people who will have a dinner at the restaurant.

Constraints:

2 < N <- 50000

1 <= M <= 100000

1 <= K, B[i][e], 8[i][1] <= N

1 <= B[i][2] <= 1e4

1 <= C[i][1] <= 1e9

Example:

Input 1: A=4 B = [ [1, 2, 2], [2, 4, 1], [4, 3, 10], [3, 1, 1] ] C = [ [1, 1] ]

Output 1: 2

Explanation 1: Policemen at Node 1 and Node 3 will have a meal at node 1 without wasting any time.

Entering edit mode
0

Can you share solutions for XOR subsequences and Fractional knapsack problems?

Ankur Mishra
• 0
Entering edit mode
0

How is the answer 2 in the 3rd question? Can someone explain the example solution

Tp
• 0
7
Entering edit mode

# FOR HUNGRY POLICEMAN

using multisource dijkstras

``````void solve()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
}
int k;
cin>>k;
vector<int> v(n+1,-1);
priority_queue<pair<int,int>> pq;
for(int i=0;i<k;i++)
{
int a,b;
cin>>a>>b;
v[a]=b;
pq.push({b,a});
}

while(!pq.empty())
{
int w=pq.top().first;
int node=pq.top().second;
pq.pop();
{
int newnode=i.first;
int len=i.second;
if(w-len>v[newnode])
{
v[newnode]=w-len;
pq.push({v[newnode],newnode});
}
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(v[i]>=0)
cnt++;
}
cout<<cnt<<endl;

}``````

Entering edit mode
0

How is answer 2 for sample testacase?

Harshit Mishra
• 10
Entering edit mode
0

is this solution 100% correct?

op
• 0
7
Entering edit mode

FRACTIONAL KANPSACK SOLUTION

``````#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve(){
ll N, M;
cin >> N >> M;
vector<ll> bt(70, 0);
vector<ll> btt(70, 0);
for(ll i = 0; i < 62; ++i){
if(((N >> i) & 1) == 1) btt[i]++;
}
ll a;
for(ll i = 0; i < M; ++i){
cin >> a;
for(ll i = 0; i < 40; ++i){
if(((a >> i) & 1) == 1) bt[i]++;
}
}
ll r = 0;
for(ll i = 0; i < 62; ++i){
if(bt[i] < 0) {bt[i + 1] -= 1; bt[i] += 2; ++r;}
if(btt[i]){
bt[i] -= 1;
if(bt[i] < 0) {bt[i + 1] -= 1; bt[i] += 2; ++r;}
}
bt[i + 1] += bt[i] / 2;
}
ll fl = 0;
for(ll i = 0; i < 70; ++i){
if(bt[i] < 0) fl = 1;
}
if(fl) cout << -1 << '\n';
else cout << r << '\n';
}

int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll T;
cin >> T;
while(T--){
solve();
}
}
``````

Entering edit mode
1

# CHECK FRACTIONAL KNAPSACK

``````#include<bits/stdc++.h>
using namespace std;

bool sol(int arr[],int n,int sum,int k,int &ans)
{
if(sum==k)  return true;
else if(n==0)   return false;

if(arr[n-1]<=k)
{
sum+=arr[n-1];
if(sol(arr,n-1,sum,k,ans))    return true;
sum-=arr[n-1];
return sol(arr,n-1,sum,k,ans);
}

else
{
if(sol(arr,n-1,sum,k,ans))  return true;
int y = arr[n-1]/2;
ans+=1;
arr[n-1] = y;
return sol(arr,n,sum,k,ans);
}
}

int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)    cin>>arr[i];
int k;
cin>>k;
int sum = 0;
int ans = 0;
if(sol(arr,n,sum,k,ans)) cout<<ans<<endl;
else    cout<<-1<<endl;
}``````
xyz
• 10
4
Entering edit mode

def minimumDivisions(A, B):
# Convert the array into a max heap
A = [-1 * i for i in A]
heapq.heapify(A)

total_sum = sum([-1 * i for i in A])

# If total sum of weights is less than B, return -1
if total_sum < B:
return -1

count = 0

while B > 0:
# Get the heaviest coin
heaviest = -1 * heapq.heappop(A)

# If the weight of the heaviest coin is less than or equal to B,
# subtract it from B
if heaviest <= B:
B -= heaviest
else:
# If the weight of the heaviest coin is more than B,
# divide the coin into two parts such that one part is as large as possible but not more than B
while heaviest > B:
heaviest >>= 1
count += 1
B -= heaviest

# If we have used all the coins and the knapsack is not full,
# return -1
if not A and B > 0:
return -1

return count

# Test the function with the provided test cases

print(minimumDivisions([16, 1, 4, 1], 23))
print(minimumDivisions([1, 32, 1], 10))

1
Entering edit mode

Hey Suryansh,I had some questions :

Q1. Why you have also checked the last index of the array(even without sorting)?

Q2. After dividing a no by 2. You have stored only one no(i.e num/2) where is the other number.

In given TC array is [ 16 ] and target is 10 so you have to divide 16  into [8,8] then one 8 into [4,4]. array became [8,4,4] then split 4 into 2 twos. array [2,2,4,8]. But what you are doing you divided 16 into only 1 8 which will not satisfy target value

0
Entering edit mode

Fractional Knapsack

#include<bits/stdc++.h>

using namespace std;

int UTIL(int idx, int n, int K , vector<int> &arr,int count,int &res){

if(K==0){
//   cout<<res<<" "<<count<<endl;
res = min(res , count);
return 0;
}

if(idx==n)
return 0;

UTIL(idx +1 , n, K, arr, count,res);   //not_taken

if( arr[idx] <= K )
UTIL(idx + 1, n, K - arr[idx] ,arr,count,res);

else{

arr[idx]/= 2;
UTIL(idx , n , K , arr, count + 1,res );
arr[idx]*=2;

}

}

int main(){

int n;
cin>>n;

vector<int> arr(n);

for(int i=0;i<n;i++)
cin>>arr[i];

int K;
cin>>K;
int res=INT_MAX;;

UTIL(0,n,K,arr,0,res);

if(res==INT_MAX)
cout<<-1;

cout<<res;

}