Ohh yess, but now it gives me
0 0
0 0
0 0
as output
We can even just directly iterate from maximum possible set bit we can get from two arrays , This way our time complexity will be (O(maxmsb(a,b))*n)
My code :
// Note i have used one indexing for bits
#include<bits/stdc++.h>
using namespace std;
int setbitk(int n , int k){
return (n&(1<<(k)))>>k;
}
int msb(int n){
return 1 + log2(n);
}
void solve(){
int n;
cin >> n;
vector <int> a(n) , b(n);
for(auto &x : a) cin >> x;
for(auto &x : b) cin >> x;
vector <int> canflip(n,true);
int maxmsb = 0;
for(int i=0;i<n;i++){
maxmsb = max({maxmsb,msb(a[i]),msb(b[i])});
}
int flips = 0;
for(int k=maxmsb;k>=0;k--){
bool canset = true;
vector <int> noMoreFlips;
vector <int> needsSwap;
vector <int> pos;
for(int i=0;i<n;i++){
int x = setbitk(a[i],k);
int y = setbitk(b[i],k);
if(x==1){
if(y==0){
noMoreFlips.push_back(i);
}
// else u may flip
}
else{
if(y==0 or !canflip[i]){
canset = false;
break;
}
else{
needsSwap.push_back(i);
noMoreFlips.push_back(i); // no more flips
}
}
}
if(canset){
for(auto i : noMoreFlips){
canflip[i] = false;
}
for(auto i : needsSwap){
swap(a[i],b[i]);
flips++;
}
}
}
int ans = a[0];
for(int i=1;i<n;i++){
ans &= a[i];
}
cout << ans << " " << flips << "\n";
}
int main(){
int t;
cin >> t;
while(t-->0) solve();
}
I have spent so much time building this solution , and i dont know what is wrong with my approach.
please do look at my solution and help me .
thanks in advance.
link :- sol
Can some one please explain the logic used for the loop for the solution linked to the editorial.
Why is it for(int msb = (1<<29); msb > 0; msb /= 2)
Can we use msb - - ?
Why are we dividing it by 2 every time?
Thanks
Can anyone please review my code, it is passing sample test but failing on submissionā¦
And what about N==1 case?
void solve(){
int n;
cin>>n;
vector<int>arr(n),b(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
if(n==1){
cout<<arr[0]<<" "<<0<<endl;
return;
}
vector<int>res(n,-1);
int count=0;
for(int i=30;i>=0;i--){
int j=0,flag=0;
for(;j<n;j++){
if(arr[j]&(1<<i)) continue;
else if(b[j]&(1<<i)){
res[j]=b[j]; flag=1;
}else break;
}
if(flag && j==n){
for(int i=0;i<n;i++){
if(not (res[i]==-1) && not(arr[i]==res[i])){
arr[i]=res[i];
count++;
}
}
}
res.clear();
res.resize(n,-1);
}
int ans=arr[0]&arr[1];
for(int i=2;i<n;i++){
ans&=arr[i];
}
cout<<ans<<" "<<count<<endl;
}
msb
refers to the most significant bit (which starts with 1<<29
and ends with 1<<0
). The reasoning for this, and not iterating from 29
to 0
(as the editorial states) is ease of implementation, as I donāt have to bit shift every time I want to do an AND operation (lines 34,35,36,43,44 would have ...&msb
replacd with ...&(1<<i)
which is redundant)
Please help !
Why am I getting WA for Subtask 3.
Have used diff logic.
First checking what can be max allowed by all nums, then checking individually if the max is possible and updating val and count accordingly.
int n;cin>>n;
vector<ll> a(n),b(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
ll val=a[0]|b[0];
for(int i=1;i<n;i++)
{
val=val&(a[i]|b[i]);
}
ll c=0;
// cout<<val<<" ";
for(int i=0;i<n;i++)
{
ll a1=val&a[i];
ll b1=val&b[i];
if(a1!=val)
{
if(b1==val||a1<b1)
{
val=b1;c++;
}
else
val=a1;
}
}
cout<<val<<" "<<c<<"\n";
Thank you for your reply but I wanted to know what it does in the program like why we have to initialize ans with it
Can anyone please tell me why I am getting wrong answer by this code? I have only given the main code below.
int t;cin>>t;while(tā){
int n; cin>>n;
vi a(n),b(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
int flipped=0;
bool pass=true;
vi select(n,0);
for(int i=1<<30;i>0;i>>=1)
{
pass=true;
for(int j=0;j<n;j++)
{
if((a[j]&i)!=0)
{continue;}
if((b[j]&i)!=0)
{
flipped++;
select[j]=1;
continue;
}
pass=false;
flipped=0;
break;
}
if(pass)
{
break;
}
for(int j=0;j<n;j++)
{
select[j]=0;
}
}
if(pass)
{
int x=(1<<30)-1;
for(int i=0;i<n;i++)
{
if(select[i]==1)
{
x&=b[i];
}
else{x&=a[i];}
}
cout<<x<<" "<<flipped<<endl;
continue;
}
cout<<0<<" "<<0<<endl;
}
return 0;
}
Can you please tell why this code is not working. I have used same logic as per the editorial.
int t;cin>>t;while(tā)
{
int n; cin>>n;
vi a(n),b(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
int flipped=0;
bool pass=true;
vi select(n,0);
for(int i=1<<30;i>0;i>>=1)
{
pass=true;
for(int j=0;j<n;j++)
{
if((a[j]&i)!=0)
{continue;}
if((b[j]&i)!=0)
{
flipped++;
select[j]=1;
continue;
}
pass=false;
flipped=0;
break;
}
if(pass)
{
break;
}
for(int j=0;j<n;j++)
{
select[j]=0;
}
}
if(pass)
{
int x=(1<<30)-1;
for(int i=0;i<n;i++)
{
if(select[i]==1)
{
x&=b[i];
}
else{x&=a[i];}
}
cout<<x<<" ā<<flipped<<endl;
continue;
}
cout<<0<<ā "<<0<<endl;
}
return 0;
}
Can anyone tell me for the case, if to set xth bit to 1 , doing a flip may cause a higher bit set to 0, how are we handling that case?
Once a bit is flipped, it canāt be un-flipped (a boolean vector can be used for this), rest other bits which are flexible till now can only be flipped after that.
This is what Iād missed while solving the problem, but later I got it luckily.
Try solving maximum AND value ques on GFG you will understand it better then.
I have extended that same approach hereā¦
Your question is - In the iteration, if we flip a particular card to make the x^{th} bit in the answer 1, how do we know bit i\space(i>x) is still set in the answer?
See step 2 in the editorial. When processing the i^{th} bit, a card is left undecided ONLY if flipping the card doesnāt unset the i^{th} bit. Therefore, if the card is flipped when processing the x^{th} bit, the i^{th} bit is still on.