Join Us
How is answer 2 for sample testacase?
Entering edit mode
Q1 XOR subsequences
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
- B[i] < B[i+1] where 1 <= i<|B|.
- 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
Problem Constraints
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
Ques 2.
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
FOR HUNGRY POLICEMAN
using multisource dijkstras
void solve()
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> adj[n+1];
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
adj[a].pb({b,w});
adj[b].pb({a,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();
for(auto i:adj[node])
{
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
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;
}
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))
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
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;
}
Loading Similar Posts
Can you share solutions for XOR subsequences and Fractional knapsack problems?
How is the answer 2 in the 3rd question? Can someone explain the example solution