Magical Flips CodeChef Solution

Problem -Magical Flips CodeChef Solution

“ ”

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Magical Flips CodeChef Solution in C++17

“ ”

#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long int
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define rep(i,n) for(int i=0; i<n; i++)
#define fo(i,k,n) for(int i=k; i<=n; i++)
#define nl cout<<endl
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
const int mod = 1000000007;
const double PI = 3.14159265358979323846;
int power(int x,int y,int p);
void read(vector<int> &a);
void read(vector<vector<int>> &a);
void print(vector<int>&a);
void print(vector<vector<int>>&a);

bool isSet(int n, int k){
    return n & (1LL<<k);
}

bool noChange(int num, vi &ans, int pos){
    for(int bit = 63; bit>pos; bit--){
        if(ans[bit] and !isSet(num, bit)) return 0;
    }
    return 1;
}

void solve(){
    int n, x; cin>>n;
    vi a(n); read(a);
    vi b(n); read(b);

    vi flip(n);
    vi ans(64);

    for(int bit=63; bit>=0; bit--){
        bool ok = 1;
        vi moves;
        for(int i=0; i<n; i++){
            if(!isSet(a[i], bit)){
                if(isSet(b[i], bit)){
                    if(noChange(b[i], ans, bit)){
                        moves.pb(i);
                    }
                    else{
                        ok = 0;
                        break;
                    }
                }
                else{
                    ok = 0;
                    break;
                }
            }
        }
        if(ok){
            ans[bit] = ok;
            for(auto i: moves){
                swap(a[i], b[i]);
                flip[i] = 1;
            }
        }
    }

    int cnt = count(all(flip), 1LL);

    int res = 0;
    // print(ans);
    // print(flip);

    int p = 1;
    for(int i=0; i<64; i++){
        if(ans[i])  res += p;
        if(i<63)    p*=2;
    }
    cout<<res<<" "<<cnt<<'\n';
}

signed main(){
    fio;

    int t = 1;
    cin>>t;

    while(t--)	solve();
 
    return 0;
}

void read(vector<int> &a){
    rep(i,sz(a)) cin>>a[i];
}
void read(vector<vector<int>> &a){
    rep(i,sz(a)) rep(j,sz(a[i])) cin>>a[i][j];
}
void print(vector<int> &a){
    for(auto x: a) cout<<x<<' '; nl;
}
void print(vector<vector<int>> &a){
    for(auto x: a){
        for(auto z: x)  cout<<z<<" "; nl; 
    }
}
int power(int x,int y,int p){int res = 1; x%=p; if(!x) return 0; while(y){ if(y&1) res=(res*x)%p;  y=y>>1; x=(x*x)%p; }  return res;}

Magical Flips CodeChef Solution in C++14

“ ”

#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less

using namespace __gnu_pbds; //for policy based ds
using namespace std;

#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
    for (int &i : arr)   \
        cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

time_t Begin;

//////////////////Debug///////////////
#define debug(x)       \
    cout << #x << " "; \
    _print(x);         \
    cout << endl;
void _print(ll t)
{
    cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
    for (ll i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cout << "{";
    _print(p.ff);
    cout << ",";
    _print(p.ss);
    cout << "}";
}
template <class T>
void _print(vector<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(set<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
    cout << "[ ";
    for (T i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
    cout << "[ ";
    for (auto i : v)
    {
        _print(i);
        cout << " ";
    }
    cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }

void init()
{
    Begin = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
    double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
    cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}

vector<int> computeLps(string s, int M)
{
    int len = 0;
    vector<int> lps(M + 20);

    lps[0] = 0;

    int i = 1;
    while (i < M)
    {
        if (s[i] == s[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
    // debug(len);
    return lps;
}

int ceiling(int x, int y)
{
    int res = x / y;
    if (x % y)
    {
        if (x >= 0)
            res++;
    }
    return res;
}

vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> prefix(n + 1, vector<int>(m + 1));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
        }
    }

    return prefix;
}

int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
    // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;

    // cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
    return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}

int toInt(string &s)
{
    int res = 0;
    for (char c : s)
        res = res * 10 + (c - '0');
    return res;
}

bool isValid(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};

int moduloExponentiation(int a, int b, int m)
{
    if (b == 0)
        return 1;

    int res = moduloExponentiation(a, b / 2, m);
    res = (res * res) % m;

    if (b % 2)
        res = (res * a) % m;
    return res;
}

vector<int> smallesrPrimeDivisor(int n)
{
    vector<int> arr(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (arr[i])
            continue;
        for (int j = i; j <= n; j += i)
            if (!arr[j])
                arr[j] = i;
    }
    arr[1] = 1;
    return arr;
}

// const int MX = 100000;
int32_t main()
{
    init();
    //--------------------

    vector<int> smallestPrimeDivisorArr = smallesrPrimeDivisor(1e6 + 10);
    int t = 1;
    cin >> t;
    for (int tt = 1; tt <= t; tt++)
    {
        int n;
        cin >> n;
        vector<int> arr(n), brr(n);
        inputArr(i, arr);
        inputArr(i, brr);
        vector<bool> fliped(n), isSame(n, true);
        int res = 0;
        for (int j = 31; j >= 0; j--)
        {
            bool ok = true, all = true;
            // for (int i : isSame)
            //     cout << i << " ";
            // cout << "\n";
            // for (int i : fliped)
            //     cout << i << " ";
            // cout << "\n";
            for (int i = 0; i < n; i++)
            {
                if (arr[i] & (1 << j))
                    continue;
                else if (isSame[i] && !fliped[i] && (brr[i] & (1 << j)))
                    continue;
                else
                    ok = false;
            }

            if (!ok)
                continue;

            for (int i = 0; i < n; i++)
            {
                isSame[i] = isSame[i] && ((arr[i] & (1 << j)) == (brr[i] & (1 << j)));
                if (arr[i] & (1 << j))
                    continue;
                fliped[i] = true;
                swap(arr[i], brr[i]);
            }

            res |= (1 << j);
        }
        int flipedCnt = 0;
        for (bool i : fliped)
            if (i)
                flipedCnt++;
        cout << res << " " << flipedCnt << endl;
    }

    //---------------------------
    timeTaken();
    return 0;
}

Magical Flips CodeChef Solution in PYTH 3

“ ”

# cook your dish here
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    vis=set()
    ans=0
    for i in range(30,-1,-1):
        f=1
        h=[]
        for j in range(n):
            if j in vis:
                if (1<<i)&b[j]==0:
                    f=0
            else:
                if a[j]&(1<<i)==0:
                    if b[j]&(1<<i) and (b[j]&ans)==ans:
                        h.append(j)
                    else:
                        f=0
        if f:
            ans+=(1<<i)
            for j in h:
                vis.add(j)
    print(ans,len(vis))

Magical Flips CodeChef Solution in C

“ ”

#include <stdio.h>

int main(void) {
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int i,a[n+1],b[n+1],state[n+1];
		
		for(i=0;i<n;i++)
		scanf("%d",&a[i]);
		
		for(i=0;i<n;i++){
			state[i]=-1;
			scanf("%d",&b[i]);
		}
		int bit;
		int flag;
		for(bit = (1 << 29); bit>=1; bit>>=1){
			flag = 0;
			for(i=0;i<n;i++){
				if(state[i] == 0 && !(a[i]&bit)) flag = 1;
				else if(state[i] == 1 && !(b[i] & bit)) flag=1;
				else if(!(a[i] & bit) && !(b[i] & bit)) flag=1;
			}
			
			if(flag == 1)
			continue;
			
			for(i=0;i<n;i++){
				if(state[i] != -1)
				continue;
				else if(!(a[i]&bit)) state[i]=1;
				else if(!(b[i]&bit)) state[i]=0;
			}
		}
		
		int ans = (1<<30) -1, flip = 0;
		
		for(i=0;i<n;i++){
			if(state[i] == 1){
				flip++;
				ans&=b[i];
				continue;
			}
			ans&=a[i];
		}
		
		printf("%d %d\n",ans,flip);
	}
	return 0;
}

Magical Flips CodeChef Solution in JAVA

“ ”

import java.util.*;


import java.io.*;
class Codechef {

	static FastScanner scr=new FastScanner();
	 static PrintStream out=new PrintStream(System.out);
	 static StringBuilder sb=new StringBuilder();
	 static  class FastScanner {
		 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
	 	String next() {
	 		while (!st.hasMoreTokens())
	 			try {
	 				st=new StringTokenizer(br.readLine());
	 			} catch (IOException e) {
	 				e.printStackTrace();
	 			}
	 			return st.nextToken();
		} long gcd(long a,long b){
			if(b==0) {
				return a;
			}
				
			return gcd(b,a%b);
		}
		int gcd(int a,int b) {
			if(a*b==0) {
				return a+b;
			}
			return gcd(b,a%b);
		}
	 	 long modPow(long base,long exp) {
			if(exp==0) {
				return 1;
			}
			if(exp%2==0) {
				long res=(modPow(base,exp/2));
				return (res*res);
			}
			return (base*modPow(base,exp-1));
		}
	 	long []reverse(long[] count){
			long b[]=new long[count.length];
			int index=0;
			for(int i=count.length-1;i>=0;i--) {
				b[index++]=count[i];
			}
			return b;
		}
	 	int []reverse(int[] count){
			int b[]=new int[count.length];
			int index=0;
			for(int i=count.length-1;i>=0;i--) {
				b[index++]=count[i];
			}
			return b;
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long getMax(long a[],int n) {
			long max=Long.MIN_VALUE;
			for(int i=0;i<n;i++) {
				max=Math.max(a[i], max);
			}
				return max;
		}
		long[] readLongArray(int n) {
			long  [] a=new long  [n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}int[] readArray(int n) {
			int  [] a=new int  [n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		 int sum(int a[]) {
			 int s=0;
			 for(int i=0;i<a.length;i++)s+=a[i];
			 return s;
		 }
		 long sum(long a[]) {
			 long s=0;
			 for(int i=0;i<a.length;i++)s+=a[i];
			 return s;
		 }
		
	}

	 static class triplet{
		 int x;
		 int y;
		 char z;
		triplet(int x,int y,char z){
			this.x=x;
			this.y=y;
			this.z=z;
		}
	} 
	 static class quad{
		 int x;
		 int y;
		 int z;
		 int i;
		 quad(int x,int y,int z,int i){
			this.x=x;
			this.y=y;
			this.z=z;
			this.i=i;
		}
	} 
	 static class pair{
		 int x;
		 int y;
			pair( int x,int y){
				this.x=x;
				this.y=y;
			}
	 }
	 static Solve s=new Solve();
	 public static  void main(String []args) {
		int t=scr.nextInt();
//		 int t=1;
//		s.fill();
		while(t-->0) {
			s.solve();
		}
		out.println(sb);
	}
	static class Solve {
		int MAX=Integer.MAX_VALUE;
		int MIN=Integer.MIN_VALUE;
		boolean visited[];
		ArrayList<Integer>list[];
		ArrayList<Integer>list1[];
		long mod=1000000007;
		void solve() {
			int n=scr.nextInt();
			long []a=scr.readLongArray(n);
			long b[]=scr.readLongArray(n);
			
			int cnt[]=new int[30];
			int cnt1[]=new int[30];
			for(int i=0;i<n;i++) {
				for(int j=0;j<30;j++) {
					if((a[i]&(1<<j))!=0) {
						cnt[j]++;
					}
				}
				for(int j=0;j<30;j++) {
					if((b[i]&(1<<j))!=0) {
						cnt1[j]++;
					}
				}
			}
			
			int ans=0;
			long and=1;
			int flip[]=new int[n];
			Arrays.fill(flip, -1);
			for(int j=30-1;j>=0;j--) {
				if(cnt[j]+cnt1[j]>=n) {
					int temp[]=flip.clone();
					boolean count=true;
					for(int i=0;i<n;i++) {
						boolean ele=false;
						long bit= ((1l<<j)&a[i])!=0?1:0;
						long bit1= ((1l<<j)&b[i])!=0?1:0;
						if(flip[i]==-1) {
							if(bit==1 && bit==bit1) {
								flip[i]=-1;
								ele=true;
							}
							if(bit==0 && bit1==1) {
								flip[i]=1;
								ele=true;
							}else if(bit1==0 && bit==1){
								flip[i]=0;
								ele=true;
							}
						}else if(flip[i]==1) {
							if(bit1!=0) {
								ele=true;
							}
						}else {
							if(bit!=0) {
								ele=true;
							}
						}
						count&=ele;
//						out.print(flip[i]+" ");
					}
//					out.println(j+" "+count);
					if(count) {
						ans+=(1<<j);
					}else {
						flip=temp.clone();
					}
				}
			}
			int ele=0;
			for(int i=0;i<n;i++) {
				if(flip[i]==1) {
					ele++;
				}
			}
			out.println(ans+" "+ele);
			
		}
	}
}

Magical Flips CodeChef Solution in PYPY 3

“ ”

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    ans=0
    ans2=0
    dp=[0]*n
    for i in range(30,-1,-1):
        f=1
        ca=[]
        be=[]
        for j in range(n):
            if dp[j]==1:
              if (1<<i)&a[j]!=0:
                  pass
              else:
                  if b[j]&(1<<i)!=0 and b[j]&ans==ans:
                      be.append(j)
                  else:
                      f=0
                      break
            elif dp[j]==2:
                if a[j]&(1<<i)==0:
                    f=0
                    break
            elif dp[j]==0:
                if a[j]&(1<<i)!=0:
                    ca.append(j)
                else:
                    if b[j]&(1<<i)!=0:
                        be.append(j)
                    else:
                        f=0
                        break
        if f==1:
            ans+=1<<i
            for k in ca:
                dp[k]=1
            for k in be:
                a[k],b[k]=b[k],a[k]
                dp[k]=2
            ans2+=len(be)
    print(ans,ans2)

Magical Flips CodeChef Solution in PYTH

“ ”

t = int(raw_input())
for i in range(t):
	N = int(raw_input())
	st = raw_input().split()
	A = []
	for x in st:
		A.append(int(x))
	# endfor x
	st = raw_input().split()
	B = []
	for x in st:
		B.append(int(x))
	# endfor x
	V = A[0]|B[0]
	for k in range(1,N):
		n = A[k]|B[k]
		V = V&n
	# endfor k
	R = V
	Z = []
	p = 0
	while V > 0:
		if V%2 == 1:
			Z.append(p)
		# endif
		V = V/2
		p += 1
	# endwhile
	Z.reverse()
	L = [x for x in range(N)]
	f = 0
	V = 0
	for p in Z:
		nz = 0
		sz = len(L)
		zp = 2**p
		if R&zp > 0:
			W = [[],[],[],[]]
			k = 0
			while (k < sz) and (nz == 0):
				n = L[k]
				sc = 0
				if A[n]&zp > 0:
					sc += 1
				# endif
				if B[n]&zp > 0:
					sc += 2
				# endif
				if sc == 0:
					nz = 1
				else:
					W[sc].append(n)
				# endif
				k += 1
			# endwhile
			if nz == 0:
				f += len(W[2])
				V += zp
				L = list(W[3])
				for x in W[1]:
					R = R&A[x]
				# endfor x
				for x in W[2]:
					R = R&B[x]
				# endfor x
			# endif
		# endif
	# endfor p
	print V, f
# endfor i

Magical Flips CodeChef Solution in GO

“ ”

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	tc := readNum(reader)
	var buf bytes.Buffer
	for tc > 0 {
		tc--
		n := readNum(reader)
		A := readNNums(reader, n)
		B := readNNums(reader, n)
		res, cnt := solve(n, A, B)
		buf.WriteString(fmt.Sprintf("%d %d\n", res, cnt))
	}
	fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func solve(n int, A []int, B []int) (int, int) {
	// fp[i] = 0, no determined yet, 1 flip, 2 not flip
	fp := make([]int, n)

	var res int

	for b := 30; b >= 0; b-- {
		ok := true
		for i := 0; i < n && ok; i++ {
			if fp[i] == 1 {
				// check B[i][b]
				if (B[i]>>uint(b))&1 == 0 {
					ok = false
				}
			} else if fp[i] == 2 {
				// check A[i]
				if (A[i]>>uint(b))&1 == 0 {
					ok = false
				}
			} else {
				if (A[i]>>uint(b))&1 == 0 && (B[i]>>uint(b))&1 == 0 {
					ok = false
				}
			}
		}
		if !ok {
			// can't set this position, no change
			continue
		}
		// can set as 1
		res |= 1 << uint(b)

		for i := 0; i < n; i++ {
			if fp[i] == 0 {
				if (A[i]>>uint(b))&1 == 0 {
					fp[i] = 1
				} else if (B[i]>>uint(b))&1 == 0 {
					fp[i] = 2
				}
				// else still stay no determined yet
			}
		}
	}
	var cnt int
	for i := 0; i < n; i++ {
		if fp[i] == 1 {
			cnt++
		}
	}
	return res, cnt
}

Magical Flips CodeChef Solution Review:

In our experience, we suggest you solve this Magical Flips CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Magical Flips CodeChef Solution.

Find on CodeChef

“ ”

Conclusion:

I hope this Magical Flips CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn